Crossings Minimization  1.0
sifting.c
Go to the documentation of this file.
1 /**
2  * @file sifting.c
3  * @brief Implementation of functions that place a node in a position on its
4  * layer that minimizes the number of crossings or minimizes the maximum
5  * number of crossings among edges incident on the node.
6  *
7  * @author Matt Stallmann
8  * @date 2009/01/08
9  * \$Id: sifting.c 64 2014-03-25 20:36:19Z mfms \$
10  */
11
12 #include"graph.h"
13 #include"defs.h"
14 #include"crossings.h"
15 #include"crossing_utilities.h"
16 #include"sifting.h"
17 #include"swap.h"
18 #include"sorting.h"
19 #include"channel.h"
20
21 #include<stdio.h>
22 #include<stdlib.h>
23 #include<assert.h>
24 #include<stdbool.h>
25 #include<limits.h>
26
27 /**
28  * Puts a node into a different position in an array of nodes.
29  * @param node The node to be repositioned
30  * @param nodes The array of nodes
31  * @param after_position The position of the node that 'node' must come
32  * after. If this is -1, then the new position is before all of the other
33  * nodes.
34  */
35 static void reposition_node( Nodeptr node, Nodeptr * nodes,
36  int after_position );
37
38 /**
39  * @brief puts the node in a position that minimizes the number of crossings.
40  *
41  * Basic algorithm is as follows:
42  *
43  * -# let x be the node to be sifted
44  * -# for each node y != x, calculate cr(x,y) and cr(y,x), where cr(a,b) is
45  * the number of crossings among edges incident to a and b if a and b are in
46  * the given order
47  * -# use the cr values to compute diff(x,y) = cr(x,y) - cr(y,x) for each y
48  * -# let y_0, ..., y_L be the nodes other than x on this layer
49  * -# let prefix(-1) = 0, prefix(i>=0) = prefix(i-1) + diff(x,y_i)
50  * -# if prefix(i) is minimum over all i, then x belongs between y_i and
51  * y_{i+1}; however, if the minimum is > 0, then x belongs before y_0
52  *
53  * Note that prefix(i) represents the crossings(i) - crossings(-1), where
54  * crossings(i) = the number of crossings that arise when the node is
55  * inserted between y_i and y_{i+1}
56  */
57 void sift( Nodeptr node )
58 {
59 #ifdef DEBUG
60  printf( "-> sift, node = %s, layer = %d, position = %d\n",
61  node->name, node->layer, node->position );
62 #endif
63  // create an array containing diff( node, y_i ) for each y_i on the same
64  // layer as 'node', assuming y_i is the node in position i of the layer
65  int layer_size = layers[node->layer]->number_of_nodes;
66  Nodeptr * nodes = layers[node->layer]->nodes;
67  int * diff = (int *) calloc( layer_size, sizeof(int) );
68  int i = 0;
69  for( i = 0; i < layer_size; i++ ) {
70  if ( nodes[i] != node ) {
71  diff[i] = node_crossings( nodes[ i ], node )
72  - node_crossings( node, nodes[ i ] );
73  }
74  else {
75  diff[i] = 0;
76  }
77 #ifdef DEBUG
78  printf( " sift loop: diff[%d] = %d\n", i, diff[i] );
79 #endif
80  }
81
82  // compute the minimum prefix sum and its position in the diff array
83  // bias the decision in favor of maximum distance from the current
84  // position; this does consistently better in preliminary experiments,
85  // possibly because it's good to cycle through a lot of possible
86  // configurations
87  int prefix_sum = 0;
88  int min_prefix_sum = 0;
89  int min_position = -1;
90  int max_distance = 0;
91  for( i = 0; i < layer_size; i++ ) {
92  prefix_sum += diff[i];
93  if( prefix_sum < min_prefix_sum
94  || ( prefix_sum == min_prefix_sum
95  && abs( i - node->position ) > max_distance ) ) {
96  min_prefix_sum = prefix_sum;
97  min_position = i;
98  max_distance = abs( i - node->position );
99  }
100  }
101  free( diff );
102
103  // if min_position is i, then the node belongs between nodes[i] and
104  // nodes[i+1];
105
106 #ifdef DEBUG
107  printf( " sift, reposition: min_prefix_sum = %d, old = %d, new = %d\n",
108  min_prefix_sum, node->position, min_position );
109 #endif
110
111  reposition_node( node, nodes, min_position );
112
113  // recompute crossings with respect to this layer
115 #ifdef DEBUG
116  printf( "<- sift, node = %s, layer = %d, position = %d\n",
117  node->name, node->layer, node->position );
118 #endif
119 }
120
121 static void reposition_node( Nodeptr node, Nodeptr * nodes,
122  int after_position )
123 {
124  // There are three cases to consider: if the node should go immediately
125  // after its predecessor or after itself, there is nothing to be done; if
126  // it should go immediately after an earlier node, it goes into
127  // after_position + 1 and the intervening nodes are shifted right; if it
128  // should go after a later node, it goes into after_position and the
129  // intervening nodes, including the one it goes after, are shifted left.
130  int i = node->position;
131  if( after_position < node->position - 1 )
132  {
133  for( ; i > after_position + 1; i-- )
134  {
135  nodes[ i ] = nodes[ i - 1 ];
136  nodes[ i ]->position = i;
137  }
138  nodes[ after_position + 1 ] = node;
139  node->position = after_position + 1;
140  }
141  else if( after_position > node->position )
142  {
143  for( ; i < after_position; i++ )
144  {
145  nodes[ i ] = nodes[ i + 1 ];
146  nodes[ i ]->position = i;
147  }
148  nodes[ after_position ] = node;
149  node->position = after_position;
150  }
151 }
152
153 /**
154  * Algorithm for sifting (a node x) in order to minimize the maximum number of
155  * crossings for any edge with one endpoint on its layer:
156  *
157  * Move to the left and then back to the right (in this case the prefix sum
158  * approach doesn't work). When x is moved to the right of y, you do
159  * - change_crossings( x, y, -1 ): sort with edges of x followed by edges of
160  * y and subtract 1 from the crossing number of an edge when it's involved
161  * in an inversion
162  * - change_crossings( y, x, +1 ): sort with edges of y followed by edges of
163  * x and add 1 from the crossing number of an edge when it's involved
164  * in an inversion
165  * - among all the edges of x and y, find the one with maximum number of
166  * crossings and use that number as the 'value' of the current position of
167  * x
168  * The calculation of inversions needs to be done both for the upward and the
169  * downward edges.
170  */
171
173  assert( node == edge->up_node || node == edge->down_node );
174 #ifdef DEBUG
175  printf( "-> sift_node_for_edge_crossings: %s -> %s, %s\n",
176  edge->down_node->name, edge->up_node->name, node->name );
177 #endif
178  int layer = node->layer;
179  int layer_size = layers[ layer ]->number_of_nodes;
180  Nodeptr * nodes_on_layer = layers[ layer ]->nodes;
181
182  // find the position where the maximum edge crossing count achieves its
183  // minimum; bias the decision in favor of maximum distance from the current
184  // position; same observation applies as with sifting for minimizing
185  // overall crossings
186  int min_edge_crossing_count = edge->crossings;
187  int min_position = node->position;
188  int max_distance = 0;
189  int current_edge_crossing_count = INT_MAX;
190
191  // begin with a sweep to the left of the current node position
192  for ( int i = node->position - 1; i >= 0; i-- ) {
193  current_edge_crossing_count
194  = edge_crossings_after_swap( nodes_on_layer[i], node );
195  if ( current_edge_crossing_count < min_edge_crossing_count
196  || ( current_edge_crossing_count == min_edge_crossing_count
197  && node->position - i > max_distance )
198  ) {
199  min_edge_crossing_count = current_edge_crossing_count;
200  min_position = i - 1;
201  max_distance = node->position - i + 1;
202  }
203 #ifdef DEBUG
204  printf( " mce left sweep: pos = %2d, min_pos = %2d, edge xings = %d\n",
205  i, min_position, current_edge_crossing_count );
206 #endif
207  }
208
209  // Undo the left sweep (no need to check for min)
210  for ( int i = 0; i < node->position; i++ ) {
211  edge_crossings_after_swap( node, nodes_on_layer[i] );
212 #ifdef DEBUG
213  printf( " mce undo sweep: pos = %2d, min_pos = %2d, edge xings = %d\n",
214  i, min_position, current_edge_crossing_count );
215 #endif
216  }
217
218  // Then sweep all the way to the right
219  for ( int i = node->position + 1; i < layer_size; i++ ) {
220  current_edge_crossing_count
221  = edge_crossings_after_swap( node, nodes_on_layer[i] );
222  if ( current_edge_crossing_count < min_edge_crossing_count
223  || ( current_edge_crossing_count == min_edge_crossing_count
224  && abs(node->position - i) > max_distance )
225  ) {
226  min_edge_crossing_count = current_edge_crossing_count;
227  min_position = i;
228  max_distance = abs(node->position - i);
229  }
230 #ifdef DEBUG
231  printf( " mce right sweep: pos = %2d, min_pos = %2d, edge xings = %d\n",
232  i, min_position, current_edge_crossing_count );
233 #endif
234  }
235
236  reposition_node( node, nodes_on_layer, min_position );
237
238  // recompute crossings with respect to this layer
239  updateCrossingsForLayer( layer );
240 }
241
242 /**
243  * swap the nodes in positions i and j on the given layer
244  *
245  * @todo this might be useful elsewhere
246  */
247 static void swap_nodes(int layer, int i, int j) {
248  assert(i >= 0 && j >= 0);
249  assert(i < layers[layer]->number_of_nodes && i < layers[layer]->number_of_nodes);
250  Nodeptr * nodes_on_layer = layers[layer]->nodes;
251  Nodeptr tmp = nodes_on_layer[i];
252  nodes_on_layer[i] = nodes_on_layer[j];
253  nodes_on_layer[j] = tmp;
254  nodes_on_layer[i]->position = i;
255  nodes_on_layer[j]->position = j;
256 }
257
259  int layer = node->layer;
260  int layer_size = layers[layer]->number_of_nodes;
261
262  if ( layer_size == 1 ) return;
263
264  // resorting to the (possibly inefficient) naive algorithm here, i.e.,
265  // recomputing stretch after each move
266  double min_stretch = totalLayerStretch(layer);
267  int min_position = node->position;
268  int original_position = node->position;
269
270  // begin with a sweep to the left of the current node position, keeping
271  // track of minimum stretch, or maximum distance as a tie breaker
272  for ( int i = original_position - 1; i >= 0; i-- ) {
273  swap_nodes(layer, i, i+1);
274  double current_stretch = totalLayerStretch(layer);
275  if ( current_stretch < min_stretch
276  ||
277  (current_stretch == min_stretch
278  && original_position - i > original_position - min_position) ) {
279  min_stretch = current_stretch;
280  min_position = i;
281  }
282 #ifdef DEBUG
283  printf( " mse left sweep: pos = %2d, min_pos = %2d, stretch = %6.1f\n",
284  i, min_position, current_stretch );
285 #endif
286  }
287
288  // sweep right, back to the original position (no need to track stretch)
289  for ( int i = 0; i < original_position; i++ ) {
290  swap_nodes(layer, i, i+1);
291  }
292
293  // sweep to the right of original position, tracking stretch and distance
294  for ( int i = original_position + 1; i < layer_size; i++ ) {
295  swap_nodes(layer, i-1, i);
296  double current_stretch = totalLayerStretch(layer);
297  if ( current_stretch < min_stretch
298  ||
299  (current_stretch == min_stretch
300  && i - original_position > abs(original_position - min_position)) ) {
301  min_stretch = current_stretch;
302  min_position = i;
303  }
304 #ifdef DEBUG
305  printf( " mse right sweep: pos = %2d, min_pos = %2d, stretch = %6.1f\n",
306  i, min_position, current_stretch );
307 #endif
308  }
309
310  // sweep left to the min position
311  for ( int i = layer_size - 1; i > min_position; i-- ) {
312  swap_nodes(layer, i-1, i);
313  }
314
315 } // end, sift node for total stretch
316
static void swap_nodes(int layer, int i, int j)
Definition: sifting.c:247
Nodeptr up_node
Definition: graph.h:98
Definition of functions that are used to count and update crossings locally. Used both by crossings...
void sift_node_for_edge_crossings(Edgeptr edge, Nodeptr node)
Definition: sifting.c:172
int edge_crossings_after_swap(Nodeptr left_node, Nodeptr right_node)
Definition: swap.c:124
Definition of infrastructure functions that are used to implement sifting-based heuristics.
char * name
Definition: graph.h:63
Layerptr * layers
Definition: graph_io.c:31
void sift_node_for_total_stretch(Nodeptr node)
Definition: sifting.c:258
int number_of_nodes
Definition: graph.h:115
double totalLayerStretch(int i)
Definition: channel.c:80
Definitions common to all edge crossing heuristic source files.
int position
Definition: graph.h:73
Interface for functions that perform various sorts. All sorts are stable.
void updateCrossingsForLayer(int layer)
Definition: crossings.c:147
implementation of utilities that maintain information about channels; eventually these will replace t...
void sift(Nodeptr node)
puts the node in a position that minimizes the number of crossings.
Definition: sifting.c:57
int number_of_nodes
Definition: graph_io.c:27
Definition of functions that keep track of and update the number of crossings for each node...
int layer
Definition: graph.h:65
int crossings
Definition: graph.h:100
Definition of data structures and access functions for a layered graph.
int node_crossings(Nodeptr node_a, Nodeptr node_b)
Definition: swap.c:57
Nodeptr * nodes
Definition: graph.h:116
Headers of functions that compute the change in crossing number or max edge crossings when two neighb...
Nodeptr down_node
Definition: graph.h:99
static void reposition_node(Nodeptr node, Nodeptr *nodes, int after_position)
Definition: sifting.c:121