Crossings Minimization  1.0
dfs.c File Reference
#include <stdlib.h>
#include <stdio.h>
#include "graph.h"
#include "dfs.h"
Include dependency graph for dfs.c:

Go to the source code of this file.

Functions

static void dfs_visit (Nodeptr node)
 
static void initialize_dfs_weights (void)
 
static void visit_upper_edges (Nodeptr node)
 
static void visit_lower_edges (Nodeptr node)
 
static void dfs (void)
 
void assignDfsWeights (void)
 

Variables

static int preorder_number = 0
 

Function Documentation

◆ assignDfsWeights()

void assignDfsWeights ( void  )

Assigns weights to nodes based on their preorder number in a depth-first search that starts at the first node on the lowest layer.

Definition at line 123 of file dfs.c.

References dfs(), and initialize_dfs_weights().

Referenced by depthFirstSearch().

Here is the call graph for this function:

◆ dfs()

static void dfs ( void  )
static

Initiates a depth-first search in each connected component using the leftmost node in the lowest layer as the first node of the component. This is the standard outer loop of dfs, and would not be needed if the graph were connected.

Definition at line 94 of file dfs.c.

References dfs_visit(), layers, layer_struct::nodes, number_of_layers, layer_struct::number_of_nodes, preorder_number, and node_struct::weight.

Referenced by assignDfsWeights().

Here is the call graph for this function:

◆ dfs_visit()

static void dfs_visit ( Nodeptr  node)
static

Visits the given node, assigns it the next preorder number, and recursively visits all unvisited adjacent nodes; edges to higher-numbered layers are given precedence.

Definition at line 74 of file dfs.c.

References node_struct::name, preorder_number, visit_lower_edges(), visit_upper_edges(), and node_struct::weight.

Referenced by dfs(), visit_lower_edges(), and visit_upper_edges().

Here is the call graph for this function:

◆ initialize_dfs_weights()

static void initialize_dfs_weights ( void  )
static

Sets all preorder numbers (weights) to -1 (not visited)

Definition at line 27 of file dfs.c.

References layers, layer_struct::nodes, number_of_layers, layer_struct::number_of_nodes, and node_struct::weight.

Referenced by assignDfsWeights().

◆ visit_lower_edges()

static void visit_lower_edges ( Nodeptr  node)
static

Visits (does a dfs_visit) the nodes on the next lower layer to which the given node is adjacent.

Definition at line 59 of file dfs.c.

References dfs_visit(), node_struct::down_degree, node_struct::down_edges, edge_struct::down_node, and node_struct::weight.

Referenced by dfs_visit().

Here is the call graph for this function:

◆ visit_upper_edges()

static void visit_upper_edges ( Nodeptr  node)
static

Visits (does a dfs_visit) the nodes on the next higher layer to which the given node is adjacent.

Definition at line 45 of file dfs.c.

References dfs_visit(), node_struct::up_degree, node_struct::up_edges, edge_struct::up_node, and node_struct::weight.

Referenced by dfs_visit().

Here is the call graph for this function:

Variable Documentation

◆ preorder_number

int preorder_number = 0
static

Definition at line 15 of file dfs.c.

Referenced by dfs(), and dfs_visit().