Crossings Minimization  1.0
add_edges.c
Go to the documentation of this file.
1 /**
2  * @file add_edges.c
3  * @brief Main program for adding random edges to a given dag (usually a
4  * tree) in order to achieve a given number of edges.
5  *
6  * @author Matt Stallmann, 2011/07/07
7  *
8  * $Id: add_edges.c 27 2011-07-09 21:22:42Z mfms $
9  */
10 
11 #include<stdio.h>
12 #include<stdlib.h>
13 #include<string.h>
14 #include<libgen.h> /* basename() */
15 #include<assert.h>
16 #include"graph.h"
17 #include"graph_io.h"
18 #include"Statistics.h"
19 #include"heuristics.h"
20 #include"random_tree.h"
22 
23 static void usage_message( char * prog_name )
24 {
25  char * truncated_prog_name = basename( prog_name );
26  printf(
27  "Usage: %s input_basename output_basename edges seed\n"
28  " where input_basename.dot and input_basename.ord are the input files\n"
29  " representing the dag to which edges are to be added\n"
30  " output_basename.dot and output_basename.ord are the output files\n"
31  " representing the dag with the added edges\n"
32  " edges is the *total* number of edges desired\n"
33  " seed is a single integer seed for the random number stream\n"
34  ,
35  truncated_prog_name
36  );
37 }
38 
39 static void print_stats( void )
40 {
43  for( int layer = 0; layer < number_of_layers; layer++ )
44  {
45  add_data( layer_info, layers[ layer ]->number_of_nodes );
46  for( int position = 0; position < layers[ layer ]->number_of_nodes; position++ )
47  {
48  Nodeptr node = layers[ layer ]->nodes[ position ];
49  add_data( degree_info, DEGREE( node ) );
50  }
51  }
52  printf( "NumberOfNodes,%d\n", number_of_nodes );
53  printf( "NumberOfEdges,%d\n", number_of_edges );
54  printf( "EdgeDensity,%2.2f\n", ((double) number_of_edges) / number_of_nodes );
55  printf( "DegreeStats\t" );
56  print_statistics( degree_info, stdout, "%2.1f" );
57  printf( "\n" );
58  printf( "LayerSize\t" );
59  print_statistics( layer_info, stdout, "%2.1f" );
60  printf( "\n" );
61  free_statistics( layer_info );
62  free_statistics( degree_info );
63 }
64 
65 /**
66  * Adds an edge between two nodes whose layers are determined and adjacent to
67  * one another
68  */
69 static void add_edge( Nodeptr upper_node, Nodeptr lower_node )
70 {
71 #ifdef DEBUG
72  printf( "-> add_edge: upper_node = (%s,%d,%d), lower_node = (%s,%d,%d)\n",
73  upper_node->name, upper_node->layer, upper_node->position,
74  lower_node->name, lower_node->layer, lower_node->position );
75 #endif
76  assert( upper_node->layer == lower_node->layer + 1 );
77  Edgeptr new_edge = (Edgeptr) calloc( 1, sizeof(struct edge_struct) );
78  new_edge->up_node = upper_node;
79  new_edge->down_node = lower_node;
80  new_edge->fixed = false;
81 
82  // add new edge to master edge list, making room if necessary
84  {
86  = (Edgeptr *) realloc( master_edge_list,
88  }
89  master_edge_list[ number_of_edges++ ] = new_edge;
90 
91  // add new edge to lower edge list of upper node, making room if necessary
92  if ( upper_node->down_degree % CAPACITY_INCREMENT == 0 )
93  {
94  upper_node->down_edges
95  = (Edgeptr *) realloc( upper_node->down_edges,
96  (upper_node->down_degree + CAPACITY_INCREMENT) * sizeof(Edgeptr) );
97  }
98  upper_node->down_edges[ upper_node->down_degree++ ] = new_edge;
99  // add new edge to upper edge list of lower node, making room if necessary
100  if ( lower_node->up_degree % CAPACITY_INCREMENT == 0 )
101  {
102  lower_node->up_edges
103  = (Edgeptr *) realloc( lower_node->up_edges,
104  lower_node->up_degree + CAPACITY_INCREMENT * sizeof(Edgeptr) );
105  }
106  lower_node->up_edges[ lower_node->up_degree++ ] = new_edge;
107 
108 #ifdef DEBUG
109  printf( "<- add_edge: edge = %s -> %s\n",
110  new_edge->up_node->name, new_edge->down_node->name );
111 #endif
112 }
113 
114 /**
115  * Make it so that when the current edges are checked for existence in the
116  * future, the correct answer will be given
117  */
118 static void make_all_current_edges_exist( void )
119 {
120  for ( int i = 0; i < number_of_edges; i++ )
121  {
122  Edgeptr edge = master_edge_list[i];
123  int up_node_id = edge->up_node->id;
124  int down_node_id = edge->down_node->id;
125  pair_already_exists( up_node_id, down_node_id );
126  }
127 }
128 
129 static void add_edges( int desired_num_edges )
130 {
131 #ifdef DEBUG
132  printf( "-> add_edges: number_of_nodes = %d, current_number_of_edges = %d,"
133  " desired_number_of_edges = %d\n",
134  number_of_nodes, number_of_edges, desired_num_edges );
135 #endif
136 
137  assert(
138  number_of_nodes > 1
139  && number_of_layers > 1
140  );
141 
142  create_hash_table_for_pairs( desired_num_edges );
143 
145 
146  while ( desired_num_edges > number_of_edges )
147  {
148  // pick two random nodes that are on adjacent layers
149  // if there's not already an edge between them, add one
150 
151  // pick a node that's not on layer 0
152  int first_node_index = random() % number_of_nodes;
153  Nodeptr first_node = master_node_list[ first_node_index ];
154  int first_node_layer_number = first_node->layer;
155 #ifdef DEBUG
156  printf( " Loop iteration: number_of_edges = %d, desired = %d\n"
157  " first_node = %d [%d]\n",
158  number_of_edges, desired_num_edges,
159  first_node_index, first_node_layer_number );
160 #endif
161  if ( first_node_layer_number == 0 ) continue;
162 
163  // pick another node on the layer below that of the first node
164  int second_node_layer_number = first_node_layer_number - 1;
165  Layerptr second_node_layer = layers[ second_node_layer_number ];
166  int second_node_layer_position = random() % second_node_layer->number_of_nodes;
167  Nodeptr second_node = second_node_layer->nodes[ second_node_layer_position ];
168  int second_node_index = second_node->id;
169 
170 #ifdef DEBUG
171  printf( " Attempting to add edge: %d [%d] -> %d [%d]\n",
172  first_node_index, first_node_layer_number,
173  second_node_index, second_node_layer_number );
174 #endif
175 
176  // add the edge if it doesn't already exist
177  if ( ! pair_already_exists( first_node_index, second_node_index ) )
178  {
179  add_edge( first_node, second_node );
180  }
181  }
183 }
184 
185 int main( int argc, char * argv[] )
186 {
187  if ( argc != 5 )
188  {
189  usage_message( argv[0] );
190  return EXIT_FAILURE;
191  }
192 
193  const char * input_base_name = argv[1];
194  const char * output_base_name = argv[2];
195  int edges = atoi( argv[3] );
196  long seed = atoi( argv[4] );
197 
198  srandom( seed );
199 
200  // read the input graph
201  char dot_name_buffer[MAX_NAME_LENGTH];
202  char ord_name_buffer[MAX_NAME_LENGTH];
203  strcpy( dot_name_buffer, input_base_name );
204  strcat( dot_name_buffer, ".dot" );
205  strcpy( ord_name_buffer, input_base_name );
206  strcat( ord_name_buffer, ".ord" );
207  readGraph( dot_name_buffer, ord_name_buffer );
208  int original_num_edges = number_of_edges;
209 
210  // check whether the desired number of edges is reasonable
211  // choice of maximum density is arbitrary, based on the number obtained if
212  // all edges between two adjacent layers were present; the division by 4
213  // prevents the program from spending too long to avoid duplicate edges
214  double max_edges = (double) number_of_nodes * number_of_nodes / 4;
215  if ( edges > max_edges )
216  {
217  printf( "Desired graph is too dense to be constructed, desired edges = %d, max edges = %2.0f\n",
218  edges, max_edges );
219  return EXIT_FAILURE;
220  }
221 
222  // add edges to it
223  add_edges( edges );
224 
225  print_stats();
226 
227  strcpy( graph_name, output_base_name );
228 
229  strcpy( dot_name_buffer, output_base_name );
230  strcpy( ord_name_buffer, output_base_name );
231  strcat( dot_name_buffer, ".dot" );
232  strcat( ord_name_buffer, ".ord" );
233  char header_info_buffer[MAX_NAME_LENGTH];
234  sprintf( header_info_buffer,
235  " random dag, created by: add_edges %s %s %d %d %d %ld\n",
236  input_base_name, output_base_name,
237  number_of_nodes, original_num_edges, number_of_edges, seed
238  );
239 
240  writeDot(
241  dot_name_buffer,
242  graph_name,
243  header_info_buffer,
246  );
247 
248  writeOrd( ord_name_buffer );
249 
250  return EXIT_SUCCESS;
251 }
252 
253 /* [Last modified: 2011 07 07 at 16:57:39 GMT] */
Nodeptr * master_node_list
Definition: graph_io.c:25
Nodeptr up_node
Definition: graph.h:98
void add_data(Statistics s, double data_point)
Definition: Statistics.c:111
Statistics init_statistics(int size)
Definition: Statistics.c:26
int id
Definition: graph.h:64
Interface for functions implementing all of the heuristics Those labeled parallel are designed specif...
char * name
Definition: graph.h:63
Layerptr * layers
Definition: graph_io.c:31
int number_of_nodes
Definition: graph.h:115
Edgeptr * down_edges
Definition: graph.h:78
Interface for a Statistics class with methods for computing min, median, mean, max, and standard deviation.
int position
Definition: graph.h:73
void print_statistics(Statistics s, FILE *output_stream, const char *format)
Definition: Statistics.c:127
char * output_base_name
Definition: min_crossings.c:60
void readGraph(const char *dot_file, const char *ord_file)
Definition: graph_io.c:363
struct edge_struct * Edgeptr
Definition: graph.h:58
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
static void make_all_current_edges_exist(void)
Definition: add_edges.c:118
bool pair_already_exists(int first_int, int second_int)
int up_degree
Definition: graph.h:74
int number_of_nodes
Definition: graph_io.c:27
void create_hash_table_for_pairs(int expected_number_of_pairs)
Definition of functions for reading and writing graphs.
int layer
Definition: graph.h:65
int down_degree
Definition: graph.h:75
static void add_edges(int desired_num_edges)
Definition: add_edges.c:129
void destroy_hash_table_for_pairs(void)
Definition of data structures and access functions for a layered graph.
utility that uses hashing to check whether an edge already exists
Module for creating a random tree with a given number of nodes and layers.
#define CAPACITY_INCREMENT
Definition: defs.h:36
bool fixed
Definition: graph.h:106
static char graph_name[MAX_NAME_LENGTH]
Definition: dot.c:42
static void usage_message(char *prog_name)
Definition: add_edges.c:23
static void add_edge(Nodeptr upper_node, Nodeptr lower_node)
Definition: add_edges.c:69
int number_of_edges
Definition: graph_io.c:29
Nodeptr * nodes
Definition: graph.h:116
static void print_stats(void)
Definition: add_edges.c:39
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
void writeOrd(const char *ord_file)
Definition: graph_io.c:405
void free_statistics(Statistics s)
Definition: Statistics.c:142
int main(int argc, char *argv[])
Definition: add_edges.c:185