Crossings Minimization  1.0
random_tree.c
Go to the documentation of this file.
1 /**
2  * @file random_tree.c
3  * @brief Module for creating a random tree with a given number of nodes and
4  * layers.
5  *
6  * Paths in the tree move in a single direction until they run out of layers
7  * and then continue the process switching directions only when necessary.
8  *
9  * @author Matt Stallmann
10  * @date 2011/05/30
11  * $Id: random_tree.c 2 2011-06-07 19:50:41Z mfms $
12  */
13 
14 #include "graph.h"
15 #include "graph_io.h"
16 #include "random_tree.h"
17 #include <stdio.h>
18 #include <stdlib.h>
19 #include <stdbool.h>
20 #include <string.h>
21 #include <assert.h>
22 
23 /**
24  * New nodes randomly selected to be adjacent to the current node are put at
25  * the rear of the master node list; this global variable keeps track of that
26  * rear position; this rear position also determines the number of nodes that
27  * have been added to the tree, hence the name
28  */
29 static int number_of_tree_nodes = 0;
30 
31 /**
32  * The number of layers that have no nodes on them. Used to ensure that
33  * branching does not cause the number of layers to be less than what was
34  * requested.
35  */
36 static int layers_remaining;
37 
38 bool * going_up = NULL;
39 
40 /**
41  * Assigns a direction to each node, initially up
42  */
43 static void init_node_directions( int num_nodes )
44 {
45  going_up = calloc( num_nodes, sizeof( bool ) );
46  for ( int i = 0; i < num_nodes; i++ )
47  going_up[i] = true;
48 }
49 
50 /**
51  * initializes the data for a node at a given position in the master node list
52  * @param node_number the position of the node
53  * @return a pointer to the new node
54  */
55 static Nodeptr create_node( int node_number )
56 {
57  Nodeptr new_node = (Nodeptr) calloc( 1, sizeof(struct node_struct));
58  new_node->id = node_number;
59 
60  // give the node a name based on its position in the master list
62  sprintf( name_buffer, "n_%d", node_number );
63  new_node->name = (char *) malloc( strlen(name_buffer) + 1 );
64  strcpy( new_node->name, name_buffer );
65 
66  new_node->layer = new_node->position = -1; /* to indicate "uninitialized" */
67  new_node->up_degree = new_node->down_degree = 0;
68  new_node->up_edges = new_node->down_edges = NULL;
69  new_node->up_crossings = new_node->down_crossings = 0;
70  new_node->marked = new_node->fixed = false;
71  new_node->preorder_number = -1;
72  return new_node;
73 }
74 
75 /**
76  * Creates and initializes the master node list
77  */
78 static void create_master_node_list( int num_nodes )
79 {
80  master_node_list = (Nodeptr *) calloc( num_nodes, sizeof( Nodeptr ) );
81  for ( int i = 0; i < num_nodes; i++ )
82  {
83  master_node_list[i] = create_node( i );
84  }
85 }
86 
87 static void init_layers( int num_layers )
88 {
89  layers = (Layerptr *) calloc( num_layers, sizeof( Layerptr ) );
90  for ( int i = 0; i < num_layers; i++ )
91  {
92  layers[i] = calloc( 1, sizeof( struct layer_struct ) );
93  layers[i]->number_of_nodes = 0;
94  layers[i]->nodes = NULL;
95  layers[i]->fixed = false;
96  }
97 }
98 
99 static void add_node_to_list( Nodeptr node )
100 {
102 }
103 
104 static void add_node_to_layer( Nodeptr node, int layer )
105 {
106 #ifdef DEBUG
107  printf( "-> add_node_to_layer: node = %s, layer = %d\n", node->name, layer );
108 #endif
109  Layerptr layer_ptr = layers[layer];
110 
111  // First node on this layer means fewer layers remain
112  if ( layer_ptr->number_of_nodes == 0 )
114 
115  if ( layer_ptr->number_of_nodes % CAPACITY_INCREMENT == 0 )
116  {
117  layer_ptr->nodes
118  = (Nodeptr *) realloc( layer_ptr->nodes,
119  (layer_ptr->number_of_nodes + CAPACITY_INCREMENT) * sizeof(Nodeptr) );
120  }
121  node->layer = layer;
122  node->position = layer_ptr->number_of_nodes;
123  layer_ptr->nodes[ layer_ptr->number_of_nodes++ ] = node;
124 #ifdef DEBUG
125  printf( "<- add_node_to_layer: position = %d, number_of_nodes = %d\n",
126  node->position, layer_ptr->number_of_nodes );
127 #endif
128 }
129 
130 static void assign_child_layer_and_direction( int parent, int child )
131 {
132  Nodeptr parent_node = master_node_list[ parent ];
133  Nodeptr child_node = master_node_list[ child ];
134  int parent_layer = parent_node->layer;
135 #ifdef DEBUG
136  printf( "-> assign_child_layer_and_direction: parent = %d, child = %d\n"
137  " parent_layer = %d, going_up = %d\n",
138  parent, child, parent_layer, going_up[parent] );
139 #endif
140 
141  going_up[child] = going_up[parent];
142  // handle cases where the path needs to turn around
143  if ( going_up[parent] && parent_layer == number_of_layers - 1 )
144  going_up[child] = false;
145  else if ( ! going_up[parent] && parent_layer == 0 )
146  going_up[child] = true;
147  if ( going_up[child] )
148  child_node->layer = parent_layer + 1;
149  else child_node->layer = parent_layer - 1;
150  add_node_to_layer( child_node, child_node->layer );
151 
152 #ifdef DEBUG
153  printf( "<- assign_child_layer_and_direction: parent = %d, child = %d\n"
154  " child_layer = %d, child_going_up = %d\n",
155  parent, child, child_node->layer, going_up[child] );
156 #endif
157 }
158 
159 /**
160  * Adds an edge between two nodes whose layers are determined and adjacent to
161  * one another
162  */
163 static void add_edge( Nodeptr upper_node, Nodeptr lower_node )
164 {
165 #ifdef DEBUG
166  printf( "-> add_edge: upper_node = (%s,%d,%d), lower_node = (%s,%d,%d)\n",
167  upper_node->name, upper_node->layer, upper_node->position,
168  lower_node->name, lower_node->layer, lower_node->position );
169 #endif
170  assert( upper_node->layer == lower_node->layer + 1 );
171  Edgeptr new_edge = (Edgeptr) calloc( 1, sizeof(struct edge_struct) );
172  new_edge->up_node = upper_node;
173  new_edge->down_node = lower_node;
174  new_edge->fixed = false;
175 
176  // add new edge to master edge list, making room if necessary
177  if ( number_of_edges % CAPACITY_INCREMENT == 0 )
178  {
180  = (Edgeptr *) realloc( master_edge_list,
182  }
183  master_edge_list[ number_of_edges++ ] = new_edge;
184 
185  // add new edge to lower edge list of upper node, making room if necessary
186  if ( upper_node->down_degree % CAPACITY_INCREMENT == 0 )
187  {
188  upper_node->down_edges
189  = (Edgeptr *) realloc( upper_node->down_edges,
190  (upper_node->down_degree + CAPACITY_INCREMENT) * sizeof(Edgeptr) );
191  }
192  upper_node->down_edges[ upper_node->down_degree++ ] = new_edge;
193  // add new edge to upper edge list of lower node, making room if necessary
194  if ( lower_node->up_degree % CAPACITY_INCREMENT == 0 )
195  {
196  lower_node->up_edges
197  = (Edgeptr *) realloc( lower_node->up_edges,
198  lower_node->up_degree + CAPACITY_INCREMENT * sizeof(Edgeptr) );
199  }
200  lower_node->up_edges[ lower_node->up_degree++ ] = new_edge;
201 
202 #ifdef DEBUG
203  printf( "<- add_edge: edge = %s -> %s\n",
204  new_edge->up_node->name, new_edge->down_node->name );
205 #endif
206 }
207 
208 void create_random_tree( int num_nodes,
209  int num_layers,
210  int branching_factor )
211 {
212  assert( num_nodes > 0
213  && num_layers > 1
214  && branching_factor > 0 );
215 
216  number_of_nodes = num_nodes;
217  create_master_node_list( num_nodes );
218  number_of_layers = num_layers;
219  layers_remaining = num_layers;
220  number_of_edges = 0;
221  master_edge_list = NULL;
222 
223  init_layers( num_layers );
224  init_node_directions( num_nodes );
225 
226  // create node 0, put it on layer 0, and make it the current node
227  int current_node_id = 0;
228  Nodeptr current_node = master_node_list[ current_node_id ];
229  add_node_to_layer( current_node, 0 );
230  add_node_to_list( current_node );
231 
232  // create the tree as follows
233  // - take the node at the front of the list (current_node_id)
234  // - choose a degree d in the range [1 .. branching_factor]
235  // - put d new nodes at the rear of the list, assign them to the
236  // appropriate layer and add the appropriate edges
238  {
239  // Need to make sure that there are enough nodes left to ensure that
240  // every layer has nodes: layers_remaining may be 1 even if so; this
241  // ensures that the number of children does not exceed the number of
242  // nodes remaining
243  int nodes_remaining = number_of_nodes - number_of_tree_nodes;
244  int path_length_to_highest_layer = num_layers - 1 - current_node->layer;
245  int branch_limit = branching_factor;
246  // need to leave enough nodes for next node to have access to the top
247  // layer; this may turn out to be <= 0, in which case there should be no
248  // branching
249  if ( layers_remaining > 0 &&
250  branch_limit > nodes_remaining - path_length_to_highest_layer )
251  branch_limit = nodes_remaining - path_length_to_highest_layer;
252  // also, can't have more branches than number of nodes remaining
253  if ( branch_limit > nodes_remaining )
254  branch_limit = nodes_remaining;
255  // finally, smooth out the number of nodes in each layer
256  if ( layers[current_node->layer]->number_of_nodes
257  > num_nodes / num_layers )
258  branch_limit = 1;
259 
260  int max_branches
261  = branching_factor > branch_limit ? branch_limit : branching_factor;
262  int out_degree = 0;
263  if ( max_branches > 0 )
264  out_degree = random() % max_branches;
265  // need to have at least one successor if there are no nodes left
266  if ( out_degree == 0
267  && current_node_id + 1 >= number_of_tree_nodes )
268  out_degree = 1;
269 #ifdef DEBUG
270  printf(
271  " Picking # of children: node = %d, remaining = %d,"
272  " path_length = %d, limit = %d"
273  " max = %d, degree = %d\n",
274  current_node_id,
275  nodes_remaining,
276  path_length_to_highest_layer,
277  branch_limit,
278  max_branches,
279  out_degree
280  );
281 #endif
282  for ( int i = 0; i < out_degree; i++ )
283  {
284  int child_node_id = number_of_tree_nodes;
285  Nodeptr child_node = master_node_list[ child_node_id ];
286  add_node_to_list( child_node );
287 
288  assign_child_layer_and_direction( current_node_id, child_node_id );
289 
290  if ( current_node->layer > child_node->layer )
291  add_edge( current_node, child_node );
292  else
293  add_edge( child_node, current_node );
294  }
295 
296  current_node_id++;
297  current_node = master_node_list[ current_node_id ];
298 
299 #ifdef OMITTED
300  printf( " __ iteration %d: master_node_list, number_of_nodes = %d\n", current_node_id, number_of_tree_nodes );
301  for ( int i = 0; i < number_of_tree_nodes; i++ )
302  printf( " %d(%d,%d)",
303  master_node_list[i]->id,
304  master_node_list[i]->layer,
305  master_node_list[i]->position );
306  printf( "\n" );
307  printf( " master_edge_list, number_of_edges = %d\n", number_of_edges );
308  for ( int i = 0; i < number_of_edges; i++ )
309  printf( " %d->%d",
310  master_edge_list[i]->up_node->id,
312  );
313  printf( "\n" );
314 #endif
315  }
316 }
317 
318 #ifdef TEST
319 /**
320  * For testing
321  */
322 int main( int argc, char * argv[] )
323 {
324  assert( argc == 4 && "nodes layers braching" );
325  int num_nodes = atoi( argv[1] );
326  int num_layers = atoi( argv[2] );
327  int branching = atoi( argv[3] );
328 
329  srandom( 1 );
330 
331  create_random_tree( num_nodes, num_layers, branching );
332 
333  writeDot( "test.dot",
334  "test_graph",
335  "",
338  );
339 
340  writeOrd( "test.ord" );
341 
342  return EXIT_SUCCESS;
343 }
344 #endif
345 
346 /* [Last modified: 2011 06 03 at 19:01:11 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
static Nodeptr create_node(int node_number)
Definition: random_tree.c:55
int preorder_number
Definition: graph.h:91
int id
Definition: graph.h:64
bool * going_up
Definition: random_tree.c:38
char * name
Definition: graph.h:63
Layerptr * layers
Definition: graph_io.c:31
static char name_buffer[MAX_NAME_LENGTH]
Definition: ord.c:49
int number_of_nodes
Definition: graph.h:115
static void create_master_node_list(int num_nodes)
Definition: random_tree.c:78
Edgeptr * down_edges
Definition: graph.h:78
bool marked
Definition: graph.h:90
int position
Definition: graph.h:73
static void init_layers(int num_layers)
Definition: random_tree.c:87
static int number_of_tree_nodes
Definition: random_tree.c:29
struct node_struct * Nodeptr
Definition: graph.h:57
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
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 int layers_remaining
Definition: random_tree.c:36
static void add_node_to_layer(Nodeptr node, int layer)
Definition: random_tree.c:104
int up_degree
Definition: graph.h:74
bool fixed
Definition: graph.h:85
int number_of_nodes
Definition: graph_io.c:27
Definition of functions for reading and writing graphs.
static void init_node_directions(int num_nodes)
Definition: random_tree.c:43
static void add_node_to_list(Nodeptr node)
Definition: random_tree.c:99
int layer
Definition: graph.h:65
static void assign_child_layer_and_direction(int parent, int child)
Definition: random_tree.c:130
int down_degree
Definition: graph.h:75
int up_crossings
Definition: graph.h:86
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.
#define CAPACITY_INCREMENT
Definition: defs.h:36
bool fixed
Definition: graph.h:106
static void add_edge(Nodeptr upper_node, Nodeptr lower_node)
Definition: random_tree.c:163
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
void writeOrd(const char *ord_file)
Definition: graph_io.c:405
int main(int argc, char *argv[])
Definition: add_edges.c:185