Crossings Minimization  1.0
dfs.c
Go to the documentation of this file.
1 /**
2  * @file dfs.h
3  * @brief interface for function that assigns weights based on depth-first
4  * search
5  * @author Matthias Stallmann
6  * @date 2008/01/03
7  * $Id: dfs.c 2 2011-06-07 19:50:41Z mfms $
8  */
9 
10 #include <stdlib.h>
11 #include <stdio.h>
12 #include "graph.h"
13 #include "dfs.h"
14 
15 static int preorder_number = 0;
16 
17 /**
18  * Visits the given node, assigns it the next preorder number, and
19  * recursively visits all unvisited adjacent nodes; edges to higher-numbered
20  * layers are given precedence.
21  */
22 static void dfs_visit( Nodeptr node );
23 
24 /**
25  * Sets all preorder numbers (weights) to -1 (not visited)
26  */
27 static void initialize_dfs_weights( void )
28 {
29  int layer = 0;
30  for( ; layer < number_of_layers; layer++ )
31  {
32  int position = 0;
33  for( ; position < layers[ layer ]->number_of_nodes; position++ )
34  {
35  Nodeptr node = layers[ layer ]->nodes[ position ];
36  node->weight = -1;
37  }
38  }
39 }
40 
41 /**
42  * Visits (does a dfs_visit) the nodes on the next higher layer to which the
43  * given node is adjacent.
44  */
45 static void visit_upper_edges( Nodeptr node )
46 {
47  int edge_pos = node->up_degree - 1;
48  for( ; edge_pos >= 0; edge_pos-- )
49  {
50  Nodeptr adjacent_node = node->up_edges[ edge_pos ]->up_node;
51  if( adjacent_node->weight == -1 ) dfs_visit( adjacent_node );
52  }
53 }
54 
55 /**
56  * Visits (does a dfs_visit) the nodes on the next lower layer to which the
57  * given node is adjacent.
58  */
59 static void visit_lower_edges( Nodeptr node )
60 {
61  int edge_pos = 0;
62  for( ; edge_pos < node->down_degree; edge_pos++ )
63  {
64  Nodeptr adjacent_node = node->down_edges[ edge_pos ]->down_node;
65  if( adjacent_node->weight == -1 ) dfs_visit( adjacent_node );
66  }
67 }
68 
69 /**
70  * Visits the given node, assigns it the next preorder number, and
71  * recursively visits all unvisited adjacent nodes; edges to higher-numbered
72  * layers are given precedence.
73  */
74 static void dfs_visit( Nodeptr node )
75 {
76 #ifdef DEBUG
77  printf( "| ----> dfs_visit, node = %s\n", node->name );
78 #endif
79  node->weight = preorder_number++;
80  visit_upper_edges( node );
81  visit_lower_edges( node );
82 #ifdef DEBUG
83  printf( "<- | dfs_visit, node = %s, weight = %3.1f\n",
84  node->name, node->weight );
85 #endif
86 }
87 
88 /**
89  * Initiates a depth-first search in each connected component using the
90  * leftmost node in the lowest layer as the first node of the component.
91  * This is the standard outer loop of dfs, and would not be needed if the
92  * graph were connected.
93  */
94 static void dfs( void )
95 {
96  preorder_number = 0;
97  int number_of_components = 0;
98  int size_of_largest_component = 0;
99  // traverse all nodes, starting a new dfs_visit for any node not yet
100  // visited
101  for( int layer = 0; layer < number_of_layers; layer++ )
102  {
103  for( int position = 0; position < layers[ layer ]->number_of_nodes; position++ )
104  {
105  Nodeptr node = layers[ layer ]->nodes[ position ];
106  if( node->weight == -1 )
107  {
108  number_of_components++;
109  int start_preorder_number = preorder_number;
110  dfs_visit( node );
111  int end_preorder_number = preorder_number;
112  int size_of_current_component
113  = end_preorder_number - start_preorder_number;
114  if ( size_of_current_component > size_of_largest_component )
115  size_of_largest_component = size_of_current_component;
116  }
117  }
118  }
119  printf( "dfs done, number_of_components = %d, size_of_largest_component = %d\n",
120  number_of_components, size_of_largest_component );
121 }
122 
123 void assignDfsWeights( void )
124 {
126  dfs();
127 }
128 
129 /* [Last modified: 2011 06 04 at 20:19:23 GMT] */
Nodeptr up_node
Definition: graph.h:98
void assignDfsWeights(void)
Definition: dfs.c:123
static void visit_upper_edges(Nodeptr node)
Definition: dfs.c:45
char * name
Definition: graph.h:63
static void visit_lower_edges(Nodeptr node)
Definition: dfs.c:59
Layerptr * layers
Definition: graph_io.c:31
int number_of_nodes
Definition: graph.h:115
Edgeptr * down_edges
Definition: graph.h:78
interface for function that assigns weights based on depth-first search
static void initialize_dfs_weights(void)
Definition: dfs.c:27
Edgeptr * up_edges
Definition: graph.h:77
static void dfs_visit(Nodeptr node)
Definition: dfs.c:74
int up_degree
Definition: graph.h:74
static void dfs(void)
Definition: dfs.c:94
double weight
Definition: graph.h:82
int down_degree
Definition: graph.h:75
Definition of data structures and access functions for a layered graph.
Nodeptr * nodes
Definition: graph.h:116
static int preorder_number
Definition: dfs.c:15
Nodeptr down_node
Definition: graph.h:99
int number_of_layers
Definition: graph_io.c:28