Crossings Minimization  1.0
crossings.c
Go to the documentation of this file.
1 /**
2  * @file crossings.c
3  * @brief Implementation of functions that keep track of and update the
4  * number of crossings for each node, each layer, and for the whole graph.
5  *
6  * The algorithm used to count crossings between adjacent layers is the
7  * O(|E|+|C|) algorithm from "Simple and efficient bilayer cross counting",
8  * W. Barth, M. Juenger, P. Mutzel, in JGAA, 2004.
9  *
10  * @author Matt Stallmann
11  * @date 2008/12/23
12  * $Id: crossings.c 101 2014-10-22 16:32:05Z mfms $
13  */
14 
15 #include"graph.h"
16 #include"defs.h"
17 #include"min_crossings.h"
18 #include"crossings.h"
19 #include"crossing_utilities.h"
20 #include"heuristics.h"
21 #include"sorting.h"
22 #include"random.h"
23 
24 #include<stdio.h>
25 #include<stdlib.h>
26 #include<assert.h>
27 
28 /**
29  * Information about edges between layers i - 1 and i; the entry for 0 is not
30  * used.
31  */
32 typedef struct inter_layer_struct {
34  /**
35  * Positions on the lower layer of endpoints of the edges; these are
36  * initially sorted lexicographically by the positions of the upper
37  * endpoints, then inversions are counted in a sort by positions of the
38  * lower endpoints.
39  */
42 } * InterLayerptr;
43 
44 /**
45  * between_layers[i] is information about edges between
46  * layers i - 1 and i; the entry for i = 0 is not used
47  */
49 
50 // ******** Allocation functions for initCrossings() ************
51 
52 static int count_down_edges( int layer_number )
53 {
54  Layerptr layer = layers[ layer_number ];
55  int count = 0;
56  int j = 0;
57  for( ; j < layer->number_of_nodes; j++ )
58  {
59  count += layer->nodes[j]->down_degree;
60  }
61  return count;
62 }
63 
64 static InterLayerptr makeInterLayer( int upper_layer )
65 {
66  InterLayerptr new_interlayer
67  = (InterLayerptr) malloc( sizeof(struct inter_layer_struct ) );
68  new_interlayer->number_of_edges = count_down_edges( upper_layer );
69  new_interlayer->edges
70  = (Edgeptr *) calloc( new_interlayer->number_of_edges,
71  sizeof(Edgeptr) );
72  return new_interlayer;
73 }
74 
75 /**
76  * Initializes all crossing counts and allocates data structures used for
77  * counting crossings. Assumes that the graph has been read from the two
78  * input files and all basic data properly initialized - @see readgraph()
79  */
80 void initCrossings( void )
81 {
82  between_layers
83  = (InterLayerptr *) calloc( number_of_layers, sizeof(InterLayerptr) );
84  int i = 1;
85  for( ; i < number_of_layers; i++ )
86  {
87  between_layers[i] = makeInterLayer( i );
88  }
89 }
90 
91 /**** Other functions ********/
92 
93 int numberOfCrossings( void )
94 {
95  int i = 1;
96  int crossings = 0;
97  for( ; i < number_of_layers; i++ )
98  {
99  crossings += between_layers[i]->number_of_crossings;
100  }
101  return crossings;
102 }
103 
104 int maxEdgeCrossings( void )
105 {
107 }
108 
109 /**
110  * @return the number of crossings for the given layer
111  */
112 int numberOfCrossingsLayer( int layer )
113 {
114  int crossings = 0;
115  if( layer > 0 )
116  crossings += between_layers[ layer ]->number_of_crossings;
117  if( layer < number_of_layers - 1 )
118  crossings += between_layers[ layer + 1 ]->number_of_crossings;
119  return crossings;
120 }
121 
122 /**
123  * @return the number of crossings for the given node
124  */
126 {
127  return node->up_crossings + node->down_crossings;
128 }
129 
130 /**
131  * @return the number of crossings for the given edge
132  */
134 {
135  return edge->crossings;
136 }
137 
138 void updateAllCrossings( void )
139 {
141  for( int i = 1; i < number_of_layers; i++ )
142  {
144  }
145 }
146 
147 void updateCrossingsForLayer( int layer )
148 {
149  updateNodePositions( layer );
150  if( layer > 0 ) updateCrossingsBetweenLayers( layer );
151  if( layer < number_of_layers - 1 )
152  updateCrossingsBetweenLayers( layer + 1 );
153 }
154 
155 void updatePositionsForLayer( int layer )
156 {
157  Layerptr layer_ptr = layers[ layer ];
158  for ( int i = 0; i < layer_ptr->number_of_nodes; i++ )
159  {
160  Nodeptr node = layer_ptr->nodes[i];
161  node->position = i;
162  }
163 }
164 
165 /**
166  * Sets all node crossings relevant to the edges between layers upper_layer
167  * and upper_layer - 1 to 0
168  */
169 static void initialize_crossings( int upper_layer )
170 {
171  Layerptr up_layer = layers[ upper_layer ];
172  Layerptr down_layer = layers[ upper_layer - 1 ];
173  Nodeptr * upper_nodes = up_layer->nodes;
174  Nodeptr * lower_nodes = down_layer->nodes;
175  int upper_node_count = up_layer->number_of_nodes;
176  int lower_node_count = down_layer->number_of_nodes;
177  int i = 0;
178  for( ; i < upper_node_count; i++ )
179  {
180  upper_nodes[i]->down_crossings = 0;
181  int j = 0;
182  for( ; j < upper_nodes[i]->down_degree; j++ )
183  {
184  upper_nodes[i]->down_edges[j]->crossings = 0;
185  }
186  }
187  for( ; i < lower_node_count; i++ )
188  {
189  lower_nodes[i]->up_crossings = 0;
190  }
191 }
192 
193 /**
194  * Updates crossings between two adjacent layers. Also updates the relevant
195  * crossing fields of the two layers.
196  * @param upper_layer the higher of the two layers; crossings between layers
197  * upper_layer - 1 and upper_layer are counted
198  */
199 void updateCrossingsBetweenLayers( int upper_layer )
200 {
201  // sort edges lexicographically based primarily on upper layer endpoints
202  Layerptr layer = layers[ upper_layer ];
203  int index = 0; /* current index into edge array */
204  int upper_position = 0;
205  for( ; upper_position < layer->number_of_nodes; upper_position++ )
206  {
207  Nodeptr node = layer->nodes[upper_position];
209  add_edges_to_array( between_layers[ upper_layer ]->edges,
210  node->down_edges, node->down_degree, index );
211  index += node->down_degree;
212  }
213  initialize_crossings( upper_layer );
214  between_layers[ upper_layer ]->number_of_crossings
215  = count_inversions_down( between_layers[ upper_layer ]->edges,
216  between_layers[ upper_layer ]->number_of_edges,
217  1 );
218 }
219 
220 int maxCrossingsLayer( void ) {
221  int max_crossings_layer = -1;
222  int max_crossings = -1;
223  int * layer_sequence = (int *) malloc( number_of_layers * sizeof(int) );
224  for ( int i = 0; i < number_of_layers; i++ ) {
225  layer_sequence[i] = i;
226  }
227  if ( randomize_order ) {
228  genrand_permute( layer_sequence, number_of_layers, sizeof(int) );
229  }
230  for( int i = 0; i < number_of_layers; i++ ) {
231  int layer = layer_sequence[i];
232  if( numberOfCrossingsLayer( layer ) > max_crossings
233  && ! isFixedLayer( layer ) ) {
234  max_crossings = numberOfCrossingsLayer( layer );
235  max_crossings_layer = layer;
236  }
237  }
238  free( layer_sequence );
239  return max_crossings_layer;
240 }
241 
243  if ( randomize_order ) {
245  }
246  Nodeptr max_crossings_node = NULL;
247  int max_crossings = -1;
248  for ( int i = 0; i < number_of_nodes; i++ ) {
249  Nodeptr node = master_node_list[i];
250 #ifdef DEBUG
251  printf( " loop: maxCrossingsNode, i =%d, node = %s\n", i, node->name );
252 #endif
253  if( numberOfCrossingsNode( node ) > max_crossings
254  && ! isFixedNode( node) ) {
255  max_crossings = numberOfCrossingsNode( node );
256  max_crossings_node = node;
257  }
258  }
259  return max_crossings_node;
260 }
261 
263  Edgeptr max_crossings_edge = NULL;
264  int max_crossings = -1;
265  if ( randomize_order ) {
267  }
268  for ( int i = 0; i < number_of_edges; i++ ) {
269  Edgeptr edge = master_edge_list[i];
270  if( edge->crossings > max_crossings
271  && ! isFixedEdge( edge ) ) {
272  max_crossings = edge->crossings;
273  max_crossings_edge = edge;
274  }
275  }
276  return max_crossings_edge;
277 }
278 
279 /**
280  * @return an edge with the maximum number of crossings; does not change any
281  * state information; this is used only when computing bottleneck crossings
282  *
283  * @todo eventually this will go away when a lot of the content here is moved
284  * to channel.[ch] and the maximum bottleneck and total crossings can be
285  * maintained on a per channel basis
286  */
288  Edgeptr max_crossings_edge = NULL;
289  int max_crossings = -1;
290  for ( int i = 0; i < number_of_edges; i++ ) {
291  Edgeptr edge = master_edge_list[i];
292  if( edge->crossings > max_crossings ) {
293  max_crossings = edge->crossings;
294  max_crossings_edge = edge;
295  }
296  }
297  return max_crossings_edge;
298 }
299 
300 /**
301  * Prints down crossings for the nodes on layer i
302  */
303 static void print_down_crossings_nodes( int i )
304 {
305  Layerptr layer = layers[ i ];
306  int j = 0;
307  for( ; j < layer->number_of_nodes; j++ )
308  {
309  Nodeptr node = layer->nodes[j];
310  printf( " %-10s layer = %3d, position = %3d, down_x = %3d\n",
311  node->name, node->layer, node->position, node->down_crossings );
312  }
313 }
314 
315 /**
316  * Prints the crossings for the down edges of nodes on layer i
317  */
318 static void print_down_crossings_edges( int i )
319 {
320  Layerptr layer = layers[ i ];
321  int j = 0;
322  for( ; j < layer->number_of_nodes; j++ )
323  {
324  Nodeptr node = layer->nodes[j];
325  int edge_position = 0;
326  for( ; edge_position < node->down_degree; edge_position++ )
327  {
328  Edgeptr edge = node->down_edges[ edge_position ];
329  printf( " :: %10s -> %10s has %4d crossings\n",
330  edge->down_node->name, edge->up_node->name, edge->crossings );
331  }
332  }
333 }
334 
335 /**
336  * Prints up crossings for the nodes on layer i
337  */
339 {
340  Layerptr layer = layers[ i ];
341  int j = 0;
342  for( ; j < layer->number_of_nodes; j++ )
343  {
344  Nodeptr node = layer->nodes[j];
345  printf( " %-10s layer = %3d, position = %3d, up_x = %3d\n",
346  node->name, node->layer, node->position, node->up_crossings );
347  }
348 }
349 
350 /**
351  * Prints information for crossings between layers i-1 and i
352  */
354 {
355  printf( " --- between layers %d and %d crossings = %3d\n",
356  i - 1, i, between_layers[i]->number_of_crossings );
357  printf( " ___ upper nodes\n" );
359  printf( " ^^^ lower nodes\n" );
360  print_up_crossings_nodes( i - 1 );
361  printf( " ---\n" );
362 }
363 
364 /**
365  * Prints information about the crossings, mostly for debugging
366  */
367 void printCrossings( void )
368 {
369  printf( "xxx total_crossings = %d\n", numberOfCrossings() );
370  int i = 1;
371  for( ; i < number_of_layers; i++ )
372  {
374  }
375  printf("->-> edge crossings\n");
376  i = 1;
377  for( ; i < number_of_layers; i++ )
378  {
380  }
381 }
382 
383 #ifdef TEST
384 
385 #include"graph_io.h"
386 
387 // the following are to avoid bringing in more modules than necessary
389 int max_iterations;
390 void barycenterDownSweep(int layer) {}
391 void barycenterUpSweep(int layer) {}
392 
393 int main( int argc, char * argv[] )
394 {
395  readGraph( argv[1], argv[2] );
396  initCrossings();
398  printCrossings();
399  fprintf( stderr, "total crossings = %d\n", numberOfCrossings() );
400  // test maximum crossings node
401  printf("\nMax crossings nodes:\n");
402  clearFixedNodes();
403  Nodeptr node = maxCrossingsNode();
404  for( ; node != NULL; node = maxCrossingsNode() )
405  {
406  printf( "max crossings node = %s, crossings = %d\n",
407  node->name, numberOfCrossingsNode( node ) );
408  fixNode( node );
409  }
410  // test maximum crossings edge
411  printf("\nMax crossings edges:\n");
412  clearFixedEdges();
413  Edgeptr edge = maxCrossingsEdge();
414  for( ; edge != NULL; edge = maxCrossingsEdge() )
415  {
416  printf( "max crossings edge: %s -> %s, crossings = %d\n",
417  edge->down_node->name, edge->up_node->name,
418  numberOfCrossingsEdge( edge ) );
419  fixEdge( edge );
420  }
421  // test maximum crossings layer
422  printf("\nMax crossings layers:\n");
424  int layer = maxCrossingsLayer();
425  for( ; layer != -1; layer = maxCrossingsLayer() )
426  {
427  printf( "max crossings layer = %d, crossings = %d\n",
428  layer, numberOfCrossingsLayer( layer ) );
429  fixLayer( layer );
430  }
431  return 0;
432 }
433 
434 #endif
435 
436 /* [Last modified: 2016 03 01 at 01:32:37 GMT] */
Nodeptr * master_node_list
Definition: graph_io.c:25
Nodeptr up_node
Definition: graph.h:98
int down_crossings
Definition: graph.h:87
Definition of functions that are used to count and update crossings locally. Used both by crossings...
void fixLayer(int layer)
Definition: heuristics.c:299
void updateCrossingsBetweenLayers(int upper_layer)
Definition: crossings.c:199
struct inter_layer_struct * InterLayerptr
void initCrossings(void)
Definition: crossings.c:80
Interface for functions implementing all of the heuristics Those labeled parallel are designed specif...
char * name
Definition: graph.h:63
int maxCrossingsLayer(void)
Definition: crossings.c:220
Layerptr * layers
Definition: graph_io.c:31
int number_of_nodes
Definition: graph.h:115
Edgeptr * down_edges
Definition: graph.h:78
Edgeptr maxCrossingsEdgeStatic(void)
Definition: crossings.c:287
static void print_down_crossings_nodes(int i)
Definition: crossings.c:303
static void initialize_crossings(int upper_layer)
Definition: crossings.c:169
int capture_iteration
Definition: min_crossings.c:52
Global variables, functions, and parameters specified on the command line.
Definitions common to all edge crossing heuristic source files.
int position
Definition: graph.h:73
void clearFixedNodes(void)
Definition: heuristics.c:315
int max_iterations
Definition: min_crossings.c:41
bool isFixedNode(Nodeptr node)
Definition: heuristics.c:294
bool randomize_order
Definition: min_crossings.c:54
bool barycenterDownSweep(int starting_layer)
Definition: barycenter.c:260
Nodeptr maxCrossingsNode(void)
Definition: crossings.c:242
Interface for functions that perform various sorts. All sorts are stable.
void readGraph(const char *dot_file, const char *ord_file)
Definition: graph_io.c:363
int numberOfCrossingsLayer(int layer)
Definition: crossings.c:112
void updateCrossingsForLayer(int layer)
Definition: crossings.c:147
Edgeptr maxCrossingsEdge(void)
Definition: crossings.c:262
void clearFixedLayers(void)
Definition: heuristics.c:348
void updateAllPositions(void)
Definition: sorting.c:141
void print_crossings_between_layers(int i)
Definition: crossings.c:353
void add_edges_to_array(Edgeptr *edge_array, Edgeptr *edges_to_add, int num_edges, int start_pos)
int number_of_nodes
Definition: graph_io.c:27
static InterLayerptr makeInterLayer(int upper_layer)
Definition: crossings.c:64
void print_up_crossings_nodes(int i)
Definition: crossings.c:338
Edgeptr * edges
Definition: crossings.c:40
Definition of functions for reading and writing graphs.
bool isFixedLayer(int layer)
Definition: heuristics.c:296
void fixNode(Nodeptr node)
Definition: heuristics.c:297
Definition of functions that keep track of and update the number of crossings for each node...
int layer
Definition: graph.h:65
int down_degree
Definition: graph.h:75
void updatePositionsForLayer(int layer)
Definition: crossings.c:155
int up_crossings
Definition: graph.h:86
int crossings
Definition: graph.h:100
static InterLayerptr * between_layers
Definition: crossings.c:48
Definition of data structures and access functions for a layered graph.
void printCrossings(void)
Definition: crossings.c:367
static void print_down_crossings_edges(int i)
Definition: crossings.c:318
int numberOfCrossingsEdge(Edgeptr edge)
Definition: crossings.c:133
int count_inversions_down(Edgeptr *edge_array, int number_of_edges, int diff)
bool isFixedEdge(Edgeptr edge)
Definition: heuristics.c:295
Nodeptr * nodes
Definition: graph.h:116
int numberOfCrossingsNode(Nodeptr node)
Definition: crossings.c:125
Nodeptr down_node
Definition: graph.h:99
int number_of_layers
Definition: graph_io.c:28
int maxEdgeCrossings(void)
Definition: crossings.c:104
void clearFixedEdges(void)
Definition: heuristics.c:329
void updateAllCrossings(void)
Definition: crossings.c:138
bool barycenterUpSweep(int starting_layer)
Definition: barycenter.c:239
int numberOfCrossings(void)
Definition: crossings.c:93
Edgeptr * master_edge_list
Definition: graph_io.c:26
void sortByDownNodePosition(Edgeptr *edge_array, int num_edges)
Definition: sorting.c:200
static int count_down_edges(int layer_number)
Definition: crossings.c:52
void fixEdge(Edgeptr edge)
Definition: heuristics.c:298
void genrand_permute(void *A, int length, int element_size)
Definition: random.c:183
int main(int argc, char *argv[])
Definition: add_edges.c:185
void updateNodePositions(int layer)
Definition: sorting.c:149