DfsVisit< _Graph, _Visitor, _Traits > Class Template Reference
[Graph Search]

---

Detailed Description

template<typename _Graph, typename _Visitor, typename _Traits>
class lemon::DfsVisit< _Graph, _Visitor, _Traits >

This class provides an efficient implementation of the DFS algorithm with visitor interface.

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.

Parameters:

	_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.

Author:

Jacint Szabo, Alpar Juttner and Balazs Dezso

#include <lemon/dfs.h>

List of all members.

Classes
struct	DefReachedMap
class	UninitializedParameter
	Exception for uninitialized parameters. More...
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 ()
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 ()
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 >
Edge	start (const EM &em)
	Executes the algorithm until a condition is met.
void	run (Node s)
	Runs DFSVisit algorithm from node s.
void	run ()
	Runs DFSVisit algorithm to visit all nodes in the graph.
Query Functions
Checks if a node is reachable from the root. 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. Returns true if v is reachable from the root(s). Warning: The source nodes are inditated as unreachable. Precondition: Either run() or start() must be called before using this function.
bool	reached (Node v)
Private Member Functions
void	create_maps ()
Private Attributes
const Graph *	_graph
	Pointer to the underlying graph.
Visitor *	_visitor
	Pointer to the visitor object.
ReachedMap *	_reached
	Pointer to the map of reached status of the nodes.
bool	local_reached
	Indicates if _reached is locally allocated (true) or not.

---

Constructor & Destructor Documentation

DfsVisit	(	const Graph &	graph,
		Visitor &	visitor
	)			[inline]

Constructor.

Parameters:

	graph	the graph the algorithm will run on.
	visitor	The visitor of the algorithm.

~DfsVisit

(

)

[inline]

Destructor.

---

Member Function Documentation

void create_maps

(

)

[inline, private]

Creates the maps if necessary.

DfsVisit& 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.

Returns:

(*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.

Returns:

The processed edge.

Precondition:

The stack must not be empty!

Edge nextEdge

(

)

[inline]

Next edge to be processed.

Returns:

The next edge to be processed or INVALID if the stack is empty.

bool emptyQueue

(

)

[inline]

Returns false if there are nodes to be processed in the queue

int queueSize

(

)

[inline]

Returns the number of the nodes to be processed in the queue.

void start

(

)

[inline]

Executes the algorithm.

Precondition:

init() must be called and at least one node should be added with addSource() before using this function.

void start

(

Node

dest

)

[inline]

Executes the algorithm until dest is reached.

Precondition:

init() must be called and at least one node should be added with addSource() before using this function.

Edge start

(

const EM &

em

)

[inline]

Executes the algorithm until a condition is met.

Precondition:

init() must be called and at least one node should be added with addSource() before using this function.

Parameters:

em

must be a bool (or convertible) edge map. The algorithm will stop when it reaches an edge e with em[e] true.

Returns:

The reached edge e with em[e] true or INVALID if no such edge was found.

Warning:

Contrary to Bfs and Dijkstra, em is an edge map, not a node map.

void run

(

Node

s

)

[inline]

This method runs the DFS algorithm from a root node s.

Note:

d.run(s) is just a shortcut of the following code.

          d.init();
          d.addSource(s);
          d.start();

void run

(

)

[inline]

This method runs the DFS algorithm in order to compute the DFS path to each node. The algorithm computes

• The DFS tree.
• The distance of each node from the root in the DFS tree.

Note:

d.run() is just a shortcut of the following code.

         d.init();
         for (NodeIt it(graph); it != INVALID; ++it) {
           if (!d.reached(it)) {
             d.addSource(it);
             d.start();
           }
         }