Crossings Minimization  1.0
random_dag.c
Go to the documentation of this file.
1 /**
2  * @file random_tree.c
3  * @brief Module for creating a random dag with a given number of nodes and
4  * layers. First a tree is created to form the backbone of the dag.
5  *
6  * @author Matt Stallmann
7  * @date 2011/06/01
8  * \$Id: random_dag.c 27 2011-07-09 21:22:42Z mfms \$
9  */
10
11 #include "graph.h"
12 #include "graph_io.h"
13 #include "random_tree.h"
14 #include "random_dag.h"
15 #include "check_edge_duplication.h"
16 #include <stdio.h>
17 #include <stdlib.h>
18 #include <stdbool.h>
19 #include <string.h>
20 #include <assert.h>
21
22 /**
23  * Adds an edge between two nodes whose layers are determined and adjacent to
24  * one another
25  *
26  * @todo Avoid duplication with the same function in create_random_tree and
28  */
29 static void add_edge( Nodeptr upper_node, Nodeptr lower_node )
30 {
31 #ifdef DEBUG
32  printf( "-> add_edge: upper_node = (%s,%d,%d), lower_node = (%s,%d,%d)\n",
33  upper_node->name, upper_node->layer, upper_node->position,
34  lower_node->name, lower_node->layer, lower_node->position );
35 #endif
36  assert( upper_node->layer == lower_node->layer + 1 );
37  Edgeptr new_edge = (Edgeptr) calloc( 1, sizeof(struct edge_struct) );
38  new_edge->up_node = upper_node;
39  new_edge->down_node = lower_node;
40  new_edge->fixed = false;
41
42  // add new edge to master edge list, making room if necessary
44  {
46  = (Edgeptr *) realloc( master_edge_list,
48  }
49  master_edge_list[ number_of_edges++ ] = new_edge;
50
51  // add new edge to lower edge list of upper node, making room if necessary
52  if ( upper_node->down_degree % CAPACITY_INCREMENT == 0 )
53  {
54  upper_node->down_edges
55  = (Edgeptr *) realloc( upper_node->down_edges,
56  (upper_node->down_degree + CAPACITY_INCREMENT) * sizeof(Edgeptr) );
57  }
58  upper_node->down_edges[ upper_node->down_degree++ ] = new_edge;
59  // add new edge to upper edge list of lower node, making room if necessary
60  if ( lower_node->up_degree % CAPACITY_INCREMENT == 0 )
61  {
62  lower_node->up_edges
63  = (Edgeptr *) realloc( lower_node->up_edges,
64  lower_node->up_degree + CAPACITY_INCREMENT * sizeof(Edgeptr) );
65  }
66  lower_node->up_edges[ lower_node->up_degree++ ] = new_edge;
67
68 #ifdef DEBUG
69  printf( "<- add_edge: edge = %s -> %s\n",
70  new_edge->up_node->name, new_edge->down_node->name );
71 #endif
72 }
73
74 /**
75  * Make it so that when the current edges are checked for existence in the
76  * future, the correct answer will be given; for use after tree edges are
77  * created.
78  */
79 static void make_all_current_edges_exist( void )
80 {
81  for ( int i = 0; i < number_of_edges; i++ )
82  {
83  Edgeptr edge = master_edge_list[i];
84  int up_node_id = edge->up_node->id;
85  int down_node_id = edge->down_node->id;
86  pair_already_exists( up_node_id, down_node_id );
87  }
88 }
89
90 void create_random_dag( int num_nodes,
91  int desired_num_edges,
92  int num_layers,
93  int branching_factor )
94 {
95 #ifdef DEBUG
96  printf( "-> create_random_dag: nodes = %d, edges = %d, layers = %d, branching = %d\n"
97  " number_of_nodes = %d, number_of_edges = %d\n",
98  num_nodes, desired_num_edges, num_layers, branching_factor, number_of_nodes, number_of_edges );
99 #endif
100
101  assert( num_nodes > 0
102  && desired_num_edges > 0
103  && num_layers > 1
104  && branching_factor > 0 );
105
106  create_random_tree( num_nodes, num_layers, branching_factor );
107 #ifdef DEBUG
108  printf( " After create_random_tree: number_of_nodes = %d, number_of_edges = %d, desired = %d\n",
109  number_of_nodes, number_of_edges, desired_num_edges );
110 #endif
111
112  create_hash_table_for_pairs( desired_num_edges );
113
115
116  while ( desired_num_edges > number_of_edges )
117  {
118  // pick two random nodes that are on adjacent layers
119  // if there's not already an edge between them, add one
120
121  // pick a node that's not on layer 0
122  int first_node_index = random() % number_of_nodes;
123  Nodeptr first_node = master_node_list[ first_node_index ];
124  int first_node_layer_number = first_node->layer;
125 #ifdef DEBUG
126  printf( " Loop iteration: number_of_edges = %d, desired = %d\n"
127  " first_node = %d [%d]\n",
128  number_of_edges, desired_num_edges,
129  first_node_index, first_node_layer_number );
130 #endif
131  if ( first_node_layer_number == 0 ) continue;
132
133  // pick another node on the layer below that of the first node
134  int second_node_layer_number = first_node_layer_number - 1;
135  Layerptr second_node_layer = layers[ second_node_layer_number ];
136  int second_node_layer_position = random() % second_node_layer->number_of_nodes;
137  Nodeptr second_node = second_node_layer->nodes[ second_node_layer_position ];
138  int second_node_index = second_node->id;
139
140 #ifdef DEBUG
141  printf( " Attempting to add edge: %d [%d] -> %d [%d]\n",
142  first_node_index, first_node_layer_number,
143  second_node_index, second_node_layer_number );
144 #endif
145
146  // add the edge if it doesn't already exist
147  if ( ! pair_already_exists( first_node_index, second_node_index ) )
148  {
149  add_edge( first_node, second_node );
150  }
151  }
153 }
154
155 /* [Last modified: 2011 07 07 at 16:12:28 GMT] */
Nodeptr * master_node_list
Definition: graph_io.c:25
Nodeptr up_node
Definition: graph.h:98
void create_random_dag(int num_nodes, int desired_num_edges, int num_layers, int branching_factor)
Definition: random_dag.c:90
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
Edgeptr * down_edges
Definition: graph.h:78
int position
Definition: graph.h:73
static void make_all_current_edges_exist(void)
Definition: random_dag.c:79
struct edge_struct * Edgeptr
Definition: graph.h:58
void create_random_tree(int num_nodes, int num_layers, int branching_factor)
Definition: random_tree.c:208
Edgeptr * up_edges
Definition: graph.h:77
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
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
int number_of_edges
Definition: graph_io.c:29
static void add_edge(Nodeptr upper_node, Nodeptr lower_node)
Definition: random_dag.c:29
Module for creating a random dag with a given number of nodes and layers.
Nodeptr * nodes
Definition: graph.h:116
Nodeptr down_node
Definition: graph.h:99
Edgeptr * master_edge_list
Definition: graph_io.c:26