Crossings Minimization  1.0
stats.c
Go to the documentation of this file.
1 /**
2  * @file stats.c
3  * @brief Implementation of functions that print statistics
4  * @author Matt Stallmann
5  * @date 2009/05/19
6  *
7  * @todo To keep things simple, total stretch is rounded to an integer value
8  * $Id: stats.c 131 2016-01-12 01:07:39Z mfms $
9  */
10 
11 
12 #include<stdio.h>
13 #include<stdlib.h>
14 #include<limits.h>
15 #include<math.h>
16 #include<float.h>
17 
18 #include"stats.h"
19 #include"defs.h"
20 #include"heuristics.h"
21 #include"graph.h"
22 #include"min_crossings.h"
23 #include"crossings.h"
24 #include"channel.h"
25 #include"priority_edges.h"
26 #include"Statistics.h"
27 #include"timing.h"
28 
29 typedef struct pareto_item {
30  double objective_one;
31  double objective_two;
32  int iteration;
33  struct pareto_item * rest;
34 } * PARETO_LIST;
35 
36 static PARETO_LIST pareto_list = NULL;
37 
38 static void init_pareto_list( void ) { pareto_list = NULL; }
39 
40 static void print_pareto_list( PARETO_LIST list, FILE * output_stream ) {
41  PARETO_LIST local_list = list;
42  while ( local_list != NULL ) {
44  fprintf(output_stream, "%d^%d",
45  (int) local_list->objective_one,
46  (int) local_list->objective_two);
47  }
48  else if ( pareto_objective == STRETCH_TOTAL ) {
49  fprintf(output_stream, "%f^%d",
50  local_list->objective_one,
51  (int) local_list->objective_two);
52  }
53  else { // pareto_objective == BOTTLENECK_STRETCH
54  fprintf(output_stream, "%d^%f",
55  (int) local_list->objective_one,
56  local_list->objective_two);
57  }
58  local_list = local_list->rest;
59  if ( local_list != NULL ) fprintf(output_stream, ";");
60  }
61  local_list = list;
62  printf(", ");
63  while ( local_list != NULL ) {
64  fprintf(output_stream, "%d", local_list->iteration);
65  local_list = local_list->rest;
66  if ( local_list != NULL ) fprintf(output_stream, ";");
67  }
68 }
69 
70 /**
71  * Inserts, if appropriate, an item with the given values of objective_one and
72  * and objective_two into the list representing a Pareto frontier. The frontier
73  * is maintained in increasing objective_one, decreasing objective_two order.
74  */
76  double objective_two,
77  int iteration,
78  PARETO_LIST list) {
79 #ifdef DEBUG
80  printf("-> pareto_insert: %f, %f, %d, ",
81  objective_one, objective_two, iteration);
82  print_pareto_list(list, stdout);
83  printf("\n");
84 #endif
85  PARETO_LIST new_list = NULL;
86  if ( list == NULL ) {
87  new_list = (PARETO_LIST) calloc(1, sizeof(struct pareto_item));
88  new_list->objective_one = objective_one;
89  new_list->objective_two = objective_two;
90  new_list->iteration = iteration;
91  new_list->rest = NULL;
92  }
93  else {
94  double first_objective_one = list->objective_one;
95  double first_objective_two = list->objective_two;
96  if ( objective_one < first_objective_one
97  && objective_two > first_objective_two ) {
98  // new pareto point
99  new_list = (PARETO_LIST) calloc(1, sizeof(struct pareto_item));
100  new_list->objective_one = objective_one;
101  new_list->objective_two = objective_two;
102  new_list->iteration = iteration;
103  new_list->rest = list;
104  }
105  else if ( objective_one < first_objective_one
106  && objective_two == first_objective_two ) {
107  // replace first point, found one with smaller objective_one value
109  list->iteration = iteration;
110  new_list = list;
111  }
112  else if ( objective_one <= first_objective_one
113  && objective_two < first_objective_two ) {
114  // replace first point with better one; since the new point also has
115  // smaller objective_two, it may replace others down the line; in this
116  // case, we need to actually delete the existing first point
117  new_list = pareto_insert(objective_one,
118  objective_two,
119  iteration,
120  list->rest);
121  free(list);
122  }
123  else if ( objective_one > first_objective_one
124  && objective_two < first_objective_two ) {
125  // need to keep looking; point with greater or equal objective_one not
126  // found
127  list->rest = pareto_insert(objective_one,
128  objective_two,
129  iteration,
130  list->rest);
131  new_list = list;
132  }
133  else {
134  // otherwise, no need to continue: objective_one >= first_objective_one and
135  // objective_two >= first_objective_two
136  new_list = list;
137  }
138  }
139 #ifdef DEBUG
140  printf("<- pareto_insert: ");
141  print_pareto_list(new_list, stdout);
142  printf("\n");
143 #endif
144  return new_list;
145 }
146 
153 
155  const char * name )
156 {
157  stats->name = name;
158  stats->at_beginning = INT_MAX;
159  stats->after_preprocessing = INT_MAX;
160  stats->after_heuristic = INT_MAX;
161  stats->after_post_processing = INT_MAX;
162  stats->best = INT_MAX;
163  stats->previous_best = INT_MAX;
164  stats->best_heuristic_iteration = -1;
165  stats->post_processing_iteration = -1;
166 }
167 
169  const char * name )
170 {
171  stats->name = name;
172  stats->at_beginning = DBL_MAX;
173  stats->after_preprocessing = DBL_MAX;
174  stats->after_heuristic = DBL_MAX;
175  stats->after_post_processing = DBL_MAX;
176  stats->best = DBL_MAX;
177  stats->previous_best = DBL_MAX;
178  stats->best_heuristic_iteration = -1;
179  stats->post_processing_iteration = -1;
180 }
181 
183 {
184  init_specific_crossing_stats_int( & total_crossings, "Crossings" );
185  init_specific_crossing_stats_int( & max_edge_crossings, "EdgeCrossings" );
186  init_specific_crossing_stats_double( & total_stretch, "Stretch" );
187  init_specific_crossing_stats_double( & bottleneck_stretch, "BottleneckStretch" );
188 #ifdef FAVORED
189  init_specific_crossing_stats( & favored_edge_crossings, "FavoredCrossings" );
190 #endif
191  if ( pareto_objective != NO_PARETO )
193 }
194 
196 {
197  total_crossings.at_beginning = numberOfCrossings();
198  max_edge_crossings.at_beginning = maxEdgeCrossings();
199  total_stretch.at_beginning = totalStretch();
200  bottleneck_stretch.at_beginning = maxEdgeStretch();
201 #ifdef FAVORED
202  favored_edge_crossings.at_beginning = priorityEdgeCrossings();
203 #endif
204 }
205 
207 {
208  total_crossings.after_preprocessing = numberOfCrossings();
209  max_edge_crossings.after_preprocessing = maxEdgeCrossings();
210  total_stretch.after_preprocessing = totalStretch();
211  bottleneck_stretch.after_preprocessing = maxEdgeStretch();
212 #ifdef FAVORED
213  favored_edge_crossings.after_preprocessing = priorityEdgeCrossings();
214 #endif
215 }
216 
218 {
219  total_crossings.after_heuristic = total_crossings.best;
220  max_edge_crossings.after_heuristic = max_edge_crossings.best;
221  total_stretch.after_heuristic = total_stretch.best;
222  bottleneck_stretch.after_heuristic = bottleneck_stretch.best;
223 #ifdef FAVORED
224  favored_edge_crossings.after_heuristic = priority_edge_crossings.best;
225 #endif
226 }
227 
229 {
230  // the post processing iterations are merely counted since the total number
231  // of crossings improves after each one by definition; not so with
232  // bottleneck crossings or stretch
233  total_crossings.after_post_processing = total_crossings.best;
235  max_edge_crossings.after_post_processing = max_edge_crossings.best;
236  total_stretch.after_post_processing = total_stretch.best;
237  bottleneck_stretch.after_post_processing = bottleneck_stretch.best;
238 #ifdef FAVORED
239  // ditto for favored edge crossings
240  favored_edge_crossings.after_post_processing =
241  favored_edge_crossings.after_heuristic;
242 #endif
243 }
244 
246  int (* crossing_retrieval_function) (void) )
247 {
248 #ifdef DEBUG
249  printf("-> update_best_int, %s, %d\n", stats->name, stats->best);
250 #endif
251  int current_value = crossing_retrieval_function();
252  if( current_value < stats->best )
253  {
254  stats->best = current_value;
256  save_order( order );
257  }
258 #ifdef DEBUG
259  printf("<- update_best_int, %s, %d\n", stats->name, stats->best);
260 #endif
261 }
262 
264  double (* crossing_retrieval_function) (void) )
265 {
266 #ifdef DEBUG
267  printf("-> update_best_double, %s, %f\n", stats->name, stats->best);
268 #endif
269  double current_value = crossing_retrieval_function();
270  if( current_value < stats->best )
271  {
272  stats->best = current_value;
274  save_order( order );
275  }
276 #ifdef DEBUG
277  printf("<- update_best_double, %s, %f\n", stats->name, stats->best);
278 #endif
279 }
280 
281 void update_best_all( void )
282 {
284  update_best_int( & max_edge_crossings,
287  update_best_double( & bottleneck_stretch,
289 #ifdef FAVORED
290  update_best( & favored_edge_crossings, best_favored_crossings_order, priorityEdgeCrossings );
291 #endif
293  pareto_list = pareto_insert( maxEdgeCrossings(),
295  iteration,
296  pareto_list );
297  else if ( pareto_objective == STRETCH_TOTAL )
298  pareto_list = pareto_insert( totalStretch(),
300  iteration,
301  pareto_list );
302  else if ( pareto_objective == BOTTLENECK_STRETCH )
303  pareto_list = pareto_insert( maxEdgeCrossings(),
304  totalStretch(),
305  iteration,
306  pareto_list );
307 }
308 
310 {
311 #ifdef DEBUG
312  printf( "-> has_improved_int, stats = %s, best = %d, previous = %d\n",
313  stats->name, stats->best, stats->previous_best );
314 #endif
315  bool improved = false;
316  if ( stats->best < stats->previous_best ) {
317  improved = true;
318  stats->previous_best = stats->best;
319  }
320 #ifdef DEBUG
321  printf( "<- has_improved, return %d, best = %d, previous = %d, iteration = %d\n",
322  improved, stats->best, stats->previous_best, iteration );
323 #endif
324  return improved;
325 }
326 
328 {
329 #ifdef DEBUG
330  printf( "-> has_improved_double, stats = %s, best = %f, previous = %f\n",
331  stats->name, stats->best, stats->previous_best );
332 #endif
333  bool improved = false;
334  if ( stats->best < stats->previous_best ) {
335  improved = true;
336  stats->previous_best = stats->best;
337  }
338 #ifdef DEBUG
339  printf( "<- has_improved_double, return %d, best = %f, previous = %f, iteration = %d\n",
340  improved, stats->best, stats->previous_best, iteration );
341 #endif
342  return improved;
343 }
344 
345 static int total_layer_degree( int layer )
346 {
347  int total_degree = 0;
348  int position = 0;
349  for( ; position < layers[ layer ]->number_of_nodes; position++ )
350  {
351  Nodeptr node = layers[ layer ]->nodes[ position ];
352  total_degree += DEGREE( node );
353  }
354  return total_degree;
355 }
356 
357 static void add_layer_degrees( int layer, Statistics s )
358 {
359  int position = 0;
360  for( ; position < layers[ layer ]->number_of_nodes; position++ )
361  {
362  Nodeptr node = layers[ layer ]->nodes[ position ];
363  if ( DEGREE( node ) > 0 )
364  add_data( s, DEGREE( node ) );
365  }
366 }
367 
368 static void print_layer_degree_statistics( int layer, FILE * output_stream )
369 {
370  int layer_size = layers[layer]->number_of_nodes;
371  Nodeptr * nodes = layers[ layer ]->nodes;
372  Statistics layer_degree = init_statistics( layer_size );
373  int position = 0;
374  for( ; position < layer_size; position++ )
375  {
376  Nodeptr node = nodes[ position ];
377  if ( DEGREE( node ) > 0 )
378  add_data( layer_degree, DEGREE( node ) );
379  }
380  fprintf( output_stream, "NDegree,%3d,", layer );
381  print_statistics( layer_degree, output_stream, "%7.2lf" );
382  fprintf( output_stream, "\n" );
383  free_statistics( layer_degree );
384 }
385 
386 static void print_channel_degree_statistics( FILE * output_stream )
387 {
388  Statistics channel_degree_discrepancy
390  for ( int layer = 1; layer < number_of_layers; layer++ )
391  {
392  Layerptr upper_layer = layers[layer];
393  Layerptr lower_layer = layers[layer - 1];
394  int upper_layer_size = upper_layer->number_of_nodes;
395  int lower_layer_size = lower_layer->number_of_nodes;
396  Statistics channel_degree
397  = init_statistics( upper_layer_size + lower_layer_size );
398  for ( int i = 0; i < upper_layer_size; i++ )
399  {
400  Nodeptr node = upper_layer->nodes[i];
401  if ( node->down_degree > 0 )
402  add_data( channel_degree, node->down_degree );
403  }
404  for ( int i = 0; i < lower_layer_size; i++ )
405  {
406  Nodeptr node = lower_layer->nodes[i];
407  if ( node->up_degree > 0 )
408  add_data( channel_degree, node->up_degree );
409  }
410  fprintf( output_stream, "CDegree,%3d,", layer );
411  print_statistics( channel_degree, output_stream, "%7.2lf" );
412  fprintf( output_stream, "\n" );
413  add_data( channel_degree_discrepancy,
414  get_max( channel_degree ) / get_median( channel_degree ) );
415  free_statistics( channel_degree );
416  }
417  fprintf( output_stream, "AvgCDegreeDisc," );
418  print_statistics( channel_degree_discrepancy, output_stream, "%7.2f" );
419  fprintf( output_stream, "\n" );
420  free_statistics( channel_degree_discrepancy );
421 }
422 
423 static void print_channel_edge_counts( FILE * output_stream ) {
424  for ( int layer = 1; layer < number_of_layers; layer++ ) {
425  Layerptr upper_layer = layers[layer];
426  int upper_layer_size = upper_layer->number_of_nodes;
427  // count the number of edges into the channel from the upper layer (these
428  // are the same as the edges from the lower layer into the channel)
429  int edges_from_upper_layer = 0;
430  for ( int i = 0; i < upper_layer_size; i++ ) {
431  Nodeptr node = upper_layer->nodes[i];
432  edges_from_upper_layer += node->down_degree;
433  }
434  fprintf( output_stream, "EdgesInChannel\t%d\t%d\n",
435  layer,
436  edges_from_upper_layer );
437  }
438 }
439 
440 static void compute_degree_statistics( void )
441 {
442  for( int layer = 0; layer < number_of_layers; layer++ )
443  {
444  for( int position = 0; position < layers[ layer ]->number_of_nodes; position++ )
445  {
446  Nodeptr node = layers[ layer ]->nodes[ position ];
447  add_data( overall_degree, DEGREE( node ) );
448  }
449  }
450 }
451 
452 static void print_degree_statistics( FILE * output_stream )
453 {
454  Statistics nodes_per_layer = init_statistics( number_of_layers );
455  Statistics layer_degrees = init_statistics( number_of_layers );
456  for ( int i = 0; i < number_of_layers; i++ )
457  {
458  add_layer_degrees( i, overall_degree );
459  add_data( nodes_per_layer, layers[i]->number_of_nodes );
460  add_data( layer_degrees, total_layer_degree( i ) );
461  print_layer_degree_statistics( i, output_stream );
462  }
463  fprintf( output_stream, "LDegree,%3d,", -1 );
464  print_statistics( layer_degrees, output_stream, "%7.2lf" );
465  fprintf( output_stream, "\n" );
466  fprintf( output_stream, "TDegree,%3d,", -1 );
467  print_statistics( overall_degree, output_stream, "%7.2lf" );
468  fprintf( output_stream, "\n" );
469  fprintf( output_stream, "PerLayerNodes,%3d,", -1 );
470  print_statistics( nodes_per_layer, output_stream, "%7.2lf" );
471  fprintf( output_stream, "\n" );
472  free_statistics( layer_degrees );
473  free_statistics( nodes_per_layer );
474 }
475 
476 // The following has not been used or tested
477 
478 /**
479  * @todo minimize maximum crossings on any layer
480  */
481 /* static void print_layer_crossing_statistics( int layer, FILE * output_stream ) */
482 /* { */
483 /* } */
484 
485 void print_graph_statistics( FILE * output_stream )
486 {
487  int effective_number_of_nodes = number_of_nodes - number_of_isolated_nodes;
488  fprintf( output_stream, "GraphName,%s\n", graph_name );
489  fprintf( output_stream, "NumberOfLayers,%d\n", number_of_layers );
490  fprintf( output_stream, "NumberOfNodes,%d\n", number_of_nodes );
491  fprintf( output_stream, "IsolatedNodes,%d\n", number_of_isolated_nodes );
492  fprintf( output_stream, "EffectiveNodes,%d\n", effective_number_of_nodes );
493  fprintf( output_stream, "NumberOfEdges,%d\n", number_of_edges );
494  fprintf( output_stream, "EdgeDensity,%2.2f\n",
495  (double) number_of_edges / effective_number_of_nodes );
496  overall_degree = init_statistics( number_of_nodes );
497  if ( verbose )
498  {
499  print_degree_statistics( output_stream );
500  print_channel_degree_statistics( output_stream );
501  print_channel_edge_counts( output_stream );
502  }
503  else
505  fprintf( output_stream, "MinDegree,%d\n", (int) get_min( overall_degree ) );
506  fprintf( output_stream, "MaxDegree,%d\n", (int) get_max( overall_degree ) );
507  fprintf( output_stream, "MeanDegree,%2.2f\n", get_mean( overall_degree ) );
508  fprintf( output_stream, "MedianDegree,%2.1f\n", get_median( overall_degree ) );
509  free_statistics( overall_degree );
510 }
511 
512 static void print_crossing_stats_int(FILE * output_stream,
513  CROSSING_STATS_INT stats) {
514  fprintf( output_stream, "Start%s,%d\n", stats.name, stats.at_beginning );
515  fprintf( output_stream, "Pre%s,%d\n", stats.name, stats.after_preprocessing );
516  fprintf( output_stream, "Heuristic%s,%d,iteration,%d\n",
517  stats.name, stats.after_heuristic, stats.best_heuristic_iteration );
518  fprintf( output_stream, "Final%s,%d,iteration,%d\n",
520 }
521 
522 static void print_crossing_stats_double(FILE * output_stream,
523  CROSSING_STATS_DOUBLE stats) {
524  fprintf( output_stream, "Start%s,%f\n", stats.name, stats.at_beginning );
525  fprintf( output_stream, "Pre%s,%f\n", stats.name, stats.after_preprocessing );
526  fprintf( output_stream, "Heuristic%s,%f,iteration,%d\n",
527  stats.name, stats.after_heuristic, stats.best_heuristic_iteration );
528  fprintf( output_stream, "Final%s,%f,iteration,%d\n",
530 }
531 
532 void print_run_statistics( FILE * output_stream )
533 {
534  fprintf( output_stream, "Preprocessor,%s\n", preprocessor );
535  fprintf( output_stream, "Heuristic,%s\n", heuristic );
536  fprintf( output_stream, "Iterations,%d\n", iteration );
537  fprintf( output_stream, "Runtime,%2.3f\n", RUNTIME );
538 
539  print_crossing_stats_int( output_stream, total_crossings );
540  print_crossing_stats_int( output_stream, max_edge_crossings );
541  print_crossing_stats_double( output_stream, total_stretch );
542  print_crossing_stats_double( output_stream, bottleneck_stretch );
543 #ifdef FAVORED
544  print_crossing_stats_int( output_stream, favored_edge_crossings );
545 #endif
546  if ( pareto_objective != NO_PARETO ) {
547  fprintf( output_stream, "Pareto,");
548  print_pareto_list( pareto_list, output_stream );
549  fprintf( output_stream, "\n" );
550  }
551 }
552 
553 /* [Last modified: 2016 05 20 at 21:28:41 GMT] */
static int total_layer_degree(int layer)
Definition: stats.c:345
const char * name
Definition: stats.h:39
double get_median(Statistics s)
Definition: Statistics.c:44
void add_data(Statistics s, double data_point)
Definition: Statistics.c:111
double after_preprocessing
Definition: stats.h:32
Statistics init_statistics(int size)
Definition: Statistics.c:26
static void add_layer_degrees(int layer, Statistics s)
Definition: stats.c:357
double get_max(Statistics s)
Definition: Statistics.c:63
static PARETO_LIST pareto_list
Definition: stats.c:36
static void print_pareto_list(PARETO_LIST list, FILE *output_stream)
Definition: stats.c:40
int after_post_processing
Definition: stats.h:22
void capture_preprocessing_stats(void)
Definition: stats.c:206
static void compute_degree_statistics(void)
Definition: stats.c:440
Interface for functions implementing all of the heuristics Those labeled parallel are designed specif...
static void print_channel_edge_counts(FILE *output_stream)
Definition: stats.c:423
Layerptr * layers
Definition: graph_io.c:31
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 void init_specific_crossing_stats_double(CROSSING_STATS_DOUBLE *stats, const char *name)
Definition: stats.c:168
CROSSING_STATS_INT max_edge_crossings
Definition: stats.c:148
double at_beginning
Definition: stats.h:31
Interface for a Statistics class with methods for computing min, median, mean, max, and standard deviation.
const char * name
Definition: stats.h:27
int number_of_isolated_nodes
Definition: graph_io.c:30
Global variables, functions, and parameters specified on the command line.
Definitions common to all edge crossing heuristic source files.
void update_best_all(void)
Definition: stats.c:281
struct pareto_item * PARETO_LIST
int priorityEdgeCrossings(void)
void capture_post_processing_stats(void)
Definition: stats.c:228
static void print_channel_degree_statistics(FILE *output_stream)
Definition: stats.c:386
void print_statistics(Statistics s, FILE *output_stream, const char *format)
Definition: Statistics.c:127
double previous_best
Definition: stats.h:36
enum pareto_objective_enum pareto_objective
Definition: min_crossings.c:51
int after_preprocessing
Definition: stats.h:20
struct pareto_item * rest
Definition: stats.c:33
double maxEdgeStretch()
Definition: channel.c:126
#define RUNTIME
Definition: min_crossings.h:35
static void print_layer_degree_statistics(int layer, FILE *output_stream)
Definition: stats.c:368
Functions for reporting various statistics about the graph and the outcomes.
void capture_heuristic_stats(void)
Definition: stats.c:217
Orderptr best_bottleneck_stretch_order
Definition: min_crossings.c:69
static void print_degree_statistics(FILE *output_stream)
Definition: stats.c:452
int previous_best
Definition: stats.h:24
CROSSING_STATS_INT total_crossings
Definition: stats.c:147
double get_mean(Statistics s)
Definition: Statistics.c:61
int best_heuristic_iteration
Definition: stats.h:37
implementation of utilities that maintain information about channels; eventually these will replace t...
int after_heuristic
Definition: stats.h:21
static void print_crossing_stats_int(FILE *output_stream, CROSSING_STATS_INT stats)
Definition: stats.c:512
double objective_one
Definition: stats.c:30
int up_degree
Definition: graph.h:74
int number_of_nodes
Definition: graph_io.c:27
char * heuristic
Definition: min_crossings.c:39
double totalStretch()
Definition: channel.c:109
void update_best_int(CROSSING_STATS_INT *stats, Orderptr order, int(*crossing_retrieval_function)(void))
Definition: stats.c:245
int post_processing_iteration
Definition: stats.h:26
Definition of functions that keep track of and update the number of crossings for each node...
bool verbose
Definition: min_crossings.c:62
int down_degree
Definition: graph.h:75
CROSSING_STATS_INT favored_edge_crossings
Definition: stats.c:149
int post_processing_iteration
Definition: stats.h:38
double get_min(Statistics s)
Definition: Statistics.c:42
int post_processing_iteration
Definition: heuristics.c:48
bool has_improved_double(CROSSING_STATS_DOUBLE *stats)
Definition: stats.c:327
Definition of data structures and access functions for a layered graph.
static void print_crossing_stats_double(FILE *output_stream, CROSSING_STATS_DOUBLE stats)
Definition: stats.c:522
Statistics overall_degree
Definition: stats.c:152
CROSSING_STATS_DOUBLE total_stretch
Definition: stats.c:150
static char graph_name[MAX_NAME_LENGTH]
Definition: dot.c:42
void capture_beginning_stats(void)
Definition: stats.c:195
void print_graph_statistics(FILE *output_stream)
Definition: stats.c:485
int number_of_edges
Definition: graph_io.c:29
Nodeptr * nodes
Definition: graph.h:116
void print_run_statistics(FILE *output_stream)
Definition: stats.c:532
void save_order(Orderptr ord_info)
Definition: order.c:48
static void init_specific_crossing_stats_int(CROSSING_STATS_INT *stats, const char *name)
Definition: stats.c:154
double objective_two
Definition: stats.c:31
double after_post_processing
Definition: stats.h:34
double after_heuristic
Definition: stats.h:33
int number_of_layers
Definition: graph_io.c:28
int maxEdgeCrossings(void)
Definition: crossings.c:104
bool has_improved_int(CROSSING_STATS_INT *stats)
Definition: stats.c:309
Orderptr best_total_stretch_order
Definition: min_crossings.c:68
char * preprocessor
Definition: min_crossings.c:40
static PARETO_LIST pareto_insert(double objective_one, double objective_two, int iteration, PARETO_LIST list)
Definition: stats.c:75
void init_crossing_stats(void)
Definition: stats.c:182
int numberOfCrossings(void)
Definition: crossings.c:93
void update_best_double(CROSSING_STATS_DOUBLE *stats, Orderptr order, double(*crossing_retrieval_function)(void))
Definition: stats.c:263
Orderptr best_crossings_order
Definition: min_crossings.c:66
int at_beginning
Definition: stats.h:19
static void init_pareto_list(void)
Definition: stats.c:38
int best_heuristic_iteration
Definition: stats.h:25
void free_statistics(Statistics s)
Definition: Statistics.c:142
Header for a simple function to compute CPU user milliseconds.
int iteration
Definition: stats.c:32
Orderptr best_favored_crossings_order
Definition: min_crossings.c:70
Orderptr best_edge_crossings_order
Definition: min_crossings.c:67