Crossings Minimization  1.0
graph.h
Go to the documentation of this file.
1 /**
2  * @file graph.h
3  * @brief Definition of data structures and access functions for a layered
4  * graph.
5  * @author Matt Stallmann, based on Saurabh Gupta's crossing heuristics
6  * implementation.
7  * @date 2008/12/19
8  * $Id: graph.h 90 2014-08-13 20:31:25Z mfms $
9  *
10  * Global data
11  * - number_of_layers
12  * - layers: an array of pointers to layer_struct's
13  * - graph_name: used for output
14  * Layers are referred to by number except when internal info is needed.<br>
15  * Nodes are referred to by pointers to node_struct's and all information
16  * about a node (including layer and position) is stored in the struct.
17  *
18  * To traverse all the nodes of a graph, do the following; see also master_node_list:
19  *
20  for( int layer = 0; layer < number_of_layers; layer++ )
21  {
22  for( int position = 0; position < layers[ layer ]->number_of_nodes; position++ )
23  {
24  Nodeptr node = layers[ layer ]->nodes[ position ];
25  // do something with the node
26  }
27  }
28  *
29  * To traverse all the edges of the graph (as down edges of layers 1 through
30  * number_of_layers - 1), do -- this is O(m); see also master_edge_list:
31 
32  for( int layer = 1; layer < number_of_layers; layer++ )
33  {
34  for(
35  int node_position = 0;
36  node_position < layers[ layer ]->number_of_nodes;
37  node_position++ )
38  {
39  Nodeptr node = layers[ layer ]->nodes[ node_position ];
40  for( int edge_position = 0; edge_position < node->down_degree; edge_position++ )
41  {
42  Edgeptr edge = node->down_edges[ edge_position ];
43  // do something with the edge
44  }
45  }
46  }
47 
48  */
49 
50 #include<stdbool.h>
51 
52 #ifndef GRAPH_H
53 #define GRAPH_H
54 
55 #include"defs.h"
56 
57 typedef struct node_struct * Nodeptr;
58 typedef struct edge_struct * Edgeptr;
59 typedef struct layer_struct * Layerptr;
60 
62 {
63  char * name;
64  int id; /* unique identifier */
65  int layer;
66  /**
67  * position of the node within its layer; this is essential for correct
68  * computation of crossings; it is automatically updated by the update
69  * functions for crossings in the crossings module and should be updated
70  * locally by any heuristic that relies on dynamic information about
71  * crossings.
72  */
73  int position;
74  int up_degree;
76 
77  Edgeptr * up_edges;
78  Edgeptr * down_edges;
79 
80  // for heuristics based on sorting (in most cases this will be an int, but
81  // barycenter involves fractions
82  double weight;
83 
84  // Added on 09-11-08 for max. crossings node heuristic
85  bool fixed;
88 
89  // for DFS
90  bool marked;
92 };
93 
94 #define DEGREE( node ) ( node->up_degree + node->down_degree )
95 #define CROSSINGS( node ) ( node->up_crossings + node->down_crossings )
96 
97 struct edge_struct {
98  Nodeptr up_node;
99  Nodeptr down_node;
101 
102  // for heuristics
103  /**
104  * true if edge has been processed in current iteration
105  */
106  bool fixed;
107  /**
108  * true if minimizing crossings for this edge should be given priority (not
109  * used - instead, a list of priority edges is maintained)
110  */
111  // bool prioritize;
112 };
113 
114 struct layer_struct {
116  Nodeptr * nodes;
117 
118  // for algorithms that fix layers during an iteration
119  bool fixed;
120 };
121 
122 // The following are defined in graph_io.c
123 
124 /**
125  * Allows nodes to be accessed randomly by their unique id #'s; not used for
126  * anything at this point.
127  *
128  * @todo this and master_edge_list could really be useful for heuristics such
129  * as mcn and mce.
130  */
131 extern Nodeptr * master_node_list;
132 
133 /**
134  * @see master_node_list
135  */
136 extern Edgeptr * master_edge_list;
137 
138 extern int number_of_layers;
139 extern int number_of_nodes;
140 extern int number_of_edges;
141 extern int number_of_isolated_nodes;
142 extern Layerptr * layers;
143 extern char graph_name[MAX_NAME_LENGTH];
144 
145 #endif
146 
147 /* [Last modified: 2016 02 15 at 16:44:04 GMT] */
Nodeptr * master_node_list
Definition: graph_io.c:25
bool fixed
Definition: graph.h:119
Nodeptr up_node
Definition: graph.h:98
int down_crossings
Definition: graph.h:87
int preorder_number
Definition: graph.h:91
int id
Definition: graph.h:64
char * name
Definition: graph.h:63
Layerptr * layers
Definition: graph_io.c:31
int number_of_nodes
Definition: graph.h:115
struct layer_struct * Layerptr
Definition: graph.h:59
Edgeptr * down_edges
Definition: graph.h:78
bool marked
Definition: graph.h:90
int number_of_isolated_nodes
Definition: graph_io.c:30
Definitions common to all edge crossing heuristic source files.
int position
Definition: graph.h:73
struct node_struct * Nodeptr
Definition: graph.h:57
struct edge_struct * Edgeptr
Definition: graph.h:58
Edgeptr * up_edges
Definition: graph.h:77
int up_degree
Definition: graph.h:74
bool fixed
Definition: graph.h:85
int number_of_nodes
Definition: graph_io.c:27
char graph_name[MAX_NAME_LENGTH]
Definition: graph_io.c:32
double weight
Definition: graph.h:82
int layer
Definition: graph.h:65
int down_degree
Definition: graph.h:75
int up_crossings
Definition: graph.h:86
int crossings
Definition: graph.h:100
bool fixed
Definition: graph.h:106
int number_of_edges
Definition: graph_io.c:29
Nodeptr * nodes
Definition: graph.h:116
Nodeptr down_node
Definition: graph.h:99
int number_of_layers
Definition: graph_io.c:28
#define MAX_NAME_LENGTH
Definition: defs.h:32
Edgeptr * master_edge_list
Definition: graph_io.c:26