alpar@100: /* -*- C++ -*- alpar@100: * alpar@100: * This file is a part of LEMON, a generic C++ optimization library alpar@100: * alpar@100: * Copyright (C) 2003-2008 alpar@100: * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport alpar@100: * (Egervary Research Group on Combinatorial Optimization, EGRES). alpar@100: * alpar@100: * Permission to use, modify and distribute this software is granted alpar@100: * provided that this copyright notice appears in all copies. For alpar@100: * precise terms see the accompanying LICENSE file. alpar@100: * alpar@100: * This software is provided "AS IS" with no warranty of any kind, alpar@100: * express or implied, and with no claim as to its suitability for any alpar@100: * purpose. alpar@100: * alpar@100: */ alpar@100: alpar@100: #ifndef LEMON_DFS_H alpar@100: #define LEMON_DFS_H alpar@100: alpar@100: ///\ingroup search alpar@100: ///\file alpar@100: ///\brief Dfs algorithm. alpar@100: alpar@100: #include alpar@100: #include alpar@100: #include alpar@100: #include alpar@100: #include alpar@100: #include alpar@100: alpar@100: #include alpar@100: alpar@100: namespace lemon { alpar@100: alpar@100: alpar@100: ///Default traits class of Dfs class. alpar@100: alpar@100: ///Default traits class of Dfs class. kpeter@157: ///\tparam GR Digraph type. alpar@100: template alpar@100: struct DfsDefaultTraits alpar@100: { alpar@100: ///The digraph type the algorithm runs on. alpar@100: typedef GR Digraph; alpar@100: ///\brief The type of the map that stores the last alpar@100: ///arcs of the %DFS paths. alpar@100: /// alpar@100: ///The type of the map that stores the last alpar@100: ///arcs of the %DFS paths. alpar@100: ///It must meet the \ref concepts::WriteMap "WriteMap" concept. alpar@100: /// alpar@100: typedef typename Digraph::template NodeMap PredMap; alpar@100: ///Instantiates a PredMap. alpar@100: alpar@100: ///This function instantiates a \ref PredMap. alpar@100: ///\param G is the digraph, to which we would like to define the PredMap. alpar@100: ///\todo The digraph alone may be insufficient to initialize alpar@100: static PredMap *createPredMap(const GR &G) alpar@100: { alpar@100: return new PredMap(G); alpar@100: } alpar@100: alpar@100: ///The type of the map that indicates which nodes are processed. alpar@100: alpar@100: ///The type of the map that indicates which nodes are processed. alpar@100: ///It must meet the \ref concepts::WriteMap "WriteMap" concept. alpar@100: ///\todo named parameter to set this type, function to read and write. alpar@100: typedef NullMap ProcessedMap; alpar@100: ///Instantiates a ProcessedMap. alpar@100: alpar@100: ///This function instantiates a \ref ProcessedMap. alpar@100: ///\param g is the digraph, to which alpar@100: ///we would like to define the \ref ProcessedMap alpar@100: #ifdef DOXYGEN alpar@100: static ProcessedMap *createProcessedMap(const GR &g) alpar@100: #else alpar@100: static ProcessedMap *createProcessedMap(const GR &) alpar@100: #endif alpar@100: { alpar@100: return new ProcessedMap(); alpar@100: } alpar@100: ///The type of the map that indicates which nodes are reached. alpar@100: alpar@100: ///The type of the map that indicates which nodes are reached. alpar@100: ///It must meet the \ref concepts::WriteMap "WriteMap" concept. alpar@100: ///\todo named parameter to set this type, function to read and write. alpar@100: typedef typename Digraph::template NodeMap ReachedMap; alpar@100: ///Instantiates a ReachedMap. alpar@100: alpar@100: ///This function instantiates a \ref ReachedMap. alpar@100: ///\param G is the digraph, to which alpar@100: ///we would like to define the \ref ReachedMap. alpar@100: static ReachedMap *createReachedMap(const GR &G) alpar@100: { alpar@100: return new ReachedMap(G); alpar@100: } alpar@100: ///The type of the map that stores the dists of the nodes. alpar@100: alpar@100: ///The type of the map that stores the dists of the nodes. alpar@100: ///It must meet the \ref concepts::WriteMap "WriteMap" concept. alpar@100: /// alpar@100: typedef typename Digraph::template NodeMap DistMap; alpar@100: ///Instantiates a DistMap. alpar@100: alpar@100: ///This function instantiates a \ref DistMap. alpar@100: ///\param G is the digraph, to which we would like to define the \ref DistMap alpar@100: static DistMap *createDistMap(const GR &G) alpar@100: { alpar@100: return new DistMap(G); alpar@100: } alpar@100: }; alpar@100: alpar@100: ///%DFS algorithm class. alpar@100: alpar@100: ///\ingroup search alpar@100: ///This class provides an efficient implementation of the %DFS algorithm. alpar@100: /// kpeter@157: ///\tparam GR The digraph type the algorithm runs on. The default value is alpar@100: ///\ref ListDigraph. The value of GR is not used directly by Dfs, it alpar@100: ///is only passed to \ref DfsDefaultTraits. kpeter@157: ///\tparam TR Traits class to set various data types used by the algorithm. alpar@100: ///The default traits class is alpar@100: ///\ref DfsDefaultTraits "DfsDefaultTraits". alpar@100: ///See \ref DfsDefaultTraits for the documentation of alpar@100: ///a Dfs traits class. alpar@100: #ifdef DOXYGEN alpar@100: template alpar@100: #else alpar@100: template > alpar@100: #endif alpar@100: class Dfs { alpar@100: public: alpar@100: /** alpar@100: * \brief \ref Exception for uninitialized parameters. alpar@100: * alpar@100: * This error represents problems in the initialization alpar@100: * of the parameters of the algorithms. alpar@100: */ alpar@100: class UninitializedParameter : public lemon::UninitializedParameter { alpar@100: public: alpar@100: virtual const char* what() const throw() { alpar@100: return "lemon::Dfs::UninitializedParameter"; alpar@100: } alpar@100: }; alpar@100: alpar@100: typedef TR Traits; alpar@100: ///The type of the underlying digraph. alpar@100: typedef typename TR::Digraph Digraph; alpar@100: ///\e alpar@100: typedef typename Digraph::Node Node; alpar@100: ///\e alpar@100: typedef typename Digraph::NodeIt NodeIt; alpar@100: ///\e alpar@100: typedef typename Digraph::Arc Arc; alpar@100: ///\e alpar@100: typedef typename Digraph::OutArcIt OutArcIt; alpar@100: alpar@100: ///\brief The type of the map that stores the last alpar@100: ///arcs of the %DFS paths. alpar@100: typedef typename TR::PredMap PredMap; alpar@100: ///The type of the map indicating which nodes are reached. alpar@100: typedef typename TR::ReachedMap ReachedMap; alpar@100: ///The type of the map indicating which nodes are processed. alpar@100: typedef typename TR::ProcessedMap ProcessedMap; alpar@100: ///The type of the map that stores the dists of the nodes. alpar@100: typedef typename TR::DistMap DistMap; alpar@100: private: alpar@100: /// Pointer to the underlying digraph. alpar@100: const Digraph *G; alpar@100: ///Pointer to the map of predecessors arcs. alpar@100: PredMap *_pred; alpar@100: ///Indicates if \ref _pred is locally allocated (\c true) or not. alpar@100: bool local_pred; alpar@100: ///Pointer to the map of distances. alpar@100: DistMap *_dist; alpar@100: ///Indicates if \ref _dist is locally allocated (\c true) or not. alpar@100: bool local_dist; alpar@100: ///Pointer to the map of reached status of the nodes. alpar@100: ReachedMap *_reached; alpar@100: ///Indicates if \ref _reached is locally allocated (\c true) or not. alpar@100: bool local_reached; alpar@100: ///Pointer to the map of processed status of the nodes. alpar@100: ProcessedMap *_processed; alpar@100: ///Indicates if \ref _processed is locally allocated (\c true) or not. alpar@100: bool local_processed; alpar@100: alpar@100: std::vector _stack; alpar@100: int _stack_head; alpar@100: alpar@100: ///Creates the maps if necessary. alpar@100: alpar@100: ///\todo Better memory allocation (instead of new). alpar@100: void create_maps() alpar@100: { alpar@100: if(!_pred) { alpar@100: local_pred = true; alpar@100: _pred = Traits::createPredMap(*G); alpar@100: } alpar@100: if(!_dist) { alpar@100: local_dist = true; alpar@100: _dist = Traits::createDistMap(*G); alpar@100: } alpar@100: if(!_reached) { alpar@100: local_reached = true; alpar@100: _reached = Traits::createReachedMap(*G); alpar@100: } alpar@100: if(!_processed) { alpar@100: local_processed = true; alpar@100: _processed = Traits::createProcessedMap(*G); alpar@100: } alpar@100: } alpar@100: alpar@100: protected: alpar@100: alpar@100: Dfs() {} alpar@100: alpar@100: public: alpar@100: alpar@100: typedef Dfs Create; alpar@100: alpar@100: ///\name Named template parameters alpar@100: alpar@100: ///@{ alpar@100: alpar@100: template alpar@100: struct DefPredMapTraits : public Traits { alpar@100: typedef T PredMap; alpar@100: static PredMap *createPredMap(const Digraph &G) alpar@100: { alpar@100: throw UninitializedParameter(); alpar@100: } alpar@100: }; alpar@100: ///\brief \ref named-templ-param "Named parameter" for setting alpar@100: ///PredMap type alpar@100: /// alpar@100: ///\ref named-templ-param "Named parameter" for setting PredMap type alpar@100: /// alpar@100: template alpar@100: struct DefPredMap : public Dfs > { alpar@100: typedef Dfs > Create; alpar@100: }; alpar@100: alpar@100: alpar@100: template alpar@100: struct DefDistMapTraits : public Traits { alpar@100: typedef T DistMap; alpar@100: static DistMap *createDistMap(const Digraph &) alpar@100: { alpar@100: throw UninitializedParameter(); alpar@100: } alpar@100: }; alpar@100: ///\brief \ref named-templ-param "Named parameter" for setting alpar@100: ///DistMap type alpar@100: /// alpar@100: ///\ref named-templ-param "Named parameter" for setting DistMap alpar@100: ///type alpar@100: template alpar@100: struct DefDistMap { alpar@100: typedef Dfs > Create; alpar@100: }; alpar@100: alpar@100: template alpar@100: struct DefReachedMapTraits : public Traits { alpar@100: typedef T ReachedMap; alpar@100: static ReachedMap *createReachedMap(const Digraph &) alpar@100: { alpar@100: throw UninitializedParameter(); alpar@100: } alpar@100: }; alpar@100: ///\brief \ref named-templ-param "Named parameter" for setting alpar@100: ///ReachedMap type alpar@100: /// alpar@100: ///\ref named-templ-param "Named parameter" for setting ReachedMap type alpar@100: /// alpar@100: template alpar@100: struct DefReachedMap : public Dfs< Digraph, DefReachedMapTraits > { alpar@100: typedef Dfs< Digraph, DefReachedMapTraits > Create; alpar@100: }; alpar@100: alpar@100: template alpar@100: struct DefProcessedMapTraits : public Traits { alpar@100: typedef T ProcessedMap; alpar@100: static ProcessedMap *createProcessedMap(const Digraph &) alpar@100: { alpar@100: throw UninitializedParameter(); alpar@100: } alpar@100: }; alpar@100: ///\brief \ref named-templ-param "Named parameter" for setting alpar@100: ///ProcessedMap type alpar@100: /// alpar@100: ///\ref named-templ-param "Named parameter" for setting ProcessedMap type alpar@100: /// alpar@100: template alpar@100: struct DefProcessedMap : public Dfs< Digraph, DefProcessedMapTraits > { alpar@100: typedef Dfs< Digraph, DefProcessedMapTraits > Create; alpar@100: }; alpar@100: alpar@100: struct DefDigraphProcessedMapTraits : public Traits { alpar@100: typedef typename Digraph::template NodeMap ProcessedMap; alpar@100: static ProcessedMap *createProcessedMap(const Digraph &G) alpar@100: { alpar@100: return new ProcessedMap(G); alpar@100: } alpar@100: }; alpar@100: ///\brief \ref named-templ-param "Named parameter" alpar@100: ///for setting the ProcessedMap type to be Digraph::NodeMap. alpar@100: /// alpar@100: ///\ref named-templ-param "Named parameter" alpar@100: ///for setting the ProcessedMap type to be Digraph::NodeMap. alpar@100: ///If you don't set it explicitely, it will be automatically allocated. alpar@100: template alpar@100: class DefProcessedMapToBeDefaultMap : alpar@100: public Dfs< Digraph, DefDigraphProcessedMapTraits> { alpar@100: typedef Dfs< Digraph, DefDigraphProcessedMapTraits> Create; alpar@100: }; alpar@100: alpar@100: ///@} alpar@100: alpar@100: public: alpar@100: alpar@100: ///Constructor. alpar@100: alpar@100: ///\param _G the digraph the algorithm will run on. alpar@100: /// alpar@100: Dfs(const Digraph& _G) : alpar@100: G(&_G), alpar@100: _pred(NULL), local_pred(false), alpar@100: _dist(NULL), local_dist(false), alpar@100: _reached(NULL), local_reached(false), alpar@100: _processed(NULL), local_processed(false) alpar@100: { } alpar@100: alpar@100: ///Destructor. alpar@100: ~Dfs() alpar@100: { alpar@100: if(local_pred) delete _pred; alpar@100: if(local_dist) delete _dist; alpar@100: if(local_reached) delete _reached; alpar@100: if(local_processed) delete _processed; alpar@100: } alpar@100: alpar@100: ///Sets the map storing the predecessor arcs. alpar@100: alpar@100: ///Sets the map storing the predecessor arcs. alpar@100: ///If you don't use this function before calling \ref run(), alpar@100: ///it will allocate one. The destuctor deallocates this alpar@100: ///automatically allocated map, of course. alpar@100: ///\return (*this) alpar@100: Dfs &predMap(PredMap &m) alpar@100: { alpar@100: if(local_pred) { alpar@100: delete _pred; alpar@100: local_pred=false; alpar@100: } alpar@100: _pred = &m; alpar@100: return *this; alpar@100: } alpar@100: alpar@100: ///Sets the map storing the distances calculated by the algorithm. alpar@100: alpar@100: ///Sets the map storing the distances calculated by the algorithm. alpar@100: ///If you don't use this function before calling \ref run(), alpar@100: ///it will allocate one. The destuctor deallocates this alpar@100: ///automatically allocated map, of course. alpar@100: ///\return (*this) alpar@100: Dfs &distMap(DistMap &m) alpar@100: { alpar@100: if(local_dist) { alpar@100: delete _dist; alpar@100: local_dist=false; alpar@100: } alpar@100: _dist = &m; alpar@100: return *this; alpar@100: } alpar@100: alpar@100: ///Sets the map indicating if a node is reached. alpar@100: alpar@100: ///Sets the map indicating if a node is reached. alpar@100: ///If you don't use this function before calling \ref run(), alpar@100: ///it will allocate one. The destuctor deallocates this alpar@100: ///automatically allocated map, of course. alpar@100: ///\return (*this) alpar@100: Dfs &reachedMap(ReachedMap &m) alpar@100: { alpar@100: if(local_reached) { alpar@100: delete _reached; alpar@100: local_reached=false; alpar@100: } alpar@100: _reached = &m; alpar@100: return *this; alpar@100: } alpar@100: alpar@100: ///Sets the map indicating if a node is processed. alpar@100: alpar@100: ///Sets the map indicating if a node is processed. alpar@100: ///If you don't use this function before calling \ref run(), alpar@100: ///it will allocate one. The destuctor deallocates this alpar@100: ///automatically allocated map, of course. alpar@100: ///\return (*this) alpar@100: Dfs &processedMap(ProcessedMap &m) alpar@100: { alpar@100: if(local_processed) { alpar@100: delete _processed; alpar@100: local_processed=false; alpar@100: } alpar@100: _processed = &m; alpar@100: return *this; alpar@100: } alpar@100: alpar@100: public: alpar@100: ///\name Execution control alpar@100: ///The simplest way to execute the algorithm is to use alpar@100: ///one of the member functions called \c run(...). alpar@100: ///\n alpar@100: ///If you need more control on the execution, alpar@100: ///first you must call \ref init(), then you can add a source node alpar@100: ///with \ref addSource(). alpar@100: ///Finally \ref start() will perform the actual path alpar@100: ///computation. alpar@100: alpar@100: ///@{ alpar@100: alpar@100: ///Initializes the internal data structures. alpar@100: alpar@100: ///Initializes the internal data structures. alpar@100: /// alpar@100: void init() alpar@100: { alpar@100: create_maps(); alpar@100: _stack.resize(countNodes(*G)); alpar@100: _stack_head=-1; alpar@100: for ( NodeIt u(*G) ; u!=INVALID ; ++u ) { alpar@100: _pred->set(u,INVALID); alpar@100: // _predNode->set(u,INVALID); alpar@100: _reached->set(u,false); alpar@100: _processed->set(u,false); alpar@100: } alpar@100: } alpar@100: alpar@100: ///Adds a new source node. alpar@100: alpar@100: ///Adds a new source node to the set of nodes to be processed. alpar@100: /// alpar@100: ///\warning dists are wrong (or at least strange) alpar@100: ///in case of multiple sources. alpar@100: void addSource(Node s) alpar@100: { alpar@100: if(!(*_reached)[s]) alpar@100: { alpar@100: _reached->set(s,true); alpar@100: _pred->set(s,INVALID); alpar@100: OutArcIt e(*G,s); alpar@100: if(e!=INVALID) { alpar@100: _stack[++_stack_head]=e; alpar@100: _dist->set(s,_stack_head); alpar@100: } alpar@100: else { alpar@100: _processed->set(s,true); alpar@100: _dist->set(s,0); alpar@100: } alpar@100: } alpar@100: } alpar@100: alpar@100: ///Processes the next arc. alpar@100: alpar@100: ///Processes the next arc. alpar@100: /// alpar@100: ///\return The processed arc. alpar@100: /// alpar@100: ///\pre The stack must not be empty! alpar@100: Arc processNextArc() alpar@100: { alpar@100: Node m; alpar@100: Arc e=_stack[_stack_head]; alpar@100: if(!(*_reached)[m=G->target(e)]) { alpar@100: _pred->set(m,e); alpar@100: _reached->set(m,true); alpar@100: ++_stack_head; alpar@100: _stack[_stack_head] = OutArcIt(*G, m); alpar@100: _dist->set(m,_stack_head); alpar@100: } alpar@100: else { alpar@100: m=G->source(e); alpar@100: ++_stack[_stack_head]; alpar@100: } alpar@100: while(_stack_head>=0 && _stack[_stack_head]==INVALID) { alpar@100: _processed->set(m,true); alpar@100: --_stack_head; alpar@100: if(_stack_head>=0) { alpar@100: m=G->source(_stack[_stack_head]); alpar@100: ++_stack[_stack_head]; alpar@100: } alpar@100: } alpar@100: return e; alpar@100: } alpar@100: ///Next arc to be processed. alpar@100: alpar@100: ///Next arc to be processed. alpar@100: /// alpar@100: ///\return The next arc to be processed or INVALID if the stack is alpar@100: /// empty. alpar@100: OutArcIt nextArc() alpar@100: { alpar@100: return _stack_head>=0?_stack[_stack_head]:INVALID; alpar@100: } alpar@100: alpar@100: ///\brief Returns \c false if there are nodes alpar@100: ///to be processed in the queue alpar@100: /// alpar@100: ///Returns \c false if there are nodes alpar@100: ///to be processed in the queue alpar@100: bool emptyQueue() { return _stack_head<0; } alpar@100: ///Returns the number of the nodes to be processed. alpar@100: alpar@100: ///Returns the number of the nodes to be processed in the queue. alpar@100: int queueSize() { return _stack_head+1; } alpar@100: alpar@100: ///Executes the algorithm. alpar@100: alpar@100: ///Executes the algorithm. alpar@100: /// alpar@100: ///\pre init() must be called and at least one node should be added alpar@100: ///with addSource() before using this function. alpar@100: /// alpar@100: ///This method runs the %DFS algorithm from the root node(s) alpar@100: ///in order to alpar@100: ///compute the alpar@100: ///%DFS path to each node. The algorithm computes alpar@100: ///- The %DFS tree. alpar@100: ///- The distance of each node from the root(s) in the %DFS tree. alpar@100: /// alpar@100: void start() alpar@100: { alpar@100: while ( !emptyQueue() ) processNextArc(); alpar@100: } alpar@100: alpar@100: ///Executes the algorithm until \c dest is reached. alpar@100: alpar@100: ///Executes the algorithm until \c dest is reached. alpar@100: /// alpar@100: ///\pre init() must be called and at least one node should be added alpar@100: ///with addSource() before using this function. alpar@100: /// alpar@100: ///This method runs the %DFS algorithm from the root node(s) alpar@100: ///in order to alpar@100: ///compute the alpar@100: ///%DFS path to \c dest. The algorithm computes alpar@100: ///- The %DFS path to \c dest. alpar@100: ///- The distance of \c dest from the root(s) in the %DFS tree. alpar@100: /// alpar@100: void start(Node dest) alpar@100: { alpar@100: while ( !emptyQueue() && G->target(_stack[_stack_head])!=dest ) alpar@100: processNextArc(); alpar@100: } alpar@100: alpar@100: ///Executes the algorithm until a condition is met. alpar@100: alpar@100: ///Executes the algorithm until a condition is met. alpar@100: /// alpar@100: ///\pre init() must be called and at least one node should be added alpar@100: ///with addSource() before using this function. alpar@100: /// alpar@100: ///\param em must be a bool (or convertible) arc map. The algorithm alpar@100: ///will stop when it reaches an arc \c e with em[e] true. alpar@100: /// alpar@100: ///\return The reached arc \c e with em[e] true or alpar@100: ///\c INVALID if no such arc was found. alpar@100: /// alpar@100: ///\warning Contrary to \ref Bfs and \ref Dijkstra, \c em is an arc map, alpar@100: ///not a node map. alpar@100: template alpar@100: Arc start(const EM &em) alpar@100: { alpar@100: while ( !emptyQueue() && !em[_stack[_stack_head]] ) alpar@100: processNextArc(); alpar@100: return emptyQueue() ? INVALID : _stack[_stack_head]; alpar@100: } alpar@100: alpar@100: ///Runs %DFS algorithm to visit all nodes in the digraph. alpar@100: alpar@100: ///This method runs the %DFS algorithm in order to alpar@100: ///compute the alpar@100: ///%DFS path to each node. The algorithm computes alpar@100: ///- The %DFS tree. alpar@100: ///- The distance of each node from the root in the %DFS tree. alpar@100: /// alpar@100: ///\note d.run() is just a shortcut of the following code. alpar@100: ///\code alpar@100: /// d.init(); alpar@100: /// for (NodeIt it(digraph); it != INVALID; ++it) { alpar@100: /// if (!d.reached(it)) { alpar@100: /// d.addSource(it); alpar@100: /// d.start(); alpar@100: /// } alpar@100: /// } alpar@100: ///\endcode alpar@100: void run() { alpar@100: init(); alpar@100: for (NodeIt it(*G); it != INVALID; ++it) { alpar@100: if (!reached(it)) { alpar@100: addSource(it); alpar@100: start(); alpar@100: } alpar@100: } alpar@100: } alpar@100: alpar@100: ///Runs %DFS algorithm from node \c s. alpar@100: alpar@100: ///This method runs the %DFS algorithm from a root node \c s alpar@100: ///in order to alpar@100: ///compute the alpar@100: ///%DFS path to each node. The algorithm computes alpar@100: ///- The %DFS tree. alpar@100: ///- The distance of each node from the root in the %DFS tree. alpar@100: /// alpar@100: ///\note d.run(s) is just a shortcut of the following code. alpar@100: ///\code alpar@100: /// d.init(); alpar@100: /// d.addSource(s); alpar@100: /// d.start(); alpar@100: ///\endcode alpar@100: void run(Node s) { alpar@100: init(); alpar@100: addSource(s); alpar@100: start(); alpar@100: } alpar@100: alpar@100: ///Finds the %DFS path between \c s and \c t. alpar@100: alpar@100: ///Finds the %DFS path between \c s and \c t. alpar@100: /// alpar@100: ///\return The length of the %DFS s---t path if there exists one, alpar@100: ///0 otherwise. alpar@100: ///\note Apart from the return value, d.run(s,t) is alpar@100: ///just a shortcut of the following code. alpar@100: ///\code alpar@100: /// d.init(); alpar@100: /// d.addSource(s); alpar@100: /// d.start(t); alpar@100: ///\endcode alpar@100: int run(Node s,Node t) { alpar@100: init(); alpar@100: addSource(s); alpar@100: start(t); alpar@100: return reached(t)?_stack_head+1:0; alpar@100: } alpar@100: alpar@100: ///@} alpar@100: alpar@100: ///\name Query Functions alpar@100: ///The result of the %DFS algorithm can be obtained using these alpar@100: ///functions.\n alpar@100: ///Before the use of these functions, alpar@100: ///either run() or start() must be called. alpar@100: alpar@100: ///@{ alpar@100: alpar@100: typedef PredMapPath Path; alpar@100: alpar@100: ///Gives back the shortest path. alpar@100: alpar@100: ///Gives back the shortest path. alpar@100: ///\pre The \c t should be reachable from the source. alpar@100: Path path(Node t) alpar@100: { alpar@100: return Path(*G, *_pred, t); alpar@100: } alpar@100: alpar@100: ///The distance of a node from the root(s). alpar@100: alpar@100: ///Returns the distance of a node from the root(s). alpar@100: ///\pre \ref run() must be called before using this function. alpar@100: ///\warning If node \c v is unreachable from the root(s) then the return alpar@100: ///value of this funcion is undefined. alpar@100: int dist(Node v) const { return (*_dist)[v]; } alpar@100: alpar@100: ///Returns the 'previous arc' of the %DFS tree. alpar@100: alpar@100: ///For a node \c v it returns the 'previous arc' alpar@100: ///of the %DFS path, alpar@100: ///i.e. it returns the last arc of a %DFS path from the root(s) to \c alpar@100: ///v. It is \ref INVALID alpar@100: ///if \c v is unreachable from the root(s) or \c v is a root. The alpar@100: ///%DFS tree used here is equal to the %DFS tree used in alpar@100: ///\ref predNode(). alpar@100: ///\pre Either \ref run() or \ref start() must be called before using alpar@100: ///this function. alpar@100: Arc predArc(Node v) const { return (*_pred)[v];} alpar@100: alpar@100: ///Returns the 'previous node' of the %DFS tree. alpar@100: alpar@100: ///For a node \c v it returns the 'previous node' alpar@100: ///of the %DFS tree, alpar@100: ///i.e. it returns the last but one node from a %DFS path from the alpar@100: ///root(s) to \c v. alpar@100: ///It is INVALID if \c v is unreachable from the root(s) or alpar@100: ///if \c v itself a root. alpar@100: ///The %DFS tree used here is equal to the %DFS alpar@100: ///tree used in \ref predArc(). alpar@100: ///\pre Either \ref run() or \ref start() must be called before alpar@100: ///using this function. alpar@100: Node predNode(Node v) const { return (*_pred)[v]==INVALID ? INVALID: alpar@100: G->source((*_pred)[v]); } alpar@100: alpar@100: ///Returns a reference to the NodeMap of distances. alpar@100: alpar@100: ///Returns a reference to the NodeMap of distances. alpar@100: ///\pre Either \ref run() or \ref init() must alpar@100: ///be called before using this function. alpar@100: const DistMap &distMap() const { return *_dist;} alpar@100: alpar@100: ///Returns a reference to the %DFS arc-tree map. alpar@100: alpar@100: ///Returns a reference to the NodeMap of the arcs of the alpar@100: ///%DFS tree. alpar@100: ///\pre Either \ref run() or \ref init() alpar@100: ///must be called before using this function. alpar@100: const PredMap &predMap() const { return *_pred;} alpar@100: alpar@100: ///Checks if a node is reachable from the root. alpar@100: alpar@100: ///Returns \c true if \c v is reachable from the root(s). alpar@100: ///\warning The source nodes are inditated as unreachable. alpar@100: ///\pre Either \ref run() or \ref start() alpar@100: ///must be called before using this function. alpar@100: /// alpar@100: bool reached(Node v) { return (*_reached)[v]; } alpar@100: alpar@100: ///@} alpar@100: }; alpar@100: alpar@100: ///Default traits class of Dfs function. alpar@100: alpar@100: ///Default traits class of Dfs function. kpeter@157: ///\tparam GR Digraph type. alpar@100: template alpar@100: struct DfsWizardDefaultTraits alpar@100: { alpar@100: ///The digraph type the algorithm runs on. alpar@100: typedef GR Digraph; alpar@100: ///\brief The type of the map that stores the last alpar@100: ///arcs of the %DFS paths. alpar@100: /// alpar@100: ///The type of the map that stores the last alpar@100: ///arcs of the %DFS paths. alpar@100: ///It must meet the \ref concepts::WriteMap "WriteMap" concept. alpar@100: /// alpar@100: typedef NullMap PredMap; alpar@100: ///Instantiates a PredMap. alpar@100: alpar@100: ///This function instantiates a \ref PredMap. alpar@100: ///\param g is the digraph, to which we would like to define the PredMap. alpar@100: ///\todo The digraph alone may be insufficient to initialize alpar@100: #ifdef DOXYGEN alpar@100: static PredMap *createPredMap(const GR &g) alpar@100: #else alpar@100: static PredMap *createPredMap(const GR &) alpar@100: #endif alpar@100: { alpar@100: return new PredMap(); alpar@100: } alpar@100: alpar@100: ///The type of the map that indicates which nodes are processed. alpar@100: alpar@100: ///The type of the map that indicates which nodes are processed. alpar@100: ///It must meet the \ref concepts::WriteMap "WriteMap" concept. alpar@100: ///\todo named parameter to set this type, function to read and write. alpar@100: typedef NullMap ProcessedMap; alpar@100: ///Instantiates a ProcessedMap. alpar@100: alpar@100: ///This function instantiates a \ref ProcessedMap. alpar@100: ///\param g is the digraph, to which alpar@100: ///we would like to define the \ref ProcessedMap alpar@100: #ifdef DOXYGEN alpar@100: static ProcessedMap *createProcessedMap(const GR &g) alpar@100: #else alpar@100: static ProcessedMap *createProcessedMap(const GR &) alpar@100: #endif alpar@100: { alpar@100: return new ProcessedMap(); alpar@100: } alpar@100: ///The type of the map that indicates which nodes are reached. alpar@100: alpar@100: ///The type of the map that indicates which nodes are reached. alpar@100: ///It must meet the \ref concepts::WriteMap "WriteMap" concept. alpar@100: ///\todo named parameter to set this type, function to read and write. alpar@100: typedef typename Digraph::template NodeMap ReachedMap; alpar@100: ///Instantiates a ReachedMap. alpar@100: alpar@100: ///This function instantiates a \ref ReachedMap. alpar@100: ///\param G is the digraph, to which alpar@100: ///we would like to define the \ref ReachedMap. alpar@100: static ReachedMap *createReachedMap(const GR &G) alpar@100: { alpar@100: return new ReachedMap(G); alpar@100: } alpar@100: ///The type of the map that stores the dists of the nodes. alpar@100: alpar@100: ///The type of the map that stores the dists of the nodes. alpar@100: ///It must meet the \ref concepts::WriteMap "WriteMap" concept. alpar@100: /// alpar@100: typedef NullMap DistMap; alpar@100: ///Instantiates a DistMap. alpar@100: alpar@100: ///This function instantiates a \ref DistMap. alpar@100: ///\param g is the digraph, to which we would like to define the \ref DistMap alpar@100: #ifdef DOXYGEN alpar@100: static DistMap *createDistMap(const GR &g) alpar@100: #else alpar@100: static DistMap *createDistMap(const GR &) alpar@100: #endif alpar@100: { alpar@100: return new DistMap(); alpar@100: } alpar@100: }; alpar@100: alpar@100: /// Default traits used by \ref DfsWizard alpar@100: alpar@100: /// To make it easier to use Dfs algorithm alpar@100: ///we have created a wizard class. alpar@100: /// This \ref DfsWizard class needs default traits, alpar@100: ///as well as the \ref Dfs class. alpar@100: /// The \ref DfsWizardBase is a class to be the default traits of the alpar@100: /// \ref DfsWizard class. alpar@100: template alpar@100: class DfsWizardBase : public DfsWizardDefaultTraits alpar@100: { alpar@100: alpar@100: typedef DfsWizardDefaultTraits Base; alpar@100: protected: alpar@100: /// Type of the nodes in the digraph. alpar@100: typedef typename Base::Digraph::Node Node; alpar@100: alpar@100: /// Pointer to the underlying digraph. alpar@100: void *_g; alpar@100: ///Pointer to the map of reached nodes. alpar@100: void *_reached; alpar@100: ///Pointer to the map of processed nodes. alpar@100: void *_processed; alpar@100: ///Pointer to the map of predecessors arcs. alpar@100: void *_pred; alpar@100: ///Pointer to the map of distances. alpar@100: void *_dist; alpar@100: ///Pointer to the source node. alpar@100: Node _source; alpar@100: alpar@100: public: alpar@100: /// Constructor. alpar@100: alpar@100: /// This constructor does not require parameters, therefore it initiates alpar@100: /// all of the attributes to default values (0, INVALID). alpar@100: DfsWizardBase() : _g(0), _reached(0), _processed(0), _pred(0), alpar@100: _dist(0), _source(INVALID) {} alpar@100: alpar@100: /// Constructor. alpar@100: alpar@100: /// This constructor requires some parameters, alpar@100: /// listed in the parameters list. alpar@100: /// Others are initiated to 0. alpar@100: /// \param g is the initial value of \ref _g alpar@100: /// \param s is the initial value of \ref _source alpar@100: DfsWizardBase(const GR &g, Node s=INVALID) : alpar@100: _g(reinterpret_cast(const_cast(&g))), alpar@100: _reached(0), _processed(0), _pred(0), _dist(0), _source(s) {} alpar@100: alpar@100: }; alpar@100: alpar@100: /// A class to make the usage of the Dfs algorithm easier alpar@100: alpar@100: /// This class is created to make it easier to use the Dfs algorithm. alpar@100: /// It uses the functions and features of the plain \ref Dfs, alpar@100: /// but it is much simpler to use it. alpar@100: /// alpar@100: /// Simplicity means that the way to change the types defined alpar@100: /// in the traits class is based on functions that returns the new class alpar@100: /// and not on templatable built-in classes. alpar@100: /// When using the plain \ref Dfs alpar@100: /// the new class with the modified type comes from alpar@100: /// the original class by using the :: alpar@100: /// operator. In the case of \ref DfsWizard only alpar@100: /// a function have to be called and it will alpar@100: /// return the needed class. alpar@100: /// alpar@100: /// It does not have own \ref run method. When its \ref run method is called alpar@100: /// it initiates a plain \ref Dfs object, and calls the \ref Dfs::run alpar@100: /// method of it. alpar@100: template alpar@100: class DfsWizard : public TR alpar@100: { alpar@100: typedef TR Base; alpar@100: alpar@100: ///The type of the underlying digraph. alpar@100: typedef typename TR::Digraph Digraph; alpar@100: //\e alpar@100: typedef typename Digraph::Node Node; alpar@100: //\e alpar@100: typedef typename Digraph::NodeIt NodeIt; alpar@100: //\e alpar@100: typedef typename Digraph::Arc Arc; alpar@100: //\e alpar@100: typedef typename Digraph::OutArcIt OutArcIt; alpar@100: alpar@100: ///\brief The type of the map that stores alpar@100: ///the reached nodes alpar@100: typedef typename TR::ReachedMap ReachedMap; alpar@100: ///\brief The type of the map that stores alpar@100: ///the processed nodes alpar@100: typedef typename TR::ProcessedMap ProcessedMap; alpar@100: ///\brief The type of the map that stores the last alpar@100: ///arcs of the %DFS paths. alpar@100: typedef typename TR::PredMap PredMap; alpar@100: ///The type of the map that stores the distances of the nodes. alpar@100: typedef typename TR::DistMap DistMap; alpar@100: alpar@100: public: alpar@100: /// Constructor. alpar@100: DfsWizard() : TR() {} alpar@100: alpar@100: /// Constructor that requires parameters. alpar@100: alpar@100: /// Constructor that requires parameters. alpar@100: /// These parameters will be the default values for the traits class. alpar@100: DfsWizard(const Digraph &g, Node s=INVALID) : alpar@100: TR(g,s) {} alpar@100: alpar@100: ///Copy constructor alpar@100: DfsWizard(const TR &b) : TR(b) {} alpar@100: alpar@100: ~DfsWizard() {} alpar@100: alpar@100: ///Runs Dfs algorithm from a given node. alpar@100: alpar@100: ///Runs Dfs algorithm from a given node. alpar@100: ///The node can be given by the \ref source function. alpar@100: void run() alpar@100: { alpar@100: if(Base::_source==INVALID) throw UninitializedParameter(); alpar@100: Dfs alg(*reinterpret_cast(Base::_g)); alpar@100: if(Base::_reached) alpar@100: alg.reachedMap(*reinterpret_cast(Base::_reached)); alpar@100: if(Base::_processed) alpar@100: alg.processedMap(*reinterpret_cast(Base::_processed)); alpar@100: if(Base::_pred) alpar@100: alg.predMap(*reinterpret_cast(Base::_pred)); alpar@100: if(Base::_dist) alpar@100: alg.distMap(*reinterpret_cast(Base::_dist)); alpar@100: alg.run(Base::_source); alpar@100: } alpar@100: alpar@100: ///Runs Dfs algorithm from the given node. alpar@100: alpar@100: ///Runs Dfs algorithm from the given node. alpar@100: ///\param s is the given source. alpar@100: void run(Node s) alpar@100: { alpar@100: Base::_source=s; alpar@100: run(); alpar@100: } alpar@100: alpar@100: template alpar@100: struct DefPredMapBase : public Base { alpar@100: typedef T PredMap; alpar@100: static PredMap *createPredMap(const Digraph &) { return 0; }; alpar@100: DefPredMapBase(const TR &b) : TR(b) {} alpar@100: }; alpar@100: alpar@100: ///\brief \ref named-templ-param "Named parameter" alpar@100: ///function for setting PredMap type alpar@100: /// alpar@100: /// \ref named-templ-param "Named parameter" alpar@100: ///function for setting PredMap type alpar@100: /// alpar@100: template alpar@100: DfsWizard > predMap(const T &t) alpar@100: { alpar@100: Base::_pred=reinterpret_cast(const_cast(&t)); alpar@100: return DfsWizard >(*this); alpar@100: } alpar@100: alpar@100: alpar@100: template alpar@100: struct DefReachedMapBase : public Base { alpar@100: typedef T ReachedMap; alpar@100: static ReachedMap *createReachedMap(const Digraph &) { return 0; }; alpar@100: DefReachedMapBase(const TR &b) : TR(b) {} alpar@100: }; alpar@100: alpar@100: ///\brief \ref named-templ-param "Named parameter" alpar@100: ///function for setting ReachedMap alpar@100: /// alpar@100: /// \ref named-templ-param "Named parameter" alpar@100: ///function for setting ReachedMap alpar@100: /// alpar@100: template alpar@100: DfsWizard > reachedMap(const T &t) alpar@100: { deba@158: Base::_reached=reinterpret_cast(const_cast(&t)); alpar@100: return DfsWizard >(*this); alpar@100: } alpar@100: alpar@100: alpar@100: template alpar@100: struct DefProcessedMapBase : public Base { alpar@100: typedef T ProcessedMap; alpar@100: static ProcessedMap *createProcessedMap(const Digraph &) { return 0; }; alpar@100: DefProcessedMapBase(const TR &b) : TR(b) {} alpar@100: }; alpar@100: alpar@100: ///\brief \ref named-templ-param "Named parameter" alpar@100: ///function for setting ProcessedMap alpar@100: /// alpar@100: /// \ref named-templ-param "Named parameter" alpar@100: ///function for setting ProcessedMap alpar@100: /// alpar@100: template alpar@100: DfsWizard > processedMap(const T &t) alpar@100: { deba@158: Base::_processed=reinterpret_cast(const_cast(&t)); alpar@100: return DfsWizard >(*this); alpar@100: } alpar@100: alpar@100: template alpar@100: struct DefDistMapBase : public Base { alpar@100: typedef T DistMap; alpar@100: static DistMap *createDistMap(const Digraph &) { return 0; }; alpar@100: DefDistMapBase(const TR &b) : TR(b) {} alpar@100: }; alpar@100: alpar@100: ///\brief \ref named-templ-param "Named parameter" alpar@100: ///function for setting DistMap type alpar@100: /// alpar@100: /// \ref named-templ-param "Named parameter" alpar@100: ///function for setting DistMap type alpar@100: /// alpar@100: template alpar@100: DfsWizard > distMap(const T &t) alpar@100: { alpar@100: Base::_dist=reinterpret_cast(const_cast(&t)); alpar@100: return DfsWizard >(*this); alpar@100: } alpar@100: alpar@100: /// Sets the source node, from which the Dfs algorithm runs. alpar@100: alpar@100: /// Sets the source node, from which the Dfs algorithm runs. alpar@100: /// \param s is the source node. alpar@100: DfsWizard &source(Node s) alpar@100: { alpar@100: Base::_source=s; alpar@100: return *this; alpar@100: } alpar@100: alpar@100: }; alpar@100: alpar@100: ///Function type interface for Dfs algorithm. alpar@100: alpar@100: ///\ingroup search alpar@100: ///Function type interface for Dfs algorithm. alpar@100: /// alpar@100: ///This function also has several alpar@100: ///\ref named-templ-func-param "named parameters", alpar@100: ///they are declared as the members of class \ref DfsWizard. alpar@100: ///The following alpar@100: ///example shows how to use these parameters. alpar@100: ///\code alpar@100: /// dfs(g,source).predMap(preds).run(); alpar@100: ///\endcode alpar@100: ///\warning Don't forget to put the \ref DfsWizard::run() "run()" alpar@100: ///to the end of the parameter list. alpar@100: ///\sa DfsWizard alpar@100: ///\sa Dfs alpar@100: template alpar@100: DfsWizard > alpar@100: dfs(const GR &g,typename GR::Node s=INVALID) alpar@100: { alpar@100: return DfsWizard >(g,s); alpar@100: } alpar@100: alpar@100: #ifdef DOXYGEN alpar@100: /// \brief Visitor class for dfs. alpar@100: /// alpar@100: /// It gives a simple interface for a functional interface for dfs alpar@100: /// traversal. The traversal on a linear data structure. alpar@100: template alpar@100: struct DfsVisitor { alpar@100: typedef _Digraph Digraph; alpar@100: typedef typename Digraph::Arc Arc; alpar@100: typedef typename Digraph::Node Node; alpar@100: /// \brief Called when the arc reach a node. alpar@100: /// alpar@100: /// It is called when the dfs find an arc which target is not alpar@100: /// reached yet. alpar@100: void discover(const Arc& arc) {} alpar@100: /// \brief Called when the node reached first time. alpar@100: /// alpar@100: /// It is Called when the node reached first time. alpar@100: void reach(const Node& node) {} alpar@100: /// \brief Called when we step back on an arc. alpar@100: /// alpar@100: /// It is called when the dfs should step back on the arc. alpar@100: void backtrack(const Arc& arc) {} alpar@100: /// \brief Called when we step back from the node. alpar@100: /// alpar@100: /// It is called when we step back from the node. alpar@100: void leave(const Node& node) {} alpar@100: /// \brief Called when the arc examined but target of the arc alpar@100: /// already discovered. alpar@100: /// alpar@100: /// It called when the arc examined but the target of the arc alpar@100: /// already discovered. alpar@100: void examine(const Arc& arc) {} alpar@100: /// \brief Called for the source node of the dfs. alpar@100: /// alpar@100: /// It is called for the source node of the dfs. alpar@100: void start(const Node& node) {} alpar@100: /// \brief Called when we leave the source node of the dfs. alpar@100: /// alpar@100: /// It is called when we leave the source node of the dfs. alpar@100: void stop(const Node& node) {} alpar@100: alpar@100: }; alpar@100: #else alpar@100: template alpar@100: struct DfsVisitor { alpar@100: typedef _Digraph Digraph; alpar@100: typedef typename Digraph::Arc Arc; alpar@100: typedef typename Digraph::Node Node; alpar@100: void discover(const Arc&) {} alpar@100: void reach(const Node&) {} alpar@100: void backtrack(const Arc&) {} alpar@100: void leave(const Node&) {} alpar@100: void examine(const Arc&) {} alpar@100: void start(const Node&) {} alpar@100: void stop(const Node&) {} alpar@100: alpar@100: template alpar@100: struct Constraints { alpar@100: void constraints() { alpar@100: Arc arc; alpar@100: Node node; alpar@100: visitor.discover(arc); alpar@100: visitor.reach(node); alpar@100: visitor.backtrack(arc); alpar@100: visitor.leave(node); alpar@100: visitor.examine(arc); alpar@100: visitor.start(node); alpar@100: visitor.stop(arc); alpar@100: } alpar@100: _Visitor& visitor; alpar@100: }; alpar@100: }; alpar@100: #endif alpar@100: alpar@100: /// \brief Default traits class of DfsVisit class. alpar@100: /// alpar@100: /// Default traits class of DfsVisit class. kpeter@157: /// \tparam _Digraph Digraph type. alpar@100: template alpar@100: struct DfsVisitDefaultTraits { alpar@100: alpar@100: /// \brief The digraph type the algorithm runs on. alpar@100: typedef _Digraph Digraph; alpar@100: alpar@100: /// \brief The type of the map that indicates which nodes are reached. alpar@100: /// alpar@100: /// The type of the map that indicates which nodes are reached. alpar@100: /// It must meet the \ref concepts::WriteMap "WriteMap" concept. alpar@100: /// \todo named parameter to set this type, function to read and write. alpar@100: typedef typename Digraph::template NodeMap ReachedMap; alpar@100: alpar@100: /// \brief Instantiates a ReachedMap. alpar@100: /// alpar@100: /// This function instantiates a \ref ReachedMap. alpar@100: /// \param digraph is the digraph, to which alpar@100: /// we would like to define the \ref ReachedMap. alpar@100: static ReachedMap *createReachedMap(const Digraph &digraph) { alpar@100: return new ReachedMap(digraph); alpar@100: } alpar@100: alpar@100: }; alpar@100: alpar@100: /// %DFS Visit algorithm class. alpar@100: alpar@100: /// \ingroup search alpar@100: /// This class provides an efficient implementation of the %DFS algorithm alpar@100: /// with visitor interface. alpar@100: /// alpar@100: /// The %DfsVisit class provides an alternative interface to the Dfs alpar@100: /// class. It works with callback mechanism, the DfsVisit object calls alpar@100: /// on every dfs event the \c Visitor class member functions. alpar@100: /// kpeter@157: /// \tparam _Digraph The digraph type the algorithm runs on. The default value is alpar@100: /// \ref ListDigraph. The value of _Digraph is not used directly by Dfs, it alpar@100: /// is only passed to \ref DfsDefaultTraits. kpeter@157: /// \tparam _Visitor The Visitor object for the algorithm. The alpar@100: /// \ref DfsVisitor "DfsVisitor<_Digraph>" is an empty Visitor which alpar@100: /// does not observe the Dfs events. If you want to observe the dfs alpar@100: /// events you should implement your own Visitor class. kpeter@157: /// \tparam _Traits Traits class to set various data types used by the alpar@100: /// algorithm. The default traits class is alpar@100: /// \ref DfsVisitDefaultTraits "DfsVisitDefaultTraits<_Digraph>". alpar@100: /// See \ref DfsVisitDefaultTraits for the documentation of alpar@100: /// a Dfs visit traits class. alpar@100: /// alpar@100: /// \author Jacint Szabo, Alpar Juttner and Balazs Dezso alpar@100: #ifdef DOXYGEN alpar@100: template alpar@100: #else alpar@100: template , alpar@100: typename _Traits = DfsDefaultTraits<_Digraph> > alpar@100: #endif alpar@100: class DfsVisit { alpar@100: public: alpar@100: alpar@100: /// \brief \ref Exception for uninitialized parameters. alpar@100: /// alpar@100: /// This error represents problems in the initialization alpar@100: /// of the parameters of the algorithms. alpar@100: class UninitializedParameter : public lemon::UninitializedParameter { alpar@100: public: alpar@100: virtual const char* what() const throw() alpar@100: { alpar@100: return "lemon::DfsVisit::UninitializedParameter"; alpar@100: } alpar@100: }; alpar@100: alpar@100: typedef _Traits Traits; alpar@100: alpar@100: typedef typename Traits::Digraph Digraph; alpar@100: alpar@100: typedef _Visitor Visitor; alpar@100: alpar@100: ///The type of the map indicating which nodes are reached. alpar@100: typedef typename Traits::ReachedMap ReachedMap; alpar@100: alpar@100: private: alpar@100: alpar@100: typedef typename Digraph::Node Node; alpar@100: typedef typename Digraph::NodeIt NodeIt; alpar@100: typedef typename Digraph::Arc Arc; alpar@100: typedef typename Digraph::OutArcIt OutArcIt; alpar@100: alpar@100: /// Pointer to the underlying digraph. alpar@100: const Digraph *_digraph; alpar@100: /// Pointer to the visitor object. alpar@100: Visitor *_visitor; alpar@100: ///Pointer to the map of reached status of the nodes. alpar@100: ReachedMap *_reached; alpar@100: ///Indicates if \ref _reached is locally allocated (\c true) or not. alpar@100: bool local_reached; alpar@100: alpar@100: std::vector _stack; alpar@100: int _stack_head; alpar@100: alpar@100: /// \brief Creates the maps if necessary. alpar@100: /// alpar@100: /// Creates the maps if necessary. alpar@100: void create_maps() { alpar@100: if(!_reached) { alpar@100: local_reached = true; alpar@100: _reached = Traits::createReachedMap(*_digraph); alpar@100: } alpar@100: } alpar@100: alpar@100: protected: alpar@100: alpar@100: DfsVisit() {} alpar@100: alpar@100: public: alpar@100: alpar@100: typedef DfsVisit Create; alpar@100: alpar@100: /// \name Named template parameters alpar@100: alpar@100: ///@{ alpar@100: template alpar@100: struct DefReachedMapTraits : public Traits { alpar@100: typedef T ReachedMap; alpar@100: static ReachedMap *createReachedMap(const Digraph &digraph) { alpar@100: throw UninitializedParameter(); alpar@100: } alpar@100: }; alpar@100: /// \brief \ref named-templ-param "Named parameter" for setting alpar@100: /// ReachedMap type alpar@100: /// alpar@100: /// \ref named-templ-param "Named parameter" for setting ReachedMap type alpar@100: template alpar@100: struct DefReachedMap : public DfsVisit< Digraph, Visitor, alpar@100: DefReachedMapTraits > { alpar@100: typedef DfsVisit< Digraph, Visitor, DefReachedMapTraits > Create; alpar@100: }; alpar@100: ///@} alpar@100: alpar@100: public: alpar@100: alpar@100: /// \brief Constructor. alpar@100: /// alpar@100: /// Constructor. alpar@100: /// alpar@100: /// \param digraph the digraph the algorithm will run on. alpar@100: /// \param visitor The visitor of the algorithm. alpar@100: /// alpar@100: DfsVisit(const Digraph& digraph, Visitor& visitor) alpar@100: : _digraph(&digraph), _visitor(&visitor), alpar@100: _reached(0), local_reached(false) {} alpar@100: alpar@100: /// \brief Destructor. alpar@100: /// alpar@100: /// Destructor. alpar@100: ~DfsVisit() { alpar@100: if(local_reached) delete _reached; alpar@100: } alpar@100: alpar@100: /// \brief Sets the map indicating if a node is reached. alpar@100: /// alpar@100: /// Sets the map indicating if a node is reached. alpar@100: /// If you don't use this function before calling \ref run(), alpar@100: /// it will allocate one. The destuctor deallocates this alpar@100: /// automatically allocated map, of course. alpar@100: /// \return (*this) alpar@100: DfsVisit &reachedMap(ReachedMap &m) { alpar@100: if(local_reached) { alpar@100: delete _reached; alpar@100: local_reached=false; alpar@100: } alpar@100: _reached = &m; alpar@100: return *this; alpar@100: } alpar@100: alpar@100: public: alpar@100: /// \name Execution control alpar@100: /// The simplest way to execute the algorithm is to use alpar@100: /// one of the member functions called \c run(...). alpar@100: /// \n alpar@100: /// If you need more control on the execution, alpar@100: /// first you must call \ref init(), then you can adda source node alpar@100: /// with \ref addSource(). alpar@100: /// Finally \ref start() will perform the actual path alpar@100: /// computation. alpar@100: alpar@100: /// @{ alpar@100: /// \brief Initializes the internal data structures. alpar@100: /// alpar@100: /// Initializes the internal data structures. alpar@100: /// alpar@100: void init() { alpar@100: create_maps(); alpar@100: _stack.resize(countNodes(*_digraph)); alpar@100: _stack_head = -1; alpar@100: for (NodeIt u(*_digraph) ; u != INVALID ; ++u) { alpar@100: _reached->set(u, false); alpar@100: } alpar@100: } alpar@100: alpar@100: /// \brief Adds a new source node. alpar@100: /// alpar@100: /// Adds a new source node to the set of nodes to be processed. alpar@100: void addSource(Node s) { alpar@100: if(!(*_reached)[s]) { alpar@100: _reached->set(s,true); alpar@100: _visitor->start(s); alpar@100: _visitor->reach(s); alpar@100: Arc e; alpar@100: _digraph->firstOut(e, s); alpar@100: if (e != INVALID) { alpar@100: _stack[++_stack_head] = e; alpar@100: } else { alpar@100: _visitor->leave(s); alpar@100: } alpar@100: } alpar@100: } alpar@100: alpar@100: /// \brief Processes the next arc. alpar@100: /// alpar@100: /// Processes the next arc. alpar@100: /// alpar@100: /// \return The processed arc. alpar@100: /// alpar@100: /// \pre The stack must not be empty! alpar@100: Arc processNextArc() { alpar@100: Arc e = _stack[_stack_head]; alpar@100: Node m = _digraph->target(e); alpar@100: if(!(*_reached)[m]) { alpar@100: _visitor->discover(e); alpar@100: _visitor->reach(m); alpar@100: _reached->set(m, true); alpar@100: _digraph->firstOut(_stack[++_stack_head], m); alpar@100: } else { alpar@100: _visitor->examine(e); alpar@100: m = _digraph->source(e); alpar@100: _digraph->nextOut(_stack[_stack_head]); alpar@100: } alpar@100: while (_stack_head>=0 && _stack[_stack_head] == INVALID) { alpar@100: _visitor->leave(m); alpar@100: --_stack_head; alpar@100: if (_stack_head >= 0) { alpar@100: _visitor->backtrack(_stack[_stack_head]); alpar@100: m = _digraph->source(_stack[_stack_head]); alpar@100: _digraph->nextOut(_stack[_stack_head]); alpar@100: } else { alpar@100: _visitor->stop(m); alpar@100: } alpar@100: } alpar@100: return e; alpar@100: } alpar@100: alpar@100: /// \brief Next arc to be processed. alpar@100: /// alpar@100: /// Next arc to be processed. alpar@100: /// alpar@100: /// \return The next arc to be processed or INVALID if the stack is alpar@100: /// empty. alpar@100: Arc nextArc() { alpar@100: return _stack_head >= 0 ? _stack[_stack_head] : INVALID; alpar@100: } alpar@100: alpar@100: /// \brief Returns \c false if there are nodes alpar@100: /// to be processed in the queue alpar@100: /// alpar@100: /// Returns \c false if there are nodes alpar@100: /// to be processed in the queue alpar@100: bool emptyQueue() { return _stack_head < 0; } alpar@100: alpar@100: /// \brief Returns the number of the nodes to be processed. alpar@100: /// alpar@100: /// Returns the number of the nodes to be processed in the queue. alpar@100: int queueSize() { return _stack_head + 1; } alpar@100: alpar@100: /// \brief Executes the algorithm. alpar@100: /// alpar@100: /// Executes the algorithm. alpar@100: /// alpar@100: /// \pre init() must be called and at least one node should be added alpar@100: /// with addSource() before using this function. alpar@100: void start() { alpar@100: while ( !emptyQueue() ) processNextArc(); alpar@100: } alpar@100: alpar@100: /// \brief Executes the algorithm until \c dest is reached. alpar@100: /// alpar@100: /// Executes the algorithm until \c dest is reached. alpar@100: /// alpar@100: /// \pre init() must be called and at least one node should be added alpar@100: /// with addSource() before using this function. alpar@100: void start(Node dest) { alpar@100: while ( !emptyQueue() && _digraph->target(_stack[_stack_head]) != dest ) alpar@100: processNextArc(); alpar@100: } alpar@100: alpar@100: /// \brief Executes the algorithm until a condition is met. alpar@100: /// alpar@100: /// Executes the algorithm until a condition is met. alpar@100: /// alpar@100: /// \pre init() must be called and at least one node should be added alpar@100: /// with addSource() before using this function. alpar@100: /// alpar@100: /// \param em must be a bool (or convertible) arc map. The algorithm alpar@100: /// will stop when it reaches an arc \c e with em[e] true. alpar@100: /// alpar@100: ///\return The reached arc \c e with em[e] true or alpar@100: ///\c INVALID if no such arc was found. alpar@100: /// alpar@100: /// \warning Contrary to \ref Bfs and \ref Dijkstra, \c em is an arc map, alpar@100: /// not a node map. alpar@100: template alpar@100: Arc start(const EM &em) { alpar@100: while ( !emptyQueue() && !em[_stack[_stack_head]] ) alpar@100: processNextArc(); alpar@100: return emptyQueue() ? INVALID : _stack[_stack_head]; alpar@100: } alpar@100: alpar@100: /// \brief Runs %DFSVisit algorithm from node \c s. alpar@100: /// alpar@100: /// This method runs the %DFS algorithm from a root node \c s. alpar@100: /// \note d.run(s) is just a shortcut of the following code. alpar@100: ///\code alpar@100: /// d.init(); alpar@100: /// d.addSource(s); alpar@100: /// d.start(); alpar@100: ///\endcode alpar@100: void run(Node s) { alpar@100: init(); alpar@100: addSource(s); alpar@100: start(); alpar@100: } alpar@100: alpar@100: /// \brief Runs %DFSVisit algorithm to visit all nodes in the digraph. alpar@100: alpar@100: /// This method runs the %DFS algorithm in order to alpar@100: /// compute the %DFS path to each node. The algorithm computes alpar@100: /// - The %DFS tree. alpar@100: /// - The distance of each node from the root in the %DFS tree. alpar@100: /// alpar@100: ///\note d.run() is just a shortcut of the following code. alpar@100: ///\code alpar@100: /// d.init(); alpar@100: /// for (NodeIt it(digraph); it != INVALID; ++it) { alpar@100: /// if (!d.reached(it)) { alpar@100: /// d.addSource(it); alpar@100: /// d.start(); alpar@100: /// } alpar@100: /// } alpar@100: ///\endcode alpar@100: void run() { alpar@100: init(); alpar@100: for (NodeIt it(*_digraph); it != INVALID; ++it) { alpar@100: if (!reached(it)) { alpar@100: addSource(it); alpar@100: start(); alpar@100: } alpar@100: } alpar@100: } alpar@100: ///@} alpar@100: alpar@100: /// \name Query Functions alpar@100: /// The result of the %DFS algorithm can be obtained using these alpar@100: /// functions.\n alpar@100: /// Before the use of these functions, alpar@100: /// either run() or start() must be called. alpar@100: ///@{ alpar@100: /// \brief Checks if a node is reachable from the root. alpar@100: /// alpar@100: /// Returns \c true if \c v is reachable from the root(s). alpar@100: /// \warning The source nodes are inditated as unreachable. alpar@100: /// \pre Either \ref run() or \ref start() alpar@100: /// must be called before using this function. alpar@100: /// alpar@100: bool reached(Node v) { return (*_reached)[v]; } alpar@100: ///@} alpar@100: }; alpar@100: alpar@100: alpar@100: } //END OF NAMESPACE LEMON alpar@100: alpar@100: #endif alpar@100: