Crossings Minimization  1.0
channel.h
Go to the documentation of this file.
1 /**
2  * @file channel.h
3  * @brief header for utilities that maintain information about channels
4  *
5  * @todo eventually channels should replace the interlayer structures in
6  * crossings.c since can they serve more general purposes; note that the
7  * current discipline in crossings.[ch] is that, when an iteration sorts a
8  * layer, the crossings for the adjoining channels are updated, including the
9  * max crossings node and edge; here, we do this with stretch and leave the
10  * crossings updates alone for now.
11  */
12 
13 #include "graph.h"
14 
15 /**
16  * Information about edges in the channel between two layers. Channels are
17  * numbered starting at 1 (for the channel between layers 0 and 1).
18  */
19 typedef struct channel_struct {
21  /**
22  * Positions on the lower layer of endpoints of the edges; these are sorted
23  * lexicographically by the positions of the upper endpoints. Crossings can
24  * be determined by counting inversions in a sort by positions of lower endpoints.
25  */
27 } * Channelptr;
28 
29 /**
30  * initializes data structures relevant to channels
31  */
32 void initChannels(void);
33 
34 /**
35  * channels[i] is information about edges between
36  * layers i - 1 and i; the entry for i = 0 is not used
37  */
38 extern Channelptr * channels;
39 
40 /**
41  * @return the total strech of edges in channel i; assumes the positions of
42  * nodes on the two layers have been updated correctly
43  */
44 double totalChannelStretch(int i);
45 
46 /**
47  * @return the total stretch of edges incident on layer i
48  */
49 double totalLayerStretch(int i);
50 
51 /**
52  * @return the maximum stretch of any edge in channel i; assumes positions of
53  * nodes in the two layers have been updated correctly
54  */
55 double maxEdgeStretchInChannel(int i);
56 
57 /**
58  * @return the total stretch of all edges
59  */
60 double totalStretch();
61 
62 /**
63  * @return the maximu stretch of any edge overall
64  */
65 double maxEdgeStretch();
66 
67 /**
68  * @return the edge with maximum stretch among edges that have not been fixed
69  */
71 
72 /* [Last modified: 2016 05 20 at 18:39:03 GMT] */
double totalLayerStretch(int i)
Definition: channel.c:80
double maxEdgeStretchInChannel(int i)
Definition: channel.c:95
int number_of_edges
Definition: channel.h:20
Channelptr * channels
Definition: channel.c:17
struct channel_struct * Channelptr
double totalChannelStretch(int i)
Definition: channel.c:69
double maxEdgeStretch()
Definition: channel.c:126
Edgeptr * edges
Definition: channel.h:26
Definition of data structures and access functions for a layered graph.
Edgeptr maxStretchEdge()
Definition: channel.c:146
void initChannels(void)
Definition: channel.c:57
double totalStretch()
Definition: channel.c:109