Crossings Minimization  1.0
random_dag.c File Reference
#include "graph.h"
#include "graph_io.h"
#include "random_tree.h"
#include "random_dag.h"
#include "check_edge_duplication.h"
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <string.h>
#include <assert.h>
Include dependency graph for random_dag.c:

Go to the source code of this file.

Functions

static void add_edge (Nodeptr upper_node, Nodeptr lower_node)
 
static void make_all_current_edges_exist (void)
 
void create_random_dag (int num_nodes, int desired_num_edges, int num_layers, int branching_factor)
 

Function Documentation

◆ add_edge()

static void add_edge ( Nodeptr  upper_node,
Nodeptr  lower_node 
)
static

Adds an edge between two nodes whose layers are determined and adjacent to one another

Todo:
Avoid duplication with the same function in create_random_tree and add_edges

Definition at line 29 of file random_dag.c.

References CAPACITY_INCREMENT, node_struct::down_degree, node_struct::down_edges, edge_struct::down_node, edge_struct::fixed, node_struct::layer, master_edge_list, node_struct::name, number_of_edges, node_struct::position, node_struct::up_degree, node_struct::up_edges, and edge_struct::up_node.

Referenced by create_random_dag().

◆ create_random_dag()

void create_random_dag ( int  num_nodes,
int  num_edges,
int  num_layers,
int  branching_factor 
)

Creates a random dag with the given number of nodes and layers. Assumes that the nodes and layers of the dag have already been created, and that the master_edge_list contains the edges of the backbone tree

Parameters
branching_factorthe number of chidren of a tree node is a random number in the range [1 .. branching_factor]; a large branching factor means that the variance in degree will be larger. Since the tree forms the backbone of the random dag, the same observation applies to the dag

Definition at line 90 of file random_dag.c.

References add_edge(), create_hash_table_for_pairs(), create_random_tree(), destroy_hash_table_for_pairs(), node_struct::id, node_struct::layer, layers, make_all_current_edges_exist(), master_node_list, layer_struct::nodes, number_of_edges, layer_struct::number_of_nodes, number_of_nodes, and pair_already_exists().

Referenced by main().

Here is the call graph for this function:

◆ make_all_current_edges_exist()

static void make_all_current_edges_exist ( void  )
static

Make it so that when the current edges are checked for existence in the future, the correct answer will be given; for use after tree edges are created.

Definition at line 79 of file random_dag.c.

References edge_struct::down_node, node_struct::id, master_edge_list, number_of_edges, pair_already_exists(), and edge_struct::up_node.

Referenced by create_random_dag().

Here is the call graph for this function: