Crossings Minimization  1.0
heuristics.h
Go to the documentation of this file.
1 /**
2  * @file heuristics.h
3  * @brief Interface for functions implementing all of the heuristics
4  * Those labeled <strong><em>parallel</em></strong> are designed specifically
5  * for parallel implementation and their iterations are defined by
6  * "synchronization points"
7  *
8  * @author Matthias Stallmann
9  * @date 2008/12/29
10  * $Id: heuristics.h 110 2015-06-12 12:26:27Z mfms $
11  */
12 
13 #ifndef HEURISTICS_H
14 #define HEURISTICS_H
15 
16 #include<stdbool.h>
17 #include"graph.h"
18 #include"order.h"
19 
20 /**
21  * The current iteration, or, the number of iterations up to this point.
22  */
23 extern int iteration;
24 
25 /**
26  * The minimum total number of crossings during post processing
27  */
28 extern int post_processing_crossings;
29 
30 /**
31  * The current iteration during post processing
32  */
33 extern int post_processing_iteration;
34 
35 /**
36  * Creates an ord file name from the graph name, preprocessor and heuristic.
37  * @param output_file_name a buffer for the file name to be created, assumed
38  * to be big enough
39  * @param appendix a string that is attached just before the .ord extension
40  */
41 void createOrdFileName( char * output_file_name, const char * appendix );
42 
43 /**
44  * Creates a dot file name using the graph name and the appendix
45  * @param output_file_name a buffer for the file name to be created, assumed
46  * to be big enough
47  * @param appendix a string that is attached just before the .dot extension
48  */
49 void createDotFileName( char * output_file_name, const char * appendix );
50 
51 /**
52  * Prints information about current number of iterations, crossings, etc.,
53  * @param message a message identifying the context of the printout.
54  * @param layer the layer that was just sorted
55  */
56 void tracePrint( int layer, const char * message );
57 
58 /**
59  * Does things that are appropriate at the end of an iteration, such as
60  * checking whether the ordering needs to be captured and the min
61  * crossings/edge crossings need to be updated. Also increments the
62  * iteration counter
63  *
64  * @return true if max_iterations has been reached
65  */
66 bool end_of_iteration( void );
67 
68 // ******** maintenance of fixed nodes and layers (for many of the
69 // ******** heuristics)
70 
71 bool isFixedNode( Nodeptr node );
72 bool isFixedEdge( Edgeptr edge );
73 bool isFixedLayer( int layer );
74 void fixNode( Nodeptr node );
75 void fixEdge( Edgeptr edge );
76 void fixLayer( int layer );
77 void clearFixedNodes( void );
78 void clearFixedEdges( void );
79 void clearFixedLayers( void );
80 
81 // ******** Miscellaneous
82 
83 /**
84  * @return the total degree of nodes on the given layer
85  */
86 int totalDegree( int layer );
87 
88 /**
89  * @return the layer with maximum total degree
90  */
91 int maxDegreeLayer();
92 
93 // ******** The actual heuristics
94 
95 /**
96  * implements the median heuristic
97  */
98 void median( void );
99 
100 /**
101  * implements the barycenter heuristic
102  */
103 void barycenter( void );
104 
105 void modifiedBarycenter( void );
106 
107 /**
108  * Computes weights on each layer independently and alternates sweep directions
109  * <em>(parallel)</em>
110  */
111 void staticBarycenter( void );
112 
113 /**
114  * Alternates barycenter iterations between even and odd layers, computing
115  * weights for both adjoining layers each time.
116  * <em>(parallel)</em>
117  */
118 void evenOddBarycenter( void );
119 
120 /**
121  * Alternates between odd and even numbered layers, but instead of
122  * alternating at every iteration and using both neighboring layers to assign
123  * weights, this version uses the downward layer (starting with odd layers)
124  * for a number of iterations corresponding to the number of layers, and then
125  * the upward layer for an equal number of iterations.
126  * <em>(parallel)</em>
127  */
128 
129 /**
130  * Alternates between even numbered and odd numbered layers. Unlike alt_bary,
131  * which bases sorting on both neighboring layers simultaneously, this
132  * version rotates between doing upward, downward, and both.
133  * <em>(parallel)</em>
134  */
135 void rotatingBarycenter( void );
136 
137 void upDownBarycenter( void );
138 
139 /**
140  * Each processor does a full-blown barycenter algorithm. Starts are
141  * staggered at distance max(layers/processors,2) and each sweep wraps around
142  * to make the best use of of each processor. Startting layer shifts by 1 at
143  * each iteration.
144  *
145  * @todo rename this as shiftBarycenter, which would be more in keeping with
146  * its behavior.
147  */
148 void slabBarycenter( void );
149 
150 void maximumCrossingsNode( void );
151 
152 /**
153  * mce as described in M. Stallmann, JEA 2012.
154  */
155 void maximumCrossingsEdge( void );
156 
157 /**
158  * A variation of the mce heuristic in which the two endpoints of the edge
159  * with maximum crossings are sifted so as to minimize the total number of
160  * crossings rather than the more complicated objective of mce that is
161  * described in M. Stallmann, JEA 2012.
162  */
164 
165 /**
166  * similar to mce, except that, in each iteration, the edge with maximum
167  * stretch is chosen and the endpoints are moved to positions that minimize
168  * the total stretch of their incident edges
169  *
170  * @todo one could also base the movement on minimizing the maximum stretch
171  * of any edge, similar to mce
172  */
173 void maximumStretchEdge( void );
174 
175 void sifting( void );
176 
177 // preprocessors
178 
179 void breadthFirstSearch( void );
180 
181 void depthFirstSearch( void );
182 
183 void middleDegreeSort( void );
184 
185 // post processing
186 
187 /**
188  * Swaps neighboring nodes when this improves the total number of crossings
189  * until no improvement is possible.
190  * <em>(embarrasingly parallel)</em>
191  */
192 void swapping( void );
193 
194 #endif
195 
196 /* [Last modified: 2016 05 19 at 15:19:35 GMT] */
void maximumCrossingsNode(void)
Definition: heuristics.c:805
static char output_file_name[MAX_NAME_LENGTH]
Definition: min_crossings.c:73
void slabBarycenter(void)
Definition: heuristics.c:649
void clearFixedNodes(void)
Definition: heuristics.c:315
bool isFixedLayer(int layer)
Definition: heuristics.c:296
void fixLayer(int layer)
Definition: heuristics.c:299
void maximumCrossingsEdge(void)
Definition: heuristics.c:875
void clearFixedLayers(void)
Definition: heuristics.c:348
void swapping(void)
Definition: heuristics.c:1195
void breadthFirstSearch(void)
Definition: heuristics.c:1065
void maximumCrossingsEdgeWithSifting(void)
Definition: heuristics.c:828
void fixNode(Nodeptr node)
Definition: heuristics.c:297
int post_processing_crossings
Definition: heuristics.c:51
bool end_of_iteration(void)
Definition: heuristics.c:183
void maximumStretchEdge(void)
Definition: heuristics.c:912
void createOrdFileName(char *output_file_name, const char *appendix)
Definition: heuristics.c:64
int maxDegreeLayer()
Definition: heuristics.c:369
int iteration
Definition: heuristics.c:47
void barycenter(void)
Definition: heuristics.c:428
bool isFixedNode(Nodeptr node)
Definition: heuristics.c:294
void staticBarycenter(void)
Definition: heuristics.c:492
void median(void)
Definition: heuristics.c:413
void upDownBarycenter(void)
Definition: heuristics.c:570
void middleDegreeSort(void)
Definition: heuristics.c:1098
data structure and function headers for saving/restoring order information.
Definition of data structures and access functions for a layered graph.
int totalDegree(int layer)
Definition: heuristics.c:357
void sifting(void)
Definition: heuristics.c:1006
void fixEdge(Edgeptr edge)
Definition: heuristics.c:298
void createDotFileName(char *output_file_name, const char *appendix)
Definition: heuristics.c:83
void tracePrint(int layer, const char *message)
Definition: heuristics.c:122
void clearFixedEdges(void)
Definition: heuristics.c:329
void rotatingBarycenter(void)
Definition: heuristics.c:686
void depthFirstSearch(void)
Definition: heuristics.c:1070
void modifiedBarycenter(void)
Definition: heuristics.c:443
int post_processing_iteration
Definition: heuristics.c:48
void evenOddBarycenter(void)
Definition: heuristics.c:523
bool isFixedEdge(Edgeptr edge)
Definition: heuristics.c:295