Graph/DepthFirstSearch/dfs.cxx File Reference

Contains the Depth-First Search implementation

Implementation of Depth First Search algorithm over a graph. More...

#include "dfs.h"

Functions

void dfs_visit (Graph const &graph, int u, vector< int > &d, vector< int > &f, vector< int > &pred, vector< vertexColor > &color, int &ctr, list< EdgeLabel > &labels)
 Visit a vertex, u, in the graph and update information.
void dfs_search (Graph const &graph, int s, vector< int > &d, vector< int > &f, vector< int > &pred, list< EdgeLabel > &labels)
 Perform Depth First Search starting from vertex s, and compute the values d[u] (when vertex u was first discovered), f[u] (when all vertices adjacent to u have been processed), pred[u] (the predecessor vertex to u in resulting depth-first search forest), and label edges according to their type.


Detailed Description

Contains the Depth-First Search implementation

Implementation of Depth First Search algorithm over a graph.

Author:
George Heineman
Date:
6/15/08

Function Documentation

void dfs_search ( Graph const &  graph,
int  s,
vector< int > &  d,
vector< int > &  f,
vector< int > &  pred,
list< EdgeLabel > &  labels 
)

Perform Depth First Search starting from vertex s, and compute the values d[u] (when vertex u was first discovered), f[u] (when all vertices adjacent to u have been processed), pred[u] (the predecessor vertex to u in resulting depth-first search forest), and label edges according to their type.

Parameters:
graph the graph being searched.
s the vertex to use as the source vertex.
d array of counter values when each vertex is discovered.
f array of counter values when each vertex is finished.
pred array of previous vertices in the depth-first search tree.
labels structure to store all edge labels.

void dfs_visit ( Graph const &  graph,
int  u,
vector< int > &  d,
vector< int > &  f,
vector< int > &  pred,
vector< vertexColor > &  color,
int &  ctr,
list< EdgeLabel > &  labels 
)

Visit a vertex, u, in the graph and update information.

Parameters:
graph the graph being searched.
u the vertex being visited.
d array of counter values when each vertex is discovered.
f array of counter values when each vertex is finished.
pred array of previous vertices in the depth-first search tree.
color array of vertex colors in the depth-first search tree.
ctr counter to use for assigning d[] and f[] values.
labels structure to store all edge labels.

Algorithm Development Kit 1.0