Main Page | Modules | Namespace List | Class Hierarchy | Alphabetical List | Class List | Directories | File List | Namespace Members | Class Members | File Members | Related Pages

Dfs Class Template Reference
[Path and Flow Algorithms]

#include <lemon/dfs.h>

List of all members.


Detailed Description

template<typename GR>
class lemon::Dfs< GR >

This class provides an efficient implementation of DFS algorithm.

Parameters:
GR The graph type the algorithm runs on.
Author:
Alpar Juttner

Definition at line 47 of file dfs.h.

Public Types

typedef GR Graph
 The type of the underlying graph.
typedef Graph::Node Node
 
typedef Graph::NodeIt NodeIt
 
typedef Graph::Edge Edge
 
typedef Graph::OutEdgeIt OutEdgeIt
 
typedef Graph::template NodeMap<
Edge
PredMap
 The type of the map that stores the last edges of the paths on the DFS tree.
typedef Graph::template NodeMap<
Node
PredNodeMap
 The type of the map that stores the last but one nodes of the paths on the DFS tree.
typedef Graph::template NodeMap<
int > 
DistMap
 The type of the map that stores the dists of the nodes on the DFS tree.

Public Member Functions

 Dfs (const Graph &_G)
 Constructor.
 ~Dfs ()
 Destructor.
DfssetPredMap (PredMap &m)
 Sets the map storing the predecessor edges.
DfssetPredNodeMap (PredNodeMap &m)
 Sets the map storing the predecessor nodes.
DfssetDistMap (DistMap &m)
 Sets the map storing the distances calculated by the algorithm.
void run (Node s)
 Runs DFS algorithm from node s.
int dist (Node v) const
 The distance of a node from the root on the DFS tree.
Edge pred (Node v) const
 Returns the 'previous edge' of the DFS path tree.
Node predNode (Node v) const
 Returns the 'previous node' of the DFS tree.
const DistMapdistMap () const
 Returns a reference to the NodeMap of distances on the DFS tree.
const PredMappredMap () const
 Returns a reference to the DFS tree map.
const PredNodeMappredNodeMap () const
 Returns a reference to the map of last but one nodes of the DFS tree.
bool reached (Node v)
 Checks if a node is reachable from the root.


Constructor & Destructor Documentation

Dfs const Graph _G  )  [inline]
 

Parameters:
_G the graph the algorithm will run on.

Definition at line 111 of file dfs.h.


Member Function Documentation

Dfs& setPredMap PredMap m  )  [inline]
 

Sets the map storing the predecessor edges. If you don't use this function before calling run(), it will allocate one. The destuctor deallocates this automatically allocated map, of course.

Returns:
(*this)

Definition at line 133 of file dfs.h.

Dfs& setPredNodeMap PredNodeMap m  )  [inline]
 

Sets the map storing the predecessor nodes. If you don't use this function before calling run(), it will allocate one. The destuctor deallocates this automatically allocated map, of course.

Returns:
(*this)

Definition at line 150 of file dfs.h.

Dfs& setDistMap DistMap m  )  [inline]
 

Sets the map storing the distances calculated by the algorithm. If you don't use this function before calling run(), it will allocate one. The destuctor deallocates this automatically allocated map, of course.

Returns:
(*this)

Definition at line 167 of file dfs.h.

void run Node  s  )  [inline]
 

This method runs the DFS algorithm from a root node s in order to compute

  • a DFS tree and
  • the distance of each node from the root on this tree.

Definition at line 185 of file dfs.h.

Here is the call graph for this function:

int dist Node  v  )  const [inline]
 

Returns the distance of a node from the root on the DFS tree.

Precondition:
run() must be called before using this function.
Warning:
If node v in unreachable from the root the return value of this funcion is undefined.

Definition at line 227 of file dfs.h.

Edge pred Node  v  )  const [inline]
 

For a node v it returns the last edge of the path on the DFS tree from the root to v. It is INVALID if v is unreachable from the root or if v=s. The DFS tree used here is equal to the DFS tree used in predNode(Node v).

Precondition:
run() must be called before using this function.

Definition at line 238 of file dfs.h.

Node predNode Node  v  )  const [inline]
 

For a node v it returns the 'previous node' on the DFS tree, i.e. it returns the last but one node of the path from the root to /v on the DFS tree. It is INVALID if v is unreachable from the root or if v=s.

Precondition:
run() must be called before using this function.

Definition at line 249 of file dfs.h.

const DistMap& distMap  )  const [inline]
 

Returns a reference to the NodeMap of distances on the DFS tree.

Precondition:
run() must be called before using this function.

Definition at line 256 of file dfs.h.

const PredMap& predMap  )  const [inline]
 

Returns a reference to the NodeMap of the edges of the DFS tree.

Precondition:
run() must be called before using this function.

Definition at line 263 of file dfs.h.

const PredNodeMap& predNodeMap  )  const [inline]
 

Returns a reference to the NodeMap of the last but one nodes of the paths on the DFS tree.

Precondition:
run() must be called before using this function.

Definition at line 271 of file dfs.h.

bool reached Node  v  )  [inline]
 

Returns true if v is reachable from the root.

Note:
The root node is reported to be reached!
Precondition:
run() must be called before using this function.

Definition at line 280 of file dfs.h.


The documentation for this class was generated from the following file:
Generated on Sat Mar 19 10:58:48 2005 for LEMON by  doxygen 1.4.1