Crossings Minimization  1.0
random_tree.c File Reference

Module for creating a random dag with a given number of nodes and layers. First a tree is created to form the backbone of the dag. More...

#include "graph.h"
#include "graph_io.h"
#include "random_tree.h"
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <string.h>
#include <assert.h>
Include dependency graph for random_tree.c:

Go to the source code of this file.

Functions

static void init_node_directions (int num_nodes)
 
static Nodeptr create_node (int node_number)
 
static void create_master_node_list (int num_nodes)
 
static void init_layers (int num_layers)
 
static void add_node_to_list (Nodeptr node)
 
static void add_node_to_layer (Nodeptr node, int layer)
 
static void assign_child_layer_and_direction (int parent, int child)
 
static void add_edge (Nodeptr upper_node, Nodeptr lower_node)
 
void create_random_tree (int num_nodes, int num_layers, int branching_factor)
 

Variables

static int number_of_tree_nodes = 0
 
static int layers_remaining
 
bool * going_up = NULL
 

Detailed Description

Module for creating a random dag with a given number of nodes and layers. First a tree is created to form the backbone of the dag.

Module for creating a random tree with a given number of nodes and layers.

Author
Matt Stallmann
Date
2011/06/01
Id
random_dag.c 27 2011-07-09 21:22:42Z mfms

Paths in the tree move in a single direction until they run out of layers and then continue the process switching directions only when necessary.

Author
Matt Stallmann
Date
2011/05/30
Id
random_tree.c 2 2011-06-07 19:50:41Z mfms

Definition in file random_tree.c.

Function Documentation

◆ add_edge()

static void add_edge ( Nodeptr  upper_node,
Nodeptr  lower_node 
)
static

◆ add_node_to_layer()

static void add_node_to_layer ( Nodeptr  node,
int  layer 
)
static

◆ add_node_to_list()

static void add_node_to_list ( Nodeptr  node)
static

Definition at line 99 of file random_tree.c.

References master_node_list, and number_of_tree_nodes.

Referenced by create_random_tree().

◆ assign_child_layer_and_direction()

static void assign_child_layer_and_direction ( int  parent,
int  child 
)
static

Definition at line 130 of file random_tree.c.

References add_node_to_layer(), going_up, node_struct::layer, master_node_list, and number_of_layers.

Referenced by create_random_tree().

Here is the call graph for this function:

◆ create_master_node_list()

static void create_master_node_list ( int  num_nodes)
static

Creates and initializes the master node list

Definition at line 78 of file random_tree.c.

References create_node(), and master_node_list.

Referenced by create_random_tree().

Here is the call graph for this function:

◆ create_node()

static Nodeptr create_node ( int  node_number)
static

initializes the data for a node at a given position in the master node list

Parameters
node_numberthe position of the node
Returns
a pointer to the new node

Definition at line 55 of file random_tree.c.

References node_struct::down_crossings, node_struct::down_degree, node_struct::down_edges, node_struct::fixed, node_struct::id, node_struct::layer, node_struct::marked, MAX_NAME_LENGTH, node_struct::name, name_buffer, node_struct::position, node_struct::preorder_number, node_struct::up_crossings, node_struct::up_degree, and node_struct::up_edges.

Referenced by create_master_node_list().

◆ create_random_tree()

void create_random_tree ( int  num_nodes,
int  num_layers,
int  branching_factor 
)

Creates a random tree with the given number of nodes and layers.

Parameters
branching_factorthe number of chidren of a node is a random number in the range [1 .. branching_factor]; a large branching factor means that the variance in degree will be larger.

Definition at line 208 of file random_tree.c.

References add_edge(), add_node_to_layer(), add_node_to_list(), assign_child_layer_and_direction(), create_master_node_list(), create_random_tree(), edge_struct::down_node, node_struct::id, init_layers(), init_node_directions(), node_struct::layer, layers, layers_remaining, main(), master_edge_list, master_node_list, number_of_edges, number_of_layers, layer_struct::number_of_nodes, number_of_nodes, number_of_tree_nodes, writeDot(), and writeOrd().

Referenced by create_random_dag(), and create_random_tree().

Here is the call graph for this function:

◆ init_layers()

static void init_layers ( int  num_layers)
static

◆ init_node_directions()

static void init_node_directions ( int  num_nodes)
static

Assigns a direction to each node, initially up

Definition at line 43 of file random_tree.c.

References going_up.

Referenced by create_random_tree().

Variable Documentation

◆ going_up

bool* going_up = NULL

Definition at line 38 of file random_tree.c.

Referenced by assign_child_layer_and_direction(), and init_node_directions().

◆ layers_remaining

int layers_remaining
static

The number of layers that have no nodes on them. Used to ensure that branching does not cause the number of layers to be less than what was requested.

Definition at line 36 of file random_tree.c.

Referenced by add_node_to_layer(), and create_random_tree().

◆ number_of_tree_nodes

int number_of_tree_nodes = 0
static

New nodes randomly selected to be adjacent to the current node are put at the rear of the master node list; this global variable keeps track of that rear position; this rear position also determines the number of nodes that have been added to the tree, hence the name

Definition at line 29 of file random_tree.c.

Referenced by add_node_to_list(), and create_random_tree().