#include <lemon/dfs.h>
Inherited by Dfs::DefPredMap, Dfs::DefProcessedMap, Dfs::DefProcessedMapToBeDefaultMap, and Dfs::DefReachedMap.
Inheritance diagram for Dfs:
GR | The graph type the algorithm runs on. The default value is ListGraph. The value of GR is not used directly by Dfs, it is only passed to DfsDefaultTraits. | |
TR | Traits class to set various data types used by the algorithm. The default traits class is DfsDefaultTraits<GR>. See DfsDefaultTraits for the documentation of a Dfs traits class. |
Public Types | |
typedef TR::Graph | Graph |
The type of the underlying graph. | |
typedef Graph::Node | Node |
| |
typedef Graph::NodeIt | NodeIt |
| |
typedef Graph::Edge | Edge |
| |
typedef Graph::OutEdgeIt | OutEdgeIt |
| |
typedef TR::PredMap | PredMap |
The type of the map that stores the last edges of the DFS paths. | |
typedef TR::ReachedMap | ReachedMap |
The type of the map indicating which nodes are reached. | |
typedef TR::ProcessedMap | ProcessedMap |
The type of the map indicating which nodes are processed. | |
typedef TR::DistMap | DistMap |
The type of the map that stores the dists of the nodes. | |
Public Member Functions | |
Dfs (const Graph &_G) | |
Constructor. | |
~Dfs () | |
Destructor. | |
Dfs & | predMap (PredMap &m) |
Sets the map storing the predecessor edges. | |
Dfs & | distMap (DistMap &m) |
Sets the map storing the distances calculated by the algorithm. | |
Dfs & | reachedMap (ReachedMap &m) |
Sets the map indicating if a node is reached. | |
Dfs & | processedMap (ProcessedMap &m) |
Sets the map indicating if a node is processed. | |
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 add a 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. | |
OutEdgeIt | 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 in the queue. | |
void | start () |
Executes the algorithm. | |
void | start (Node dest) |
Executes the algorithm until dest is reached. | |
template<class EM> | |
void | start (const EM &em) |
Executes the algorithm until a condition is met. | |
void | run () |
Runs DFS algorithm to visit all nodes in the graph. | |
void | run (Node s) |
Runs DFS algorithm from node s . | |
int | run (Node s, Node t) |
Finds the DFS path between s and t . | |
Query Functions | |
The result of the DFS algorithm can be obtained using these functions. Before the use of these functions, either run() or start() must be called. | |
template<class P> | |
bool | getPath (P &p, Node t) |
Copies the path to t on the DFS tree into p . | |
int | dist (Node v) const |
The distance of a node from the root(s). | |
Edge | predEdge (Node v) const |
Returns the 'previous edge' of the DFS tree. | |
Node | predNode (Node v) const |
Returns the 'previous node' of the DFS tree. | |
const DistMap & | distMap () const |
Returns a reference to the NodeMap of distances. | |
const PredMap & | predMap () const |
Returns a reference to the DFS edge-tree map. | |
bool | reached (Node v) |
Checks if a node is reachable from the root. | |
Private Member Functions | |
void | create_maps () |
Private Attributes | |
const Graph * | G |
Pointer to the underlying graph. | |
PredMap * | _pred |
Pointer to the map of predecessors edges. | |
bool | local_pred |
Indicates if _pred is locally allocated (true ) or not. | |
DistMap * | _dist |
Pointer to the map of distances. | |
bool | local_dist |
Indicates if _dist is locally allocated (true ) or not. | |
ReachedMap * | _reached |
Pointer to the map of reached status of the nodes. | |
bool | local_reached |
Indicates if _reached is locally allocated (true ) or not. | |
ProcessedMap * | _processed |
Pointer to the map of processed status of the nodes. | |
bool | local_processed |
Indicates if _processed is locally allocated (true ) or not. | |
Classes | |
struct | DefDistMap |
Named parameter for setting DistMap type More... | |
struct | DefPredMap |
Named parameter for setting PredMap type More... | |
struct | DefProcessedMap |
Named parameter for setting ProcessedMap type More... | |
class | DefProcessedMapToBeDefaultMap |
Named parameter for setting the ProcessedMap type to be Graph::NodeMap<bool>. More... | |
struct | DefReachedMap |
Named parameter for setting ReachedMap type More... | |
class | UninitializedParameter |
Exception for uninitialized parameters. More... |
void create_maps | ( | ) | [inline, private] |
Sets the map storing the predecessor edges. If you don't use this function before calling run(), it will allocate one. The destuctor deallocates this automatically allocated map, of course.
(*this)
Sets the map storing the distances calculated by the algorithm. If you don't use this function before calling run(), it will allocate one. The destuctor deallocates this automatically allocated map, of course.
(*this)
Dfs& reachedMap | ( | ReachedMap & | m | ) | [inline] |
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.
(*this)
Dfs& processedMap | ( | ProcessedMap & | m | ) | [inline] |
Sets the map indicating if a node is processed. If you don't use this function before calling run(), it will allocate one. The destuctor deallocates this automatically allocated map, of course.
(*this)
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.
Edge processNextEdge | ( | ) | [inline] |
Processes the next edge.
OutEdgeIt nextEdge | ( | ) | [inline] |
Next edge to be processed.
bool emptyQueue | ( | ) | [inline] |
Returns false
if there are nodes to be processed in the queue
void start | ( | ) | [inline] |
Executes the algorithm.
void start | ( | Node | dest | ) | [inline] |
Executes the algorithm until dest
is reached.
dest
. The algorithm computesdest
.dest
from the root(s) in the DFS tree. void start | ( | const EM & | em | ) | [inline] |
Executes the algorithm until a condition is met.
em | must be a bool (or convertible) edge map. The algorithm will stop when it reaches an edge e with em[e]==true
|
void run | ( | ) | [inline] |
This method runs the DFS algorithm in order to compute the DFS path to each node. The algorithm computes
void run | ( | Node | s | ) | [inline] |
This method runs the DFS algorithm from a root node s
in order to compute the DFS path to each node. The algorithm computes
d.init(); d.addSource(s); d.start();
Finds the DFS path between s
and t
.
d.init(); d.addSource(s); d.start(t);
bool getPath | ( | P & | p, | |
Node | t | |||
) | [inline] |
This function copies the path to t
on the DFS tree into p
. If t
is a source itself or unreachable, then it does not alter p
.
true
if a path to t
was actually copied to p
, false
otherwise. int dist | ( | Node | v | ) | const [inline] |
Returns the distance of a node from the root(s).
v
is unreachable from the root(s) then the return value of this funcion is undefined.
For a node v
it returns the 'previous edge' of the DFS path, i.e. it returns the last edge of a DFS path from the root(s) to v
. It is INVALID if v
is unreachable from the root(s) or v
is a root. The DFS tree used here is equal to the DFS tree used in predNode().
For a node v
it returns the 'previous node' of the DFS tree, i.e. it returns the last but one node from a DFS path from the root(s) to v
. It is INVALID if v
is unreachable from the root(s) or if v
itself a root. The DFS tree used here is equal to the DFS tree used in predEdge().
const DistMap& distMap | ( | ) | const [inline] |
const PredMap& predMap | ( | ) | const [inline] |
bool reached | ( | Node | v | ) | [inline] |