Crossings Minimization  1.0
min_crossings.h
Go to the documentation of this file.
1 /**
2  * @file min_crossings.h
3  * @brief Global variables, functions, and parameters specified on the
4  * command line
5  * @author Matthias Stallmann
6  * @date 2008/12/29
7  * $Id: min_crossings.h 82 2014-07-30 16:20:32Z mfms $
8  */
9 
10 #ifndef MIN_CROSSINGS_H
11 #define MIN_CROSSINGS_H
12 
13 #include<stdbool.h>
14 
15 #include"defs.h"
16 #include"order.h"
17 
18 // parameters based on command-line options
19 
20 /**
21  * Maximum number of iterations for the main heuristic; this is the number of
22  * times a layer is sorted. If neither max_iterations nor max_runtime is
23  * specified, standard_termination is used.
24  */
25 extern int max_iterations;
26 
27 /**
28  * Time that the preprocessor (or heuristic if none) started running
29  */
30 extern double start_time;
31 
32 /**
33  * Time that the program has been running since the start of preprocessing.
34  */
35 #define RUNTIME (getUserSeconds() - start_time)
36 
37 /**
38  * Runtime (in seconds) at which the main heuristic will be terminated; the
39  * termination takes place at this runtime or at max_iterations, whichever
40  * comes first. If neither max_iterations nor max_runtime is specified,
41  * standard_termination is used.
42  */
43 extern double max_runtime;
44 
45 /**
46  * When simulating a heuristic that can be parallelized, there may be a
47  * tradeoff between number of processors and solution quality. Fewer
48  * processors may lead to fewer crossings because the number of crossings can
49  * be checked more often. For example, if there is only one processor, you
50  * can check every time a change occurs. If there are more, you have to wait
51  * until the next synchronization point.
52  */
53 extern int number_of_processors;
54 
55 /**
56  * True if using the standard, "natural" stopping criterion for the iterative
57  * heuristic, e.g., no improvement after a sweep for barycenter.
58  */
59 extern bool standard_termination;
60 
61 /**
62  * True if there is a list of favored edges based on predecessors and
63  * successors of a central node
64  */
65 extern bool favored_edges;
66 
67 /**
68  * True if taking average of averages when calculating barycenter or median
69  * weights wrt both neighboring layers. False if dividing total position by
70  * total degree.
71  */
72 extern bool balanced_weight;
73 
74 extern char * heuristic;
75 extern char * preprocessor;
76 
77 /**
78  * structure to save layer orderings for minimum crossings so far
79  */
81 /**
82  * structure to save layer orderings for minimum edge crossings so far
83  */
85 /**
86  * structure to save layer orderings for minimum total edge stretch so far
87  */
89 /**
90  * structure to save layer orderings for minimum bottleneck edge stretch so far
91  */
93 /**
94  * structure to save layer orderings for minimum crossings involving favored
95  * edges so far
96  */
98 
99 /**
100  * True if the edge list (node list) is to be randomized after each pass of
101  * mce (sifting)
102  */
103 extern bool randomize_order;
104 
105 /**
106  * For barycenter heuristic: how to deal with nodes that have no
107  * edges in the direction on which weights are based: see
108  * adjust_weights_left() and adjust_weights_avg() in barycenter.c. LEFT is
109  * the default (the nodes follow their left neighbor; this keeps the nodes
110  * together and makes the heuristic more stable).
111  */
113 
114 /**
115  * Based on Matuszewski et al. "Extending sifting for k-layer straightline
116  * crossing minimaization": The order in which nodes are sifted can be (1)
117  * based on a layer-by-layer sweep; (2) based on their degree (largest degree
118  * first); or (3) random. Number (2), DEGREE, is the default and the only
119  * option currently implemented.
120  */
122 
123 /**
124  * When a node is sifted during sifting, mcn, or mce, one can either base its
125  * position on the minimum number of total crossings or, as in the original
126  * mce design, on (local) maximum number of crossings for an edge. These two
127  * options are denoted by TOTAL and MAX, respectively. DEFAULT means use
128  * TOTAL for sifting and mcn, MAX for mce.
129  *
130  * @todo The introduction of mce_s as a separate heuristic makes this enum
131  * superfluous for now, but maybe it should be revived for the sake of
132  * symmetry and completeness -- so that the sifting heuristic can be used
133  * with bottleneck minimization
134  */
136 
137 /**
138  * During a pass of maximum crossings edge, each iteration fixes both an edge
139  * and the two endpoints of the edge. A pass can end in one of three ways:
140  * - all nodes are fixed (NODES); each node is sifted only once
141  * - all edges are fixed (EDGES); both endpoints of an edge are sifted at
142  * each iteration (fixing of nodes is irrelevant)
143  * - as soon as both endpoints of the current edge are fixed (EARLY)
144  * NODES appears to work best.
145  * The new option, ONE_NODE, sifts only one endpoint of the max crossings
146  * edge, the one with the most node crossings; does not appear to work very
147  * well.
148  */
150 
151 /**
152  * For Pareto optimization we can choose a variety of different objectives;
153  * for now we consider two at a time. This option currently affects only what
154  * gets updated and reported, not the behavior of any heuristic.
155  * NO_PARETO = no Pareto optimization, i.e., don't report Pareto points
156  * BOTTLENECK_TOTAL = maxEdgeCrossings(),numberOfCrossings()
157  * STRETCH_TOTAL = totalStretch(),numberOfCrossings()
158  * BOTTLENECK_STRETCH = maxEdgeCrossings(),totalStretch()
159  */
162 
163 /**
164  * Save the order at the end of the given iteration in a file called
165  * capture-x.ord, where x is the iteration number. If the value is negative,
166  * no capture takes place.
167  */
168 extern int capture_iteration;
169 
170 /**
171  * True if ord files representing the minimum number of crossings should be
172  * written
173  */
174 extern bool produce_output;
175 
176 /**
177  * output file names are of the form output_base_name-x.ord, where x is
178  * information about the heuristic used
179  */
180 extern char * output_base_name;
181 
182 /**
183  * True if verbose information about the graph should be printed
184  */
185 extern bool verbose;
186 
187 /**
188  * -1 means no tracing, 0 means end of iteration only, trace_freq > 0 means
189  * print a trace message every trace_freq iterations.
190  */
191 extern int trace_freq;
192 
193 #endif
194 
195 /* [Last modified: 2016 05 18 at 20:18:47 GMT] */
int capture_iteration
Definition: min_crossings.c:52
enum sifting_style_enum sifting_style
bool balanced_weight
Definition: min_crossings.c:58
int number_of_processors
Definition: min_crossings.c:45
double max_runtime
Definition: min_crossings.c:43
char * preprocessor
Definition: min_crossings.c:40
enum sift_option_enum sift_option
bool randomize_order
Definition: min_crossings.c:54
char * output_base_name
Definition: min_crossings.c:60
bool standard_termination
Definition: min_crossings.c:46
Orderptr best_edge_crossings_order
Definition: min_crossings.c:67
sifting_style_enum
Definitions common to all edge crossing heuristic source files.
sift_option_enum
mce_option_enum
pareto_objective_enum
Orderptr best_total_stretch_order
Definition: min_crossings.c:68
adjust_weights_enum
Orderptr best_crossings_order
Definition: min_crossings.c:66
int trace_freq
Definition: min_crossings.c:63
Orderptr best_favored_crossings_order
Definition: min_crossings.c:70
Orderptr best_bottleneck_stretch_order
Definition: min_crossings.c:69
bool produce_output
Definition: min_crossings.c:59
data structure and function headers for saving/restoring order information.
char * heuristic
Definition: min_crossings.c:39
enum pareto_objective_enum pareto_objective
bool verbose
Definition: min_crossings.c:62
enum mce_option_enum mce_option
bool favored_edges
Definition: min_crossings.c:53
int max_iterations
Definition: min_crossings.c:41
enum adjust_weights_enum adjust_weights
double start_time
Definition: min_crossings.c:44