Crossings Minimization  1.0
sifting.c File Reference

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>
Include dependency graph for sifting.c:

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)
 

Detailed Description

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.

Author
Matt Stallmann
Date
2009/01/08
Id
sifting.c 64 2014-03-25 20:36:19Z mfms

Definition in file sifting.c.

Function Documentation

◆ reposition_node()

static void reposition_node ( Nodeptr  node,
Nodeptr nodes,
int  after_position 
)
static

Puts a node into a different position in an array of nodes.

Parameters
nodeThe node to be repositioned
nodesThe array of nodes
after_positionThe 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().

◆ sift()

void sift ( Nodeptr  node)

puts the node in a position that minimizes the 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 
)

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:

◆ swap_nodes()

static void swap_nodes ( int  layer,
int  i,
int  j 
)
static

swap the nodes in positions i and j on the given layer

Todo:
this might be useful elsewhere

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