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 init() first, then you can add a source node with addSource() and perform the actual computation with start(). This procedure can be repeated if there are nodes that have not been reached.
|
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.