Main Page | Modules | Namespace List | Class Hierarchy | Alphabetical List | Class List | Directories | File List | Namespace Members | Class Members | File Members | Related Pages

Bfs Class Template Reference
[Path and Flow Algorithms]

#include <lemon/bfs.h>

List of all members.


Detailed Description

template<typename GR>
class lemon::Bfs< GR >

This class provides an efficient implementation of BFS algorithm.
Parameters:
GR The graph type the algorithm runs on. This class does the same as Dijkstra does with constant 1 edge length, but it is faster.
Author:
Alpar Juttner

Definition at line 49 of file bfs.h.

Public Types

typedef GR Graph
 The type of the underlying graph.
typedef Graph::Node Node
 
typedef Graph::NodeIt NodeIt
 
typedef Graph::Edge Edge
 
typedef Graph::OutEdgeIt OutEdgeIt
 
typedef Graph::template NodeMap<
Edge
PredMap
 The type of the map that stores the last edges of the shortest paths.
typedef Graph::template NodeMap<
Node
PredNodeMap
 The type of the map that stores the last but one nodes of the shortest paths.
typedef Graph::template NodeMap<
int > 
DistMap
 The type of the map that stores the dists of the nodes.

Public Member Functions

 Bfs (const Graph &_G)
 Constructor.
 ~Bfs ()
 Destructor.
BfssetPredMap (PredMap &m)
 Sets the map storing the predecessor edges.
BfssetPredNodeMap (PredNodeMap &m)
 Sets the map storing the predecessor nodes.
BfssetDistMap (DistMap &m)
 Sets the map storing the distances calculated by the algorithm.
void run (Node s)
 Runs BFS algorithm from node s.
int dist (Node v) const
 The distance of a node from the root.
Edge pred (Node v) const
 Returns the 'previous edge' of the BFS path tree.
Node predNode (Node v) const
 Returns the 'previous node' of the BFS tree.
const DistMapdistMap () const
 Returns a reference to the NodeMap of distances.
const PredMappredMap () const
 Returns a reference to the BFS tree map.
const PredNodeMappredNodeMap () const
 Returns a reference to the map of last but one nodes of shortest paths.
bool reached (Node v)
 Checks if a node is reachable from the root.


Constructor & Destructor Documentation

Bfs const Graph _G  )  [inline]
 

Parameters:
_G the graph the algorithm will run on.

Definition at line 113 of file bfs.h.


Member Function Documentation

Bfs& setPredMap PredMap m  )  [inline]
 

Sets the map storing the predecessor edges. 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)

Definition at line 135 of file bfs.h.

Bfs& setPredNodeMap PredNodeMap m  )  [inline]
 

Sets the map storing the predecessor nodes. 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)

Definition at line 152 of file bfs.h.

Bfs& setDistMap DistMap m  )  [inline]
 

Sets the map storing the distances calculated by the algorithm. 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)

Definition at line 169 of file bfs.h.

void run Node  s  )  [inline]
 

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

  • The BFS tree.
  • The distance of each node from the root.

Definition at line 188 of file bfs.h.

Here is the call graph for this function:

int dist Node  v  )  const [inline]
 

Returns the distance of a node from the root.

Precondition:
run() must be called before using this function.
Warning:
If node v in unreachable from the root the return value of this funcion is undefined.

Definition at line 227 of file bfs.h.

Edge pred Node  v  )  const [inline]
 

For a node v it returns the 'previous edge' of the BFS tree, i.e. it returns the last edge of a shortest path from the root to v. It is INVALID if v is unreachable from the root or if v=s. The BFS tree used here is equal to the BFS tree used in predNode(Node v).

Precondition:
run() must be called before using this function.

Definition at line 238 of file bfs.h.

Node predNode Node  v  )  const [inline]
 

For a node v it returns the 'previous node' on the BFS tree, i.e. it returns the last but one node from a shortest path from the root to /v. It is INVALID if v is unreachable from the root or if v=s. The shortest path tree used here is equal to the BFS tree used in pred(Node v).

Precondition:
run() must be called before using this function.

Definition at line 248 of file bfs.h.

const DistMap& distMap  )  const [inline]
 

Returns a reference to the NodeMap of distances.

Precondition:
run() must be called before using this function.

Definition at line 254 of file bfs.h.

const PredMap& predMap  )  const [inline]
 

Returns a reference to the NodeMap of the edges of the BFS tree.

Precondition:
run() must be called before using this function.

Definition at line 261 of file bfs.h.

const PredNodeMap& predNodeMap  )  const [inline]
 

Returns a reference to the NodeMap of the last but one nodes on the BFS tree.

Precondition:
run() must be called before using this function.

Definition at line 268 of file bfs.h.

bool reached Node  v  )  [inline]
 

Returns true if v is reachable from the root.

Note:
The root node is reported to be reached!
Precondition:
run() must be called before using this function.

Definition at line 277 of file bfs.h.


The documentation for this class was generated from the following file:
Generated on Sat Mar 19 10:58:48 2005 for LEMON by  doxygen 1.4.1