Crossings Minimization  1.0
sifting.h File Reference

Definition of infrastructure functions that are used to implement sifting-based heuristics. More...

#include <stdbool.h>
#include "defs.h"
#include "graph.h"
Include dependency graph for sifting.h:
This graph shows which files directly or indirectly include this file:

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)
 

Detailed Description

Definition of infrastructure functions that are used to implement sifting-based heuristics.

Author
Matt Stallmann
Date
2009/01/08
Id
sifting.h 2 2011-06-07 19:50:41Z mfms

Definition in file sifting.h.

Function Documentation

◆ sift()

void sift ( Nodeptr  node)

puts the node in a position that minimizes the number of crossings.

Parameters
nodeThis node is placed on its layer in a position that minimizes the total number of crossings

Basic algorithm is as follows:

  1. let x be the node to be sifted
  2. for each node y != x, calculate cr(x,y) and cr(y,x), where cr(a,b) is the number of crossings among edges incident to a and b if a and b are in the given order
  3. use the cr values to compute diff(x,y) = cr(x,y) - cr(y,x) for each y
  4. let y_0, ..., y_L be the nodes other than x on this layer
  5. let prefix(-1) = 0, prefix(i>=0) = prefix(i-1) + diff(x,y_i)
  6. if prefix(i) is minimum over all i, then x belongs between y_i and y_{i+1}; however, if the minimum is > 0, then x belongs before y_0

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().

Here is the call graph for this function:

◆ sift_node_for_edge_crossings()

void sift_node_for_edge_crossings ( Edgeptr  edge,
Nodeptr  node 
)
Parameters
edgeAn 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
nodeThis 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

  • change_crossings( x, y, -1 ): sort with edges of x followed by edges of y and subtract 1 from the crossing number of an edge when it's involved in an inversion
  • change_crossings( y, x, +1 ): sort with edges of y followed by edges of x and add 1 from the crossing number of an edge when it's involved in an inversion
  • among all the edges of x and y, find the one with maximum number of crossings and use that number as the 'value' of the current position of x The calculation of inversions needs to be done both for the upward and the downward edges.

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().

Here is the call graph for this function:

◆ sift_node_for_total_stretch()

void sift_node_for_total_stretch ( Nodeptr  node)
Parameters
nodeThis 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().

Here is the call graph for this function: