Crossings Minimization  1.0
crossings.h
Go to the documentation of this file.
1 /**
2  * @file crossings.h
3  * @brief Definition of functions that keep track of and update the number of
4  * crossings for each node, each layer, and for the whole graph.
5  * @author Matt Stallmann
6  * @date 2008/12/23
7  * $Id: crossings.h 2 2011-06-07 19:50:41Z mfms $
8  */
9 
10 #include<stdbool.h>
11 
12 #ifndef CROSSINGS_H
13 #define CROSSINGS_H
14 
15 #include"defs.h"
16 #include"graph.h"
17 
18 /**
19  * Initializes all crossing counts and allocates data structures used for
20  * counting crossings.
21  */
22 void initCrossings( void );
23 
24 /**
25  * @return the total number of crossings in the graph
26  */
27 int numberOfCrossings( void );
28 
29 /**
30  * @return the maximum number of crossings for any edge
31  */
32 int maxEdgeCrossings( void );
33 
34 /**
35  * @return the number of crossings for the given layer
36  */
37 int numberOfCrossingsLayer( int layer );
38 
39 /**
40  * @return the number of crossings for the given node
41  */
42 int numberOfCrossingsNode( Nodeptr node );
43 
44 /**
45  * Updates all crossings based on current ordering of nodes on each layer.
46  * The position pointers for all nodes are made consistent as well, using
47  * updateAllPositions() in the sorting module
48  */
49 void updateAllCrossings( void );
50 
51 /**
52  * Updates crossings after the given layer has been permuted. The position
53  * pointers for all nodes on the layer are made consistent as well, using
54  * updateNodePositions() in the sorting module
55  */
56 void updateCrossingsForLayer( int layer );
57 
58 /**
59  * Updates crossings between two adjacent layers. Also updates the relevant
60  * crossing fields and position fields of nodes for the two layers.
61  * @param upper_layer the higher of the two layers; crossings between layers
62  * upper_layer - 1 and upper_layer are counted
63  */
64 void updateCrossingsBetweenLayers( int upper_layer );
65 
66 /**
67  * @return The number of an unfixed layer whose incident edges have the
68  * largest number of total crossings, or -1 if all layers are fixed.
69  */
70 int maxCrossingsLayer( void );
71 
72 /**
73  * @return A pointer to an unfixed node whose incident edges have the most
74  * crossings, or NULL if all nodes are fixed. The layer and position of the
75  * node are stored with it. When there are ties, bias is in favor of a node
76  * not on the same layer as the most recent node chosen; this is to avoid a
77  * lot of repeated sifting on the same layer.
78  */
80 
81 /**
82  * @return A pointer to an unfixed edge with the most crossings, or NULL if
83  * all edges are fixed.
84  */
86 
87 /**
88  * @return A pointer to an edge with the most crossings; ignores the current
89  * status of the edge (fixed or not) and has no impact on the state of any
90  * heuristic.
91  */
93 
94 /**
95  * Prints information about the crossings, mostly for debugging
96  */
97 void printCrossings( void );
98 
99 #endif
100 
101 /* [Last modified: 2016 05 19 at 20:23:37 GMT] */
int numberOfCrossings(void)
Definition: crossings.c:93
void updateCrossingsBetweenLayers(int upper_layer)
Definition: crossings.c:199
Definitions common to all edge crossing heuristic source files.
Nodeptr maxCrossingsNode(void)
Definition: crossings.c:242
void updateCrossingsForLayer(int layer)
Definition: crossings.c:147
int numberOfCrossingsLayer(int layer)
Definition: crossings.c:112
int numberOfCrossingsNode(Nodeptr node)
Definition: crossings.c:125
Definition of data structures and access functions for a layered graph.
Edgeptr maxCrossingsEdgeStatic(void)
Definition: crossings.c:287
void printCrossings(void)
Definition: crossings.c:367
int maxEdgeCrossings(void)
Definition: crossings.c:104
void initCrossings(void)
Definition: crossings.c:80
int maxCrossingsLayer(void)
Definition: crossings.c:220
Edgeptr maxCrossingsEdge(void)
Definition: crossings.c:262
void updateAllCrossings(void)
Definition: crossings.c:138