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.
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. |
#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 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). |
Dfs& reachedMap | ( | ReachedMap & | m | ) | [inline] |
Dfs& processedMap | ( | ProcessedMap & | m | ) | [inline] |
void init | ( | ) | [inline] |
Initializes the internal data structures.
void addSource | ( | Node | s | ) | [inline] |
Adds a new source node to the set of nodes to be processed.
Arc processNextArc | ( | ) | [inline] |
Processes the next arc.
OutArcIt nextArc | ( | ) | const [inline] |
Next arc to be processed.
INVALID
if the stack is empty. bool emptyQueue | ( | ) | const [inline] |
Returns false
if there are nodes to be processed in the queue (stack).
int queueSize | ( | ) | const [inline] |
Returns the number of the nodes to be processed in the queue (stack).
void start | ( | ) | [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. while ( !d.emptyQueue() ) {
d.processNextArc();
}
void start | ( | Node | t | ) | [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.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.
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.void run | ( | Node | s | ) | [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. d.init(); d.addSource(s); d.start();
bool run | ( | Node | s, |
Node | t | ||
) | [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. d.init(); d.addSource(s); d.start(t);
void run | ( | ) | [inline] |
This method runs the DFS algorithm in order to visit all nodes in the digraph.
d.run()
is just a shortcut of the following code. d.init(); for (NodeIt n(digraph); n != INVALID; ++n) { if (!d.reached(n)) { d.addSource(n); d.start(); } }
Path path | ( | Node | t | ) | const [inline] |
int dist | ( | Node | v | ) | const [inline] |
Arc predArc | ( | Node | v | ) | const [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() and predMap().
Node predNode | ( | Node | v | ) | const [inline] |
const DistMap& distMap | ( | ) | const [inline] |
const PredMap& predMap | ( | ) | const [inline] |