Crossings Minimization
1.0

Definition of infrastructure functions that are used to implement siftingbased heuristics. More...
Go to the source code of this file.
Functions  
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) 
void  sift_node_for_total_stretch (Nodeptr node) 
Definition of infrastructure functions that are used to implement siftingbased heuristics.
Definition in file sifting.h.
void sift  (  Nodeptr  node  ) 
puts the node in a position that minimizes the number of crossings.
node  This node is placed on its layer in a position that minimizes the total 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().
edge  An edge that has the current maximum number of crossings; for convience so that this does not need to be recalculated, it is assumed that the node is one of its enpoints 
node  This node is placed on its layer in a position that minimizes the maximum number of crossings for any edge incident on the layer. 
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().