Crossings Minimization
1.0

Global variables, functions, and parameters specified on the command line. More...
Go to the source code of this file.
Macros  
#define  RUNTIME (getUserSeconds()  start_time) 
Enumerations  
enum  adjust_weights_enum { NONE, LEFT, AVG } 
enum  sift_option_enum { LAYER, DEGREE, RANDOM } 
enum  sifting_style_enum { DEFAULT, TOTAL, MAX } 
enum  mce_option_enum { NODES, EDGES, EARLY, ONE_NODE } 
enum  pareto_objective_enum { NO_PARETO, BOTTLENECK_TOTAL, STRETCH_TOTAL, BOTTLENECK_STRETCH } 
Variables  
int  max_iterations 
double  start_time 
double  max_runtime 
int  number_of_processors 
bool  standard_termination 
bool  favored_edges 
bool  balanced_weight 
char *  heuristic 
char *  preprocessor 
Orderptr  best_crossings_order 
Orderptr  best_edge_crossings_order 
Orderptr  best_total_stretch_order 
Orderptr  best_bottleneck_stretch_order 
Orderptr  best_favored_crossings_order 
bool  randomize_order 
enum adjust_weights_enum  adjust_weights 
enum sift_option_enum  sift_option 
enum sifting_style_enum  sifting_style 
enum mce_option_enum  mce_option 
enum pareto_objective_enum  pareto_objective 
int  capture_iteration 
bool  produce_output 
char *  output_base_name 
bool  verbose 
int  trace_freq 
Global variables, functions, and parameters specified on the command line.
Definition in file min_crossings.h.
#define RUNTIME (getUserSeconds()  start_time) 
Time that the program has been running since the start of preprocessing.
Definition at line 35 of file min_crossings.h.
Referenced by end_of_iteration(), main(), print_last_iteration_message(), print_run_statistics(), and trace_printer().
enum adjust_weights_enum 
For barycenter heuristic: how to deal with nodes that have no edges in the direction on which weights are based: see adjust_weights_left() and adjust_weights_avg() in barycenter.c. LEFT is the default (the nodes follow their left neighbor; this keeps the nodes together and makes the heuristic more stable).
Enumerator  

NONE  
LEFT  
AVG 
Definition at line 112 of file min_crossings.h.
enum mce_option_enum 
During a pass of maximum crossings edge, each iteration fixes both an edge and the two endpoints of the edge. A pass can end in one of three ways:
Enumerator  

NODES  
EDGES  
EARLY  
ONE_NODE 
Definition at line 149 of file min_crossings.h.
For Pareto optimization we can choose a variety of different objectives; for now we consider two at a time. This option currently affects only what gets updated and reported, not the behavior of any heuristic. NO_PARETO = no Pareto optimization, i.e., don't report Pareto points BOTTLENECK_TOTAL = maxEdgeCrossings(),numberOfCrossings() STRETCH_TOTAL = totalStretch(),numberOfCrossings() BOTTLENECK_STRETCH = maxEdgeCrossings(),totalStretch()
Enumerator  

NO_PARETO  
BOTTLENECK_TOTAL  
STRETCH_TOTAL  
BOTTLENECK_STRETCH 
Definition at line 160 of file min_crossings.h.
enum sift_option_enum 
Based on Matuszewski et al. "Extending sifting for klayer straightline crossing minimaization": The order in which nodes are sifted can be (1) based on a layerbylayer sweep; (2) based on their degree (largest degree first); or (3) random. Number (2), DEGREE, is the default and the only option currently implemented.
Enumerator  

LAYER  
DEGREE  
RANDOM 
Definition at line 121 of file min_crossings.h.
enum sifting_style_enum 
When a node is sifted during sifting, mcn, or mce, one can either base its position on the minimum number of total crossings or, as in the original mce design, on (local) maximum number of crossings for an edge. These two options are denoted by TOTAL and MAX, respectively. DEFAULT means use TOTAL for sifting and mcn, MAX for mce.
Enumerator  

DEFAULT  
TOTAL  
MAX 
Definition at line 135 of file min_crossings.h.
enum adjust_weights_enum adjust_weights 
bool balanced_weight 
True if taking average of averages when calculating barycenter or median weights wrt both neighboring layers. False if dividing total position by total degree.
Definition at line 58 of file min_crossings.c.
Referenced by barycenterWeights(), main(), and runHeuristic().
Orderptr best_bottleneck_stretch_order 
structure to save layer orderings for minimum bottleneck edge stretch so far
Definition at line 69 of file min_crossings.c.
Referenced by update_best_all().
Orderptr best_crossings_order 
structure to save layer orderings for minimum crossings so far
Definition at line 66 of file min_crossings.c.
Referenced by swapping(), and update_best_all().
Orderptr best_edge_crossings_order 
structure to save layer orderings for minimum edge crossings so far
Definition at line 67 of file min_crossings.c.
Referenced by update_best_all().
Orderptr best_favored_crossings_order 
structure to save layer orderings for minimum crossings involving favored edges so far
Definition at line 70 of file min_crossings.c.
Referenced by update_best_all().
Orderptr best_total_stretch_order 
structure to save layer orderings for minimum total edge stretch so far
Definition at line 68 of file min_crossings.c.
Referenced by update_best_all().
int capture_iteration 
Save the order at the end of the given iteration in a file called capturex.ord, where x is the iteration number. If the value is negative, no capture takes place.
Definition at line 52 of file min_crossings.c.
Referenced by end_of_iteration(), main(), and printCrossings().
bool favored_edges 
True if there is a list of favored edges based on predecessors and successors of a central node
Definition at line 53 of file min_crossings.c.
Referenced by main().
char* heuristic 
Definition at line 39 of file min_crossings.c.
Referenced by createOrdFileName(), edge_sift_iteration(), main(), print_run_statistics(), runHeuristic(), sift_iteration(), and total_stretch_sift_iteration().
int max_iterations 
Maximum number of iterations for the main heuristic; this is the number of times a layer is sorted. If neither max_iterations nor max_runtime is specified, standard_termination is used.
Definition at line 41 of file min_crossings.c.
Referenced by end_of_iteration(), main(), print_last_iteration_message(), printCrossings(), sift_decreasing(), sift_increasing(), sifting(), and terminate().
double max_runtime 
Runtime (in seconds) at which the main heuristic will be terminated; the termination takes place at this runtime or at max_iterations, whichever comes first. If neither max_iterations nor max_runtime is specified, standard_termination is used.
Definition at line 43 of file min_crossings.c.
Referenced by end_of_iteration(), and main().
enum mce_option_enum mce_option 
int number_of_processors 
When simulating a heuristic that can be parallelized, there may be a tradeoff between number of processors and solution quality. Fewer processors may lead to fewer crossings because the number of crossings can be checked more often. For example, if there is only one processor, you can check every time a change occurs. If there are more, you have to wait until the next synchronization point.
Definition at line 45 of file min_crossings.c.
Referenced by adjust_weights_avg(), evenOddBarycenter(), main(), rotatingBarycenter(), runHeuristic(), slab_bary_iteration(), slabBarycenter(), staticBarycenter(), and upDownBarycenter().
char* output_base_name 
output file names are of the form output_base_namex.ord, where x is information about the heuristic used
Definition at line 60 of file min_crossings.c.
Referenced by createOrdFileName(), and main().
enum pareto_objective_enum pareto_objective 
char* preprocessor 
Definition at line 40 of file min_crossings.c.
Referenced by createOrdFileName(), main(), print_run_statistics(), and runPreprocessor().
bool produce_output 
True if ord files representing the minimum number of crossings should be written
Definition at line 59 of file min_crossings.c.
Referenced by main().
bool randomize_order 
True if the edge list (node list) is to be randomized after each pass of mce (sifting)
Definition at line 54 of file min_crossings.c.
Referenced by main(), maxCrossingsEdge(), maxCrossingsLayer(), maxCrossingsNode(), maxStretchEdge(), and sifting().
enum sift_option_enum sift_option 
enum sifting_style_enum sifting_style 
bool standard_termination 
True if using the standard, "natural" stopping criterion for the iterative heuristic, e.g., no improvement after a sweep for barycenter.
Definition at line 46 of file min_crossings.c.
Referenced by main(), sifting(), and terminate().
double start_time 
Time that the preprocessor (or heuristic if none) started running
Definition at line 44 of file min_crossings.c.
Referenced by main().
int trace_freq 
1 means no tracing, 0 means end of iteration only, trace_freq > 0 means print a trace message every trace_freq iterations.
Definition at line 63 of file min_crossings.c.
Referenced by main(), and tracePrint().
bool verbose 
True if verbose information about the graph should be printed
Definition at line 62 of file min_crossings.c.
Referenced by main(), and print_graph_statistics().