Crossings Minimization  1.0
heuristics.c
Go to the documentation of this file.
1 /**
2  * @file heuristics.c
3  * @brief High-level implementations of various heuristics
4  * @author Matthias Stallmann
5  * @date 2008/12/29
6  * $Id: heuristics.c 140 2016-02-15 16:13:56Z mfms $
7  */
8 
9 /**
10  * @todo The incrementing of 'iteration' is far from transparent; it takes
11  * place in end_of_iteration(), which is called from a number of different
12  * places, most in other modules; perhaps this is okay, but the comments
13  * should at least indicate what's going on. Furthermore, the stopping
14  * criteria are buried in lots of different places and the functions that are
15  * invoked have other side effects.
16  */
17 
18 #include<stdio.h>
19 #include<stdlib.h>
20 #include<limits.h>
21 #include<string.h>
22 #include<math.h>
23 
24 #include"min_crossings.h"
25 #include"heuristics.h"
26 #include"graph.h"
27 #include"barycenter.h"
28 #include"median.h"
29 #include"dfs.h"
30 #include"crossings.h"
31 #include"channel.h"
32 #include"sorting.h"
33 #include"graph_io.h"
34 #include"sifting.h"
35 #include"stats.h"
36 #include"priority_edges.h"
37 #include"swap.h"
38 #include"timing.h"
39 #include"random.h"
40 
41 /**
42  * if trace_freq is <= TRACE_FREQ_THRESHOLD, then a message is printed at the
43  * end of each pass; end of pass messages don't appear otherwise.
44  */
45 #define TRACE_FREQ_THRESHOLD 2
46 
47 int iteration = 0;
49 
50 int min_crossings = INT_MAX;
52 int min_edge_crossings = INT_MAX;
55 
56 /**
57  * buffer for formatting all tracePrint strings
58  */
59 static char buffer[ MAX_NAME_LENGTH ];
60 
61 
62 #if ! defined( TEST )
63 
64 void createOrdFileName( char * output_file_name, const char * appendix )
65 {
66  if ( output_base_name == NULL )
67  {
68  output_base_name = "temp";
69  printf( "WARNING: no output base name specified, using %s\n", "temp" );
70  printf( " Use -o to get something different\n" );
71  }
72  strcpy( output_file_name, output_base_name );
73  strcat( output_file_name, "-" );
74  strcat( output_file_name, preprocessor );
75  if( strcmp( preprocessor, "" ) != 0
76  && strcmp( heuristic, "" ) != 0 )
77  strcat( output_file_name, "+" );
78  strcat( output_file_name, heuristic );
79  strcat( output_file_name, appendix );
80  strcat( output_file_name, ".ord" );
81 }
82 
83 void createDotFileName( char * output_file_name, const char * appendix )
84 {
85  strcpy( output_file_name, graph_name );
86  if ( strcmp( appendix, "" ) != 0 )
87  strcat( output_file_name, "-" );
88  strcat( output_file_name, appendix );
89  strcat( output_file_name, ".dot" );
90 }
91 
92 /**
93  * Does the actual printing for tracePrint
94  *
95  * @todo Use trace_freq == -1 to indicate that printing should only be done
96  * if there has been improvement since last time; can use INT_MAX as default
97  * instead of -1.
98  *
99  * The logic would be something like:
100  * - update crossings
101  * - trace_freq == -1 then
102  * _ update_best (stats.c)
103  * _ return if ! has_improved (stats.c)
104  */
105 static void trace_printer( int layer, const char * message )
106 {
108  int number_of_crossings = numberOfCrossings();
109  int bottleneck_crossings = maxEdgeCrossings();
110  double current_total_stretch = totalStretch();
111  char * tag = layer < 0 ? "+" : "";
112  printf( "%siteration %4d | layer %2d | crossings %3d | best %3d"
113  " | bottleneck %2d | best %2d | stretch %5.2f | best %5.2f"
114  " | time %4.2f"
115  " | %s\n",
116  tag, iteration, layer, number_of_crossings, total_crossings.best,
117  bottleneck_crossings, max_edge_crossings.best,
118  current_total_stretch, total_stretch.best,
119  RUNTIME, message );
120 }
121 
122 void tracePrint( int layer, const char * message )
123 {
124  static int previous_print_iteration = 0;
125  if ( trace_freq > 0 && iteration % trace_freq == 0
126  && iteration > previous_print_iteration ) {
127  trace_printer( layer, message );
128  if ( layer >= 0 )
129  previous_print_iteration = iteration;
130  }
131  else if ( trace_freq >= 0 && trace_freq <= TRACE_FREQ_THRESHOLD && layer < 0 ) {
132  trace_printer( layer, message );
133  }
134 }
135 
136 /**
137  * @return true if none of the crossing measures of interest have improved
138  * since the last call to this function
139  *
140  * <em>Side effect:</em> all measures are updated
141  */
142 static bool no_improvement( void )
143 {
144  // avoid shortcut logic to make sure side effects really happen
145  bool better_total_crossings = has_improved_int( & total_crossings );
146  bool better_max_edge_crossings = has_improved_int( & max_edge_crossings );
147  bool better_total_stretch = has_improved_double( & total_stretch );
148  bool better_bottleneck_stretch = has_improved_double( & bottleneck_stretch );
149 #ifdef FAVORED
150  bool better_favored_edge_crossings = has_improved( & favored_edge_crossings );
151 #endif
152  return
153  ! better_total_crossings
154  && ! better_max_edge_crossings
155  && ! better_total_stretch
156  && ! better_bottleneck_stretch
157 #ifdef FAVORED
158  && ! better_favored_edge_crossings
159 #endif
160  ;
161 }
162 
163 /**
164  * Prints a message if number of crossings (of various types) are still
165  * improving but max iterations have been reached.
166  */
167 static void print_last_iteration_message( void )
168 {
169  // stopping early because of reaching max iterations even though
170  // improvement has occurred
171  if ( iteration >= max_iterations
172  && ! no_improvement() )
173  {
174  /**
175  * @todo more information in the "still improving" message
176  */
177  printf( "*** still improving but max iterations or runtime reached:"
178  " iteration %d, runtime %2.3f, graph %s\n",
180  }
181 }
182 
183 bool end_of_iteration( void )
184 {
185 #ifdef DEBUG
186  printf( "-> end_of_iteration: iteration = %d, capture_iteration = %d\n",
188 #endif
190  {
192  char appendix[MAX_NAME_LENGTH];
193  sprintf( appendix, "-%d", iteration );
194  createOrdFileName( output_file_name, appendix );
195  writeOrd( output_file_name );
196  }
197 #ifdef DEBUG
198  printf( " ### crossings at end of iteration:\n"
199  " current: total = %d,"
200 #ifdef MAX_EDGE
201  " edge = %d"
202 #endif
203  "\n"
204  " best: total = %d,"
205 #ifdef MAX_EDGE
206  " edge = %d"
207 #endif
208  "\n"
209  " iteration: %d"
210 #ifdef MAX_EDGE
211  " %d"
212 #endif
213  "\n",
215 #ifdef MAX_EDGE
217 #endif
219 #ifdef MAX_EDGE
221 #endif
223 #ifdef MAX_EDGE
225 #endif
226  );
227 #endif // DEBUG
228  bool done = false;
230  {
231  done = true;
233  }
234  update_best_all();
235 #ifdef DEBUG
236  printf( "<- end_of_iteration: iteration = %d, max_iterations = %d, done = %d\n",
237  iteration, max_iterations, done );
238 #endif
239  iteration++;
240  return done;
241 }
242 
243 /**
244  * Prints a message to indicate the point at which standard termination would
245  * have occurred if the option is to keep going. This is called at the end of
246  * a pass. It will not be called if max iterations has been reached.
247  */
249 {
250  /** message already printed? */
251  static bool standard_termination_message_printed = false;
252 
253  if ( ! standard_termination_message_printed )
254  {
255  printf( "*** standard termination here: iteration %d crossings %d"
256 #ifdef MAX_EDGE
257  " edge_crossings %d"
258 #endif
259  " graph %s ***\n",
261 #ifdef MAX_EDGE
263 #endif
264  graph_name );
265  }
266  standard_termination_message_printed = true;
267 }
268 
269 /**
270  * @return True if termination is based on "convergence" rather than the number
271  * of iterations and the heuristic exhibits no improvement in any of the
272  * crossing counts.
273  *
274  * Prints a message about failure to improve even if stopping criterion is
275  * number of iterations.
276  */
277 static bool terminate()
278 {
279  // no_improvement() has side effects
280  bool no_improvement_seen
281  = no_improvement();
282 
283  // separating message from actual termination
284  if ( no_improvement_seen )
286 
287  if ( standard_termination && no_improvement_seen ) return true;
288  if ( iteration >= max_iterations ) return true;
289  return false;
290 }
291 
292 #endif // ! defined( TEST )
293 
294 bool isFixedNode( Nodeptr node ) { return node->fixed; }
295 bool isFixedEdge( Edgeptr edge ) { return edge->fixed; }
296 bool isFixedLayer( int layer ) { return layers[layer]->fixed; }
297 void fixNode( Nodeptr node ) { node->fixed = true; }
298 void fixEdge( Edgeptr edge ) { edge->fixed = true; }
299 void fixLayer( int layer ) { layers[layer]->fixed = true; }
300 bool allNodesFixed( void )
301 {
302  int layer = 0;
303  for( ; layer < number_of_layers; layer++ )
304  {
305  int position = 0;
306  for( ; position < layers[ layer ]->number_of_nodes; position++ )
307  {
308  Nodeptr node = layers[ layer ]->nodes[ position ];
309  if( ! isFixedNode( node ) ) return false;
310  }
311  }
312  return true;
313 }
314 
315 void clearFixedNodes( void )
316 {
317  int layer = 0;
318  for( ; layer < number_of_layers; layer++ )
319  {
320  int position = 0;
321  for( ; position < layers[ layer ]->number_of_nodes; position++ )
322  {
323  Nodeptr node = layers[ layer ]->nodes[ position ];
324  node->fixed = false;
325  }
326  }
327 }
328 
329 void clearFixedEdges( void )
330 {
331  int layer = 1;
332  for( ; layer < number_of_layers; layer++ )
333  {
334  int node_position = 0;
335  for( ; node_position < layers[ layer ]->number_of_nodes; node_position++ )
336  {
337  Nodeptr node = layers[ layer ]->nodes[ node_position ];
338  int edge_position = 0;
339  for( ; edge_position < node->down_degree; edge_position++ )
340  {
341  Edgeptr edge = node->down_edges[ edge_position ];
342  edge->fixed = false;
343  }
344  }
345  }
346 }
347 
348 void clearFixedLayers( void )
349 {
350  int layer = 0;
351  for( ; layer < number_of_layers; layer++ )
352  {
353  layers[ layer ]->fixed = false;
354  }
355 }
356 
357 int totalDegree( int layer )
358 {
359  int total = 0;
360  int position = 0;
361  for( ; position < layers[ layer ]->number_of_nodes; position++ )
362  {
363  Nodeptr node = layers[ layer ]->nodes[ position ];
364  total += node->up_degree + node->down_degree;
365  }
366  return total;
367 }
368 
369 int maxDegreeLayer( void )
370 {
371  int max_deg_layer = -1;
372  int max_deg = -1;
373  int layer = 0;
374  for( ; layer < number_of_layers; layer++ )
375  {
376  int layer_degree = totalDegree( layer );
377  if ( layer_degree > max_deg )
378  {
379  max_deg_layer = layer;
380  max_deg = layer_degree;
381  }
382  }
383  return max_deg_layer;
384 }
385 
387 {
388  int layer = 0;
389  int max_degree = 0;
390  Nodeptr max_degree_node = NULL;
391  for( ; layer < number_of_layers; layer++ )
392  {
393  int position = 0;
394  for( ; position < layers[ layer ]->number_of_nodes; position++ )
395  {
396  Nodeptr node = layers[ layer ]->nodes[ position ];
397  if ( DEGREE( node ) > max_degree )
398  {
399  max_degree = DEGREE( node );
400  max_degree_node = node;
401  }
402  }
403  }
404  return max_degree_node;
405 }
406 
407 // ******* The actual heuristics
408 
409 // crossings_test requires the functions related to fixing nodes and layers
410 // but not the heuristics.
411 #if ! defined(TEST)
412 
413 void median( void )
414 {
415  tracePrint( -1, "*** start median" );
416  while( ! terminate() )
417  {
418  // return if max iterations have been reached as reported by one of the
419  // sweep functions
420  if ( medianUpSweep( 1 ) )
421  return;
422  if ( medianDownSweep( number_of_layers - 2 ) )
423  return;
424  tracePrint( -1, "--- median end of pass" );
425  }
426 }
427 
428 void barycenter( void )
429 {
430  tracePrint( -1, "*** start barycenter" );
431  while( ! terminate() )
432  {
433  // return if max iterations have been reached as reported by one of the
434  // sweep functions
435  if ( barycenterUpSweep( 1 ) )
436  return;
438  return;
439  tracePrint( -1, "--- bary end of pass" );
440  }
441 }
442 
443 void modifiedBarycenter( void )
444 {
445  tracePrint( -1, "*** start modified barycenter" );
446  while( ! terminate() )
447  {
449  while ( true ) /* quit when all layers are fixed */
450  {
451  int layer = maxCrossingsLayer();
452  if ( layer == -1 ) break;
453  fixLayer( layer );
454 
455  barycenterWeights( layer, BOTH );
456  layerSort( layer );
457  updateCrossingsForLayer( layer );
458 
459  tracePrint( layer, "max crossings layer" );
460  // stop if end_of_iteration() reports that max has been reached,
461  // either directly or via the sweep functions
462  if ( end_of_iteration() )
463  return;
464  if ( barycenterUpSweep( layer + 1 ) )
465  return;
466  if ( barycenterDownSweep( layer - 1 ) )
467  return;
468  tracePrint( -1, "--- mod_bary end of pass" );
469  }
470  tracePrint( -1, "=== mod_bary, all layers fixed" );
471  }
472 }
473 
474 /**
475  * @todo For the following variations of barycenter, staticBarycenter() and
476  * evenOddBarycenter(), which are intended to be parallelized, it would be
477  * useful to have a global variable 'number_of_processors' to govern when the
478  * end of an iteration takes place. The current code assumes that the number
479  * of processors is unlimited, but synchronization and capture of current
480  * minimum takes place only at synchronization points, i.e., calls to
481  * end_of_iteration().
482  *
483  * The mechanism would count local_iterations and do something like:<br>
484  * if ( local_iterations % number_of_processors == 0 )
485  * end_of_iteration();
486  * <br>
487  * local_iterations would be updated in the body of each for loop that is
488  * intended to be parallelized (and effects a change) and the above code
489  * woul occur at the end of such a loop
490  */
491 
492 void staticBarycenter( void )
493 {
494  tracePrint( -1, "*** start static barycenter" );
495  while ( ! terminate() )
496  {
497  // sort all layers independently (in parallel) and do a sweep - doesn't
498  // matter which direction
499  for ( int layer = 0; layer < number_of_layers; layer++ )
500  {
501  barycenterWeights( layer, BOTH );
502  }
503  for ( int layer = 0; layer < number_of_layers; layer++ )
504  {
505  layerSort( layer );
506  updateCrossingsForLayer( layer );
507  tracePrint( layer, "static barycenter" );
508  if ( number_of_processors == 1 && end_of_iteration() )
509  return;
510  }
511  if ( number_of_processors != 1 && end_of_iteration() )
512  return;
513  }
514 }
515 
516 /**
517  * Should really be called oddEvenBarycenter, and is referred to as
518  * alt_bary in the user interface. Alternates between sorting odd and even
519  * numbered layers based on both neighboring layers. Weight assignment is
520  * affected by the 'balanced_weight' parameter, set with the -b command-line
521  * option.
522  */
523 void evenOddBarycenter( void ) {
524  int layer;
525  tracePrint( -1, "*** start odd/even barycenter" );
526  while ( ! terminate() ) {
527  // compute weights, then sort the odd layers
528 #ifdef _OPENMP
529 #pragma omp parallel for default(none) private(layer) \
530  shared(number_of_layers, trace_freq, number_of_processors)
531 #endif
532  for ( layer = 1; layer < number_of_layers; layer += 2 ) {
533  barycenterWeights( layer, BOTH );
534  layerSort( layer );
535  updateCrossingsForLayer( layer );
536  tracePrint( layer, "odd layers" );
537  if ( number_of_processors == 1 && end_of_iteration() )
538  return;
539  }
540  tracePrint( -1, "--- evenOddBarycenter end of iteration" );
541  if ( number_of_processors != 1 && end_of_iteration() )
542  return;
543 
544  // ditto for the even layers
545 #ifdef _OPENMP
546 #pragma omp parallel for default(none) private(layer) \
547  shared(number_of_layers, trace_freq, number_of_processors)
548 #endif
549  for ( layer = 0; layer < number_of_layers; layer += 2 ) {
550  barycenterWeights( layer, BOTH );
551  layerSort( layer );
552  updateCrossingsForLayer( layer );
553  tracePrint( layer, "evenlayers" );
554  if ( number_of_processors == 1 && end_of_iteration() )
555  return;
556  }
557  tracePrint( -1, "--- evenOddBarycenter end of iteration" );
558  if ( number_of_processors != 1 && end_of_iteration() )
559  return;
560  }
561 }
562 
563 /**
564  * Alternates between odd and even numbered layers, but instead of
565  * alternating at every iteration and using both neighboring layers to assign
566  * weights, this version uses the downward layer (starting with odd layers)
567  * for a number of iterations corresponding to the number of layers, and then
568  * the upward layer for an equal number of iterations.
569  */
570 void upDownBarycenter( void ) {
571  tracePrint( -1, "*** start up/down barycenter" );
572  Orientation sort_direction = DOWNWARD;
573  while ( ! terminate() ) {
574  // compute weights, then sort the odd layers
575 #ifdef _OPENMP
576 #pragma omp parallel for default(none) private(layer) \
577  shared(number_of_layers, trace_freq, number_of_processors)
578 #endif
579  int start_layer = 1; /* 1 for odd, 0 for even */
580  for ( int i = 0; i < number_of_layers; i++ ) {
581  for ( int layer = start_layer; layer < number_of_layers; layer += 2 ) {
582  barycenterWeights( layer, sort_direction );
583  layerSort( layer );
584  updateCrossingsForLayer( layer );
585  char buffer[LINE_LENGTH+1];
586  sprintf( buffer, "odd/even = %d, direction = %d",
587  start_layer, sort_direction );
588  tracePrint( layer, buffer );
589  if ( number_of_processors == 1 && end_of_iteration() )
590  return;
591  } // end, sort either odd or even layers
592  tracePrint( -1, "--- upDownBaryCenter, end of iteration" );
593  if ( number_of_processors != 1 && end_of_iteration() )
594  return;
595  start_layer = 1 - start_layer;
596 #ifdef _OPENMP
597 #pragma omp parallel for default(none) private(layer) \
598  shared(number_of_layers, trace_freq, number_of_processors)
599 #endif
600  } // end, do number_of_layers times
601  if ( sort_direction == DOWNWARD ) sort_direction = UPWARD;
602  else sort_direction = DOWNWARD;
603  } // end, while ( ! terminate() )
604 } // end, upDownBarycenter
605 
606 /**
607  * Does the parallel part of each iteration of the slabBarycenter algorithm
608  * below.
609  * @param offset how far above the bottom of the slab each layer to be sorted is
610  * @return true if this iteration is to be the last one
611  */
612 static bool slab_bary_iteration( int offset,
613  int slab_size,
614  Orientation sort_direction ) {
615  char buffer[LINE_LENGTH+1];
616  for ( int slab_bottom = 0;
617  slab_bottom < number_of_layers - 1;
618  slab_bottom += slab_size ) {
619  int layer = (slab_bottom + offset) % number_of_layers;
620  if ( ( sort_direction == DOWNWARD && layer == 0 )
621  || ( sort_direction == UPWARD && layer == number_of_layers - 1 )
622  ) continue;
623  barycenterWeights( layer, sort_direction );
624  layerSort( layer );
625  updateCrossingsForLayer( layer );
626  sprintf( buffer, "offset = %d, slab_bottom = %d, direction = %d",
627  offset, slab_bottom, sort_direction );
628  tracePrint( layer, buffer );
629  if ( number_of_processors == 1 && end_of_iteration() )
630  return true;
631  } // end, sort a layer in each slab
632  sprintf( buffer, "--- slabBarycenter, end of iteration, offset = %d", offset );
633  tracePrint( -1, buffer );
634  if ( number_of_processors != 1 && end_of_iteration() )
635  return true;
636 #ifdef _OPENMP
637 #pragma omp parallel for default(none) private(layer) \
638  shared(number_of_layers, trace_freq, number_of_processors)
639 #endif
640  return false;
641 }
642 
643 /**
644  * Each processor does a full-blown barycenter algorithm. Starts are
645  * staggered at distance max(layers/processors,2) and each sweep wraps around
646  * to make the best use of of each processor. Startting layer shifts by 1 at
647  * each iteration.
648  */
649 void slabBarycenter( void ) {
650  int slab_size = number_of_layers;
651  if ( number_of_processors > 1 ) slab_size /= number_of_processors;
652  if ( slab_size < 2 ) slab_size = 2;
653  char buffer[LINE_LENGTH+1];
654  sprintf( buffer, "*** start slab barycenter, slab size = %d", slab_size );
655  tracePrint( -1, buffer );
656  while ( ! terminate() ) {
657  // compute weights, then sort the odd layers
658 #ifdef _OPENMP
659 #pragma omp parallel for default(none) private(layer) \
660  shared(number_of_layers, trace_freq, number_of_processors)
661 #endif
662  // first do an upsweep in each slab
663  // use the bottom layer of the next slab up as well
664  for ( int offset = 1; offset < number_of_layers; offset++ ) {
665  bool no_more_iterations
666  = slab_bary_iteration( offset, slab_size, DOWNWARD );
667  if ( no_more_iterations ) return;
668  } // end, upward sweep
669 
670  // now a downward sweep in each slab, using the top layer of the next
671  // slab down during the last iteration
672  for ( int offset = slab_size - 1; offset > 0; offset-- ) {
673  bool no_more_iterations
674  = slab_bary_iteration( offset, slab_size, UPWARD );
675  if ( no_more_iterations ) return;
676  } // end, downward sweep
677 
678  } // end, while ( ! terminate() )
679 } // end, slabBarycenter
680 
681 /**
682  * Alternates between even numbered and odd numbered layers. Unlike alt_bary,
683  * which bases sorting on both neighboring layers simultaneously, this
684  * version rotates between doing upward, downward, and both.
685  */
686 void rotatingBarycenter( void ) {
687  tracePrint( -1, "*** start rotating barycenter" );
688  Orientation sort_direction = BOTH;
689  int start_layer = 1; /* 1 for odd, 0 for even */
690  while ( ! terminate() ) {
691  // compute weights, then sort the odd layers
692 #ifdef _OPENMP
693 #pragma omp parallel for default(none) private(layer) \
694  shared(number_of_layers, trace_freq, number_of_processors)
695 #endif
696  for ( int layer = start_layer; layer < number_of_layers; layer += 2 ) {
697  barycenterWeights( layer, sort_direction );
698  layerSort( layer );
699  updateCrossingsForLayer( layer );
700  char buffer[LINE_LENGTH+1];
701  sprintf( buffer, "odd/even = %d, direction = %d",
702  start_layer, sort_direction );
703  tracePrint( layer, buffer );
704  if ( number_of_processors == 1 && end_of_iteration() )
705  return;
706  } // end, sort either odd or even layers
707  tracePrint( -1, "--- upDownBaryCenter, end of iteration" );
708  if ( number_of_processors != 1 && end_of_iteration() )
709  return;
710 #ifdef _OPENMP
711 #pragma omp parallel for default(none) private(layer) \
712  shared(number_of_layers, trace_freq, number_of_processors)
713 #endif
714  start_layer = 1 - start_layer;
715  if ( sort_direction == DOWNWARD ) sort_direction = UPWARD;
716  else if ( sort_direction == UPWARD ) sort_direction = BOTH;
717  else sort_direction = DOWNWARD;
718  } // end, while ( ! terminate() )
719 }
720 
721 /**
722  * Handles sifting of a node and all related bookkeeping
723  * @return true if max_iterations reached
724  */
725 static bool sift_iteration( Nodeptr node )
726 {
727  sift( node );
728  fixNode( node );
729  sprintf( buffer, "$$$ %s, node = %s", heuristic, node->name );
730  tracePrint( node->layer, buffer );
731  if ( end_of_iteration() ) return true;
732  return false;
733 }
734 
735 /**
736  * Handles sifting of both endpoints of an edge and all related bookkeeping
737  *
738  * @return true if max iterations reached
739  *
740  * @todo Consider sifting only one endpoint even if both are not fixed and
741  * leaving the edge unfixed in that case.
742  */
743 static bool edge_sift_iteration( Edgeptr edge )
744 {
745  // figure out which of the two nodes to sift (none, one, or both)
746  bool sift_up_node = false;
747  bool sift_down_node = false;
748  if ( mce_option == EDGES ) {
749  sift_up_node = sift_down_node = true;
750  }
751  if ( ! isFixedNode( edge->up_node ) ) {
752  sift_up_node = true;
753  }
754  if ( ! isFixedNode( edge->down_node ) ) {
755  sift_down_node = true;
756  }
757  if ( mce_option == ONE_NODE ) {
758  // if neither node is fixed, sift only the one with the most crossings
759  if ( sift_up_node && sift_down_node ) {
760  if ( numberOfCrossingsNode( edge->down_node )
761  > numberOfCrossingsNode( edge->up_node ) ) {
762  sift_up_node = false;
763  }
764  else {
765  sift_down_node = false;
766  }
767  }
768  }
769  if ( sift_up_node )
770  {
771  sift_node_for_edge_crossings( edge, edge->up_node );
772  fixNode( edge->up_node );
773  sprintf( buffer, "$$$ %s, node = %s, position = %d",
774  heuristic, edge->up_node->name, edge->up_node->position );
775  tracePrint( edge->up_node->layer, buffer );
776  if ( end_of_iteration() )
777  return true;
778  }
779 
780  if ( sift_down_node )
781  {
783  fixNode( edge->down_node );
784  sprintf( buffer, "$$$ %s, node = %s, position = %d",
785  heuristic, edge->down_node->name, edge->down_node->position );
786  tracePrint( edge->down_node->layer, buffer );
787  if ( end_of_iteration() )
788  return true;
789  }
790  return false;
791 }
792 
795  fixNode(node);
797  sprintf(buffer, "$$$ %s, node = %s, position = %d",
798  heuristic, node->name, node->position);
799  tracePrint(node->layer, buffer);
800  if (end_of_iteration())
801  return true;
802  return false;
803 }
804 
806 {
807  tracePrint( -1, "*** start maximum crossings node" );
808  while( ! terminate() )
809  {
810  clearFixedNodes();
811  while ( true )
812  // keep going until all nodes are fixed
813  {
814  Nodeptr node = maxCrossingsNode();
815  if ( node == NULL ) break;
816  bool last_iteration = false;
817  /* if ( sifting_style == MAX ) */
818  /* last_iteration = edge_sift_iteration( edge, node ); */
819  /* else */
820  last_iteration = sift_iteration( node );
821  if ( last_iteration )
822  return;
823  }
824  tracePrint( -1, "$$$ mcn, all nodes fixed" );
825  }
826 }
827 
829  tracePrint( -1, "*** start maximum crossings edge with sifting" );
830  while( ! terminate() ) {
831  clearFixedNodes();
832  clearFixedEdges();
833  while ( true ) {
834  Edgeptr edge = maxCrossingsEdge();
835  if ( edge == NULL || allNodesFixed() ) break;
836  sprintf( buffer, "->- mce_s, edge %s -> %s",
837  edge->down_node->name, edge->up_node->name );
838  tracePrint( edge->up_node->layer, buffer );
839  bool last_iteration = false;
840  if ( ! isFixedNode( edge->up_node ) ) {
841  last_iteration = sift_iteration( edge->up_node );
842  fixNode( edge->up_node );
843  if ( last_iteration ) return;
844  }
845  if ( ! isFixedNode( edge->down_node ) ) {
846  last_iteration = sift_iteration( edge->down_node );
847  fixNode( edge->down_node );
848  if ( last_iteration ) return;
849  }
850  fixEdge( edge );
851  }
852  tracePrint( -1, "--- mce with sifting, end pass" );
853  }
854 }
855 
856 /**
857  * @return true if the pass should end based on command-line option
858  * mce_option; note: if the option is EDGES, maxCrossingsEdge() will return
859  * NULL and this will not happen unless all the nodes have been fixed as
860  * well, in most cases more than once.
861  */
862 static bool end_mce_pass( Edgeptr edge )
863 {
864  if( edge == NULL ) return true;
865  if( mce_option == EARLY
866  && isFixedNode( edge->up_node )
867  && isFixedNode( edge->down_node )
868  ) return true;
869  if( mce_option == NODES
870  && allNodesFixed()
871  ) return true;
872  return false;
873 }
874 
876 {
877  tracePrint( -1, "*** start maximum crossings edge" );
878  while( ! terminate() )
879  {
880  clearFixedNodes();
881  clearFixedEdges();
882  while ( true )
883  // keep going until specified pass ending is encountered
884  {
885  // complicated: current implementation visits edges based on layer
886  // and node order within layer
887  // if ( randomize_order ) randomize_edge_list();
888  Edgeptr edge = maxCrossingsEdge();
889  if ( edge == NULL ) break;
890  sprintf( buffer, "->- mce, edge %s -> %s",
891  edge->down_node->name, edge->up_node->name );
892  tracePrint( edge->up_node->layer, buffer );
893  if ( end_mce_pass( edge ) ) break;
894  bool last_iteration = false;
895  /**
896  * @todo what follows is now incorporated into
897  * maximumCrossingsEdgeWithSifting(); eventually the two could be
898  * merged
899  */
900  /* if ( sifting_style == TOTAL ) */
901  /* last_iteration = sift_iteration( node ); */
902  /* else */
903  last_iteration = edge_sift_iteration( edge );
904  if ( last_iteration )
905  return;
906  fixEdge( edge );
907  }
908  tracePrint( -1, "--- mce, end pass" );
909  }
910 }
911 
912 void maximumStretchEdge( void ) {
913  tracePrint( -1, "*** start maximum strech edge with total stretch sifting" );
914  while( ! terminate() ) {
915  clearFixedNodes();
916  clearFixedEdges();
917  while ( true ) {
918  Edgeptr edge = maxStretchEdge();
919  if ( edge == NULL || allNodesFixed() ) break;
920  sprintf( buffer, "->- mse, edge %s -> %s",
921  edge->down_node->name, edge->up_node->name );
922  tracePrint( edge->up_node->layer, buffer );
923  bool last_iteration = false;
924  if ( ! isFixedNode( edge->up_node ) ) {
925  last_iteration = total_stretch_sift_iteration( edge->up_node );
926  fixNode( edge->up_node );
927  if ( last_iteration ) return;
928  }
929  if ( ! isFixedNode( edge->down_node ) ) {
930  last_iteration = total_stretch_sift_iteration( edge->down_node );
931  fixNode( edge->down_node );
932  if ( last_iteration ) return;
933  }
934  fixEdge( edge );
935  }
936  tracePrint( -1, "--- mse with sifting, end pass" );
937  }
938 }
939 
940 // the value used in the Matuszewski et al. paper
941 #define MAX_FAILS 1
942 
943 /**
944  * Sifts node in decreasing order as determined by the input array
945  * @return false if the sift was unsuccessful, i.e., it did not improve upon
946  * initial_crossings or if the maximum number of iterations was reached
947  *
948  * @note here the key is improvement upon the number of crossings at the
949  * beginning of this sifting pass, not necessarily the number of crossings
950  * overall.
951  */
952 static bool sift_decreasing( const Nodeptr * node_array,
953  int num_nodes, int initial_crossings )
954 {
955 #ifdef DEBUG
956  printf( "-> sift_decreasing, num_nodes = %d, crossings = %d\n",
957  num_nodes, initial_crossings );
958 #endif
959  // sift by decreasing 'weight' (degree in this case)
960  int i;
961  for( i = num_nodes - 1; i >= 0; i-- )
962  {
963 #ifdef DEBUG
964  printf( " sifting i = %d, node = %s\n", i, node_array[i]->name );
965 #endif
966  sift( node_array[ i ] );
967  tracePrint( node_array[ i ]->layer, "^^^ sift_increasing ^^^" );
968  sprintf( buffer, " $$$ sift, node = %s, pos = %d",
969  node_array[i]->name, node_array[i]->position );
970  tracePrint( node_array[ i ]->layer, buffer );
971  if ( end_of_iteration() ) break;
972  }
973 #ifdef DEBUG
974  printf( "<- sift_decreasing, crossings = %d\n",
975  numberOfCrossings() );
976 #endif
977  return numberOfCrossings() < initial_crossings && iteration < max_iterations;
978 }
979 
980 /**
981  * Sifts node in increasing order as determined by the input array
982  * @return false if the sift was unsuccessful, i.e., it did not improve upon
983  * initial_crossings or if the maximum number of iterations was reached
984  *
985  * @note here the key is improvement upon the number of crossings at the
986  * beginning of this sifting pass, not necessarily the number of crossings
987  * overall.
988  */
989 static bool sift_increasing( const Nodeptr * node_array,
990  int num_nodes, int initial_crossings )
991 {
992  // sift by increasing 'weight' (degree in this case)
993  int i;
994  for( i = 0; i < num_nodes; i++ )
995  {
996  sift( node_array[ i ] );
997  tracePrint( node_array[ i ]->layer, "^^^ sift_increasing ^^^" );
998  sprintf( buffer, " $$$ sift, node = %s, pos = %d",
999  node_array[i]->name, node_array[i]->position );
1000  tracePrint( node_array[ i ]->layer, buffer );
1001  if ( end_of_iteration() ) break;
1002  }
1003  return numberOfCrossings() < initial_crossings && iteration < max_iterations;
1004 }
1005 
1006 void sifting( void ) {
1007  // sort nodes by increasing degree (other options not implemented yet); but
1008  // if randomize_order is true, then the order is randomized and the node
1009  // list is resorted before each pass
1011 #ifdef DEBUG
1012  printf( " sifting: nodes after sorting -\n" );
1013  for( index = 0; index < number_of_nodes; index++ )
1014  printf( " node_array[%2d] = %s\n", index, node_array[index]->name );
1015 #endif
1016 
1017  /* the sifting algorithm from the Matuszewski et al. paper, except that a
1018  * fixed number of iterations or a specific runtime limit may supercede the
1019  * standard stopping criterion
1020  */
1021  int fail_count = 0;
1022  while( ( standard_termination && fail_count < MAX_FAILS )
1023  || ! terminate() ) {
1024  int crossings_before = numberOfCrossings();
1025  bool fail = false;
1026  if ( randomize_order ) {
1027  genrand_permute( master_node_list, number_of_nodes, sizeof(Nodeptr) );
1028  sortByDegree( master_node_list, number_of_nodes );
1029  }
1030  fail = ! sift_decreasing( master_node_list, number_of_nodes, crossings_before );
1031  if ( iteration >= max_iterations )
1032  break;
1033  tracePrint( -1, "--- end of sifting pass" );
1034  if( fail ) {
1035  fail_count++;
1036  if ( randomize_order ) {
1037  genrand_permute( master_node_list, number_of_nodes, sizeof(Nodeptr) );
1038  sortByDegree( master_node_list, number_of_nodes );
1039  }
1040  fail = ! sift_increasing( master_node_list, number_of_nodes,
1041  crossings_before );
1042  if ( end_of_iteration() )
1043  break;
1044  }
1045  else {
1046  if ( randomize_order ) {
1047  genrand_permute( master_node_list, number_of_nodes, sizeof(Nodeptr) );
1048  sortByDegree( master_node_list, number_of_nodes );
1049  }
1050  fail = ! sift_decreasing( master_node_list, number_of_nodes,
1051  crossings_before );
1052  if ( end_of_iteration() )
1053  break;
1054  }
1055  tracePrint( -1, "--- end of sifting pass" );
1056  // wait for mce implementation
1057 /* if ( randomize_order ) */
1058 /* RN_permute( node_array, number_of_nodes, sizeof(nodePtr) ); */
1059  if ( fail ) fail_count++;
1060  }
1061 }
1062 
1063 // preprocessors
1064 
1066 {
1067  printf( "bfs not implemented\n" );
1068 }
1069 
1070 void depthFirstSearch( void )
1071 {
1072  assignDfsWeights();
1073  int layer = 0;
1074  for( ; layer < number_of_layers; layer++ )
1075  layerSort( layer );
1076 }
1077 
1078 /**
1079  * Assigns weights so that, in a subsequent layer sort, the last node on the
1080  * layer is moved to the middle position, the next to last on one side, the
1081  * third from last on the other, etc.
1082  */
1083 static void weight_first_to_middle( int layer )
1084 {
1085  int n = layers[ layer ]->number_of_nodes;
1086  int position = 0;
1087  for( ; position < n; position++ )
1088  {
1089  int position_from_last = n - position - 1;
1090  Nodeptr node = layers[ layer ]->nodes[ position ];
1091  node->weight
1092  = ( position_from_last % 2 == 0 )
1093  ? n / 2 - position_from_last
1094  : n / 2 + position_from_last;
1095  }
1096 }
1097 
1098 void middleDegreeSort( void )
1099 {
1100  for ( int layer = 0; layer < number_of_layers; layer++ )
1101  {
1102  sortByDegree( layers[layer]->nodes, layers[layer]->number_of_nodes );
1103  weight_first_to_middle( layer );
1104  layerQuicksort( layer );
1105  }
1106 }
1107 
1108 // The following is the original implementation - not of much use in a
1109 // parallel setting because of the barycenter sweeps
1110 
1111 /* void middleDegreeSort( void ) */
1112 /* { */
1113 /* // sort nodes on the layer of the largest degree node so that it is in */
1114 /* // the middle and degree decreases as you move to the outside */
1115 /* Nodeptr node = maxDegreeNode(); */
1116 /* int layer = node->layer; */
1117 /* #ifdef DEBUG */
1118 /* printf( "-> middleDegreeSort: node = %s, layer = %d\n", */
1119 /* node->name, layer ); */
1120 /* #endif */
1121 /* sortByDegree( layers[layer]->nodes, layers[layer]->number_of_nodes ); */
1122 /* weight_first_to_middle( layer ); */
1123 /* layerSort( layer ); */
1124 
1125 /* // do barycenter up and down sweeps from the (sorted) max degree layer */
1126 /* #ifdef DEBUG */
1127 /* printf( " middleDegreeSort: start upsweep\n" ); */
1128 /* #endif */
1129 /* barycenterUpSweep( layer + 1 ); */
1130 /* #ifdef DEBUG */
1131 /* printf( " middleDegreeSort: start downsweep\n" ); */
1132 /* #endif */
1133 /* barycenterDownSweep( layer - 1 ); */
1134 /* #ifdef DEBUG */
1135 /* printf( "<- middleDegreeSort\n" ); */
1136 /* #endif */
1137 /* } */
1138 
1139 static void swap_nodes( Nodeptr * node_array, int i, int j )
1140 {
1141  node_array[i]->position = j;
1142  node_array[j]->position = i;
1143  Nodeptr temp = node_array[i];
1144  node_array[i] = node_array[j];
1145  node_array[j] = temp;
1146 }
1147 
1148 /**
1149  * Does an iteration where either all swaps between nodes i, i+1 on layers L,
1150  * L+1 are considered where i, L are either even or odd
1151  * @param crossings the number of crossings before this iteration
1152  * @param odd_even is 1 if odd values of i and L are considered, even
1153  * otherwise
1154  * @return the number of crossings after this iteration
1155  */
1156 static int swapping_iteration( int crossings, int odd_even )
1157 {
1158 #ifdef DEBUG
1159  printf( "-> swapping_iteration, crossings = %d, odd = %d\n",
1160  crossings, odd_even );
1161 #endif
1162  for ( int layer = odd_even; layer < number_of_layers; layer += 2 )
1163  {
1164  Layerptr layer_ptr = layers[ layer ];
1165  for ( int i = odd_even; i < layer_ptr->number_of_nodes - 1; i += 2 )
1166  {
1167  Nodeptr * nodes = layer_ptr->nodes;
1168  int crossings_before_swap = node_crossings( nodes[i], nodes[i+1] );
1169  int crossings_after_swap = node_crossings( nodes[i+1], nodes[i] );
1170  int diff = crossings_before_swap - crossings_after_swap;
1171  if ( diff > 0 )
1172  {
1173  swap_nodes( nodes, i, i+1 );
1174  crossings -= diff;
1175  }
1176 #ifdef DEBUG
1177  printf( " swapping, layer = %d, node = %d, diff = %d, crossings = %d\n",
1178  layer, i, diff, crossings );
1179 #endif
1180  }
1181  tracePrint( layer, "<-> swapping" );
1182  }
1183 #ifdef DEBUG
1184  printf( "<- swapping_iteration, crossings = %d\n",
1185  crossings );
1186 #endif
1187  return crossings;
1188 }
1189 
1190 
1191 /**
1192  * !!! attempted to update this so that it would fix the Pareto frontier, but
1193  a swapping iteration does not actually recompute total crossings !!!
1194  */
1195 void swapping( void )
1196 {
1197  bool improved = true;
1199  int previous_best_crossings = post_processing_crossings;
1201 
1202 #ifdef DEBUG
1203  printf( "-> swapping, post_processing_crossings = %d\n", post_processing_crossings );
1204 #endif
1205 
1206  tracePrint( -1, "*** start swapping ***" );
1207  while ( improved )
1208  {
1209  // look for improvements by swapping nodes i, i+1 on layers L, L+1,
1210  // where i and L are even
1213  if ( post_processing_crossings < previous_best_crossings )
1214  {
1215  improved = true;
1217  previous_best_crossings = post_processing_crossings;
1218  update_best_all();
1219  }
1220  else improved = false;
1222 
1223  // look for improvements by swapping nodes i, i+1 on layers L, L+1,
1224  // where i and L are odd
1226  if ( post_processing_crossings < previous_best_crossings )
1227  {
1228  improved = true;
1230  previous_best_crossings = post_processing_crossings;
1231  update_best_all();
1232  }
1233  // don't set improved to false here -- there may have been improvement
1234  // during the even iteration
1236  tracePrint( -1, "-- end of swapping pass" );
1237  } // while improved
1238 
1239 #ifdef DEBUG
1240  printf( "<- swapping, post_processing_crossings = %d\n", post_processing_crossings );
1241 #endif
1242 
1243 }
1244 
1245 #endif // ! defined(TEST)
1246 
1247 /* [Last modified: 2016 06 10 at 13:11:47 GMT] */
Nodeptr * master_node_list
Definition: graph_io.c:25
void staticBarycenter(void)
Definition: heuristics.c:492
static bool sift_decreasing(const Nodeptr *node_array, int num_nodes, int initial_crossings)
Definition: heuristics.c:952
static char output_file_name[MAX_NAME_LENGTH]
Definition: min_crossings.c:73
bool fixed
Definition: graph.h:119
Nodeptr up_node
Definition: graph.h:98
Nodeptr maxDegreeNode(void)
Definition: heuristics.c:386
bool medianUpSweep(int starting_layer)
Definition: median.c:187
void maximumCrossingsNode(void)
Definition: heuristics.c:805
void assignDfsWeights(void)
Definition: dfs.c:123
void fixLayer(int layer)
Definition: heuristics.c:299
int trace_freq
Definition: min_crossings.c:63
Definition: defs.h:43
void maximumStretchEdge(void)
Definition: heuristics.c:912
int min_edge_crossings
Definition: heuristics.c:52
int min_crossings_iteration
Definition: heuristics.c:53
void sift_node_for_edge_crossings(Edgeptr edge, Nodeptr node)
Definition: sifting.c:172
Orientation
Definition: defs.h:43
void maximumCrossingsEdge(void)
Definition: heuristics.c:875
Definition of infrastructure functions that are used to implement sifting-based heuristics.
Interface for functions implementing all of the heuristics Those labeled parallel are designed specif...
static void weight_first_to_middle(int layer)
Definition: heuristics.c:1083
char * name
Definition: graph.h:63
int maxCrossingsLayer(void)
Definition: crossings.c:220
static char buffer[MAX_NAME_LENGTH]
Definition: heuristics.c:59
bool allNodesFixed(void)
Definition: heuristics.c:300
void swapping(void)
Definition: heuristics.c:1195
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
CROSSING_STATS_DOUBLE bottleneck_stretch
Definition: stats.c:151
Functions for setting up priority edges and retrieving the number of crossings involving them...
static bool slab_bary_iteration(int offset, int slab_size, Orientation sort_direction)
Definition: heuristics.c:612
Edgeptr * down_edges
Definition: graph.h:78
static void trace_printer(int layer, const char *message)
Definition: heuristics.c:105
CROSSING_STATS_INT max_edge_crossings
Definition: stats.c:148
void maximumCrossingsEdgeWithSifting(void)
Definition: heuristics.c:828
interface for function that assigns weights based on depth-first search
int capture_iteration
Definition: min_crossings.c:52
bool end_of_iteration(void)
Definition: heuristics.c:183
Global variables, functions, and parameters specified on the command line.
void update_best_all(void)
Definition: stats.c:281
int position
Definition: graph.h:73
void breadthFirstSearch(void)
Definition: heuristics.c:1065
double max_runtime
Definition: min_crossings.c:43
void clearFixedNodes(void)
Definition: heuristics.c:315
int max_iterations
Definition: min_crossings.c:41
static bool terminate()
Definition: heuristics.c:277
static bool sift_increasing(const Nodeptr *node_array, int num_nodes, int initial_crossings)
Definition: heuristics.c:989
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
#define LINE_LENGTH
Definition: defs.h:34
Nodeptr maxCrossingsNode(void)
Definition: crossings.c:242
#define RUNTIME
Definition: min_crossings.h:35
Interface for functions that perform various sorts. All sorts are stable.
Functions for reporting various statistics about the graph and the outcomes.
void createOrdFileName(char *output_file_name, const char *appendix)
Definition: heuristics.c:64
char * output_base_name
Definition: min_crossings.c:60
void updateCrossingsForLayer(int layer)
Definition: crossings.c:147
Edgeptr maxCrossingsEdge(void)
Definition: crossings.c:262
int iteration
Definition: heuristics.c:47
CROSSING_STATS_INT total_crossings
Definition: stats.c:147
void barycenter(void)
Definition: heuristics.c:428
#define TRACE_FREQ_THRESHOLD
Definition: heuristics.c:45
implementation of utilities that maintain information about channels; eventually these will replace t...
void clearFixedLayers(void)
Definition: heuristics.c:348
void modifiedBarycenter(void)
Definition: heuristics.c:443
void sift(Nodeptr node)
puts the node in a position that minimizes the number of crossings.
Definition: sifting.c:57
int up_degree
Definition: graph.h:74
bool fixed
Definition: graph.h:85
static bool total_stretch_sift_iteration(Nodeptr node)
Definition: heuristics.c:793
int number_of_nodes
Definition: graph_io.c:27
char * heuristic
Definition: min_crossings.c:39
static void print_standard_termination_message()
Definition: heuristics.c:248
void sortByDegree(Nodeptr *node_array, int num_nodes)
Definition: sorting.c:215
int post_processing_crossings
Definition: heuristics.c:51
double totalStretch()
Definition: channel.c:109
Definition of functions for reading and writing graphs.
bool isFixedLayer(int layer)
Definition: heuristics.c:296
bool standard_termination
Definition: min_crossings.c:46
void sifting(void)
Definition: heuristics.c:1006
static int swapping_iteration(int crossings, int odd_even)
Definition: heuristics.c:1156
void median(void)
Definition: heuristics.c:413
void upDownBarycenter(void)
Definition: heuristics.c:570
void fixNode(Nodeptr node)
Definition: heuristics.c:297
double weight
Definition: graph.h:82
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
CROSSING_STATS_INT favored_edge_crossings
Definition: stats.c:149
void createDotFileName(char *output_file_name, const char *appendix)
Definition: heuristics.c:83
int post_processing_iteration
Definition: heuristics.c:48
bool medianDownSweep(int starting_layer)
Definition: median.c:206
bool has_improved_double(CROSSING_STATS_DOUBLE *stats)
Definition: stats.c:327
Definition of data structures and access functions for a layered graph.
CROSSING_STATS_DOUBLE total_stretch
Definition: stats.c:150
bool fixed
Definition: graph.h:106
static char graph_name[MAX_NAME_LENGTH]
Definition: dot.c:42
static void print_last_iteration_message(void)
Definition: heuristics.c:167
static bool end_mce_pass(Edgeptr edge)
Definition: heuristics.c:862
bool isFixedEdge(Edgeptr edge)
Definition: heuristics.c:295
Definition: defs.h:43
void tracePrint(int layer, const char *message)
Definition: heuristics.c:122
void barycenterWeights(int layer, Orientation orientation)
Definition: barycenter.c:206
void layerSort(int layer)
Definition: sorting.c:159
enum mce_option_enum mce_option
Definition: min_crossings.c:49
int node_crossings(Nodeptr node_a, Nodeptr node_b)
Definition: swap.c:57
Nodeptr * nodes
Definition: graph.h:116
int numberOfCrossingsNode(Nodeptr node)
Definition: crossings.c:125
interface for various functions related to median heuristics
static bool edge_sift_iteration(Edgeptr edge)
Definition: heuristics.c:743
void save_order(Orderptr ord_info)
Definition: order.c:48
Headers of functions that compute the change in crossing number or max edge crossings when two neighb...
Nodeptr down_node
Definition: graph.h:99
int number_of_layers
Definition: graph_io.c:28
static bool sift_iteration(Nodeptr node)
Definition: heuristics.c:725
void slabBarycenter(void)
Definition: heuristics.c:649
int maxEdgeCrossings(void)
Definition: crossings.c:104
int number_of_processors
Definition: min_crossings.c:45
int totalDegree(int layer)
Definition: heuristics.c:357
static void swap_nodes(Nodeptr *node_array, int i, int j)
Definition: heuristics.c:1139
bool has_improved_int(CROSSING_STATS_INT *stats)
Definition: stats.c:309
static bool no_improvement(void)
Definition: heuristics.c:142
char * preprocessor
Definition: min_crossings.c:40
interface for various functions related to barycenter heuristics
void evenOddBarycenter(void)
Definition: heuristics.c:523
int min_crossings
Definition: heuristics.c:50
void clearFixedEdges(void)
Definition: heuristics.c:329
void updateAllCrossings(void)
Definition: crossings.c:138
#define MAX_NAME_LENGTH
Definition: defs.h:32
Edgeptr maxStretchEdge()
Definition: channel.c:146
void middleDegreeSort(void)
Definition: heuristics.c:1098
bool barycenterUpSweep(int starting_layer)
Definition: barycenter.c:239
int numberOfCrossings(void)
Definition: crossings.c:93
Orderptr best_crossings_order
Definition: min_crossings.c:66
int best_heuristic_iteration
Definition: stats.h:25
void writeOrd(const char *ord_file)
Definition: graph_io.c:405
int min_edge_crossings_iteration
Definition: heuristics.c:54
#define MAX_FAILS
Definition: heuristics.c:941
void rotatingBarycenter(void)
Definition: heuristics.c:686
void layerQuicksort(int layer)
Definition: sorting.c:189
Header for a simple function to compute CPU user milliseconds.
void fixEdge(Edgeptr edge)
Definition: heuristics.c:298
void depthFirstSearch(void)
Definition: heuristics.c:1070
int maxDegreeLayer(void)
Definition: heuristics.c:369
void genrand_permute(void *A, int length, int element_size)
Definition: random.c:183
Definition: defs.h:43