/* -*- C++ -*-
* src/lemon/dfs.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_DFS_H
#define LEMON_DFS_H
///\ingroup flowalgs
///\file
///\brief %DFS algorithm.
///
///\todo Revise Manual.
#include
#include
namespace lemon {
/// \addtogroup flowalgs
/// @{
///%DFS algorithm class.
///This class provides an efficient implementation of %DFS algorithm.
///
///\param GR The graph type the algorithm runs on.
///
///\author Alpar Juttner
#ifdef DOXYGEN
template
#else
template
#endif
class Dfs{
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 paths on the %DFS tree.
typedef typename Graph::template NodeMap PredMap;
///\brief The type of the map that stores the last but one
///nodes of the paths on the %DFS tree.
typedef typename Graph::template NodeMap PredNodeMap;
///The type of the map that stores the dists of the nodes on the %DFS tree.
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.
///
Dfs(const Graph& _G) :
G(&_G),
predecessor(NULL), local_predecessor(false),
pred_node(NULL), local_pred_node(false),
distance(NULL), local_distance(false)
{ }
///Destructor.
~Dfs()
{
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) `
Dfs &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) `
Dfs &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) `
Dfs &setDistMap(DistMap &m)
{
if(local_distance) {
delete distance;
local_distance=false;
}
distance = &m;
return *this;
}
///Runs %DFS algorithm from node \c s.
///This method runs the %DFS algorithm from a root node \c s
///in order to
///compute
///- a %DFS tree and
///- the distance of each node from the root on this tree.
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=G->nodeNum();
std::vector Q(N);
int Qh=0;
G->first(Q[Qh],s);
distance->set(s, 0);
Node n=s;
Node m;
OutEdgeIt e;
do {
if((e=Q[Qh])!=INVALID)
if((m=G->head(e))!=s && (*predecessor)[m=G->head(e)]==INVALID) {
predecessor->set(m,e);
pred_node->set(m,n);
G->first(Q[++Qh],m);
distance->set(m,Qh);
n=m;
}
else ++Q[Qh];
else if(--Qh>=0) n=G->tail(Q[Qh]);
} while(Qh>=0);
}
///The distance of a node from the root on the %DFS tree.
///Returns the distance of a node from the root on the %DFS tree.
///\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 %DFS path tree.
///For a node \c v it returns the last edge of the path on the %DFS tree
///from the root to \c
///v. It is \ref INVALID
///if \c v is unreachable from the root or if \c v=s. The
///%DFS tree used here is equal to the %DFS 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 %DFS tree.
///For a node \c v it returns the 'previous node' on the %DFS tree,
///i.e. it returns the last but one node of the path from the
///root to \c /v on the %DFS tree.
///It is INVALID if \c v is unreachable from the root or if
///\c v=s.
///\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 on the %DFS tree.
///Returns a reference to the NodeMap of distances on the %DFS tree.
///\pre \ref run() must
///be called before using this function.
const DistMap &distMap() const { return *distance;}
///Returns a reference to the %DFS tree map.
///Returns a reference to the NodeMap of the edges of the
///%DFS 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 the %DFS tree.
///Returns a reference to the NodeMap of the last but one nodes of the paths
///on the
///%DFS 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