BfsVisit

Declared in lemon/bfs.h, in the group Graph Search; the same class on the Doxygen site.

template< typename GR , typename VS , typename TR >
class BfsVisit

BFS algorithm class with visitor interface.

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

The BfsVisit class provides an alternative interface to the Bfs class. It works with callback mechanism, the BfsVisit object calls the member functions of the Visitor class on every BFS event.

This interface of the BFS algorithm should be used in special cases when extra actions have to be performed in connection with certain events of the BFS algorithm. Otherwise consider to use Bfs or bfs() instead.

Template Parameters:
  • GR – The type of the digraph the algorithm runs on. The default type is ListDigraph. The value of GR is not used directly by BfsVisit, it is only passed to BfsVisitDefaultTraits.

  • VS – The Visitor type that is used by the algorithm. BfsVisitor< GR > is an empty visitor, which does not observe the BFS events. If you want to observe the BFS events, you should implement your own visitor class.

  • TR – The traits class that defines various types used by the algorithm. By default, it is BfsVisitDefaultTraits< GR >. In most cases, this parameter should not be set directly, consider to use the named template parameters instead.

Execution Control

The simplest way to execute the BFS 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 several source nodes with addSource(). Finally the actual path computation can be performed with one of the start() functions.

inline void init()

Initializes the internal data structures.

inline void addSource( Node s )

Adds a new source node.

Adds a new source node to the set of nodes to be processed.

inline Node processNextNode()

Processes the next node.

Returns:

The processed node.

Pre:

The queue must not be empty.

inline Node processNextNode( Node target , bool & reach )

Processes the next node.

Processes the next node and checks if the given target node is reached. If the target node is reachable from the processed node, then the reach parameter will be set to true.

Parameters:
  • target – The target node.

  • reach – [inout] Indicates if the target node is reached. It should be initially false.

Returns:

The processed node.

Pre:

The queue must not be empty.

template< typename NM >
inline Node processNextNode( const NM & nm , Node & rnode )

Processes the next node.

Processes the next node and checks if at least one of reached nodes has true value in the nm node map. If one node with true value is reachable from the processed node, then the rnode parameter will be set to the first of such nodes.

Parameters:
  • nm – A bool (or convertible) node map that indicates the possible targets.

  • rnode – [inout] The reached target node. It should be initially INVALID.

Returns:

The processed node.

Pre:

The queue must not be empty.

inline Node nextNode() const

The next node to be processed.

Returns the next node to be processed or INVALID if the queue is empty.

inline bool emptyQueue() const

Returns false if there are nodes to be processed.

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

inline int queueSize() const

Returns the number of the nodes to be processed.

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

inline void start()

Executes the algorithm.

This method runs the BFS algorithm from the root node(s) in order to compute the shortest path to each node.

The algorithm computes

  • the shortest path tree (forest),

  • the distance of each node from the root(s).

Note

b.start() is just a shortcut of the following code.

while( ! b.emptyQueue() ) {
 b.processNextNode();
 }

Pre:

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

inline void start( Node t )

Executes the algorithm until the given target node is reached.

This method runs the BFS algorithm from the root node(s) in order to compute the shortest path to t.

The algorithm computes

  • the shortest path to t,

  • the distance of t from the root(s).

Note

b.start(t) is just a shortcut of the following code.

bool reach = false;
while( ! b.emptyQueue() && ! reach ) {
 b.processNextNode( t , reach );
 }

Pre:

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

template< typename NM >
inline Node start( const NM & nm )

Executes the algorithm until a condition is met.

This method runs the BFS algorithm from the root node(s) in order to compute the shortest path to a node v with nm[v] true, if such a node can be found.

Note

b.start(nm) is just a shortcut of the following code.

Node rnode = INVALID;
while( ! b.emptyQueue() && rnode == INVALID ) {
 b.processNextNode( nm , rnode );
 }
return( rnode );

Parameters:

nm – must be a bool (or convertible) node map. The algorithm will stop when it reaches a node v with nm[v] true.

Returns:

The reached node v with nm[v] true or INVALID if no such node was found.

Pre:

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

inline void run( Node s )

Runs the algorithm from the given source node.

This method runs the BFS algorithm from node s in order to compute the shortest path to each node.

The algorithm computes

  • the shortest path tree,

  • the distance of each node from the root.

Note

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

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

inline bool run( Node s , Node t )

Finds the shortest path between s and t.

This method runs the BFS algorithm from node s in order to compute the shortest path to node t (it stops searching when t is reached).

Note

Apart from the return value, b.run(s,t) is just a shortcut of the following code.

b.init();
b.addSource( s );
b.start( t );

Returns:

true if t is reachable form s.

inline void run()

Runs the algorithm to visit all nodes in the digraph.

This method runs the BFS algorithm in order to visit all nodes in the digraph.

Note

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

b.init();
for( NodeIt n( gr ) ; n != INVALID ; ++n )
{
 if( ! b.reached( n ) ) {
  b.addSource( n );
  b.start();
  }
 }

Query Functions

The results of the BFS algorithm can be obtained using these functions.

Either

run() or start() should be called before using them.

inline bool reached( Node v ) const

Checks if the given node is reached from the root(s).

Returns true if v is reached from the root(s).

Pre:

Either run() or init() must be called before using this function.

Public Types

typedef TR Traits

The traits class.

typedef Traits::Digraph Digraph

The type of the digraph the algorithm runs on.

typedef VS Visitor

The visitor type used by the algorithm.

typedef Traits::ReachedMap ReachedMap

The type of the map that indicates which nodes are reached.

typedef BfsVisit Create

Public Functions

inline BfsVisit( const Digraph & digraph , Visitor & visitor )

Constructor.

Parameters:
  • digraph – The digraph the algorithm runs on.

  • visitor – The visitor object of the algorithm.

inline ~BfsVisit()

Destructor.

inline BfsVisit & reachedMap( ReachedMap & m )

Sets the map that indicates which nodes are reached. If you don’t use this function before calling run() or init(), an instance will be allocated automatically. The destructor deallocates this automatically allocated map, of course.

Returns:

(*this)

Protected Functions

inline BfsVisit()
template< class T >
struct SetReachedMapTraits : public Traits

Public Types

typedef T ReachedMap

Public Static Functions

static inline ReachedMap * createReachedMap( const Digraph & )
template< class T >
struct SetReachedMap : public BfsVisit< Digraph , Visitor , SetReachedMapTraits< T > >

Named parameter for setting ReachedMap type.

Public Types

typedef BfsVisit< Digraph , Visitor , SetReachedMapTraits< T > > Create