diff -r 0a75c3e6a91a -r c13f6b4aa40e lemon/dfs.h --- a/lemon/dfs.h Wed Nov 02 12:44:50 2005 +0000 +++ b/lemon/dfs.h Wed Nov 02 15:22:28 2005 +0000 @@ -27,9 +27,10 @@ #include #include +#include + namespace lemon { - ///Default traits class of Dfs class. @@ -123,8 +124,6 @@ ///a Dfs traits class. /// ///\author Jacint Szabo and Alpar Juttner - ///\todo A compare object would be nice. - #ifdef DOXYGEN template @@ -275,7 +274,7 @@ ///\ref named-templ-param "Named parameter" for setting ReachedMap type /// template - struct DefReachedMap { + struct DefReachedMap : public Dfs< Graph, DefReachedMapTraits > { typedef Dfs< Graph, DefReachedMapTraits > Create; }; @@ -326,7 +325,6 @@ Dfs(const Graph& _G) : G(&_G), _pred(NULL), local_pred(false), -// _predNode(NULL), local_predNode(false), _dist(NULL), local_dist(false), _reached(NULL), local_reached(false), _processed(NULL), local_processed(false) @@ -336,7 +334,6 @@ ~Dfs() { if(local_pred) delete _pred; -// if(local_predNode) delete _predNode; if(local_dist) delete _dist; if(local_reached) delete _reached; if(local_processed) delete _processed; @@ -359,23 +356,6 @@ return *this; } -// ///Sets the map storing the predecessor nodes. - -// ///Sets the map storing the predecessor nodes. -// ///If you don't use this function before calling \ref run(), -// ///it will allocate one. The destuctor deallocates this -// ///automatically allocated map, of course. -// ///\return (*this) -// Dfs &predNodeMap(PredNodeMap &m) -// { -// if(local_predNode) { -// delete _predNode; -// local_predNode=false; -// } -// _predNode = &m; -// return *this; -// } - ///Sets the map storing the distances calculated by the algorithm. ///Sets the map storing the distances calculated by the algorithm. @@ -468,7 +448,6 @@ { _reached->set(s,true); _pred->set(s,INVALID); - // _predNode->set(u,INVALID); OutEdgeIt e(*G,s); if(e!=INVALID) { _stack[++_stack_head]=e; @@ -495,7 +474,6 @@ if(!(*_reached)[m=G->target(e)]) { _pred->set(m,e); _reached->set(m,true); - // _pred_node->set(m,G->source(e)); ++_stack_head; _stack[_stack_head] = OutEdgeIt(*G, m); _dist->set(m,_stack_head); @@ -504,7 +482,6 @@ m=G->source(e); ++_stack[_stack_head]; } - //'m' is now the (original) source of the _stack[_stack_head] while(_stack_head>=0 && _stack[_stack_head]==INVALID) { _processed->set(m,true); --_stack_head; @@ -590,14 +567,14 @@ ///\param nm must be a bool (or convertible) edge map. The algorithm ///will stop when it reaches an edge \c e with nm[e]==true. /// - ///\warning Contrary to \ref Dfs and \ref Dijkstra, \c nm is an edge map, + ///\warning Contrary to \ref Dfs and \ref Dijkstra, \c em is an edge map, ///not a node map. - template - void start(const NM &nm) - { - while ( !emptyQueue() && !nm[_stack[_stack_head]] ) processNextEdge(); - } - + template + void start(const EM &em) + { + while ( !emptyQueue() && !em[_stack[_stack_head]] ) processNextEdge(); + } + ///Runs %DFS algorithm from node \c s. ///This method runs the %DFS algorithm from a root node \c s @@ -725,13 +702,6 @@ ///must be called before using this function. const PredMap &predMap() const { return *_pred;} -// ///Returns a reference to the map of nodes of %DFS paths. - -// ///Returns a reference to the NodeMap of the last but one nodes of the -// ///%DFS tree. -// ///\pre \ref run() must be called before using this function. -// const PredNodeMap &predNodeMap() const { return *_predNode;} - ///Checks if a node is reachable from the root. ///Returns \c true if \c v is reachable from the root(s). @@ -774,23 +744,6 @@ { return new PredMap(); } -// ///\brief The type of the map that stores the last but one -// ///nodes of the %DFS paths. -// /// -// ///The type of the map that stores the last but one -// ///nodes of the %DFS paths. -// ///It must meet the \ref concept::WriteMap "WriteMap" concept. -// /// -// typedef NullMap PredNodeMap; -// ///Instantiates a PredNodeMap. - -// ///This function instantiates a \ref PredNodeMap. -// ///\param G is the graph, to which -// ///we would like to define the \ref PredNodeMap -// static PredNodeMap *createPredNodeMap(const GR &G) -// { -// return new PredNodeMap(); -// } ///The type of the map that indicates which nodes are processed. @@ -871,8 +824,6 @@ void *_processed; ///Pointer to the map of predecessors edges. void *_pred; -// ///Pointer to the map of predecessors nodes. -// void *_predNode; ///Pointer to the map of distances. void *_dist; ///Pointer to the source node. @@ -884,7 +835,6 @@ /// This constructor does not require parameters, therefore it initiates /// all of the attributes to default values (0, INVALID). DfsWizardBase() : _g(0), _reached(0), _processed(0), _pred(0), -// _predNode(0), _dist(0), _source(INVALID) {} /// Constructor. @@ -896,7 +846,6 @@ /// \param s is the initial value of \ref _source DfsWizardBase(const GR &g, Node s=INVALID) : _g((void *)&g), _reached(0), _processed(0), _pred(0), -// _predNode(0), _dist(0), _source(s) {} }; @@ -945,9 +894,6 @@ ///\brief The type of the map that stores the last ///edges of the %DFS paths. typedef typename TR::PredMap PredMap; -// ///\brief The type of the map that stores the last but one -// ///nodes of the %DFS paths. -// typedef typename TR::PredNodeMap PredNodeMap; ///The type of the map that stores the distances of the nodes. typedef typename TR::DistMap DistMap; @@ -978,7 +924,6 @@ if(Base::_reached) alg.reachedMap(*(ReachedMap*)Base::_reached); if(Base::_processed) alg.processedMap(*(ProcessedMap*)Base::_processed); if(Base::_pred) alg.predMap(*(PredMap*)Base::_pred); -// if(Base::_predNode) alg.predNodeMap(*(PredNodeMap*)Base::_predNode); if(Base::_dist) alg.distMap(*(DistMap*)Base::_dist); alg.run(Base::_source); } @@ -1055,27 +1000,6 @@ return DfsWizard >(*this); } - -// template -// struct DefPredNodeMapBase : public Base { -// typedef T PredNodeMap; -// static PredNodeMap *createPredNodeMap(const Graph &G) { return 0; }; -// DefPredNodeMapBase(const TR &b) : TR(b) {} -// }; - -// ///\brief \ref named-templ-param "Named parameter" -// ///function for setting PredNodeMap type -// /// -// /// \ref named-templ-param "Named parameter" -// ///function for setting PredNodeMap type -// /// -// template -// DfsWizard > predNodeMap(const T &t) -// { -// Base::_predNode=(void *)&t; -// return DfsWizard >(*this); -// } - template struct DefDistMapBase : public Base { typedef T DistMap; @@ -1132,6 +1056,414 @@ return DfsWizard >(g,s); } + /// \brief Visitor class for dfs. + /// + /// It gives a simple interface for a functional interface for dfs + /// traversal. The traversal on a linear data structure. + template + struct DfsVisitor { + typedef _Graph Graph; + typedef typename Graph::Edge Edge; + typedef typename Graph::Node Node; + /// \brief Called when the edge reach a node. + /// + /// It is called when the dfs find an edge which target is not + /// reached yet. + void discover(const Edge& edge) {} + /// \brief Called when the node reached first time. + /// + /// It is Called when the node reached first time. + void reach(const Node& node) {} + /// \brief Called when we step back on an edge. + /// + /// It is called when the dfs should step back on the edge. + void backtrack(const Edge& edge) {} + /// \brief Called when we step back from the node. + /// + /// It is called when we step back from the node. + void leave(const Node& node) {} + /// \brief Called when the edge examined but target of the edge + /// already discovered. + /// + /// It called when the edge examined but the target of the edge + /// already discovered. + void examine(const Edge& edge) {} + /// \brief Called for the source node of the dfs. + /// + /// It is called for the source node of the dfs. + void start(const Node&) {} + /// \brief Called when we leave the source node of the dfs. + /// + /// It is called when we leave the source node of the dfs. + void stop(const Node&) {} + + template + struct Constraints { + void constraints() { + Edge edge; + Node node; + visitor.discover(edge); + visitor.reach(node); + visitor.backtrack(edge); + visitor.leave(node); + visitor.examine(edge); + visitor.start(node); + visitor.stop(edge); + } + _Visitor& visitor; + }; + }; + + /// \brief Default traits class of DfsVisit class. + /// + /// Default traits class of DfsVisit class. + /// \param _Graph Graph type. + template + struct DfsVisitDefaultTraits { + + /// \brief The graph type the algorithm runs on. + typedef _Graph Graph; + + /// \brief The type of the map that indicates which nodes are reached. + /// + /// The type of the map that indicates which nodes are reached. + /// It must meet the \ref concept::WriteMap "WriteMap" concept. + /// \todo named parameter to set this type, function to read and write. + typedef typename Graph::template NodeMap ReachedMap; + + /// \brief Instantiates a ReachedMap. + /// + /// This function instantiates a \ref ReachedMap. + /// \param G is the graph, to which + /// we would like to define the \ref ReachedMap. + static ReachedMap *createReachedMap(const Graph &graph) { + return new ReachedMap(graph); + } + + }; + + /// %DFS Visit algorithm class. + + /// \ingroup flowalgs + /// This class provides an efficient implementation of the %DFS algorithm + /// with visitor interface. + /// + /// The %DfsVisit class provides an alternative interface to the Dfs + /// class. It works with callback mechanism, the DfsVisit object calls + /// on every dfs event the \c Visitor class member functions. + /// + /// \param _Graph The graph type the algorithm runs on. The default value is + /// \ref ListGraph. The value of _Graph is not used directly by Dfs, it + /// is only passed to \ref DfsDefaultTraits. + /// \param _Visitor The Visitor object for the algorithm. The + /// \ref DfsVisitor "DfsVisitor<_Graph>" is an empty Visitor which + /// does not observe the Dfs events. If you want to observe the dfs + /// events you should implement your own Visitor class. + /// \param _Traits Traits class to set various data types used by the + /// algorithm. The default traits class is + /// \ref DfsVisitDefaultTraits "DfsVisitDefaultTraits<_Graph>". + /// See \ref DfsVisitDefaultTraits for the documentation of + /// a Dfs visit traits class. + /// + /// \author Jacint Szabo, Alpar Juttner and Balazs Dezso +#ifdef DOXYGEN + template +#else + template , + typename _Traits = DfsDefaultTraits<_Graph> > +#endif + class DfsVisit { + public: + + /// \brief \ref Exception for uninitialized parameters. + /// + /// This error represents problems in the initialization + /// of the parameters of the algorithms. + class UninitializedParameter : public lemon::UninitializedParameter { + public: + virtual const char* exceptionName() const { + return "lemon::DfsVisit::UninitializedParameter"; + } + }; + + typedef _Traits Traits; + + typedef typename Traits::Graph Graph; + + typedef _Visitor Visitor; + + ///The type of the map indicating which nodes are reached. + typedef typename Traits::ReachedMap ReachedMap; + + private: + + typedef typename Graph::Node Node; + typedef typename Graph::NodeIt NodeIt; + typedef typename Graph::Edge Edge; + typedef typename Graph::OutEdgeIt OutEdgeIt; + + /// Pointer to the underlying graph. + const Graph *_graph; + /// Pointer to the visitor object. + Visitor *_visitor; + ///Pointer to the map of reached status of the nodes. + ReachedMap *_reached; + ///Indicates if \ref _reached is locally allocated (\c true) or not. + bool local_reached; + + std::vector _stack; + int _stack_head; + + /// \brief Creates the maps if necessary. + /// + /// Creates the maps if necessary. + void create_maps() { + if(!_reached) { + local_reached = true; + _reached = Traits::createReachedMap(*_graph); + } + } + + protected: + + DfsVisit() {} + + public: + + typedef DfsVisit Create; + + /// \name Named template parameters + + ///@{ + template + struct DefReachedMapTraits : public Traits { + typedef T ReachedMap; + static ReachedMap *createReachedMap(const Graph &graph) { + throw UninitializedParameter(); + } + }; + /// \brief \ref named-templ-param "Named parameter" for setting + /// ReachedMap type + /// + /// \ref named-templ-param "Named parameter" for setting ReachedMap type + template + struct DefReachedMap : public Dfs< Graph, DefReachedMapTraits > { + typedef Dfs< Graph, DefReachedMapTraits > Create; + }; + ///@} + + public: + + /// \brief Constructor. + /// + /// Constructor. + /// + /// \param graph the graph the algorithm will run on. + /// \param visitor The visitor of the algorithm. + /// + DfsVisit(const Graph& graph, Visitor& visitor) + : _graph(&graph), _visitor(&visitor), + _reached(0), local_reached(false) {} + + /// \brief Destructor. + /// + /// Destructor. + ~DfsVisit() { + if(local_reached) delete _reached; + } + + /// \brief Sets the map indicating if a node is reached. + /// + /// Sets the map indicating if a node is reached. + /// If you don't use this function before calling \ref run(), + /// it will allocate one. The destuctor deallocates this + /// automatically allocated map, of course. + /// \return (*this) + DfsVisit &reachedMap(ReachedMap &m) { + if(local_reached) { + delete _reached; + local_reached=false; + } + _reached = &m; + return *this; + } + + public: + /// \name Execution control + /// The simplest way to execute the algorithm is to use + /// one of the member functions called \c run(...). + /// \n + /// If you need more control on the execution, + /// first you must call \ref init(), then you can add several source nodes + /// with \ref addSource(). + /// Finally \ref start() will perform the actual path + /// computation. + + /// @{ + /// \brief Initializes the internal data structures. + /// + /// Initializes the internal data structures. + /// + void init() { + create_maps(); + _stack.resize(countNodes(*_graph)); + _stack_head = -1; + for (NodeIt u(*_graph) ; u != INVALID ; ++u) { + _reached->set(u, false); + } + } + + /// \brief Adds a new source node. + /// + /// Adds a new source node to the set of nodes to be processed. + void addSource(Node s) { + if(!(*_reached)[s]) { + _reached->set(s,true); + _visitor->start(s); + _visitor->reach(s); + Edge e; + _graph->firstOut(e, s); + if (e != INVALID) { + _stack[++_stack_head] = e; + } else { + _visitor->leave(s); + } + } + } + + /// \brief Processes the next edge. + /// + /// Processes the next edge. + /// + /// \return The processed edge. + /// + /// \pre The stack must not be empty! + Edge processNextEdge() { + Edge e = _stack[_stack_head]; + Node m = _graph->target(e); + if(!(*_reached)[m]) { + _visitor->discover(e); + _visitor->reach(m); + _reached->set(m, true); + _graph->firstOut(_stack[++_stack_head], m); + } else { + _visitor->examine(e); + m = _graph->source(e); + _graph->nextOut(_stack[_stack_head]); + } + while (_stack_head>=0 && _stack[_stack_head] == INVALID) { + _visitor->leave(m); + --_stack_head; + if (_stack_head >= 0) { + _visitor->backtrack(_stack[_stack_head]); + m = _graph->source(_stack[_stack_head]); + _graph->nextOut(_stack[_stack_head]); + } else { + _visitor->stop(m); + } + } + return e; + } + + /// \brief Next edge to be processed. + /// + /// Next edge to be processed. + /// + /// \return The next edge to be processed or INVALID if the stack is + /// empty. + Edge nextEdge() { + return _stack_head >= 0 ? _stack[_stack_head] : INVALID; + } + + /// \brief Returns \c false if there are nodes + /// to be processed in the queue + /// + /// Returns \c false if there are nodes + /// to be processed in the queue + /// + /// \todo This should be called emptyStack() or some "neutral" name. + bool emptyQueue() { return _stack_head < 0; } + + /// \brief Returns the number of the nodes to be processed. + /// + /// Returns the number of the nodes to be processed in the queue. + /// + ///\todo This should be called stackSize() or some "neutral" name. + int queueSize() { return _stack_head + 1; } + + /// \brief Executes the algorithm. + /// + /// Executes the algorithm. + /// + /// \pre init() must be called and at least one node should be added + /// with addSource() before using this function. + void start() { + while ( !emptyQueue() ) processNextEdge(); + } + + /// \brief Executes the algorithm until \c dest is reached. + /// + /// Executes the algorithm until \c dest is reached. + /// + /// \pre init() must be called and at least one node should be added + /// with addSource() before using this function. + void start(Node dest) { + while ( !emptyQueue() && _graph->target(_stack[_stack_head]) != dest) + processNextEdge(); + } + + /// \brief Executes the algorithm until a condition is met. + /// + /// Executes the algorithm until a condition is met. + /// + /// \pre init() must be called and at least one node should be added + /// with addSource() before using this function. + /// + /// \param nm must be a bool (or convertible) edge map. The algorithm + /// will stop when it reaches an edge \c e with nm[e]==true. + /// + /// \warning Contrary to \ref Dfs and \ref Dijkstra, \c em is an edge map, + /// not a node map. + template + void start(const EM &em) { + while (!emptyQueue() && !em[_stack[_stack_head]]) processNextEdge(); + } + + /// \brief Runs %DFS algorithm from node \c s. + /// + /// This method runs the %DFS algorithm from a root node \c s. + /// \note d.run(s) is just a shortcut of the following code. + /// \code + /// d.init(); + /// d.addSource(s); + /// d.start(); + /// \endcode + void run(Node s) { + init(); + addSource(s); + start(); + } + ///@} + + /// \name Query Functions + /// The result of the %DFS algorithm can be obtained using these + /// functions.\n + /// Before the use of these functions, + /// either run() or start() must be called. + ///@{ + /// \brief Checks if a node is reachable from the root. + /// + /// Returns \c true if \c v is reachable from the root(s). + /// \warning The source nodes are inditated as unreachable. + /// \pre Either \ref run() or \ref start() + /// must be called before using this function. + /// + bool reached(Node v) { return (*_reached)[v]; } + ///@} + }; + + } //END OF NAMESPACE LEMON #endif