/* -*- C++ -*-
* src/lemon/bfs.h - Part of LEMON, a generic C++ optimization library
*
* Copyright (C) 2004 Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
* (Egervary Combinatorial Optimization Research Group, EGRES).
*
* Permission to use, modify and distribute this software is granted
* provided that this copyright notice appears in all copies. For
* precise terms see the accompanying LICENSE file.
*
* This software is provided "AS IS" with no warranty of any kind,
* express or implied, and with no claim as to its suitability for any
* purpose.
*
*/
#ifndef LEMON_BFS_H
#define LEMON_BFS_H
///\ingroup flowalgs
///\file
///\brief Bfs algorithm.
///
///\todo Revise Manual.
#include
#include
#include
namespace lemon {
/// \addtogroup flowalgs
/// @{
///%BFS algorithm class.
///This class provides an efficient implementation of %BFS algorithm.
///\param 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
#ifdef DOXYGEN
template
#else
template
#endif
class Bfs{
public:
///The type of the underlying graph.
typedef GR Graph;
///\e
typedef typename Graph::Node Node;
///\e
typedef typename Graph::NodeIt NodeIt;
///\e
typedef typename Graph::Edge Edge;
///\e
typedef typename Graph::OutEdgeIt OutEdgeIt;
///\brief The type of the map that stores the last
///edges of the shortest paths.
typedef typename Graph::template NodeMap PredMap;
///\brief The type of the map that stores the last but one
///nodes of the shortest paths.
typedef typename Graph::template NodeMap PredNodeMap;
///The type of the map that stores the dists of the nodes.
typedef typename Graph::template NodeMap DistMap;
private:
/// Pointer to the underlying graph.
const Graph *G;
///Pointer to the map of predecessors edges.
PredMap *predecessor;
///Indicates if \ref predecessor is locally allocated (\c true) or not.
bool local_predecessor;
///Pointer to the map of predecessors nodes.
PredNodeMap *pred_node;
///Indicates if \ref pred_node is locally allocated (\c true) or not.
bool local_pred_node;
///Pointer to the map of distances.
DistMap *distance;
///Indicates if \ref distance is locally allocated (\c true) or not.
bool local_distance;
///The source node of the last execution.
Node source;
///Initializes the maps.
void init_maps()
{
if(!predecessor) {
local_predecessor = true;
predecessor = new PredMap(*G);
}
if(!pred_node) {
local_pred_node = true;
pred_node = new PredNodeMap(*G);
}
if(!distance) {
local_distance = true;
distance = new DistMap(*G);
}
}
public :
///Constructor.
///\param _G the graph the algorithm will run on.
///
Bfs(const Graph& _G) :
G(&_G),
predecessor(NULL), local_predecessor(false),
pred_node(NULL), local_pred_node(false),
distance(NULL), local_distance(false)
{ }
///Destructor.
~Bfs()
{
if(local_predecessor) delete predecessor;
if(local_pred_node) delete pred_node;
if(local_distance) delete distance;
}
///Sets the map storing the predecessor edges.
///Sets the map storing the predecessor edges.
///If you don't use this function before calling \ref run(),
///it will allocate one. The destuctor deallocates this
///automatically allocated map, of course.
///\return ` (*this) `
Bfs &setPredMap(PredMap &m)
{
if(local_predecessor) {
delete predecessor;
local_predecessor=false;
}
predecessor = &m;
return *this;
}
///Sets the map storing the predecessor nodes.
///Sets the map storing the predecessor nodes.
///If you don't use this function before calling \ref run(),
///it will allocate one. The destuctor deallocates this
///automatically allocated map, of course.
///\return ` (*this) `
Bfs &setPredNodeMap(PredNodeMap &m)
{
if(local_pred_node) {
delete pred_node;
local_pred_node=false;
}
pred_node = &m;
return *this;
}
///Sets the map storing the distances calculated by the algorithm.
///Sets the map storing the distances calculated by the algorithm.
///If you don't use this function before calling \ref run(),
///it will allocate one. The destuctor deallocates this
///automatically allocated map, of course.
///\return ` (*this) `
Bfs &setDistMap(DistMap &m)
{
if(local_distance) {
delete distance;
local_distance=false;
}
distance = &m;
return *this;
}
///Runs %BFS algorithm from node \c s.
///This method runs the %BFS algorithm from a root node \c 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.
void run(Node s) {
init_maps();
source = s;
for ( NodeIt u(*G) ; u!=INVALID ; ++u ) {
predecessor->set(u,INVALID);
pred_node->set(u,INVALID);
}
int N = countNodes(*G);
std::vector Q(N);
int Qh=0;
int Qt=0;
Q[Qh++]=source;
distance->set(s, 0);
do {
Node m;
Node n=Q[Qt++];
int d= (*distance)[n]+1;
for(OutEdgeIt e(*G,n);e!=INVALID;++e)
if((m=G->target(e))!=s && (*predecessor)[m]==INVALID) {
Q[Qh++]=m;
predecessor->set(m,e);
pred_node->set(m,n);
distance->set(m,d);
}
} while(Qt!=Qh);
}
///The distance of a node from the root.
///Returns the distance of a node from the root.
///\pre \ref run() must be called before using this function.
///\warning If node \c v in unreachable from the root the return value
///of this funcion is undefined.
int dist(Node v) const { return (*distance)[v]; }
///Returns the 'previous edge' of the %BFS path tree.
///For a node \c 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 \c
///v. It is \ref INVALID
///if \c v is unreachable from the root or if \c v=s. The
///%BFS tree used here is equal to the %BFS tree used in
///\ref predNode(Node v). \pre \ref run() must be called before using
///this function.
Edge pred(Node v) const { return (*predecessor)[v]; }
///Returns the 'previous node' of the %BFS tree.
///For a node \c 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 \c /v. It is INVALID if \c v is unreachable from the root or if
///\c v=s. The shortest path tree used here is equal to the %BFS
///tree used in \ref pred(Node v). \pre \ref run() must be called before
///using this function.
Node predNode(Node v) const { return (*pred_node)[v]; }
///Returns a reference to the NodeMap of distances.
///Returns a reference to the NodeMap of distances. \pre \ref run() must
///be called before using this function.
const DistMap &distMap() const { return *distance;}
///Returns a reference to the %BFS tree map.
///Returns a reference to the NodeMap of the edges of the
///%BFS tree.
///\pre \ref run() must be called before using this function.
const PredMap &predMap() const { return *predecessor;}
///Returns a reference to the map of last but one nodes of shortest paths.
///Returns a reference to the NodeMap of the last but one nodes on the
///%BFS tree.
///\pre \ref run() must be called before using this function.
const PredNodeMap &predNodeMap() const { return *pred_node;}
///Checks if a node is reachable from the root.
///Returns \c true if \c v is reachable from the root.
///\note The root node is reported to be reached!
///
///\pre \ref run() must be called before using this function.
///
bool reached(Node v) { return v==source || (*predecessor)[v]!=INVALID; }
};
/// @}
} //END OF NAMESPACE LEMON
#endif