Crossings Minimization  1.0
min_crossings.h File Reference

Global variables, functions, and parameters specified on the command line. More...

#include <stdbool.h>
#include "defs.h"
#include "order.h"
Include dependency graph for min_crossings.h:
This graph shows which files directly or indirectly include this file:

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
 

Detailed Description

Global variables, functions, and parameters specified on the command line.

Author
Matthias Stallmann
Date
2008/12/29
Id
min_crossings.h 82 2014-07-30 16:20:32Z mfms

Definition in file min_crossings.h.

Macro Definition Documentation

◆ RUNTIME

#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().

Enumeration Type Documentation

◆ 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.

◆ 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:

  • all nodes are fixed (NODES); each node is sifted only once
  • all edges are fixed (EDGES); both endpoints of an edge are sifted at each iteration (fixing of nodes is irrelevant)
  • as soon as both endpoints of the current edge are fixed (EARLY) NODES appears to work best. The new option, ONE_NODE, sifts only one endpoint of the max crossings edge, the one with the most node crossings; does not appear to work very well.
Enumerator
NODES 
EDGES 
EARLY 
ONE_NODE 

Definition at line 149 of file min_crossings.h.

◆ pareto_objective_enum

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.

◆ sift_option_enum

Based on Matuszewski et al. "Extending sifting for k-layer straightline crossing minimaization": The order in which nodes are sifted can be (1) based on a layer-by-layer 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.

◆ 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.

Todo:
The introduction of mce_s as a separate heuristic makes this enum superfluous for now, but maybe it should be revived for the sake of symmetry and completeness – so that the sifting heuristic can be used with bottleneck minimization
Enumerator
DEFAULT 
TOTAL 
MAX 

Definition at line 135 of file min_crossings.h.

Variable Documentation

◆ adjust_weights

enum adjust_weights_enum adjust_weights

◆ balanced_weight

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.

Todo:
not clear which value of this option works best; stay tuned ...

Definition at line 58 of file min_crossings.c.

Referenced by barycenterWeights(), main(), and runHeuristic().

◆ best_bottleneck_stretch_order

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().

◆ best_crossings_order

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().

◆ best_edge_crossings_order

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().

◆ best_favored_crossings_order

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().

◆ best_total_stretch_order

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().

◆ capture_iteration

int capture_iteration

Save the order at the end of the given iteration in a file called capture-x.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().

◆ favored_edges

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().

◆ heuristic

◆ max_iterations

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().

◆ max_runtime

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().

◆ mce_option

enum mce_option_enum mce_option

◆ number_of_processors

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().

◆ output_base_name

char* output_base_name

output file names are of the form output_base_name-x.ord, where x is information about the heuristic used

Definition at line 60 of file min_crossings.c.

Referenced by createOrdFileName(), and main().

◆ pareto_objective

enum pareto_objective_enum pareto_objective

◆ preprocessor

char* preprocessor

Definition at line 40 of file min_crossings.c.

Referenced by createOrdFileName(), main(), print_run_statistics(), and runPreprocessor().

◆ produce_output

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().

◆ randomize_order

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().

◆ sift_option

enum sift_option_enum sift_option

◆ sifting_style

enum sifting_style_enum sifting_style

◆ standard_termination

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().

◆ start_time

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().

◆ trace_freq

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().

◆ verbose

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().