template<typename GR, typename TR>
class lemon::Bfs< GR, TR >
This class provides an efficient implementation of the BFS algorithm.
There is also a function-type interface for the BFS algorithm, which is convenient in the simplier cases and it can be used easier.
- Template Parameters
-
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. |
|
| Bfs (const Digraph &g) |
| Constructor.
|
|
| ~Bfs () |
| Destructor.
|
|
Bfs & | predMap (PredMap &m) |
| Sets the map that stores the predecessor arcs.
|
|
Bfs & | reachedMap (ReachedMap &m) |
| Sets the map that indicates which nodes are reached.
|
|
Bfs & | processedMap (ProcessedMap &m) |
| Sets the map that indicates which nodes are processed.
|
|
Bfs & | distMap (DistMap &m) |
| Sets the map that stores the distances of the nodes.
|
|
|
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
|
void | init () |
| Initializes the internal data structures.
|
|
void | addSource (Node s) |
| Adds a new source node.
|
|
Node | processNextNode () |
| Processes the next node.
|
|
Node | processNextNode (Node target, bool &reach) |
| Processes the next node.
|
|
template<class NM > |
Node | processNextNode (const NM &nm, Node &rnode) |
| Processes the next node.
|
|
Node | nextNode () const |
| The next node to be processed.
|
|
bool | emptyQueue () const |
| Returns false if there are nodes to be processed.
|
|
int | queueSize () const |
| Returns the number of the nodes to be processed.
|
|
void | start () |
| Executes the algorithm.
|
|
void | start (Node t) |
| Executes the algorithm until the given target node is reached.
|
|
template<class NodeBoolMap > |
Node | start (const NodeBoolMap &nm) |
| Executes the algorithm until a condition is met.
|
|
void | run (Node s) |
| Runs the algorithm from the given source node.
|
|
bool | run (Node s, Node t) |
| Finds the shortest path between s and t .
|
|
void | run () |
| Runs the algorithm to visit all nodes in the digraph.
|
|
|
The results of the BFS algorithm can be obtained using these functions.
Either run() or start() should be called before using them.
|
Path | path (Node t) const |
| The shortest path to the given node.
|
|
int | dist (Node v) const |
| The distance of the given node from the root(s).
|
|
Arc | predArc (Node v) const |
| Returns the 'previous arc' of the shortest path tree for the given node.
|
|
Node | predNode (Node v) const |
| Returns the 'previous node' of the shortest path tree for the given node.
|
|
const DistMap & | distMap () const |
| Returns a const reference to the node map that stores the distances of the nodes.
|
|
const PredMap & | predMap () const |
| Returns a const reference to the node map that stores the predecessor arcs.
|
|
bool | reached (Node v) const |
| Checks if the given node is reached from the root(s).
|
|
template<typename GR , typename TR >
template<class NodeBoolMap >
Node start |
( |
const NodeBoolMap & | nm | ) |
|
|
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.
- Parameters
-
nm | 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.
- Precondition
- init() must be called and at least one root node should be added with addSource() before using this function.
- Note
b.start(nm)
is just a shortcut of the following code.
while ( !b.emptyQueue() && rnode ==
INVALID ) {
b.processNextNode(nm, rnode);
}
return rnode;
const Invalid INVALID
Invalid iterators.
Definition base.cc:32
template<typename GR , typename TR >
Arc predArc |
( |
Node | v | ) |
const |
|
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().
- Precondition
- Either run() or init() must be called before using this function.
template<typename GR , typename TR >
Node predNode |
( |
Node | v | ) |
const |
|
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().
- Precondition
- Either run() or init() must be called before using this function.