template<typename GR, typename TR>
class lemon::Dfs< GR, TR >
This class provides an efficient implementation of the DFS algorithm.
There is also a function-type interface for the DFS algorithm, which is convenient in the simplier cases and it can be used easier.
- Template Parameters
-
GR | The type of the digraph the algorithm runs on. The default type is ListDigraph. |
TR | The traits class that defines various types used by the algorithm. By default, it is DfsDefaultTraits<GR>. In most cases, this parameter should not be set directly, consider to use the named template parameters instead. |
|
| 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.
|
|
|
The simplest way to execute the DFS algorithm is to use one of the member functions called run().
If you need better control on the execution, you have to call
|
void | init () |
| Initializes the internal data structures.
|
|
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.
|
|
|
The results of the DFS algorithm can be obtained using these functions.
Either run() or start() should be called before using them.
|
Path | path (Node t) const |
| The DFS path to the given node.
|
|
int | dist (Node v) const |
| The distance of the given node from the root(s).
|
|
Arc | predArc (Node v) const |
| Returns the 'previous arc' of the DFS tree for the given node.
|
|
Node | predNode (Node v) const |
| Returns the 'previous node' of the DFS tree for the given node.
|
|
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 the given node. node is reached from the root(s).
|
|
template<typename GR , typename TR >
template<class ArcBoolMap >
Arc start |
( |
const ArcBoolMap & | am | ) |
|
|
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.
- Parameters
-
am | A bool (or convertible) arc map. The algorithm will stop when it reaches an arc a with am[a] true. |
- Returns
- The reached arc
a
with am[a]
true or INVALID
if no such arc was found.
- Precondition
- init() must be called and a root node should be added with addSource() before using this function.
- Warning
- Contrary to Bfs and Dijkstra,
am
is an arc map, not a node map.