diff -r 2d6c8075d9d0 -r 818510fa3d99 src/lemon/dfs.h --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/src/lemon/dfs.h Wed Sep 29 15:30:04 2004 +0000 @@ -0,0 +1,290 @@ +/* -*- 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 + +