template<typename GR, typename VS, typename TR>
class lemon::BfsVisit< GR, VS, TR >
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. |
|
| BfsVisit (const Digraph &digraph, Visitor &visitor) |
| Constructor. More...
|
|
| ~BfsVisit () |
| Destructor.
|
|
BfsVisit & | reachedMap (ReachedMap &m) |
| Sets the map that indicates which nodes are reached. More...
|
|
|
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.
|
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<typename 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<typename NM > |
Node | start (const NM &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...
|
|
|
The results of the BFS algorithm can be obtained using these functions.
Either run() or start() should be called before using them.
|
bool | reached (Node v) const |
| Checks if the given node is reached from the root(s). More...
|
|