alpar@209: /* -*- mode: C++; indent-tabs-mode: nil; -*- alpar@100: * alpar@209: * This file is a part of LEMON, a generic C++ optimization library. alpar@100: * alpar@440: * Copyright (C) 2003-2009 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 kpeter@244: ///\brief DFS algorithm. alpar@100: alpar@100: #include alpar@100: #include deba@220: #include alpar@100: #include alpar@100: #include kpeter@278: #include alpar@100: alpar@100: namespace lemon { 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: { kpeter@244: ///The type of the digraph the algorithm runs on. alpar@100: typedef GR Digraph; kpeter@244: kpeter@244: ///\brief The type of the map that stores the predecessor alpar@100: ///arcs of the %DFS paths. alpar@209: /// kpeter@244: ///The type of the map that stores the predecessor alpar@100: ///arcs of the %DFS paths. kpeter@716: ///It must conform to the \ref concepts::WriteMap "WriteMap" concept. kpeter@244: typedef typename Digraph::template NodeMap PredMap; kpeter@503: ///Instantiates a \c PredMap. alpar@209: kpeter@503: ///This function instantiates a \ref PredMap. kpeter@244: ///\param g is the digraph, to which we would like to define the kpeter@503: ///\ref PredMap. kpeter@244: static PredMap *createPredMap(const Digraph &g) alpar@100: { kpeter@244: return new PredMap(g); alpar@100: } alpar@100: alpar@100: ///The type of the map that indicates which nodes are processed. alpar@209: alpar@100: ///The type of the map that indicates which nodes are processed. kpeter@716: ///It must conform to the \ref concepts::WriteMap "WriteMap" concept. kpeter@716: ///By default it is a NullMap. alpar@100: typedef NullMap ProcessedMap; kpeter@503: ///Instantiates a \c ProcessedMap. alpar@209: kpeter@503: ///This function instantiates a \ref ProcessedMap. alpar@100: ///\param g is the digraph, to which kpeter@503: ///we would like to define the \ref ProcessedMap. alpar@100: #ifdef DOXYGEN kpeter@244: static ProcessedMap *createProcessedMap(const Digraph &g) alpar@100: #else kpeter@244: static ProcessedMap *createProcessedMap(const Digraph &) alpar@100: #endif alpar@100: { alpar@100: return new ProcessedMap(); alpar@100: } kpeter@244: alpar@100: ///The type of the map that indicates which nodes are reached. alpar@209: alpar@100: ///The type of the map that indicates which nodes are reached. kpeter@716: ///It must conform to the \ref concepts::ReadWriteMap "ReadWriteMap" concept. alpar@100: typedef typename Digraph::template NodeMap ReachedMap; kpeter@503: ///Instantiates a \c ReachedMap. alpar@209: kpeter@503: ///This function instantiates a \ref ReachedMap. kpeter@244: ///\param g is the digraph, to which kpeter@503: ///we would like to define the \ref ReachedMap. kpeter@244: static ReachedMap *createReachedMap(const Digraph &g) alpar@100: { kpeter@244: return new ReachedMap(g); alpar@100: } alpar@209: kpeter@244: ///The type of the map that stores the distances of the nodes. kpeter@244: kpeter@244: ///The type of the map that stores the distances of the nodes. kpeter@716: ///It must conform to the \ref concepts::WriteMap "WriteMap" concept. alpar@100: typedef typename Digraph::template NodeMap DistMap; kpeter@503: ///Instantiates a \c DistMap. alpar@209: kpeter@503: ///This function instantiates a \ref DistMap. kpeter@244: ///\param g is the digraph, to which we would like to define the kpeter@503: ///\ref DistMap. kpeter@244: static DistMap *createDistMap(const Digraph &g) alpar@100: { kpeter@244: return new DistMap(g); alpar@100: } alpar@100: }; alpar@209: alpar@100: ///%DFS algorithm class. alpar@209: alpar@100: ///\ingroup search alpar@100: ///This class provides an efficient implementation of the %DFS algorithm. alpar@100: /// kpeter@278: ///There is also a \ref dfs() "function-type interface" for the DFS kpeter@244: ///algorithm, which is convenient in the simplier cases and it can be kpeter@244: ///used easier. kpeter@244: /// kpeter@244: ///\tparam GR The type of the digraph the algorithm runs on. kpeter@405: ///The default type is \ref ListDigraph. 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: kpeter@244: ///The type of the digraph the algorithm runs on. kpeter@244: typedef typename TR::Digraph Digraph; kpeter@244: kpeter@244: ///\brief The type of the map that stores the predecessor arcs of the kpeter@244: ///DFS paths. kpeter@244: typedef typename TR::PredMap PredMap; kpeter@244: ///The type of the map that stores the distances of the nodes. kpeter@244: typedef typename TR::DistMap DistMap; kpeter@244: ///The type of the map that indicates which nodes are reached. kpeter@244: typedef typename TR::ReachedMap ReachedMap; kpeter@244: ///The type of the map that indicates which nodes are processed. kpeter@244: typedef typename TR::ProcessedMap ProcessedMap; kpeter@244: ///The type of the paths. kpeter@244: typedef PredMapPath Path; kpeter@244: kpeter@405: ///The \ref DfsDefaultTraits "traits class" of the algorithm. alpar@100: typedef TR Traits; kpeter@244: kpeter@244: private: kpeter@244: 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@209: kpeter@244: //Pointer to the underlying digraph. alpar@100: const Digraph *G; kpeter@244: //Pointer to the map of predecessor arcs. alpar@100: PredMap *_pred; kpeter@244: //Indicates if _pred is locally allocated (true) or not. alpar@100: bool local_pred; kpeter@244: //Pointer to the map of distances. alpar@100: DistMap *_dist; kpeter@244: //Indicates if _dist is locally allocated (true) or not. alpar@100: bool local_dist; kpeter@244: //Pointer to the map of reached status of the nodes. alpar@100: ReachedMap *_reached; kpeter@244: //Indicates if _reached is locally allocated (true) or not. alpar@100: bool local_reached; kpeter@244: //Pointer to the map of processed status of the nodes. alpar@100: ProcessedMap *_processed; kpeter@244: //Indicates if _processed is locally allocated (true) or not. alpar@100: bool local_processed; alpar@100: alpar@100: std::vector _stack; alpar@100: int _stack_head; alpar@100: alpar@280: //Creates the maps if necessary. alpar@209: void create_maps() alpar@100: { alpar@100: if(!_pred) { alpar@209: local_pred = true; alpar@209: _pred = Traits::createPredMap(*G); alpar@100: } alpar@100: if(!_dist) { alpar@209: local_dist = true; alpar@209: _dist = Traits::createDistMap(*G); alpar@100: } alpar@100: if(!_reached) { alpar@209: local_reached = true; alpar@209: _reached = Traits::createReachedMap(*G); alpar@100: } alpar@100: if(!_processed) { alpar@209: local_processed = true; alpar@209: _processed = Traits::createProcessedMap(*G); alpar@100: } alpar@100: } alpar@100: alpar@100: protected: alpar@100: alpar@100: Dfs() {} alpar@209: alpar@100: public: alpar@100: alpar@100: typedef Dfs Create; alpar@100: kpeter@584: ///\name Named Template Parameters alpar@100: alpar@100: ///@{ alpar@100: alpar@100: template kpeter@257: struct SetPredMapTraits : public Traits { alpar@100: typedef T PredMap; kpeter@244: static PredMap *createPredMap(const Digraph &) alpar@100: { deba@290: LEMON_ASSERT(false, "PredMap is not initialized"); deba@290: return 0; // ignore warnings alpar@100: } alpar@100: }; alpar@100: ///\brief \ref named-templ-param "Named parameter" for setting kpeter@503: ///\c PredMap type. alpar@100: /// kpeter@244: ///\ref named-templ-param "Named parameter" for setting kpeter@503: ///\c PredMap type. kpeter@716: ///It must conform to the \ref concepts::WriteMap "WriteMap" concept. alpar@100: template kpeter@257: struct SetPredMap : public Dfs > { kpeter@257: typedef Dfs > Create; alpar@100: }; alpar@209: alpar@100: template kpeter@257: struct SetDistMapTraits : public Traits { alpar@100: typedef T DistMap; alpar@209: static DistMap *createDistMap(const Digraph &) alpar@100: { deba@290: LEMON_ASSERT(false, "DistMap is not initialized"); deba@290: return 0; // ignore warnings alpar@100: } alpar@100: }; alpar@100: ///\brief \ref named-templ-param "Named parameter" for setting kpeter@503: ///\c DistMap type. alpar@100: /// kpeter@244: ///\ref named-templ-param "Named parameter" for setting kpeter@503: ///\c DistMap type. kpeter@716: ///It must conform to the \ref concepts::WriteMap "WriteMap" concept. alpar@100: template kpeter@257: struct SetDistMap : public Dfs< Digraph, SetDistMapTraits > { kpeter@257: typedef Dfs > Create; alpar@100: }; alpar@209: alpar@100: template kpeter@257: struct SetReachedMapTraits : public Traits { alpar@100: typedef T ReachedMap; alpar@209: static ReachedMap *createReachedMap(const Digraph &) alpar@100: { deba@290: LEMON_ASSERT(false, "ReachedMap is not initialized"); deba@290: return 0; // ignore warnings alpar@100: } alpar@100: }; alpar@100: ///\brief \ref named-templ-param "Named parameter" for setting kpeter@503: ///\c ReachedMap type. alpar@100: /// kpeter@244: ///\ref named-templ-param "Named parameter" for setting kpeter@503: ///\c ReachedMap type. kpeter@716: ///It must conform to the \ref concepts::ReadWriteMap "ReadWriteMap" concept. alpar@100: template kpeter@257: struct SetReachedMap : public Dfs< Digraph, SetReachedMapTraits > { kpeter@257: typedef Dfs< Digraph, SetReachedMapTraits > Create; alpar@100: }; alpar@100: alpar@100: template kpeter@257: struct SetProcessedMapTraits : public Traits { alpar@100: typedef T ProcessedMap; alpar@209: static ProcessedMap *createProcessedMap(const Digraph &) alpar@100: { deba@290: LEMON_ASSERT(false, "ProcessedMap is not initialized"); deba@290: return 0; // ignore warnings alpar@100: } alpar@100: }; alpar@100: ///\brief \ref named-templ-param "Named parameter" for setting kpeter@503: ///\c ProcessedMap type. alpar@100: /// kpeter@244: ///\ref named-templ-param "Named parameter" for setting kpeter@503: ///\c ProcessedMap type. kpeter@716: ///It must conform to the \ref concepts::WriteMap "WriteMap" concept. alpar@100: template kpeter@257: struct SetProcessedMap : public Dfs< Digraph, SetProcessedMapTraits > { kpeter@257: typedef Dfs< Digraph, SetProcessedMapTraits > Create; alpar@100: }; alpar@209: kpeter@257: struct SetStandardProcessedMapTraits : public Traits { alpar@100: typedef typename Digraph::template NodeMap ProcessedMap; kpeter@244: static ProcessedMap *createProcessedMap(const Digraph &g) alpar@100: { kpeter@244: return new ProcessedMap(g); alpar@100: } alpar@100: }; kpeter@244: ///\brief \ref named-templ-param "Named parameter" for setting kpeter@503: ///\c ProcessedMap type to be Digraph::NodeMap. alpar@100: /// kpeter@244: ///\ref named-templ-param "Named parameter" for setting kpeter@503: ///\c ProcessedMap type to be Digraph::NodeMap. kpeter@244: ///If you don't set it explicitly, it will be automatically allocated. kpeter@257: struct SetStandardProcessedMap : kpeter@257: public Dfs< Digraph, SetStandardProcessedMapTraits > { kpeter@257: typedef Dfs< Digraph, SetStandardProcessedMapTraits > Create; alpar@100: }; alpar@209: alpar@100: ///@} alpar@100: alpar@209: public: alpar@209: alpar@100: ///Constructor. alpar@209: kpeter@244: ///Constructor. kpeter@244: ///\param g The digraph the algorithm runs on. kpeter@244: Dfs(const Digraph &g) : kpeter@244: 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@209: alpar@100: ///Destructor. alpar@209: ~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: kpeter@244: ///Sets the map that stores the predecessor arcs. alpar@100: kpeter@244: ///Sets the map that stores the predecessor arcs. kpeter@405: ///If you don't use this function before calling \ref run(Node) "run()" kpeter@405: ///or \ref init(), an instance will be allocated automatically. kpeter@405: ///The destructor deallocates this automatically allocated map, kpeter@405: ///of course. alpar@100: ///\return (*this) alpar@209: Dfs &predMap(PredMap &m) alpar@100: { alpar@100: if(local_pred) { alpar@209: delete _pred; alpar@209: local_pred=false; alpar@100: } alpar@100: _pred = &m; alpar@100: return *this; alpar@100: } alpar@100: kpeter@244: ///Sets the map that indicates which nodes are reached. alpar@100: kpeter@244: ///Sets the map that indicates which nodes are reached. kpeter@405: ///If you don't use this function before calling \ref run(Node) "run()" kpeter@405: ///or \ref init(), an instance will be allocated automatically. kpeter@405: ///The destructor deallocates this automatically allocated map, kpeter@405: ///of course. kpeter@244: ///\return (*this) kpeter@244: Dfs &reachedMap(ReachedMap &m) kpeter@244: { kpeter@244: if(local_reached) { kpeter@244: delete _reached; kpeter@244: local_reached=false; kpeter@244: } kpeter@244: _reached = &m; kpeter@244: return *this; kpeter@244: } kpeter@244: kpeter@244: ///Sets the map that indicates which nodes are processed. kpeter@244: kpeter@244: ///Sets the map that indicates which nodes are processed. kpeter@405: ///If you don't use this function before calling \ref run(Node) "run()" kpeter@405: ///or \ref init(), an instance will be allocated automatically. kpeter@405: ///The destructor deallocates this automatically allocated map, kpeter@405: ///of course. kpeter@244: ///\return (*this) kpeter@244: Dfs &processedMap(ProcessedMap &m) kpeter@244: { kpeter@244: if(local_processed) { kpeter@244: delete _processed; kpeter@244: local_processed=false; kpeter@244: } kpeter@244: _processed = &m; kpeter@244: return *this; kpeter@244: } kpeter@244: kpeter@244: ///Sets the map that stores the distances of the nodes. kpeter@244: kpeter@244: ///Sets the map that stores the distances of the nodes calculated by kpeter@244: ///the algorithm. kpeter@405: ///If you don't use this function before calling \ref run(Node) "run()" kpeter@405: ///or \ref init(), an instance will be allocated automatically. kpeter@405: ///The destructor deallocates this automatically allocated map, kpeter@405: ///of course. alpar@100: ///\return (*this) alpar@209: Dfs &distMap(DistMap &m) alpar@100: { alpar@100: if(local_dist) { alpar@209: delete _dist; alpar@209: local_dist=false; alpar@100: } alpar@100: _dist = &m; alpar@100: return *this; alpar@100: } alpar@100: kpeter@244: public: alpar@100: kpeter@405: ///\name Execution Control kpeter@405: ///The simplest way to execute the DFS algorithm is to use one of the kpeter@405: ///member functions called \ref run(Node) "run()".\n kpeter@713: ///If you need better control on the execution, you have to call kpeter@713: ///\ref init() first, then you can add a source node with \ref addSource() kpeter@405: ///and perform the actual computation with \ref start(). kpeter@405: ///This procedure can be repeated if there are nodes that have not kpeter@405: ///been reached. alpar@100: alpar@100: ///@{ alpar@100: kpeter@405: ///\brief Initializes the internal data structures. kpeter@405: /// alpar@100: ///Initializes the internal data structures. 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@209: _pred->set(u,INVALID); alpar@209: _reached->set(u,false); alpar@209: _processed->set(u,false); alpar@100: } alpar@100: } alpar@209: 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: /// kpeter@405: ///\pre The stack must be empty. Otherwise the algorithm gives kpeter@405: ///wrong results. (One of the outgoing arcs of all the source nodes kpeter@405: ///except for the last one will not be visited and distances will kpeter@405: ///also be wrong.) alpar@100: void addSource(Node s) alpar@100: { kpeter@244: LEMON_DEBUG(emptyQueue(), "The stack is not empty."); alpar@100: if(!(*_reached)[s]) alpar@209: { alpar@209: _reached->set(s,true); alpar@209: _pred->set(s,INVALID); alpar@209: OutArcIt e(*G,s); alpar@209: if(e!=INVALID) { alpar@209: _stack[++_stack_head]=e; alpar@209: _dist->set(s,_stack_head); alpar@209: } alpar@209: else { alpar@209: _processed->set(s,true); alpar@209: _dist->set(s,0); alpar@209: } alpar@209: } alpar@100: } alpar@209: alpar@100: ///Processes the next arc. alpar@100: alpar@100: ///Processes the next arc. alpar@100: /// alpar@100: ///\return The processed arc. alpar@100: /// kpeter@244: ///\pre The stack must not be empty. alpar@100: Arc processNextArc() alpar@209: { alpar@100: Node m; alpar@100: Arc e=_stack[_stack_head]; alpar@100: if(!(*_reached)[m=G->target(e)]) { alpar@209: _pred->set(m,e); alpar@209: _reached->set(m,true); alpar@209: ++_stack_head; alpar@209: _stack[_stack_head] = OutArcIt(*G, m); alpar@209: _dist->set(m,_stack_head); alpar@100: } alpar@100: else { alpar@209: m=G->source(e); alpar@209: ++_stack[_stack_head]; alpar@100: } alpar@100: while(_stack_head>=0 && _stack[_stack_head]==INVALID) { alpar@209: _processed->set(m,true); alpar@209: --_stack_head; alpar@209: if(_stack_head>=0) { alpar@209: m=G->source(_stack[_stack_head]); alpar@209: ++_stack[_stack_head]; alpar@209: } alpar@100: } alpar@100: return e; alpar@100: } kpeter@244: alpar@100: ///Next arc to be processed. alpar@100: alpar@100: ///Next arc to be processed. alpar@100: /// kpeter@244: ///\return The next arc to be processed or \c INVALID if the stack kpeter@244: ///is empty. kpeter@244: OutArcIt nextArc() const alpar@209: { alpar@100: return _stack_head>=0?_stack[_stack_head]:INVALID; alpar@100: } alpar@100: kpeter@405: ///Returns \c false if there are nodes to be processed. kpeter@405: kpeter@405: ///Returns \c false if there are nodes to be processed kpeter@405: ///in the queue (stack). kpeter@244: bool emptyQueue() const { return _stack_head<0; } kpeter@244: alpar@100: ///Returns the number of the nodes to be processed. alpar@209: kpeter@405: ///Returns the number of the nodes to be processed kpeter@405: ///in the queue (stack). kpeter@244: int queueSize() const { return _stack_head+1; } alpar@209: alpar@100: ///Executes the algorithm. alpar@100: alpar@100: ///Executes the algorithm. alpar@100: /// kpeter@244: ///This method runs the %DFS algorithm from the root node kpeter@244: ///in order to compute the DFS path to each node. alpar@100: /// kpeter@244: /// The algorithm computes kpeter@244: ///- the %DFS tree, kpeter@244: ///- the distance of each node from the root in the %DFS tree. alpar@100: /// kpeter@244: ///\pre init() must be called and a root node should be kpeter@244: ///added with addSource() before using this function. kpeter@244: /// kpeter@244: ///\note d.start() is just a shortcut of the following code. kpeter@244: ///\code kpeter@244: /// while ( !d.emptyQueue() ) { kpeter@244: /// d.processNextArc(); kpeter@244: /// } kpeter@244: ///\endcode alpar@100: void start() alpar@100: { alpar@100: while ( !emptyQueue() ) processNextArc(); alpar@100: } alpar@209: kpeter@244: ///Executes the algorithm until the given target node is reached. alpar@100: kpeter@244: ///Executes the algorithm until the given target node is reached. alpar@100: /// kpeter@244: ///This method runs the %DFS algorithm from the root node kpeter@286: ///in order to compute the DFS path to \c t. alpar@100: /// kpeter@244: ///The algorithm computes kpeter@286: ///- the %DFS path to \c t, kpeter@286: ///- the distance of \c t from the root in the %DFS tree. alpar@100: /// kpeter@244: ///\pre init() must be called and a root node should be kpeter@244: ///added with addSource() before using this function. kpeter@286: void start(Node t) alpar@100: { kpeter@286: while ( !emptyQueue() && G->target(_stack[_stack_head])!=t ) alpar@209: processNextArc(); alpar@100: } alpar@209: alpar@100: ///Executes the algorithm until a condition is met. alpar@100: alpar@100: ///Executes the algorithm until a condition is met. alpar@100: /// kpeter@244: ///This method runs the %DFS algorithm from the root node kpeter@244: ///until an arc \c a with am[a] true is found. alpar@100: /// kpeter@244: ///\param am A \c bool (or convertible) arc map. The algorithm kpeter@244: ///will stop when it reaches an arc \c a with am[a] true. alpar@100: /// kpeter@244: ///\return The reached arc \c a with am[a] true or alpar@100: ///\c INVALID if no such arc was found. alpar@100: /// kpeter@244: ///\pre init() must be called and a root node should be kpeter@244: ///added with addSource() before using this function. kpeter@244: /// kpeter@244: ///\warning Contrary to \ref Bfs and \ref Dijkstra, \c am is an arc map, alpar@100: ///not a node map. kpeter@244: template kpeter@244: Arc start(const ArcBoolMap &am) alpar@100: { kpeter@244: while ( !emptyQueue() && !am[_stack[_stack_head]] ) alpar@100: processNextArc(); alpar@100: return emptyQueue() ? INVALID : _stack[_stack_head]; alpar@100: } alpar@100: kpeter@286: ///Runs the algorithm from the given source node. alpar@209: kpeter@244: ///This method runs the %DFS algorithm from node \c s kpeter@244: ///in order to compute the DFS path to each node. alpar@100: /// kpeter@244: ///The algorithm computes kpeter@244: ///- the %DFS tree, kpeter@244: ///- the distance of each node from the root in the %DFS tree. kpeter@244: /// kpeter@244: ///\note d.run(s) is just a shortcut of the following code. alpar@100: ///\code alpar@100: /// d.init(); kpeter@244: /// d.addSource(s); kpeter@244: /// d.start(); kpeter@244: ///\endcode kpeter@244: void run(Node s) { kpeter@244: init(); kpeter@244: addSource(s); kpeter@244: start(); kpeter@244: } kpeter@244: kpeter@244: ///Finds the %DFS path between \c s and \c t. kpeter@244: kpeter@244: ///This method runs the %DFS algorithm from node \c s kpeter@286: ///in order to compute the DFS path to node \c t kpeter@286: ///(it stops searching when \c t is processed) kpeter@244: /// kpeter@286: ///\return \c true if \c t is reachable form \c s. kpeter@244: /// kpeter@244: ///\note Apart from the return value, d.run(s,t) is kpeter@244: ///just a shortcut of the following code. kpeter@244: ///\code kpeter@244: /// d.init(); kpeter@244: /// d.addSource(s); kpeter@244: /// d.start(t); kpeter@244: ///\endcode kpeter@286: bool run(Node s,Node t) { kpeter@244: init(); kpeter@244: addSource(s); kpeter@244: start(t); kpeter@286: return reached(t); kpeter@244: } kpeter@244: kpeter@244: ///Runs the algorithm to visit all nodes in the digraph. kpeter@244: kpeter@244: ///This method runs the %DFS algorithm in order to compute the kpeter@244: ///%DFS path to each node. kpeter@244: /// kpeter@244: ///The algorithm computes kpeter@405: ///- the %DFS tree (forest), kpeter@405: ///- the distance of each node from the root(s) in the %DFS tree. kpeter@244: /// kpeter@244: ///\note d.run() is just a shortcut of the following code. kpeter@244: ///\code kpeter@244: /// d.init(); kpeter@244: /// for (NodeIt n(digraph); n != INVALID; ++n) { kpeter@244: /// if (!d.reached(n)) { kpeter@244: /// d.addSource(n); 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: ///@} alpar@100: alpar@100: ///\name Query Functions kpeter@405: ///The results of the DFS algorithm can be obtained using these alpar@100: ///functions.\n kpeter@405: ///Either \ref run(Node) "run()" or \ref start() should be called kpeter@405: ///before using them. alpar@209: alpar@100: ///@{ alpar@100: kpeter@716: ///The DFS path to the given node. alpar@100: kpeter@716: ///Returns the DFS path to the given node from the root(s). kpeter@244: /// kpeter@405: ///\warning \c t should be reached from the root(s). kpeter@244: /// kpeter@405: ///\pre Either \ref run(Node) "run()" or \ref init() kpeter@405: ///must be called before using this function. kpeter@244: Path path(Node t) const { return Path(*G, *_pred, t); } alpar@209: kpeter@716: ///The distance of the given node from the root(s). alpar@100: kpeter@716: ///Returns the distance of the given node from the root(s). kpeter@244: /// kpeter@405: ///\warning If node \c v is not reached from the root(s), then kpeter@244: ///the return value of this function is undefined. kpeter@244: /// kpeter@405: ///\pre Either \ref run(Node) "run()" or \ref init() kpeter@405: ///must be called before using this function. alpar@100: int dist(Node v) const { return (*_dist)[v]; } alpar@100: kpeter@716: ///Returns the 'previous arc' of the %DFS tree for the given node. alpar@100: kpeter@244: ///This function returns the 'previous arc' of the %DFS tree for the kpeter@405: ///node \c v, i.e. it returns the last arc of a %DFS path from a kpeter@405: ///root to \c v. It is \c INVALID if \c v is not reached from the kpeter@405: ///root(s) or if \c v is a root. kpeter@244: /// kpeter@244: ///The %DFS tree used here is equal to the %DFS tree used in kpeter@716: ///\ref predNode() and \ref predMap(). kpeter@244: /// kpeter@405: ///\pre Either \ref run(Node) "run()" or \ref init() kpeter@405: ///must be called before using this function. alpar@100: Arc predArc(Node v) const { return (*_pred)[v];} alpar@100: kpeter@716: ///Returns the 'previous node' of the %DFS tree for the given node. alpar@100: kpeter@244: ///This function returns the 'previous node' of the %DFS kpeter@244: ///tree for the node \c v, i.e. it returns the last but one node kpeter@716: ///of a %DFS path from a root to \c v. It is \c INVALID kpeter@405: ///if \c v is not reached from the root(s) or if \c v is a root. kpeter@244: /// kpeter@244: ///The %DFS tree used here is equal to the %DFS tree used in kpeter@716: ///\ref predArc() and \ref predMap(). kpeter@244: /// kpeter@405: ///\pre Either \ref run(Node) "run()" or \ref init() kpeter@405: ///must be called before using this function. alpar@100: Node predNode(Node v) const { return (*_pred)[v]==INVALID ? INVALID: alpar@209: G->source((*_pred)[v]); } alpar@209: kpeter@244: ///\brief Returns a const reference to the node map that stores the kpeter@244: ///distances of the nodes. kpeter@244: /// kpeter@244: ///Returns a const reference to the node map that stores the kpeter@244: ///distances of the nodes calculated by the algorithm. kpeter@244: /// kpeter@405: ///\pre Either \ref run(Node) "run()" or \ref init() kpeter@244: ///must be called before using this function. alpar@100: const DistMap &distMap() const { return *_dist;} alpar@209: kpeter@244: ///\brief Returns a const reference to the node map that stores the kpeter@244: ///predecessor arcs. kpeter@244: /// kpeter@244: ///Returns a const reference to the node map that stores the predecessor kpeter@716: ///arcs, which form the DFS tree (forest). kpeter@244: /// kpeter@405: ///\pre Either \ref run(Node) "run()" or \ref init() alpar@100: ///must be called before using this function. alpar@100: const PredMap &predMap() const { return *_pred;} alpar@209: kpeter@716: ///Checks if the given node. node is reached from the root(s). alpar@100: kpeter@405: ///Returns \c true if \c v is reached from the root(s). kpeter@405: /// kpeter@405: ///\pre Either \ref run(Node) "run()" or \ref init() alpar@100: ///must be called before using this function. kpeter@244: bool reached(Node v) const { return (*_reached)[v]; } alpar@209: alpar@100: ///@} alpar@100: }; alpar@100: kpeter@244: ///Default traits class of dfs() function. alpar@100: kpeter@244: ///Default traits class of dfs() function. kpeter@157: ///\tparam GR Digraph type. alpar@100: template alpar@100: struct DfsWizardDefaultTraits alpar@100: { kpeter@244: ///The type of the digraph the algorithm runs on. alpar@100: typedef GR Digraph; kpeter@244: kpeter@244: ///\brief The type of the map that stores the predecessor alpar@100: ///arcs of the %DFS paths. alpar@209: /// kpeter@244: ///The type of the map that stores the predecessor alpar@100: ///arcs of the %DFS paths. kpeter@716: ///It must conform to the \ref concepts::WriteMap "WriteMap" concept. kpeter@278: typedef typename Digraph::template NodeMap PredMap; kpeter@301: ///Instantiates a PredMap. alpar@209: kpeter@301: ///This function instantiates a PredMap. kpeter@244: ///\param g is the digraph, to which we would like to define the kpeter@301: ///PredMap. kpeter@244: static PredMap *createPredMap(const Digraph &g) alpar@100: { kpeter@278: return new PredMap(g); alpar@100: } alpar@100: alpar@100: ///The type of the map that indicates which nodes are processed. alpar@209: alpar@100: ///The type of the map that indicates which nodes are processed. kpeter@716: ///It must conform to the \ref concepts::WriteMap "WriteMap" concept. kpeter@278: ///By default it is a NullMap. alpar@100: typedef NullMap ProcessedMap; kpeter@301: ///Instantiates a ProcessedMap. alpar@209: kpeter@301: ///This function instantiates a ProcessedMap. alpar@100: ///\param g is the digraph, to which kpeter@301: ///we would like to define the ProcessedMap. alpar@100: #ifdef DOXYGEN kpeter@244: static ProcessedMap *createProcessedMap(const Digraph &g) alpar@100: #else kpeter@244: static ProcessedMap *createProcessedMap(const Digraph &) alpar@100: #endif alpar@100: { alpar@100: return new ProcessedMap(); alpar@100: } kpeter@244: alpar@100: ///The type of the map that indicates which nodes are reached. alpar@209: alpar@100: ///The type of the map that indicates which nodes are reached. kpeter@716: ///It must conform to the \ref concepts::ReadWriteMap "ReadWriteMap" concept. alpar@100: typedef typename Digraph::template NodeMap ReachedMap; kpeter@301: ///Instantiates a ReachedMap. alpar@209: kpeter@301: ///This function instantiates a ReachedMap. kpeter@244: ///\param g is the digraph, to which kpeter@301: ///we would like to define the ReachedMap. kpeter@244: static ReachedMap *createReachedMap(const Digraph &g) alpar@100: { kpeter@244: return new ReachedMap(g); alpar@100: } alpar@209: kpeter@244: ///The type of the map that stores the distances of the nodes. kpeter@244: kpeter@244: ///The type of the map that stores the distances of the nodes. kpeter@716: ///It must conform to the \ref concepts::WriteMap "WriteMap" concept. kpeter@278: typedef typename Digraph::template NodeMap DistMap; kpeter@301: ///Instantiates a DistMap. alpar@209: kpeter@301: ///This function instantiates a DistMap. alpar@210: ///\param g is the digraph, to which we would like to define kpeter@301: ///the DistMap kpeter@244: static DistMap *createDistMap(const Digraph &g) alpar@100: { kpeter@278: return new DistMap(g); alpar@100: } kpeter@278: kpeter@278: ///The type of the DFS paths. kpeter@278: kpeter@278: ///The type of the DFS paths. kpeter@716: ///It must conform to the \ref concepts::Path "Path" concept. kpeter@278: typedef lemon::Path Path; alpar@100: }; alpar@209: kpeter@313: /// Default traits class used by DfsWizard alpar@100: kpeter@716: /// Default traits class used by DfsWizard. kpeter@716: /// \tparam GR The type of the digraph. alpar@100: template alpar@100: class DfsWizardBase : public DfsWizardDefaultTraits alpar@100: { alpar@100: alpar@100: typedef DfsWizardDefaultTraits Base; alpar@100: protected: kpeter@244: //The type of the nodes in the digraph. alpar@100: typedef typename Base::Digraph::Node Node; alpar@100: kpeter@244: //Pointer to the digraph the algorithm runs on. alpar@100: void *_g; kpeter@244: //Pointer to the map of reached nodes. alpar@100: void *_reached; kpeter@244: //Pointer to the map of processed nodes. alpar@100: void *_processed; kpeter@244: //Pointer to the map of predecessors arcs. alpar@100: void *_pred; kpeter@244: //Pointer to the map of distances. alpar@100: void *_dist; kpeter@278: //Pointer to the DFS path to the target node. kpeter@278: void *_path; kpeter@278: //Pointer to the distance of the target node. kpeter@278: int *_di; alpar@209: alpar@100: public: alpar@100: /// Constructor. alpar@209: kpeter@716: /// This constructor does not require parameters, it initiates kpeter@278: /// all of the attributes to \c 0. alpar@100: DfsWizardBase() : _g(0), _reached(0), _processed(0), _pred(0), kpeter@278: _dist(0), _path(0), _di(0) {} alpar@100: alpar@100: /// Constructor. alpar@209: kpeter@278: /// This constructor requires one parameter, kpeter@278: /// others are initiated to \c 0. kpeter@244: /// \param g The digraph the algorithm runs on. kpeter@278: DfsWizardBase(const GR &g) : alpar@209: _g(reinterpret_cast(const_cast(&g))), kpeter@278: _reached(0), _processed(0), _pred(0), _dist(0), _path(0), _di(0) {} alpar@100: alpar@100: }; alpar@209: kpeter@278: /// Auxiliary class for the function-type interface of DFS algorithm. alpar@100: kpeter@278: /// This auxiliary class is created to implement the kpeter@278: /// \ref dfs() "function-type interface" of \ref Dfs algorithm. kpeter@405: /// It does not have own \ref run(Node) "run()" method, it uses the kpeter@405: /// functions and features of the plain \ref Dfs. alpar@100: /// kpeter@278: /// This class should only be used through the \ref dfs() function, kpeter@278: /// which makes it easier to use the algorithm. alpar@100: template alpar@100: class DfsWizard : public TR alpar@100: { alpar@100: typedef TR Base; alpar@100: alpar@100: typedef typename TR::Digraph Digraph; kpeter@244: 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@209: kpeter@244: typedef typename TR::PredMap PredMap; kpeter@244: typedef typename TR::DistMap DistMap; alpar@100: typedef typename TR::ReachedMap ReachedMap; alpar@100: typedef typename TR::ProcessedMap ProcessedMap; kpeter@278: typedef typename TR::Path Path; alpar@100: alpar@100: public: kpeter@244: 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. kpeter@278: /// \param g The digraph the algorithm runs on. kpeter@278: DfsWizard(const Digraph &g) : kpeter@278: TR(g) {} alpar@100: alpar@100: ///Copy constructor alpar@100: DfsWizard(const TR &b) : TR(b) {} alpar@100: alpar@100: ~DfsWizard() {} alpar@100: kpeter@278: ///Runs DFS algorithm from the given source node. alpar@209: kpeter@278: ///This method runs DFS algorithm from node \c s kpeter@278: ///in order to compute the DFS path to each node. kpeter@278: void run(Node s) kpeter@278: { kpeter@278: Dfs alg(*reinterpret_cast(Base::_g)); kpeter@278: if (Base::_pred) kpeter@278: alg.predMap(*reinterpret_cast(Base::_pred)); kpeter@278: if (Base::_dist) kpeter@278: alg.distMap(*reinterpret_cast(Base::_dist)); kpeter@278: if (Base::_reached) kpeter@278: alg.reachedMap(*reinterpret_cast(Base::_reached)); kpeter@278: if (Base::_processed) kpeter@278: alg.processedMap(*reinterpret_cast(Base::_processed)); kpeter@278: if (s!=INVALID) kpeter@278: alg.run(s); kpeter@278: else kpeter@278: alg.run(); kpeter@278: } kpeter@278: kpeter@278: ///Finds the DFS path between \c s and \c t. kpeter@278: kpeter@278: ///This method runs DFS algorithm from node \c s kpeter@278: ///in order to compute the DFS path to node \c t kpeter@278: ///(it stops searching when \c t is processed). kpeter@278: /// kpeter@278: ///\return \c true if \c t is reachable form \c s. kpeter@278: bool run(Node s, Node t) kpeter@278: { kpeter@278: Dfs alg(*reinterpret_cast(Base::_g)); kpeter@278: if (Base::_pred) kpeter@278: alg.predMap(*reinterpret_cast(Base::_pred)); kpeter@278: if (Base::_dist) kpeter@278: alg.distMap(*reinterpret_cast(Base::_dist)); kpeter@278: if (Base::_reached) kpeter@278: alg.reachedMap(*reinterpret_cast(Base::_reached)); kpeter@278: if (Base::_processed) kpeter@278: alg.processedMap(*reinterpret_cast(Base::_processed)); kpeter@278: alg.run(s,t); kpeter@278: if (Base::_path) kpeter@278: *reinterpret_cast(Base::_path) = alg.path(t); kpeter@278: if (Base::_di) kpeter@278: *Base::_di = alg.dist(t); kpeter@278: return alg.reached(t); kpeter@278: } kpeter@278: kpeter@278: ///Runs DFS algorithm to visit all nodes in the digraph. kpeter@278: kpeter@278: ///This method runs DFS algorithm in order to compute kpeter@278: ///the DFS path to each node. alpar@100: void run() alpar@100: { kpeter@278: run(INVALID); kpeter@244: } kpeter@244: alpar@100: template kpeter@257: struct SetPredMapBase : public Base { alpar@100: typedef T PredMap; alpar@100: static PredMap *createPredMap(const Digraph &) { return 0; }; kpeter@257: SetPredMapBase(const TR &b) : TR(b) {} alpar@100: }; kpeter@716: kpeter@716: ///\brief \ref named-templ-param "Named parameter" for setting kpeter@716: ///the predecessor map. alpar@100: /// kpeter@716: ///\ref named-templ-param "Named parameter" function for setting kpeter@716: ///the map that stores the predecessor arcs of the nodes. alpar@100: template kpeter@257: DfsWizard > predMap(const T &t) alpar@100: { alpar@100: Base::_pred=reinterpret_cast(const_cast(&t)); kpeter@257: return DfsWizard >(*this); alpar@100: } alpar@209: alpar@100: template kpeter@257: struct SetReachedMapBase : public Base { alpar@100: typedef T ReachedMap; alpar@100: static ReachedMap *createReachedMap(const Digraph &) { return 0; }; kpeter@257: SetReachedMapBase(const TR &b) : TR(b) {} alpar@100: }; kpeter@716: kpeter@716: ///\brief \ref named-templ-param "Named parameter" for setting kpeter@716: ///the reached map. alpar@100: /// kpeter@716: ///\ref named-templ-param "Named parameter" function for setting kpeter@716: ///the map that indicates which nodes are reached. alpar@100: template kpeter@257: DfsWizard > reachedMap(const T &t) alpar@100: { deba@158: Base::_reached=reinterpret_cast(const_cast(&t)); kpeter@257: return DfsWizard >(*this); alpar@100: } alpar@209: alpar@100: template kpeter@278: struct SetDistMapBase : public Base { kpeter@278: typedef T DistMap; kpeter@278: static DistMap *createDistMap(const Digraph &) { return 0; }; kpeter@278: SetDistMapBase(const TR &b) : TR(b) {} kpeter@278: }; kpeter@716: kpeter@716: ///\brief \ref named-templ-param "Named parameter" for setting kpeter@716: ///the distance map. kpeter@278: /// kpeter@716: ///\ref named-templ-param "Named parameter" function for setting kpeter@716: ///the map that stores the distances of the nodes calculated kpeter@716: ///by the algorithm. kpeter@278: template kpeter@278: DfsWizard > distMap(const T &t) kpeter@278: { kpeter@278: Base::_dist=reinterpret_cast(const_cast(&t)); kpeter@278: return DfsWizard >(*this); kpeter@278: } kpeter@278: kpeter@278: template kpeter@257: struct SetProcessedMapBase : public Base { alpar@100: typedef T ProcessedMap; alpar@100: static ProcessedMap *createProcessedMap(const Digraph &) { return 0; }; kpeter@257: SetProcessedMapBase(const TR &b) : TR(b) {} alpar@100: }; kpeter@716: kpeter@716: ///\brief \ref named-func-param "Named parameter" for setting kpeter@716: ///the processed map. alpar@100: /// kpeter@716: ///\ref named-templ-param "Named parameter" function for setting kpeter@716: ///the map that indicates which nodes are processed. alpar@100: template kpeter@257: DfsWizard > processedMap(const T &t) alpar@100: { deba@158: Base::_processed=reinterpret_cast(const_cast(&t)); kpeter@257: return DfsWizard >(*this); alpar@100: } alpar@209: alpar@100: template kpeter@278: struct SetPathBase : public Base { kpeter@278: typedef T Path; kpeter@278: SetPathBase(const TR &b) : TR(b) {} alpar@100: }; kpeter@278: ///\brief \ref named-func-param "Named parameter" kpeter@278: ///for getting the DFS path to the target node. alpar@100: /// kpeter@278: ///\ref named-func-param "Named parameter" kpeter@278: ///for getting the DFS path to the target node. alpar@100: template kpeter@278: DfsWizard > path(const T &t) alpar@100: { kpeter@278: Base::_path=reinterpret_cast(const_cast(&t)); kpeter@278: return DfsWizard >(*this); kpeter@278: } kpeter@278: kpeter@278: ///\brief \ref named-func-param "Named parameter" kpeter@278: ///for getting the distance of the target node. kpeter@278: /// kpeter@278: ///\ref named-func-param "Named parameter" kpeter@278: ///for getting the distance of the target node. kpeter@278: DfsWizard dist(const int &d) kpeter@278: { kpeter@278: Base::_di=const_cast(&d); kpeter@278: return *this; alpar@100: } alpar@209: alpar@100: }; alpar@209: kpeter@278: ///Function-type interface for DFS algorithm. alpar@100: alpar@100: ///\ingroup search kpeter@278: ///Function-type interface for DFS algorithm. alpar@100: /// kpeter@278: ///This function also has several \ref named-func-param "named parameters", alpar@100: ///they are declared as the members of class \ref DfsWizard. kpeter@278: ///The following examples show how to use these parameters. alpar@100: ///\code kpeter@278: /// // Compute the DFS tree kpeter@278: /// dfs(g).predMap(preds).distMap(dists).run(s); kpeter@278: /// kpeter@278: /// // Compute the DFS path from s to t kpeter@278: /// bool reached = dfs(g).path(p).dist(d).run(s,t); alpar@100: ///\endcode kpeter@405: ///\warning Don't forget to put the \ref DfsWizard::run(Node) "run()" alpar@100: ///to the end of the parameter list. alpar@100: ///\sa DfsWizard alpar@100: ///\sa Dfs alpar@100: template alpar@100: DfsWizard > kpeter@278: dfs(const GR &digraph) alpar@100: { kpeter@278: return DfsWizard >(digraph); alpar@100: } alpar@100: alpar@100: #ifdef DOXYGEN kpeter@244: /// \brief Visitor class for DFS. alpar@209: /// kpeter@244: /// This class defines the interface of the DfsVisit events, and kpeter@244: /// it could be the base of a real visitor class. kpeter@503: template alpar@100: struct DfsVisitor { kpeter@503: typedef GR Digraph; alpar@100: typedef typename Digraph::Arc Arc; alpar@100: typedef typename Digraph::Node Node; kpeter@244: /// \brief Called for the source node of the DFS. alpar@209: /// kpeter@244: /// This function is called for the source node of the DFS. kpeter@244: void start(const Node& node) {} kpeter@244: /// \brief Called when the source node is leaved. kpeter@244: /// kpeter@244: /// This function is called when the source node is leaved. kpeter@244: void stop(const Node& node) {} kpeter@244: /// \brief Called when a node is reached first time. kpeter@244: /// kpeter@244: /// This function is called when a node is reached first time. kpeter@244: void reach(const Node& node) {} kpeter@244: /// \brief Called when an arc reaches a new node. kpeter@244: /// kpeter@244: /// This function is called when the DFS finds an arc whose target node kpeter@244: /// is not reached yet. alpar@100: void discover(const Arc& arc) {} kpeter@244: /// \brief Called when an arc is examined but its target node is alpar@100: /// already discovered. alpar@209: /// kpeter@244: /// This function is called when an arc is examined but its target node is alpar@100: /// already discovered. alpar@100: void examine(const Arc& arc) {} kpeter@244: /// \brief Called when the DFS steps back from a node. alpar@209: /// kpeter@244: /// This function is called when the DFS steps back from a node. kpeter@244: void leave(const Node& node) {} kpeter@244: /// \brief Called when the DFS steps back on an arc. alpar@209: /// kpeter@244: /// This function is called when the DFS steps back on an arc. kpeter@244: void backtrack(const Arc& arc) {} alpar@100: }; alpar@100: #else kpeter@503: template alpar@100: struct DfsVisitor { kpeter@503: typedef GR Digraph; alpar@100: typedef typename Digraph::Arc Arc; alpar@100: typedef typename Digraph::Node Node; alpar@100: void start(const Node&) {} alpar@100: void stop(const Node&) {} kpeter@244: void reach(const Node&) {} kpeter@244: void discover(const Arc&) {} kpeter@244: void examine(const Arc&) {} kpeter@244: void leave(const Node&) {} kpeter@244: void backtrack(const Arc&) {} alpar@100: alpar@100: template alpar@100: struct Constraints { alpar@100: void constraints() { alpar@209: Arc arc; alpar@209: Node node; alpar@209: visitor.start(node); alpar@209: visitor.stop(arc); kpeter@244: visitor.reach(node); kpeter@244: visitor.discover(arc); kpeter@244: visitor.examine(arc); kpeter@244: visitor.leave(node); kpeter@244: visitor.backtrack(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@244: /// \tparam _Digraph The type of the digraph the algorithm runs on. kpeter@503: template alpar@100: struct DfsVisitDefaultTraits { alpar@100: kpeter@244: /// \brief The type of the digraph the algorithm runs on. kpeter@503: typedef GR Digraph; alpar@100: alpar@100: /// \brief The type of the map that indicates which nodes are reached. alpar@209: /// alpar@100: /// The type of the map that indicates which nodes are reached. kpeter@716: /// It must conform to the \ref concepts::ReadWriteMap "ReadWriteMap" concept. alpar@100: typedef typename Digraph::template NodeMap ReachedMap; alpar@100: kpeter@301: /// \brief Instantiates a ReachedMap. alpar@100: /// kpeter@301: /// This function instantiates a ReachedMap. alpar@100: /// \param digraph is the digraph, to which kpeter@301: /// we would like to define the ReachedMap. alpar@100: static ReachedMap *createReachedMap(const Digraph &digraph) { alpar@100: return new ReachedMap(digraph); alpar@100: } alpar@100: alpar@100: }; alpar@209: alpar@100: /// \ingroup search kpeter@244: /// kpeter@503: /// \brief DFS algorithm class with visitor interface. kpeter@244: /// kpeter@503: /// This class provides an efficient implementation of the DFS algorithm alpar@100: /// with visitor interface. alpar@100: /// kpeter@503: /// The DfsVisit class provides an alternative interface to the Dfs alpar@100: /// class. It works with callback mechanism, the DfsVisit object calls kpeter@244: /// the member functions of the \c Visitor class on every DFS event. alpar@100: /// kpeter@252: /// This interface of the DFS algorithm should be used in special cases kpeter@252: /// when extra actions have to be performed in connection with certain kpeter@252: /// events of the DFS algorithm. Otherwise consider to use Dfs or dfs() kpeter@252: /// instead. kpeter@252: /// kpeter@503: /// \tparam GR The type of the digraph the algorithm runs on. kpeter@503: /// The default type is \ref ListDigraph. kpeter@503: /// The value of GR is not used directly by \ref DfsVisit, kpeter@503: /// it is only passed to \ref DfsVisitDefaultTraits. kpeter@503: /// \tparam VS The Visitor type that is used by the algorithm. kpeter@503: /// \ref DfsVisitor "DfsVisitor" is an empty visitor, which kpeter@244: /// does not observe the DFS events. If you want to observe the DFS kpeter@244: /// events, you should implement your own visitor class. kpeter@503: /// \tparam TR Traits class to set various data types used by the alpar@100: /// algorithm. The default traits class is kpeter@503: /// \ref DfsVisitDefaultTraits "DfsVisitDefaultTraits". alpar@100: /// See \ref DfsVisitDefaultTraits for the documentation of kpeter@244: /// a DFS visit traits class. alpar@100: #ifdef DOXYGEN kpeter@503: template alpar@100: #else kpeter@503: template , kpeter@503: typename TR = DfsVisitDefaultTraits > alpar@100: #endif alpar@100: class DfsVisit { alpar@100: public: alpar@209: kpeter@244: ///The traits class. kpeter@503: typedef TR Traits; alpar@100: kpeter@244: ///The type of the digraph the algorithm runs on. alpar@100: typedef typename Traits::Digraph Digraph; alpar@100: kpeter@244: ///The visitor type used by the algorithm. kpeter@503: typedef VS Visitor; alpar@100: kpeter@244: ///The type of the map that indicates 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: kpeter@244: //Pointer to the underlying digraph. alpar@100: const Digraph *_digraph; kpeter@244: //Pointer to the visitor object. alpar@100: Visitor *_visitor; kpeter@244: //Pointer to the map of reached status of the nodes. alpar@100: ReachedMap *_reached; kpeter@244: //Indicates if _reached is locally allocated (true) or not. alpar@100: bool local_reached; alpar@100: alpar@100: std::vector _stack; alpar@100: int _stack_head; alpar@100: alpar@280: //Creates the maps if necessary. alpar@100: void create_maps() { alpar@100: if(!_reached) { alpar@209: local_reached = true; alpar@209: _reached = Traits::createReachedMap(*_digraph); alpar@100: } alpar@100: } alpar@100: alpar@100: protected: alpar@100: alpar@100: DfsVisit() {} alpar@209: alpar@100: public: alpar@100: alpar@100: typedef DfsVisit Create; alpar@100: kpeter@405: /// \name Named Template Parameters alpar@100: alpar@100: ///@{ alpar@100: template kpeter@257: struct SetReachedMapTraits : public Traits { alpar@100: typedef T ReachedMap; alpar@100: static ReachedMap *createReachedMap(const Digraph &digraph) { deba@290: LEMON_ASSERT(false, "ReachedMap is not initialized"); deba@290: return 0; // ignore warnings alpar@100: } alpar@100: }; alpar@209: /// \brief \ref named-templ-param "Named parameter" for setting kpeter@244: /// ReachedMap type. alpar@100: /// kpeter@244: /// \ref named-templ-param "Named parameter" for setting ReachedMap type. alpar@100: template kpeter@257: struct SetReachedMap : public DfsVisit< Digraph, Visitor, kpeter@257: SetReachedMapTraits > { kpeter@257: typedef DfsVisit< Digraph, Visitor, SetReachedMapTraits > Create; alpar@100: }; alpar@100: ///@} alpar@100: alpar@209: public: alpar@209: alpar@100: /// \brief Constructor. alpar@100: /// alpar@100: /// Constructor. alpar@100: /// kpeter@244: /// \param digraph The digraph the algorithm runs on. kpeter@244: /// \param visitor The visitor object of the algorithm. alpar@209: DfsVisit(const Digraph& digraph, Visitor& visitor) alpar@100: : _digraph(&digraph), _visitor(&visitor), alpar@209: _reached(0), local_reached(false) {} alpar@209: alpar@100: /// \brief Destructor. alpar@100: ~DfsVisit() { alpar@100: if(local_reached) delete _reached; alpar@100: } alpar@100: kpeter@244: /// \brief Sets the map that indicates which nodes are reached. alpar@100: /// kpeter@244: /// Sets the map that indicates which nodes are reached. kpeter@405: /// If you don't use this function before calling \ref run(Node) "run()" kpeter@405: /// or \ref init(), an instance will be allocated automatically. kpeter@405: /// The destructor deallocates this automatically allocated map, kpeter@405: /// of course. alpar@100: /// \return (*this) alpar@100: DfsVisit &reachedMap(ReachedMap &m) { alpar@100: if(local_reached) { alpar@209: delete _reached; alpar@209: local_reached=false; alpar@100: } alpar@100: _reached = &m; alpar@100: return *this; alpar@100: } alpar@100: alpar@100: public: kpeter@244: kpeter@405: /// \name Execution Control kpeter@405: /// The simplest way to execute the DFS algorithm is to use one of the kpeter@405: /// member functions called \ref run(Node) "run()".\n kpeter@713: /// If you need better control on the execution, you have to call kpeter@713: /// \ref init() first, then you can add a source node with \ref addSource() kpeter@405: /// and perform the actual computation with \ref start(). kpeter@405: /// This procedure can be repeated if there are nodes that have not kpeter@405: /// been reached. alpar@100: alpar@100: /// @{ kpeter@244: alpar@100: /// \brief Initializes the internal data structures. alpar@100: /// alpar@100: /// Initializes the internal data structures. 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@209: _reached->set(u, false); alpar@100: } alpar@100: } alpar@209: kpeter@405: /// \brief Adds a new source node. alpar@100: /// kpeter@405: /// Adds a new source node to the set of nodes to be processed. kpeter@244: /// kpeter@405: /// \pre The stack must be empty. Otherwise the algorithm gives kpeter@405: /// wrong results. (One of the outgoing arcs of all the source nodes kpeter@405: /// except for the last one will not be visited and distances will kpeter@405: /// also be wrong.) kpeter@244: void addSource(Node s) kpeter@244: { kpeter@244: LEMON_DEBUG(emptyQueue(), "The stack is not empty."); alpar@100: if(!(*_reached)[s]) { alpar@209: _reached->set(s,true); alpar@209: _visitor->start(s); alpar@209: _visitor->reach(s); alpar@209: Arc e; alpar@209: _digraph->firstOut(e, s); alpar@209: if (e != INVALID) { alpar@209: _stack[++_stack_head] = e; alpar@209: } else { alpar@209: _visitor->leave(s); deba@419: _visitor->stop(s); alpar@209: } alpar@209: } alpar@100: } alpar@209: 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: /// kpeter@244: /// \pre The stack must not be empty. alpar@209: Arc processNextArc() { alpar@100: Arc e = _stack[_stack_head]; alpar@100: Node m = _digraph->target(e); alpar@100: if(!(*_reached)[m]) { alpar@209: _visitor->discover(e); alpar@209: _visitor->reach(m); alpar@209: _reached->set(m, true); alpar@209: _digraph->firstOut(_stack[++_stack_head], m); alpar@100: } else { alpar@209: _visitor->examine(e); alpar@209: m = _digraph->source(e); alpar@209: _digraph->nextOut(_stack[_stack_head]); alpar@100: } alpar@100: while (_stack_head>=0 && _stack[_stack_head] == INVALID) { alpar@209: _visitor->leave(m); alpar@209: --_stack_head; alpar@209: if (_stack_head >= 0) { alpar@209: _visitor->backtrack(_stack[_stack_head]); alpar@209: m = _digraph->source(_stack[_stack_head]); alpar@209: _digraph->nextOut(_stack[_stack_head]); alpar@209: } else { alpar@209: _visitor->stop(m); alpar@209: } 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. kpeter@244: Arc nextArc() const { alpar@100: return _stack_head >= 0 ? _stack[_stack_head] : INVALID; alpar@100: } alpar@100: alpar@100: /// \brief Returns \c false if there are nodes kpeter@244: /// to be processed. alpar@100: /// alpar@100: /// Returns \c false if there are nodes kpeter@244: /// to be processed in the queue (stack). kpeter@244: bool emptyQueue() const { return _stack_head < 0; } alpar@100: alpar@100: /// \brief Returns the number of the nodes to be processed. alpar@100: /// kpeter@244: /// Returns the number of the nodes to be processed in the queue (stack). kpeter@244: int queueSize() const { return _stack_head + 1; } alpar@209: alpar@100: /// \brief Executes the algorithm. alpar@100: /// alpar@100: /// Executes the algorithm. alpar@100: /// kpeter@244: /// This method runs the %DFS algorithm from the root node kpeter@244: /// in order to compute the %DFS path to each node. kpeter@244: /// kpeter@244: /// The algorithm computes kpeter@244: /// - the %DFS tree, kpeter@244: /// - the distance of each node from the root in the %DFS tree. kpeter@244: /// kpeter@244: /// \pre init() must be called and a root node should be kpeter@244: /// added with addSource() before using this function. kpeter@244: /// kpeter@244: /// \note d.start() is just a shortcut of the following code. kpeter@244: /// \code kpeter@244: /// while ( !d.emptyQueue() ) { kpeter@244: /// d.processNextArc(); kpeter@244: /// } kpeter@244: /// \endcode alpar@100: void start() { alpar@100: while ( !emptyQueue() ) processNextArc(); alpar@100: } alpar@209: kpeter@244: /// \brief Executes the algorithm until the given target node is reached. alpar@100: /// kpeter@244: /// Executes the algorithm until the given target node is reached. alpar@100: /// kpeter@244: /// This method runs the %DFS algorithm from the root node kpeter@286: /// in order to compute the DFS path to \c t. kpeter@244: /// kpeter@244: /// The algorithm computes kpeter@286: /// - the %DFS path to \c t, kpeter@286: /// - the distance of \c t from the root in the %DFS tree. kpeter@244: /// kpeter@244: /// \pre init() must be called and a root node should be added alpar@100: /// with addSource() before using this function. kpeter@286: void start(Node t) { kpeter@286: while ( !emptyQueue() && _digraph->target(_stack[_stack_head]) != t ) alpar@209: processNextArc(); alpar@100: } alpar@209: 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: /// kpeter@244: /// This method runs the %DFS algorithm from the root node kpeter@244: /// until an arc \c a with am[a] true is found. kpeter@244: /// kpeter@244: /// \param am A \c bool (or convertible) arc map. The algorithm kpeter@244: /// will stop when it reaches an arc \c a with am[a] true. kpeter@244: /// kpeter@244: /// \return The reached arc \c a with am[a] true or kpeter@244: /// \c INVALID if no such arc was found. kpeter@244: /// kpeter@244: /// \pre init() must be called and a root node should be added alpar@100: /// with addSource() before using this function. alpar@100: /// kpeter@244: /// \warning Contrary to \ref Bfs and \ref Dijkstra, \c am is an arc map, alpar@100: /// not a node map. kpeter@244: template kpeter@244: Arc start(const AM &am) { kpeter@244: while ( !emptyQueue() && !am[_stack[_stack_head]] ) alpar@100: processNextArc(); alpar@100: return emptyQueue() ? INVALID : _stack[_stack_head]; alpar@100: } alpar@100: kpeter@286: /// \brief Runs the algorithm from the given source node. alpar@100: /// kpeter@244: /// This method runs the %DFS algorithm from node \c s. kpeter@244: /// in order to compute the DFS path to each node. kpeter@244: /// kpeter@244: /// The algorithm computes kpeter@244: /// - the %DFS tree, kpeter@244: /// - the distance of each node from the root in the %DFS tree. kpeter@244: /// kpeter@244: /// \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: kpeter@244: /// \brief Finds the %DFS path between \c s and \c t. kpeter@244: kpeter@244: /// This method runs the %DFS algorithm from node \c s kpeter@286: /// in order to compute the DFS path to node \c t kpeter@286: /// (it stops searching when \c t is processed). kpeter@244: /// kpeter@286: /// \return \c true if \c t is reachable form \c s. kpeter@244: /// kpeter@244: /// \note Apart from the return value, d.run(s,t) is kpeter@244: /// just a shortcut of the following code. kpeter@244: ///\code kpeter@244: /// d.init(); kpeter@244: /// d.addSource(s); kpeter@244: /// d.start(t); kpeter@244: ///\endcode kpeter@286: bool run(Node s,Node t) { kpeter@244: init(); kpeter@244: addSource(s); kpeter@244: start(t); kpeter@286: return reached(t); kpeter@244: } kpeter@244: kpeter@244: /// \brief Runs the algorithm to visit all nodes in the digraph. alpar@209: alpar@100: /// This method runs the %DFS algorithm in order to kpeter@244: /// compute the %DFS path to each node. alpar@100: /// kpeter@244: /// The algorithm computes kpeter@405: /// - the %DFS tree (forest), kpeter@405: /// - the distance of each node from the root(s) in the %DFS tree. kpeter@244: /// kpeter@244: /// \note d.run() is just a shortcut of the following code. alpar@100: ///\code kpeter@244: /// d.init(); kpeter@244: /// for (NodeIt n(digraph); n != INVALID; ++n) { kpeter@244: /// if (!d.reached(n)) { kpeter@244: /// d.addSource(n); kpeter@244: /// d.start(); kpeter@244: /// } kpeter@244: /// } 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: } kpeter@244: alpar@100: ///@} alpar@100: alpar@100: /// \name Query Functions kpeter@405: /// The results of the DFS algorithm can be obtained using these alpar@100: /// functions.\n kpeter@405: /// Either \ref run(Node) "run()" or \ref start() should be called kpeter@405: /// before using them. kpeter@405: alpar@100: ///@{ kpeter@244: kpeter@716: /// \brief Checks if the given node is reached from the root(s). alpar@100: /// kpeter@405: /// Returns \c true if \c v is reached from the root(s). kpeter@405: /// kpeter@405: /// \pre Either \ref run(Node) "run()" or \ref init() alpar@100: /// must be called before using this function. kpeter@420: bool reached(Node v) const { return (*_reached)[v]; } kpeter@244: alpar@100: ///@} kpeter@244: alpar@100: }; alpar@100: alpar@100: } //END OF NAMESPACE LEMON alpar@100: alpar@100: #endif