#include <lemon/dfs.h>
The DfsVisit class provides an alternative interface to the Dfs class. It works with callback mechanism, the DfsVisit object calls on every dfs event the Visitor
class member functions.
_Graph | The graph type the algorithm runs on. The default value is ListGraph. The value of _Graph is not used directly by Dfs, it is only passed to DfsDefaultTraits. | |
_Visitor | The Visitor object for the algorithm. The DfsVisitor<_Graph> is an empty Visitor which does not observe the Dfs events. If you want to observe the dfs events you should implement your own Visitor class. | |
_Traits | Traits class to set various data types used by the algorithm. The default traits class is DfsVisitDefaultTraits<_Graph>. See DfsVisitDefaultTraits for the documentation of a Dfs visit traits class. |
Public Types | |
typedef Traits::ReachedMap | ReachedMap |
The type of the map indicating which nodes are reached. | |
Public Member Functions | |
DfsVisit (const Graph &graph, Visitor &visitor) | |
Constructor. | |
~DfsVisit () | |
Destructor. | |
DfsVisit & | reachedMap (ReachedMap &m) |
Sets the map indicating if a node is reached. | |
Execution control | |
The simplest way to execute the algorithm is to use one of the member functions called run (...). If you need more control on the execution, first you must call init(), then you can adda source node with addSource(). Finally start() will perform the actual path computation. | |
void | init () |
Initializes the internal data structures. | |
void | addSource (Node s) |
Adds a new source node. | |
Edge | processNextEdge () |
Processes the next edge. | |
Edge | nextEdge () |
Next edge to be processed. | |
bool | emptyQueue () |
Returns false if there are nodes to be processed in the queue. | |
int | queueSize () |
Returns the number of the nodes to be processed. | |
void | start () |
Executes the algorithm. | |
void | start (Node dest) |
Executes the algorithm until dest is reached. | |
template<typename EM> | |
void | start (const EM &em) |
Executes the algorithm until a condition is met. | |
void | run (Node s) |
Runs DFS algorithm from node s . | |
Query Functions | |
Checks if a node is reachable from the root.
The result of the DFS algorithm can be obtained using these functions.
Returns
| |
bool | reached (Node v) |
Classes | |
struct | DefReachedMap |
Named parameter for setting ReachedMap type More... | |
class | UninitializedParameter |
Exception for uninitialized parameters. More... |
|
Constructor.
|
|
Destructor. |
|
Sets the map indicating if a node is reached. If you don't use this function before calling run(), it will allocate one. The destuctor deallocates this automatically allocated map, of course.
|
|
Initializes the internal data structures. |
|
Adds a new source node to the set of nodes to be processed. |
|
Processes the next edge.
|
|
Next edge to be processed.
|
|
Returns |
|
Returns the number of the nodes to be processed in the queue. |
|
Executes the algorithm.
|
|
Executes the algorithm until
|
|
Executes the algorithm until a condition is met.
|
|
This method runs the DFS algorithm from a root node
|