This class provides an efficient implementation of the BFS algorithm.
There is also a functiontype interface for the BFS 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 BfsDefaultTraits<GR>. In most cases, this parameter should not be set directly, consider to use the named template parameters instead. 
#include <lemon/bfs.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 shortest 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  
Bfs (const Digraph &g)  
Constructor. More...  
~Bfs ()  
Destructor.  
Bfs &  predMap (PredMap &m) 
Sets the map that stores the predecessor arcs. More...  
Bfs &  reachedMap (ReachedMap &m) 
Sets the map that indicates which nodes are reached. More...  
Bfs &  processedMap (ProcessedMap &m) 
Sets the map that indicates which nodes are processed. More...  
Bfs &  distMap (DistMap &m) 
Sets the map that stores the distances of the nodes. More...  
Execution Control  
The simplest way to execute the BFS algorithm is to use one of the member functions called run().  
void  init () 
Initializes the internal data structures. More...  
void  addSource (Node s) 
Adds a new source node. More...  
Node  processNextNode () 
Processes the next node. More...  
Node  processNextNode (Node target, bool &reach) 
Processes the next node. More...  
template<class NM >  
Node  processNextNode (const NM &nm, Node &rnode) 
Processes the next node. More...  
Node  nextNode () const 
The next node to be processed. More...  
bool  emptyQueue () const 
Returns false if there are nodes to be processed. More...  
int  queueSize () const 
Returns the number of the nodes to be processed. More...  
void  start () 
Executes the algorithm. More...  
void  start (Node t) 
Executes the algorithm until the given target node is reached. More...  
template<class NodeBoolMap >  
Node  start (const NodeBoolMap &nm) 
Executes the algorithm until a condition is met. More...  
void  run (Node s) 
Runs the algorithm from the given source node. More...  
bool  run (Node s, Node t) 
Finds the shortest path between s and t . More...  
void  run () 
Runs the algorithm to visit all nodes in the digraph. More...  
Query Functions  
Path  path (Node t) const 
The shortest path to the given node. More...  
int  dist (Node v) const 
The distance of the given node from the root(s). More...  
Arc  predArc (Node v) const 
Returns the 'previous arc' of the shortest path tree for the given node. More...  
Node  predNode (Node v) const 
Returns the 'previous node' of the shortest path tree for the given node. More...  
const DistMap &  distMap () const 
Returns a const reference to the node map that stores the distances of the nodes. More...  
const PredMap &  predMap () const 
Returns a const reference to the node map that stores the predecessor arcs. More...  
bool  reached (Node v) const 
Checks if the given node is reached from the root(s). More...  

inline 

inline 

inline 
Initializes the internal data structures.

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

inline 
Processes the next node.

inline 
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
.
target  The target node. 
reach  Indicates if the target node is reached. It should be initially false . 

inline 
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.
nm  A bool (or convertible) node map that indicates the possible targets. 
rnode  The reached target node. It should be initially INVALID . 

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

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

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

inline 
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
b.start()
is just a shortcut of the following code.

inline 
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
t
,t
from the root(s).b.start(t)
is just a shortcut of the following code.

inline 
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.
nm  A bool (or convertible) node map. The algorithm will stop when it reaches a node v with nm[v] true. 
v
with nm[v]
true or INVALID
if no such node was found.b.start(nm)
is just a shortcut of the following code.

inline 
This method runs the BFS algorithm from node s
in order to compute the shortest path to each node.
The algorithm computes
b.run(s)
is just a shortcut of the following code.

inline 
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 processed).
true
if t
is reachable form s
.b.run(s,t)
is just a shortcut of the following code.

inline 
This method runs the BFS algorithm in order to visit all nodes in the digraph.
b.run(s)
is just a shortcut of the following code.

inline 

inline 

inline 
This function returns the 'previous arc' of the shortest path tree for the node v
, i.e. it returns the last arc of a shortest 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 shortest path tree used here is equal to the shortest path tree used in predNode() and predMap().

inline 
This function returns the 'previous node' of the shortest path tree for the node v
, i.e. it returns the last but one node of a shortest 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 shortest path tree used here is equal to the shortest path tree used in predArc() and predMap().

inline 

inline 