This class provides an efficient implementation of the DFS algorithm.
There is also a functiontype interface for the DFS algorithm, which is convenient in the simplier cases and it can be used easier.
GR  The type of the digraph the algorithm runs on. The default type is ListDigraph. 
#include <lemon/dfs.h>
Classes  
struct  SetDistMap 
Named parameter for setting DistMap type. More...  
struct  SetPredMap 
Named parameter for setting PredMap type. More...  
struct  SetProcessedMap 
Named parameter for setting ProcessedMap type. More...  
struct  SetReachedMap 
Named parameter for setting ReachedMap type. More...  
struct  SetStandardProcessedMap 
Named parameter for setting ProcessedMap type to be Digraph::NodeMap<bool> . More...  
Public Types  
typedef TR::Digraph  Digraph 
The type of the digraph the algorithm runs on.  
typedef TR::PredMap  PredMap 
The type of the map that stores the predecessor arcs of the DFS paths.  
typedef TR::DistMap  DistMap 
The type of the map that stores the distances of the nodes.  
typedef TR::ReachedMap  ReachedMap 
The type of the map that indicates which nodes are reached.  
typedef TR::ProcessedMap  ProcessedMap 
The type of the map that indicates which nodes are processed.  
typedef PredMapPath< Digraph, PredMap >  Path 
The type of the paths.  
typedef TR  Traits 
The traits class of the algorithm.  
Public Member Functions  
Dfs (const Digraph &g)  
Constructor.  
~Dfs ()  
Destructor.  
Dfs &  predMap (PredMap &m) 
Sets the map that stores the predecessor arcs.  
Dfs &  reachedMap (ReachedMap &m) 
Sets the map that indicates which nodes are reached.  
Dfs &  processedMap (ProcessedMap &m) 
Sets the map that indicates which nodes are processed.  
Dfs &  distMap (DistMap &m) 
Sets the map that stores the distances of the nodes.  
Execution Control  
The simplest way to execute the DFS algorithm is to use one of the member functions called run().  
void  init () 
void  addSource (Node s) 
Adds a new source node.  
Arc  processNextArc () 
Processes the next arc.  
OutArcIt  nextArc () const 
Next arc to be processed.  
bool  emptyQueue () const 
Returns false if there are nodes to be processed.  
int  queueSize () const 
Returns the number of the nodes to be processed.  
void  start () 
Executes the algorithm.  
void  start (Node t) 
Executes the algorithm until the given target node is reached.  
template<class ArcBoolMap >  
Arc  start (const ArcBoolMap &am) 
Executes the algorithm until a condition is met.  
void  run (Node s) 
Runs the algorithm from the given source node.  
bool  run (Node s, Node t) 
Finds the DFS path between s and t .  
void  run () 
Runs the algorithm to visit all nodes in the digraph.  
Query Functions  
Path  path (Node t) const 
The DFS path to a node.  
int  dist (Node v) const 
The distance of a node from the root(s).  
Arc  predArc (Node v) const 
Returns the 'previous arc' of the DFS tree for a node.  
Node  predNode (Node v) const 
Returns the 'previous node' of the DFS tree.  
const DistMap &  distMap () const 
Returns a const reference to the node map that stores the distances of the nodes.  
const PredMap &  predMap () const 
Returns a const reference to the node map that stores the predecessor arcs.  
bool  reached (Node v) const 
Checks if a node is reached from the root(s).  

inline 

inline 

inline 
Initializes the internal data structures.

inline 
Adds a new source node to the set of nodes to be processed.

inline 
Processes the next arc.

inline 
Next arc to be processed.
INVALID
if the stack is empty.

inline 
Returns false
if there are nodes to be processed in the queue (stack).

inline 
Returns the number of the nodes to be processed in the queue (stack).

inline 
Executes the algorithm.
This method runs the DFS algorithm from the root node in order to compute the DFS path to each node.
The algorithm computes
d.start()
is just a shortcut of the following code.

inline 
Executes the algorithm until the given target node is reached.
This method runs the DFS algorithm from the root node in order to compute the DFS path to t
.
The algorithm computes
t
,t
from the root in the DFS tree.

inline 
Executes the algorithm until a condition is met.
This method runs the DFS algorithm from the root node until an arc a
with am[a]
true is found.
am  A bool (or convertible) arc map. The algorithm will stop when it reaches an arc a with am[a] true. 
a
with am[a]
true or INVALID
if no such arc was found.

inline 
This method runs the DFS algorithm from node s
in order to compute the DFS path to each node.
The algorithm computes
d.run(s)
is just a shortcut of the following code.

inline 
This method runs the DFS algorithm from node s
in order to compute the DFS path to node t
(it stops searching when t
is processed)
true
if t
is reachable form s
.d.run(s,t)
is just a shortcut of the following code.

inline 
This method runs the DFS algorithm in order to compute the DFS path to each node.
The algorithm computes
d.run()
is just a shortcut of the following code.

inline 

inline 

inline 
This function returns the 'previous arc' of the DFS tree for the node v
, i.e. it returns the last arc of a DFS path from a root to v
. It is INVALID
if v
is not reached from the root(s) or if v
is a root.
The DFS tree used here is equal to the DFS tree used in predNode().

inline 
This function returns the 'previous node' of the DFS tree for the node v
, i.e. it returns the last but one node from a DFS path from a root to v
. It is INVALID
if v
is not reached from the root(s) or if v
is a root.
The DFS tree used here is equal to the DFS tree used in predArc().

inline 

inline 