Crossings Minimization
1.0

Implementation of functions that place a node in a position on its layer that minimizes the number of crossings or minimizes the maximum number of crossings among edges incident on the node. More...
#include "graph.h"
#include "defs.h"
#include "crossings.h"
#include "crossing_utilities.h"
#include "sifting.h"
#include "swap.h"
#include "sorting.h"
#include "channel.h"
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <stdbool.h>
#include <limits.h>
Go to the source code of this file.
Functions  
static void  reposition_node (Nodeptr node, Nodeptr *nodes, int after_position) 
void  sift (Nodeptr node) 
puts the node in a position that minimizes the number of crossings. More...  
void  sift_node_for_edge_crossings (Edgeptr edge, Nodeptr node) 
static void  swap_nodes (int layer, int i, int j) 
void  sift_node_for_total_stretch (Nodeptr node) 
Implementation of functions that place a node in a position on its layer that minimizes the number of crossings or minimizes the maximum number of crossings among edges incident on the node.
Definition in file sifting.c.
Puts a node into a different position in an array of nodes.
node  The node to be repositioned 
nodes  The array of nodes 
after_position  The position of the node that 'node' must come after. If this is 1, then the new position is before all of the other nodes. 
Definition at line 121 of file sifting.c.
References node_struct::position.
Referenced by sift(), and sift_node_for_edge_crossings().
void sift  (  Nodeptr  node  ) 
puts the node in a position that minimizes the number of crossings.
Basic algorithm is as follows:
Note that prefix(i) represents the crossings(i)  crossings(1), where crossings(i) = the number of crossings that arise when the node is inserted between y_i and y_{i+1}
Definition at line 57 of file sifting.c.
References node_struct::layer, layers, node_struct::name, node_crossings(), layer_struct::nodes, layer_struct::number_of_nodes, node_struct::position, reposition_node(), and updateCrossingsForLayer().
Referenced by sift_decreasing(), sift_increasing(), and sift_iteration().
Algorithm for sifting (a node x) in order to minimize the maximum number of crossings for any edge with one endpoint on its layer:
Move to the left and then back to the right (in this case the prefix sum approach doesn't work). When x is moved to the right of y, you do
Definition at line 172 of file sifting.c.
References edge_struct::crossings, edge_struct::down_node, edge_crossings_after_swap(), node_struct::layer, layers, node_struct::name, layer_struct::nodes, layer_struct::number_of_nodes, node_struct::position, reposition_node(), edge_struct::up_node, and updateCrossingsForLayer().
Referenced by edge_sift_iteration().
void sift_node_for_total_stretch  (  Nodeptr  node  ) 
node  This node is placed into a position that minimizes the total stretch of edges incident on its layer; ties are broken by moving the node as far away as possible from its initial position 
Definition at line 258 of file sifting.c.
References node_struct::layer, layers, layer_struct::number_of_nodes, node_struct::position, swap_nodes(), and totalLayerStretch().
Referenced by total_stretch_sift_iteration().

static 
swap the nodes in positions i and j on the given layer
Definition at line 247 of file sifting.c.
References layers, layer_struct::nodes, number_of_nodes, and node_struct::position.
Referenced by sift_node_for_total_stretch().