Crossings Minimization  1.0
create_random_dag.c
Go to the documentation of this file.
1 /**
2  * @file create_random_dag.c
3  * @brief Main program for creating a random dag with a specified number of
4  * vertices, edges, and layers.
5  * @author Matt Stallmann, 2011/06/01
6  *
7  * $Id: create_random_dag.c 2 2011-06-07 19:50:41Z mfms $
8  */
9 
10 #include<stdio.h>
11 #include<stdlib.h>
12 #include<string.h>
13 #include<libgen.h> /* basename() */
14 #include"graph.h"
15 #include"graph_io.h"
16 #include"Statistics.h"
17 #include"heuristics.h"
18 #include"random_tree.h"
19 #include"random_dag.h"
20 
21 void usage_message( char * prog_name )
22 {
23  char * truncated_prog_name = basename( prog_name );
24  printf(
25  "Usage: %s basename nodes edges layers skew seed\n"
26  " where basename.dot and basename.ord are the output files\n"
27  " nodes, edges, layers are the number of nodes, edges, and layers of the dag, respectively\n"
28  " skew is a factor that affects max degree and variance of layer size\n"
29  " it should be at least 3 for sparse graphs to be interesting\n"
30  " large skew => large max degree and large variance\n"
31  " seed is a single integer seed for the random number stream\n"
32  ,
33  truncated_prog_name
34  );
35 }
36 
37 static void print_stats( void )
38 {
41  for( int layer = 0; layer < number_of_layers; layer++ )
42  {
43  add_data( layer_info, layers[ layer ]->number_of_nodes );
44  for( int position = 0; position < layers[ layer ]->number_of_nodes; position++ )
45  {
46  Nodeptr node = layers[ layer ]->nodes[ position ];
47  add_data( degree_info, DEGREE( node ) );
48  }
49  }
50  printf( "NumberOfNodes,%d\n", number_of_nodes );
51  printf( "NumberOfEdges,%d\n", number_of_edges );
52  printf( "EdgeDensity,%2.2f\n", ((double) number_of_edges) / number_of_nodes );
53  printf( "DegreeStats\t" );
54  print_statistics( degree_info, stdout, "%2.1f" );
55  printf( "\n" );
56  printf( "LayerSize\t" );
57  print_statistics( layer_info, stdout, "%2.1f" );
58  printf( "\n" );
59  free_statistics( layer_info );
60  free_statistics( degree_info );
61 }
62 
63 int main( int argc, char * argv[] )
64 {
65  if ( argc != 7 )
66  {
67  usage_message( argv[0] );
68  return EXIT_FAILURE;
69  }
70 
71  const char * base_name = argv[1];
72  int nodes = atoi( argv[2] );
73  int edges = atoi( argv[3] );
74  int layers = atoi( argv[4] );
75  int branching = atoi( argv[5] );
76  long seed = atoi( argv[6] );
77 
78  if ( edges < nodes - 1 )
79  {
80  printf( "WARNING: number of edges is %d, less than the %d required\n",
81  edges, nodes - 1 );
82  }
83 
84  // choice of maximum density is arbitrary, based on having all edges
85  // between two adjacent layers; the division by 4 avoids spending too long
86  // to avoid duplicate edges
87  double max_edges = (double) nodes * nodes / 4;
88  if ( edges > max_edges )
89  {
90  printf( "Desired graph is too dense to be constructed, desired edges = %d, max edges = %2.0f\n",
91  edges, max_edges );
92  return EXIT_FAILURE;
93  }
94 
95 
96  srandom( seed );
97 
98  create_random_dag( nodes, edges, layers, branching );
99  // create_random_tree( nodes, layers, branching );
100 
101  print_stats();
102 
103  strcpy( graph_name, base_name );
104 
105  char dot_file_buffer[MAX_NAME_LENGTH];
106  char ord_file_buffer[MAX_NAME_LENGTH];
107  char header_info_buffer[MAX_NAME_LENGTH];
108 
109  strcpy( dot_file_buffer, base_name );
110  strcpy( ord_file_buffer, base_name );
111  strcat( dot_file_buffer, ".dot" );
112  strcat( ord_file_buffer, ".ord" );
113  sprintf( header_info_buffer,
114  " random dag, created by: create_random_dag %s %d %d %d %d %ld\n",
115  graph_name, nodes, edges, layers, branching, seed
116  );
117 
118  writeDot(
119  dot_file_buffer,
120  graph_name,
121  header_info_buffer,
124  );
125 
126  writeOrd( ord_file_buffer );
127 
128  return EXIT_SUCCESS;
129 }
130 
131 /* [Last modified: 2011 06 03 at 17:57:06 GMT] */
void add_data(Statistics s, double data_point)
Definition: Statistics.c:111
void create_random_dag(int num_nodes, int desired_num_edges, int num_layers, int branching_factor)
Definition: random_dag.c:90
Statistics init_statistics(int size)
Definition: Statistics.c:26
Interface for functions implementing all of the heuristics Those labeled parallel are designed specif...
Layerptr * layers
Definition: graph_io.c:31
int number_of_nodes
Definition: graph.h:115
static void print_stats(void)
Interface for a Statistics class with methods for computing min, median, mean, max, and standard deviation.
void print_statistics(Statistics s, FILE *output_stream, const char *format)
Definition: Statistics.c:127
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
int number_of_nodes
Definition: graph_io.c:27
Definition of functions for reading and writing graphs.
Definition of data structures and access functions for a layered graph.
Module for creating a random tree with a given number of nodes and layers.
static char graph_name[MAX_NAME_LENGTH]
Definition: dot.c:42
int main(int argc, char *argv[])
int number_of_edges
Definition: graph_io.c:29
Module for creating a random dag with a given number of nodes and layers.
void usage_message(char *prog_name)
Nodeptr * nodes
Definition: graph.h:116
int number_of_layers
Definition: graph_io.c:28
static char * base_name(char *buffer)
#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