Crossings Minimization  1.0
graph_io.c
Go to the documentation of this file.
1 /**
2  * @file graph_io.c
3  * @brief Implementation of functions that create graph structures from input
4  * .dot and .ord files.
5  * @author Matt Stallmann, based on Saurabh Gupta's crossing heuristics
6  * implementation.
7  * @date 2008/12/19
8  * \$Id: graph_io.c 97 2014-09-10 17:05:19Z mfms \$
9  */
10
11 #include"graph.h"
12 #include"hash.h"
13 #include"defs.h"
14 #include"dot.h"
15 #include"ord.h"
16 #include"min_crossings.h"
17
18 #include<stdio.h>
19 #include<stdlib.h>
20 #include<string.h>
21 #include<assert.h>
22
23 #define MIN_LAYER_CAPACITY 1
24
31 Layerptr * layers = NULL;
33
34 // initial allocated size of layer array (will double as needed)
36
37 // The input algorithm is as follows:
38 // 1. Read the ord file (first pass) and
39 // (a) create each layer and expand the 'layers' array as needed
40 // (b) count the number of nodes on each layer and store in
41 // 'number_of_nodes'; also count the global number of nodes
42 // (c) allocate the 'nodes' array for each layer
43 // 2. Read the ord file again and
44 // (a) create each node
45 // (b) add each node to the appropriate layer
46 // 3. Read the dot file (first pass) and
47 // (a) count the 'up_degree' and 'down_degree' of each node
48 // (b) go through all the nodes and allocate the 'up_edges' and
49 // the 'down_edges'
50 // (c) reset 'up_degree' and 'down_degree' to 0 so that edges can
51 // be put in the right positions on the second pass
52 // 4. Read the dot file again and put the nodes into the adjacency lists
53 // based on the edges
54 //
55 // Note: The last phase ignores directions of the edges in the dot file and
56 // only looks at layer information to determine 'up' and 'down' edges for
57 // each node. For example, if a->b in the dot file and a is on layer 1 while
58 // b is on layer 0, then the edge is an up-edge for b and a down-edge for a.
59
60 /**
61  * Creates a new node and maps its name to (a pointer to) its record
62  * @param name the name of the node
63  * @return (a pointer to) the newly created node
64  */
65 Nodeptr makeNode( const char * name );
66
67 /**
68  * Put a node in the next available position on a given layer
69  */
70 void addNodeToLayer( Nodeptr node, int layer );
71
72 /**
73  * Creates a new layer; the number is assumed to be the next available layer
74  * number, i.e., layers are always created in ascending numerical order
75  */
76 void makeLayer();
77
78 /**
79  * Adds an edge to the graph. The edge comes directly from the dot
80  * file. Although instances usually direct edges from lower to higher layers,
81  * no such assumption is made here. A fatal error occurs if the nodes are
82  * not on adjacent layers.
83  */
84 void addEdge( const char * name1, const char * name2 );
85
86 Nodeptr makeNode( const char * name )
87 {
88  static int current_id = 0;
89
90  Nodeptr new_node = (Nodeptr) malloc( sizeof(struct node_struct));
91  new_node->name = (char *) malloc( strlen(name) + 1 );
92  strcpy( new_node->name, name );
93  // delay assignment of id's until edges are added so that the numbering
94  // depends on .dot file only (easier to standardize)
95  new_node->id = current_id++;
96  new_node->layer = new_node->position = -1; /* to indicate "uninitialized" */
97  new_node->up_degree = new_node->down_degree = 0;
98  new_node->up_edges = new_node->down_edges = NULL;
99  new_node->up_crossings = new_node->down_crossings = 0;
100  new_node->marked = new_node->fixed = false;
101  new_node->preorder_number = -1;
102  insertInHashTable( name, new_node );
103  master_node_list[ new_node->id ] = new_node;
104  return new_node;
105 }
106
107 void addNodeToLayer( Nodeptr node, int layer )
108 {
109  static int current_layer = 0;
110  static int current_position = 0;
111  if( layer != current_layer )
112  {
113  current_layer = layer;
114  current_position = 0;
115  }
116  node->layer = current_layer;
117  node->position = current_position;
118  layers[ layer ]->nodes[ current_position++ ] = node;
119 }
120
121 void makeLayer()
122 {
123  Layerptr new_layer = (Layerptr) malloc( sizeof(struct layer_struct) );
124  new_layer->number_of_nodes = 0;
125  new_layer->nodes = NULL;
127  {
128  layer_capacity *= 2;
129  layers
130  = (Layerptr *) realloc( layers, layer_capacity * sizeof(Layerptr) );
131  }
132  layers[ number_of_layers++ ] = new_layer;
133 }
134
135 void addEdge( const char * name1, const char * name2 )
136 {
137  static int num_edges_so_far = 0;
138  Nodeptr node1 = getFromHashTable( name1 );
139  Nodeptr node2 = getFromHashTable( name2 );
140  if ( node1->layer == node2->layer ) {
141  fprintf( stderr, "FATAL: addEdge, nodes on same layer.\n" );
142  fprintf( stderr, " Nodes %s and %s are on layer %d.\n",
143  node1->name, node2->name, node1->layer);
144  abort();
145  }
146
147  // a warning about missing nodes was already issued in the first pass
148  if ( node1 == NULL || node2 == NULL ) return;
149
150  Nodeptr upper_node
151  = ( node1->layer > node2->layer ) ? node1 : node2;
152  Nodeptr lower_node
153  = ( node1->layer < node2->layer ) ? node1 : node2;
154  if ( upper_node->layer - lower_node->layer != 1 ) {
156  fprintf( stderr, " Nodes %s is on layer %d and %s is on layer %d.\n",
157  upper_node->name, upper_node->layer,
158  lower_node->name, lower_node->layer);
159  abort();
160  }
161  Edgeptr new_edge = malloc( sizeof(struct edge_struct) );
162  new_edge->up_node = upper_node;
163  new_edge->down_node = lower_node;
164  new_edge->fixed = false;
165  upper_node->down_edges[ upper_node->down_degree++ ] = new_edge;
166  lower_node->up_edges[ lower_node->up_degree++ ] = new_edge;
167  master_edge_list[ num_edges_so_far++ ] = new_edge;
168 }
169
170 /**
171  * Sets number of nodes for the layer and allocates space for them. Note: the
172  * global number of nodes is updated in allocateLayers().
173  */
174 static void setNumberOfNodes( int layer, int number )
175 {
176  layers[ layer ]->number_of_nodes = number;
177  layers[ layer ]->nodes = (Nodeptr *) calloc( number, sizeof(Nodeptr) );
178 }
179
180 /**
181  * Implements the first pass of reading the ord file: allocates a record for
182  * each layer and space for the nodes on each layer. Creates the nodes
183  * and maps their names to (pointers to) their records. Counts the total
184  * number of nodes.
185  */
186 static void allocateLayers( const char * ord_file )
187 {
188  FILE * in = fopen( ord_file, "r" );
189  if( in == NULL )
190  {
191  fprintf( stderr, "Unable to open file %s for input\n", ord_file );
192  exit( EXIT_FAILURE );
193  }
195  layers = (Layerptr *) calloc( layer_capacity, sizeof(Layerptr) );
196
197  int layer;
198  int expected_layer = 0;
199  char name_buf[MAX_NAME_LENGTH];
200  while ( nextLayer( in, & layer ) )
201  {
202  if( layer != expected_layer )
203  {
204  fprintf( stderr, "Fatal error: Expected layer %d, found layer %d\n",
205  expected_layer, layer );
206  abort();
207  }
208  expected_layer++;
209  makeLayer();
210  int node_count = 0;
211  while ( nextNode( in, name_buf ) )
212  {
213  node_count++;
214  number_of_nodes++; /* global node count */
215  }
216  setNumberOfNodes( layer, node_count );
217  }
218  fclose( in );
219 }
220
221 /**
222  * Reads the ord file and put the nodes on their appropriate layers
223  */
224 static void assignNodesToLayers( const char * ord_file )
225 {
226  FILE * in = fopen( ord_file, "r" );
227  int layer;
228  char name_buf[MAX_NAME_LENGTH];
229  while( nextLayer( in, & layer ) )
230  {
231  while( nextNode( in, name_buf ) )
232  {
233  Nodeptr node = makeNode( name_buf );
235  }
236  }
237  fclose( in );
238 }
239
240 /**
241  * Increments the degrees of the endpoints of an edge between name1 and name2
242  */
243 void incrementDegrees( const char * name1, const char * name2 )
244 {
245  Nodeptr node1 = getFromHashTable( name1 );
246  if( node1 == NULL )
247  {
248  fprintf( stderr, "Fatal error: Node '%s' does not exist in .ord file\n"
249  " edge is %s->%s\n", name1, name1, name2);
250  abort();
251  }
252  Nodeptr node2 = getFromHashTable( name2 );
253  if( node2 == NULL )
254  {
255  fprintf( stderr, "Fatal error: Node '%s' does not exist in .ord file\n"
256  " edge is %s->%s\n", name2, name1, name2);
257  abort();
258  }
259  Nodeptr upper_node
260  = ( node1->layer > node2->layer ) ? node1 : node2;
261  Nodeptr lower_node
262  = ( node1->layer < node2->layer ) ? node1 : node2;
263  upper_node->down_degree++;
264  lower_node->up_degree++;
265 }
266
267 /**
268  * Reads the dot file and makes room for nodes on all the adjacency lists;
269  * resets up and down node degrees. This is the first pass of reading the dot
270  * file. Also saves the name of the graph.
271  */
272 void allocateAdjacencyLists( const char * dot_file )
273 {
274  FILE * in = fopen( dot_file, "r" );
275  if( in == NULL )
276  {
277  fprintf( stderr, "Unable to open file %s for input\n", dot_file );
278  exit( EXIT_FAILURE );
279  }
280  initDot( in );
282  // read the edges and use each edge to update the appropriate degree for
283  // each endpoint
284  char src_buf[MAX_NAME_LENGTH];
285  char dst_buf[MAX_NAME_LENGTH];
286  while ( nextEdge( in, src_buf, dst_buf ) )
287  {
288 #ifdef DEBUG
289  printf( " new edge: %s -> %s\n", src_buf, dst_buf );
290 #endif
291  number_of_edges++;
292  incrementDegrees( src_buf, dst_buf );
293  }
294  // allocate adjacency lists for all nodes based on the appropriate degrees
295  int layer = 0;
296  for( ; layer < number_of_layers; layer++ )
297  {
298  int position = 0;
299  for( ; position < layers[ layer ]->number_of_nodes; position++ )
300  {
301  Nodeptr node = layers[ layer ]->nodes[ position ];
302  node->up_edges
303  = (Edgeptr *) calloc( node->up_degree, sizeof(Nodeptr) );
304  node->down_edges
305  = (Edgeptr *) calloc( node->down_degree, sizeof(Nodeptr) );
306  node->up_degree = 0;
307  node->down_degree = 0;
308  }
309  }
310  fclose( in );
311 }
312
313 /**
314  * Reads the dot file and adds all the edges. This is the second pass.
315  */
316 void createEdges( const char * dot_file )
317 {
318  FILE * in = fopen( dot_file, "r" );
319  initDot( in );
320  char src_buf[MAX_NAME_LENGTH];
321  char dst_buf[MAX_NAME_LENGTH];
322  while ( nextEdge( in, src_buf, dst_buf ) )
323  {
325  }
326  fclose( in );
327 }
328
329 /**
330  * @return number of nodes whose up_degree and
331  * down_degree are both zero
332  */
333 static int countIsolatedNodes()
334 {
335  /**
336  * @todo
337  * Should eliminate the isolated nodes altogether; on each layer -
338  * <pre>
339  * deallocate isolated nodes and mark positions with NULL
340  * position = real_position = 0;
341  * for position < number_of_nodes, position++
342  * while real_position < number_of_nodes and node[position] == NULL
343  * real_position++
344  * if node[position] == NULL && real_position < number_of_nodes
345  * node[position] = node[real_position++]
346  * </pre>
347  */
348  int isolated_nodes = 0;
349  int layer = 0;
350  for( ; layer < number_of_layers; layer++ )
351  {
352  int position = 0;
353  for( ; position < layers[ layer ]->number_of_nodes; position++ )
354  {
355  Nodeptr node = layers[ layer ]->nodes[ position ];
356  if( node->up_degree + node->down_degree == 0 )
357  isolated_nodes++;
358  }
359  }
360  return isolated_nodes;
361 }
362
363 void readGraph( const char * dot_file, const char * ord_file )
364 {
365  number_of_nodes = 0;
366  number_of_edges = 0;
367  number_of_layers = 0;
368  allocateLayers( ord_file );
369  master_node_list = (Nodeptr *) calloc( number_of_nodes, sizeof(Nodeptr) );
371  assignNodesToLayers( ord_file );
372 #ifdef DEBUG
373  printf( "Master node list after reading ord file:\n" );
374  for ( int i = 0; i < number_of_nodes; i++ ) {
375  printf( "%s, layer = %d, position = %d\n", master_node_list[i]->name,
376  master_node_list[i]->layer, master_node_list[i]->position );
377  }
378 #endif
380  // at this point the number of edges is known
381  master_edge_list = (Edgeptr *) calloc( number_of_edges, sizeof(Edgeptr) );
382  createEdges( dot_file );
384  removeHashTable();
385 }
386
387 // --------------- Output to dot and ord files
388
389 static void writeNodes( FILE * out, Layerptr layerptr )
390 {
391  int i = 0;
392  for( ; i < layerptr->number_of_nodes; i++ )
393  {
394  outputNode( out, layerptr->nodes[i]->name );
395  }
396 }
397
398 /**
399  * @todo ord file should have information about heuristic that created it, etc.,
400  * embedded in it. Use of the file/graph name can be problematic if we want to
401  * check what happens when one heuristic follows another for a whole class
402  * using a script. There needs to be some way to differentiate among these
403  * files.
404  */
405 void writeOrd( const char * ord_file )
406 {
407  FILE * out = fopen( ord_file, "w" );
408  if( out == NULL )
409  {
410  fprintf( stderr, "Unable to open file %s for output\n", ord_file );
411  exit( EXIT_FAILURE );
412  }
413  ordPreamble( out, graph_name, "" );
414  int layer = 0;
415  for( ; layer < number_of_layers; layer++ )
416  {
417  beginLayer( out, layer, "heuristic-based" );
418  writeNodes( out, layers[ layer ] );
419  endLayer( out );
420  }
421  fclose( out );
422 }
423
424 void writeDot( const char * dot_file_name,
425  const char * graph_name,
427  Edgeptr * edge_list,
428  int edge_list_length
429  )
430 {
431  FILE * out = fopen( dot_file_name, "w" );
432  if( out == NULL )
433  {
434  fprintf( stderr, "Unable to open file %s for output\n", dot_file_name );
435  exit( EXIT_FAILURE );
436  }
437  dotPreamble( out, graph_name, header_information );
438  for ( int i = 0; i < edge_list_length; i++ )
439  {
440  Edgeptr current = edge_list[i];
441  Nodeptr up_node = current->up_node;
442  Nodeptr down_node = current->down_node;
443  outputEdge( out, up_node->name, down_node->name );
444  }
445  endDot( out );
446  fclose( out );
447 }
448
449 // --------------- Debugging output --------------
450
451 static void printNode( Nodeptr node )
452 {
453  printf(" [%3d ] %s layer=%d position=%d up=%d down=%d up_x=%d down_x=%d\n",
454  node->id, node->name, node->layer, node->position,
455  node->up_degree, node->down_degree,
456  node->up_crossings, node->down_crossings );
457  printf(" ^^^^up");
458  int i = 0;
459  for( ; i < node->up_degree; i++ )
460  {
461  Edgeptr edge = node->up_edges[i];
462  printf(" %s", edge->up_node->name );
463  }
464  printf("\n");
465  printf(" __down");
466  i = 0;
467  for( ; i < node->down_degree; i++ )
468  {
469  Edgeptr edge = node->down_edges[i];
470  printf(" %s", edge->down_node->name );
471  }
472  printf("\n");
473 }
474
475 static void printLayer( int layer )
476 {
477  printf(" --- layer %d nodes=%d fixed=%d\n",
478  layer, layers[layer]->number_of_nodes, layers[layer]->fixed );
479  int node = 0;
480  for( ; node < layers[layer]->number_of_nodes; node++ )
481  {
482  printNode( layers[layer]->nodes[node] );
483  }
484 }
485
487 {
488  printf("+++ begin-graph %s nodes=%d, layers=%d\n",
490  int layer = 0;
491  for( ; layer < number_of_layers; layer++ )
492  {
493  printLayer( layer );
494  }
495  printf("=== end-graph\n");
496 }
497
498 #ifdef TEST
499
500 int main( int argc, char * argv[] )
501 {
503  printGraph();
504  fprintf( stderr, "Average number of probes = %5.2f\n",
506  return 0;
507 }
508
509 #endif
510
void beginLayer(FILE *out, int layer, const char *type)
Definition: ord.c:187
Nodeptr up_node
Definition: graph.h:98
void outputEdge(FILE *out, const char *src_name, const char *dst_name)
Definition: dot.c:222
void dotPreamble(FILE *out, const char *graph_name, const char *seed_info)
Definition: dot.c:210
int down_crossings
Definition: graph.h:87
Nodeptr makeNode(const char *name)
Definition: graph_io.c:86
Definition: graph_io.c:107
static void allocateLayers(const char *ord_file)
Definition: graph_io.c:186
int preorder_number
Definition: graph.h:91
void ordPreamble(FILE *out, const char *graph_name, const char *generation_method)
Definition: ord.c:180
void endDot(FILE *out)
Definition: dot.c:217
int id
Definition: graph.h:64
Nodeptr * master_node_list
Definition: graph_io.c:25
char * name
Definition: graph.h:63
int number_of_nodes
Definition: graph.h:115
struct layer_struct * Layerptr
Definition: graph.h:59
static void assignNodesToLayers(const char *ord_file)
Definition: graph_io.c:224
Edgeptr * down_edges
Definition: graph.h:78
bool marked
Definition: graph.h:90
bool nextLayer(FILE *in, int *layer)
Definition: ord.c:112
A simple map based on a hash table, maps names to node pointers.
Global variables, functions, and parameters specified on the command line.
Definitions common to all edge crossing heuristic source files.
int position
Definition: graph.h:73
static void printLayer(int layer)
Definition: graph_io.c:475
void incrementDegrees(const char *name1, const char *name2)
Definition: graph_io.c:243
void endLayer(FILE *out)
Definition: ord.c:196
int number_of_isolated_nodes
Definition: graph_io.c:30
static void writeNodes(FILE *out, Layerptr layerptr)
Definition: graph_io.c:389
void readGraph(const char *dot_file, const char *ord_file)
Definition: graph_io.c:363
struct node_struct * Nodeptr
Definition: graph.h:57
int number_of_edges
Definition: graph_io.c:29
int number_of_layers
Definition: graph_io.c:28
Definition: graph_io.c:272
void writeDot(const char *dot_file_name, const char *graph_name, const char *header_information, Edgeptr *edge_list, int edge_list_length)
Definition: graph_io.c:424
Edgeptr * up_edges
Definition: graph.h:77
char graph_name[MAX_NAME_LENGTH]
Definition: graph_io.c:32
static int layer_capacity
Definition: graph_io.c:35
Module for reading files in .dot format.
int up_degree
Definition: graph.h:74
bool fixed
Definition: graph.h:85
void insertInHashTable(const char *name, Nodeptr node)
Definition: hash.c:81
void createEdges(const char *dot_file)
Definition: graph_io.c:316
static void printNode(Nodeptr node)
Definition: graph_io.c:451
int layer
Definition: graph.h:65
void printGraph()
Definition: graph_io.c:486
int down_degree
Definition: graph.h:75
void addEdge(const char *name1, const char *name2)
Definition: graph_io.c:135
bool nextNode(FILE *in, char *node_buffer)
Definition: ord.c:146
int up_crossings
Definition: graph.h:86
static void setNumberOfNodes(int layer, int number)
Definition: graph_io.c:174
Definition of data structures and access functions for a layered graph.
void initHashTable(int number_of_items)
Definition: hash.c:69
bool fixed
Definition: graph.h:106
Layerptr * layers
Definition: graph_io.c:31
Nodeptr * nodes
Definition: graph.h:116
void outputNode(FILE *out, const char *node)
Definition: ord.c:204
bool nextEdge(FILE *in, char *src_buf, char *dst_buf)
Definition: dot.c:172
Nodeptr down_node
Definition: graph.h:99
int number_of_nodes
Definition: graph_io.c:27
void initDot(FILE *in)
Definition: dot.c:144
Nodeptr getFromHashTable(const char *name)
Definition: hash.c:100
header for utility functions that read and write .ord files (node ordering on layers of a graph) ...
void getNameFromDotFile(char *buffer)
Definition: dot.c:167
#define MAX_NAME_LENGTH
Definition: defs.h:32
void removeHashTable()
Definition: hash.c:106
static int countIsolatedNodes()
Definition: graph_io.c:333
void writeOrd(const char *ord_file)
Definition: graph_io.c:405
Edgeptr * master_edge_list
Definition: graph_io.c:26
void makeLayer()
Definition: graph_io.c:121
double getAverageNumberOfProbes()
Definition: hash.c:111
#define MIN_LAYER_CAPACITY
Definition: graph_io.c:23
int main(int argc, char *argv[])