diff -r 4317d277ba21 -r 765619b7cbb2 lemon/dfs.h --- a/lemon/dfs.h Sun Jul 13 16:46:56 2008 +0100 +++ b/lemon/dfs.h Sun Jul 13 19:51:02 2008 +0100 @@ -1,6 +1,6 @@ -/* -*- C++ -*- +/* -*- mode: C++; indent-tabs-mode: nil; -*- * - * This file is a part of LEMON, a generic C++ optimization library + * This file is a part of LEMON, a generic C++ optimization library. * * Copyright (C) 2003-2008 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport @@ -34,7 +34,7 @@ namespace lemon { - + ///Default traits class of Dfs class. ///Default traits class of Dfs class. @@ -42,35 +42,35 @@ template struct DfsDefaultTraits { - ///The digraph type the algorithm runs on. + ///The digraph type the algorithm runs on. typedef GR Digraph; ///\brief The type of the map that stores the last ///arcs of the %DFS paths. - /// + /// ///The type of the map that stores the last ///arcs of the %DFS paths. ///It must meet the \ref concepts::WriteMap "WriteMap" concept. /// typedef typename Digraph::template NodeMap PredMap; ///Instantiates a PredMap. - - ///This function instantiates a \ref PredMap. + + ///This function instantiates a \ref PredMap. ///\param G is the digraph, to which we would like to define the PredMap. ///\todo The digraph alone may be insufficient to initialize - static PredMap *createPredMap(const GR &G) + static PredMap *createPredMap(const GR &G) { return new PredMap(G); } ///The type of the map that indicates which nodes are processed. - + ///The type of the map that indicates which nodes are processed. ///It must meet the \ref concepts::WriteMap "WriteMap" concept. ///\todo named parameter to set this type, function to read and write. typedef NullMap ProcessedMap; ///Instantiates a ProcessedMap. - - ///This function instantiates a \ref ProcessedMap. + + ///This function instantiates a \ref ProcessedMap. ///\param g is the digraph, to which ///we would like to define the \ref ProcessedMap #ifdef DOXYGEN @@ -82,14 +82,14 @@ return new ProcessedMap(); } ///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 concepts::WriteMap "WriteMap" concept. ///\todo named parameter to set this type, function to read and write. typedef typename Digraph::template NodeMap ReachedMap; ///Instantiates a ReachedMap. - - ///This function instantiates a \ref ReachedMap. + + ///This function instantiates a \ref ReachedMap. ///\param G is the digraph, to which ///we would like to define the \ref ReachedMap. static ReachedMap *createReachedMap(const GR &G) @@ -97,23 +97,23 @@ return new ReachedMap(G); } ///The type of the map that stores the dists of the nodes. - + ///The type of the map that stores the dists of the nodes. ///It must meet the \ref concepts::WriteMap "WriteMap" concept. /// typedef typename Digraph::template NodeMap DistMap; ///Instantiates a DistMap. - - ///This function instantiates a \ref DistMap. + + ///This function instantiates a \ref DistMap. ///\param G is the digraph, to which we would like to define the \ref DistMap static DistMap *createDistMap(const GR &G) { return new DistMap(G); } }; - + ///%DFS algorithm class. - + ///\ingroup search ///This class provides an efficient implementation of the %DFS algorithm. /// @@ -127,10 +127,10 @@ ///a Dfs traits class. #ifdef DOXYGEN template + typename TR> #else template > + typename TR=DfsDefaultTraits > #endif class Dfs { public: @@ -143,7 +143,7 @@ class UninitializedParameter : public lemon::UninitializedParameter { public: virtual const char* what() const throw() { - return "lemon::Dfs::UninitializedParameter"; + return "lemon::Dfs::UninitializedParameter"; } }; @@ -158,7 +158,7 @@ typedef typename Digraph::Arc Arc; ///\e typedef typename Digraph::OutArcIt OutArcIt; - + ///\brief The type of the map that stores the last ///arcs of the %DFS paths. typedef typename TR::PredMap PredMap; @@ -192,32 +192,32 @@ int _stack_head; ///Creates the maps if necessary. - + ///\todo Better memory allocation (instead of new). - void create_maps() + void create_maps() { if(!_pred) { - local_pred = true; - _pred = Traits::createPredMap(*G); + local_pred = true; + _pred = Traits::createPredMap(*G); } if(!_dist) { - local_dist = true; - _dist = Traits::createDistMap(*G); + local_dist = true; + _dist = Traits::createDistMap(*G); } if(!_reached) { - local_reached = true; - _reached = Traits::createReachedMap(*G); + local_reached = true; + _reached = Traits::createReachedMap(*G); } if(!_processed) { - local_processed = true; - _processed = Traits::createProcessedMap(*G); + local_processed = true; + _processed = Traits::createProcessedMap(*G); } } protected: Dfs() {} - + public: typedef Dfs Create; @@ -229,9 +229,9 @@ template struct DefPredMapTraits : public Traits { typedef T PredMap; - static PredMap *createPredMap(const Digraph &G) + static PredMap *createPredMap(const Digraph &G) { - throw UninitializedParameter(); + throw UninitializedParameter(); } }; ///\brief \ref named-templ-param "Named parameter" for setting @@ -243,14 +243,14 @@ struct DefPredMap : public Dfs > { typedef Dfs > Create; }; - - + + template struct DefDistMapTraits : public Traits { typedef T DistMap; - static DistMap *createDistMap(const Digraph &) + static DistMap *createDistMap(const Digraph &) { - throw UninitializedParameter(); + throw UninitializedParameter(); } }; ///\brief \ref named-templ-param "Named parameter" for setting @@ -262,13 +262,13 @@ struct DefDistMap { typedef Dfs > Create; }; - + template struct DefReachedMapTraits : public Traits { typedef T ReachedMap; - static ReachedMap *createReachedMap(const Digraph &) + static ReachedMap *createReachedMap(const Digraph &) { - throw UninitializedParameter(); + throw UninitializedParameter(); } }; ///\brief \ref named-templ-param "Named parameter" for setting @@ -284,9 +284,9 @@ template struct DefProcessedMapTraits : public Traits { typedef T ProcessedMap; - static ProcessedMap *createProcessedMap(const Digraph &) + static ProcessedMap *createProcessedMap(const Digraph &) { - throw UninitializedParameter(); + throw UninitializedParameter(); } }; ///\brief \ref named-templ-param "Named parameter" for setting @@ -295,15 +295,15 @@ ///\ref named-templ-param "Named parameter" for setting ProcessedMap type /// template - struct DefProcessedMap : public Dfs< Digraph, DefProcessedMapTraits > { + struct DefProcessedMap : public Dfs< Digraph, DefProcessedMapTraits > { typedef Dfs< Digraph, DefProcessedMapTraits > Create; }; - + struct DefDigraphProcessedMapTraits : public Traits { typedef typename Digraph::template NodeMap ProcessedMap; - static ProcessedMap *createProcessedMap(const Digraph &G) + static ProcessedMap *createProcessedMap(const Digraph &G) { - return new ProcessedMap(G); + return new ProcessedMap(G); } }; ///\brief \ref named-templ-param "Named parameter" @@ -314,16 +314,16 @@ ///If you don't set it explicitely, it will be automatically allocated. template class DefProcessedMapToBeDefaultMap : - public Dfs< Digraph, DefDigraphProcessedMapTraits> { + public Dfs< Digraph, DefDigraphProcessedMapTraits> { typedef Dfs< Digraph, DefDigraphProcessedMapTraits> Create; }; - + ///@} - public: - + public: + ///Constructor. - + ///\param _G the digraph the algorithm will run on. /// Dfs(const Digraph& _G) : @@ -333,9 +333,9 @@ _reached(NULL), local_reached(false), _processed(NULL), local_processed(false) { } - + ///Destructor. - ~Dfs() + ~Dfs() { if(local_pred) delete _pred; if(local_dist) delete _dist; @@ -350,11 +350,11 @@ ///it will allocate one. The destuctor deallocates this ///automatically allocated map, of course. ///\return (*this) - Dfs &predMap(PredMap &m) + Dfs &predMap(PredMap &m) { if(local_pred) { - delete _pred; - local_pred=false; + delete _pred; + local_pred=false; } _pred = &m; return *this; @@ -367,11 +367,11 @@ ///it will allocate one. The destuctor deallocates this ///automatically allocated map, of course. ///\return (*this) - Dfs &distMap(DistMap &m) + Dfs &distMap(DistMap &m) { if(local_dist) { - delete _dist; - local_dist=false; + delete _dist; + local_dist=false; } _dist = &m; return *this; @@ -384,11 +384,11 @@ ///it will allocate one. The destuctor deallocates this ///automatically allocated map, of course. ///\return (*this) - Dfs &reachedMap(ReachedMap &m) + Dfs &reachedMap(ReachedMap &m) { if(local_reached) { - delete _reached; - local_reached=false; + delete _reached; + local_reached=false; } _reached = &m; return *this; @@ -401,11 +401,11 @@ ///it will allocate one. The destuctor deallocates this ///automatically allocated map, of course. ///\return (*this) - Dfs &processedMap(ProcessedMap &m) + Dfs &processedMap(ProcessedMap &m) { if(local_processed) { - delete _processed; - local_processed=false; + delete _processed; + local_processed=false; } _processed = &m; return *this; @@ -434,13 +434,13 @@ _stack.resize(countNodes(*G)); _stack_head=-1; for ( NodeIt u(*G) ; u!=INVALID ; ++u ) { - _pred->set(u,INVALID); - // _predNode->set(u,INVALID); - _reached->set(u,false); - _processed->set(u,false); + _pred->set(u,INVALID); + // _predNode->set(u,INVALID); + _reached->set(u,false); + _processed->set(u,false); } } - + ///Adds a new source node. ///Adds a new source node to the set of nodes to be processed. @@ -450,21 +450,21 @@ void addSource(Node s) { if(!(*_reached)[s]) - { - _reached->set(s,true); - _pred->set(s,INVALID); - OutArcIt e(*G,s); - if(e!=INVALID) { - _stack[++_stack_head]=e; - _dist->set(s,_stack_head); - } - else { - _processed->set(s,true); - _dist->set(s,0); - } - } + { + _reached->set(s,true); + _pred->set(s,INVALID); + OutArcIt e(*G,s); + if(e!=INVALID) { + _stack[++_stack_head]=e; + _dist->set(s,_stack_head); + } + else { + _processed->set(s,true); + _dist->set(s,0); + } + } } - + ///Processes the next arc. ///Processes the next arc. @@ -473,27 +473,27 @@ /// ///\pre The stack must not be empty! Arc processNextArc() - { + { Node m; Arc e=_stack[_stack_head]; if(!(*_reached)[m=G->target(e)]) { - _pred->set(m,e); - _reached->set(m,true); - ++_stack_head; - _stack[_stack_head] = OutArcIt(*G, m); - _dist->set(m,_stack_head); + _pred->set(m,e); + _reached->set(m,true); + ++_stack_head; + _stack[_stack_head] = OutArcIt(*G, m); + _dist->set(m,_stack_head); } else { - m=G->source(e); - ++_stack[_stack_head]; + m=G->source(e); + ++_stack[_stack_head]; } while(_stack_head>=0 && _stack[_stack_head]==INVALID) { - _processed->set(m,true); - --_stack_head; - if(_stack_head>=0) { - m=G->source(_stack[_stack_head]); - ++_stack[_stack_head]; - } + _processed->set(m,true); + --_stack_head; + if(_stack_head>=0) { + m=G->source(_stack[_stack_head]); + ++_stack[_stack_head]; + } } return e; } @@ -504,7 +504,7 @@ ///\return The next arc to be processed or INVALID if the stack is /// empty. OutArcIt nextArc() - { + { return _stack_head>=0?_stack[_stack_head]:INVALID; } @@ -515,10 +515,10 @@ ///to be processed in the queue bool emptyQueue() { return _stack_head<0; } ///Returns the number of the nodes to be processed. - + ///Returns the number of the nodes to be processed in the queue. int queueSize() { return _stack_head+1; } - + ///Executes the algorithm. ///Executes the algorithm. @@ -537,7 +537,7 @@ { while ( !emptyQueue() ) processNextArc(); } - + ///Executes the algorithm until \c dest is reached. ///Executes the algorithm until \c dest is reached. @@ -554,10 +554,10 @@ /// void start(Node dest) { - while ( !emptyQueue() && G->target(_stack[_stack_head])!=dest ) - processNextArc(); + while ( !emptyQueue() && G->target(_stack[_stack_head])!=dest ) + processNextArc(); } - + ///Executes the algorithm until a condition is met. ///Executes the algorithm until a condition is met. @@ -582,7 +582,7 @@ } ///Runs %DFS algorithm to visit all nodes in the digraph. - + ///This method runs the %DFS algorithm in order to ///compute the ///%DFS path to each node. The algorithm computes @@ -610,7 +610,7 @@ } ///Runs %DFS algorithm from node \c s. - + ///This method runs the %DFS algorithm from a root node \c s ///in order to ///compute the @@ -629,9 +629,9 @@ addSource(s); start(); } - + ///Finds the %DFS path between \c s and \c t. - + ///Finds the %DFS path between \c s and \c t. /// ///\return The length of the %DFS s---t path if there exists one, @@ -649,7 +649,7 @@ start(t); return reached(t)?_stack_head+1:0; } - + ///@} ///\name Query Functions @@ -657,16 +657,16 @@ ///functions.\n ///Before the use of these functions, ///either run() or start() must be called. - + ///@{ typedef PredMapPath Path; ///Gives back the shortest path. - + ///Gives back the shortest path. ///\pre The \c t should be reachable from the source. - Path path(Node t) + Path path(Node t) { return Path(*G, *_pred, t); } @@ -675,7 +675,7 @@ ///Returns the distance of a node from the root(s). ///\pre \ref run() must be called before using this function. - ///\warning If node \c v is unreachable from the root(s) then the return + ///\warning If node \c v is unreachable from the root(s) then the return ///value of this funcion is undefined. int dist(Node v) const { return (*_dist)[v]; } @@ -705,15 +705,15 @@ ///\pre Either \ref run() or \ref start() must be called before ///using this function. Node predNode(Node v) const { return (*_pred)[v]==INVALID ? INVALID: - G->source((*_pred)[v]); } - + G->source((*_pred)[v]); } + ///Returns a reference to the NodeMap of distances. ///Returns a reference to the NodeMap of distances. ///\pre Either \ref run() or \ref init() must ///be called before using this function. const DistMap &distMap() const { return *_dist;} - + ///Returns a reference to the %DFS arc-tree map. ///Returns a reference to the NodeMap of the arcs of the @@ -721,7 +721,7 @@ ///\pre Either \ref run() or \ref init() ///must be called before using this function. const PredMap &predMap() const { return *_pred;} - + ///Checks if a node is reachable from the root. ///Returns \c true if \c v is reachable from the root(s). @@ -730,7 +730,7 @@ ///must be called before using this function. /// bool reached(Node v) { return (*_reached)[v]; } - + ///@} }; @@ -741,39 +741,39 @@ template struct DfsWizardDefaultTraits { - ///The digraph type the algorithm runs on. + ///The digraph type the algorithm runs on. typedef GR Digraph; ///\brief The type of the map that stores the last ///arcs of the %DFS paths. - /// + /// ///The type of the map that stores the last ///arcs of the %DFS paths. ///It must meet the \ref concepts::WriteMap "WriteMap" concept. /// typedef NullMap PredMap; ///Instantiates a PredMap. - - ///This function instantiates a \ref PredMap. + + ///This function instantiates a \ref PredMap. ///\param g is the digraph, to which we would like to define the PredMap. ///\todo The digraph alone may be insufficient to initialize #ifdef DOXYGEN - static PredMap *createPredMap(const GR &g) + static PredMap *createPredMap(const GR &g) #else - static PredMap *createPredMap(const GR &) + static PredMap *createPredMap(const GR &) #endif { return new PredMap(); } ///The type of the map that indicates which nodes are processed. - + ///The type of the map that indicates which nodes are processed. ///It must meet the \ref concepts::WriteMap "WriteMap" concept. ///\todo named parameter to set this type, function to read and write. typedef NullMap ProcessedMap; ///Instantiates a ProcessedMap. - - ///This function instantiates a \ref ProcessedMap. + + ///This function instantiates a \ref ProcessedMap. ///\param g is the digraph, to which ///we would like to define the \ref ProcessedMap #ifdef DOXYGEN @@ -785,14 +785,14 @@ return new ProcessedMap(); } ///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 concepts::WriteMap "WriteMap" concept. ///\todo named parameter to set this type, function to read and write. typedef typename Digraph::template NodeMap ReachedMap; ///Instantiates a ReachedMap. - - ///This function instantiates a \ref ReachedMap. + + ///This function instantiates a \ref ReachedMap. ///\param G is the digraph, to which ///we would like to define the \ref ReachedMap. static ReachedMap *createReachedMap(const GR &G) @@ -800,14 +800,14 @@ return new ReachedMap(G); } ///The type of the map that stores the dists of the nodes. - + ///The type of the map that stores the dists of the nodes. ///It must meet the \ref concepts::WriteMap "WriteMap" concept. /// typedef NullMap DistMap; ///Instantiates a DistMap. - - ///This function instantiates a \ref DistMap. + + ///This function instantiates a \ref DistMap. ///\param g is the digraph, to which we would like to define the \ref DistMap #ifdef DOXYGEN static DistMap *createDistMap(const GR &g) @@ -818,7 +818,7 @@ return new DistMap(); } }; - + /// Default traits used by \ref DfsWizard /// To make it easier to use Dfs algorithm @@ -848,28 +848,28 @@ void *_dist; ///Pointer to the source node. Node _source; - + public: /// Constructor. - + /// 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), - _dist(0), _source(INVALID) {} + _dist(0), _source(INVALID) {} /// Constructor. - + /// This constructor requires some parameters, /// listed in the parameters list. /// Others are initiated to 0. /// \param g is the initial value of \ref _g /// \param s is the initial value of \ref _source DfsWizardBase(const GR &g, Node s=INVALID) : - _g(reinterpret_cast(const_cast(&g))), + _g(reinterpret_cast(const_cast(&g))), _reached(0), _processed(0), _pred(0), _dist(0), _source(s) {} }; - + /// A class to make the usage of the Dfs algorithm easier /// This class is created to make it easier to use the Dfs algorithm. @@ -904,7 +904,7 @@ typedef typename Digraph::Arc Arc; //\e typedef typename Digraph::OutArcIt OutArcIt; - + ///\brief The type of the map that stores ///the reached nodes typedef typename TR::ReachedMap ReachedMap; @@ -934,20 +934,20 @@ ~DfsWizard() {} ///Runs Dfs algorithm from a given node. - + ///Runs Dfs algorithm from a given node. ///The node can be given by the \ref source function. void run() { if(Base::_source==INVALID) throw UninitializedParameter(); Dfs alg(*reinterpret_cast(Base::_g)); - if(Base::_reached) + if(Base::_reached) alg.reachedMap(*reinterpret_cast(Base::_reached)); - if(Base::_processed) + if(Base::_processed) alg.processedMap(*reinterpret_cast(Base::_processed)); - if(Base::_pred) + if(Base::_pred) alg.predMap(*reinterpret_cast(Base::_pred)); - if(Base::_dist) + if(Base::_dist) alg.distMap(*reinterpret_cast(Base::_dist)); alg.run(Base::_source); } @@ -968,7 +968,7 @@ static PredMap *createPredMap(const Digraph &) { return 0; }; DefPredMapBase(const TR &b) : TR(b) {} }; - + ///\brief \ref named-templ-param "Named parameter" ///function for setting PredMap type /// @@ -976,20 +976,20 @@ ///function for setting PredMap type /// template - DfsWizard > predMap(const T &t) + DfsWizard > predMap(const T &t) { Base::_pred=reinterpret_cast(const_cast(&t)); return DfsWizard >(*this); } - - + + template struct DefReachedMapBase : public Base { typedef T ReachedMap; static ReachedMap *createReachedMap(const Digraph &) { return 0; }; DefReachedMapBase(const TR &b) : TR(b) {} }; - + ///\brief \ref named-templ-param "Named parameter" ///function for setting ReachedMap /// @@ -997,12 +997,12 @@ ///function for setting ReachedMap /// template - DfsWizard > reachedMap(const T &t) + DfsWizard > reachedMap(const T &t) { Base::_reached=reinterpret_cast(const_cast(&t)); return DfsWizard >(*this); } - + template struct DefProcessedMapBase : public Base { @@ -1010,7 +1010,7 @@ static ProcessedMap *createProcessedMap(const Digraph &) { return 0; }; DefProcessedMapBase(const TR &b) : TR(b) {} }; - + ///\brief \ref named-templ-param "Named parameter" ///function for setting ProcessedMap /// @@ -1018,19 +1018,19 @@ ///function for setting ProcessedMap /// template - DfsWizard > processedMap(const T &t) + DfsWizard > processedMap(const T &t) { Base::_processed=reinterpret_cast(const_cast(&t)); return DfsWizard >(*this); } - + template struct DefDistMapBase : public Base { typedef T DistMap; static DistMap *createDistMap(const Digraph &) { return 0; }; DefDistMapBase(const TR &b) : TR(b) {} }; - + ///\brief \ref named-templ-param "Named parameter" ///function for setting DistMap type /// @@ -1038,24 +1038,24 @@ ///function for setting DistMap type /// template - DfsWizard > distMap(const T &t) + DfsWizard > distMap(const T &t) { Base::_dist=reinterpret_cast(const_cast(&t)); return DfsWizard >(*this); } - + /// Sets the source node, from which the Dfs algorithm runs. /// Sets the source node, from which the Dfs algorithm runs. /// \param s is the source node. - DfsWizard &source(Node s) + DfsWizard &source(Node s) { Base::_source=s; return *this; } - + }; - + ///Function type interface for Dfs algorithm. ///\ingroup search @@ -1082,43 +1082,43 @@ #ifdef DOXYGEN /// \brief Visitor class for dfs. - /// - /// It gives a simple interface for a functional interface for dfs - /// traversal. The traversal on a linear data structure. + /// + /// It gives a simple interface for a functional interface for dfs + /// traversal. The traversal on a linear data structure. template struct DfsVisitor { typedef _Digraph Digraph; typedef typename Digraph::Arc Arc; typedef typename Digraph::Node Node; /// \brief Called when the arc reach a node. - /// + /// /// It is called when the dfs find an arc which target is not /// reached yet. void discover(const Arc& arc) {} /// \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 arc. - /// + /// /// It is called when the dfs should step back on the arc. void backtrack(const Arc& arc) {} /// \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 arc examined but target of the arc + /// \brief Called when the arc examined but target of the arc /// already discovered. - /// - /// It called when the arc examined but the target of the arc + /// + /// It called when the arc examined but the target of the arc /// already discovered. void examine(const Arc& arc) {} /// \brief Called for the source node of the dfs. - /// + /// /// It is called for the source node of the dfs. void start(const Node& 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& node) {} @@ -1140,15 +1140,15 @@ template struct Constraints { void constraints() { - Arc arc; - Node node; - visitor.discover(arc); - visitor.reach(node); - visitor.backtrack(arc); - visitor.leave(node); - visitor.examine(arc); - visitor.start(node); - visitor.stop(arc); + Arc arc; + Node node; + visitor.discover(arc); + visitor.reach(node); + visitor.backtrack(arc); + visitor.leave(node); + visitor.examine(arc); + visitor.start(node); + visitor.stop(arc); } _Visitor& visitor; }; @@ -1162,11 +1162,11 @@ template struct DfsVisitDefaultTraits { - /// \brief The digraph type the algorithm runs on. + /// \brief The digraph type the algorithm runs on. typedef _Digraph Digraph; /// \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 concepts::WriteMap "WriteMap" concept. /// \todo named parameter to set this type, function to read and write. @@ -1174,7 +1174,7 @@ /// \brief Instantiates a ReachedMap. /// - /// This function instantiates a \ref ReachedMap. + /// This function instantiates a \ref ReachedMap. /// \param digraph is the digraph, to which /// we would like to define the \ref ReachedMap. static ReachedMap *createReachedMap(const Digraph &digraph) { @@ -1182,25 +1182,25 @@ } }; - + /// %DFS Visit algorithm class. - + /// \ingroup search /// 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. + /// on every dfs event the \c Visitor class member functions. /// /// \tparam _Digraph The digraph type the algorithm runs on. The default value is /// \ref ListDigraph. The value of _Digraph is not used directly by Dfs, it /// is only passed to \ref DfsDefaultTraits. - /// \tparam _Visitor The Visitor object for the algorithm. The + /// \tparam _Visitor The Visitor object for the algorithm. The /// \ref DfsVisitor "DfsVisitor<_Digraph>" 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. - /// \tparam _Traits Traits class to set various data types used by the + /// \tparam _Traits Traits class to set various data types used by the /// algorithm. The default traits class is /// \ref DfsVisitDefaultTraits "DfsVisitDefaultTraits<_Digraph>". /// See \ref DfsVisitDefaultTraits for the documentation of @@ -1211,21 +1211,21 @@ template #else template , - typename _Traits = DfsDefaultTraits<_Digraph> > + typename _Visitor = DfsVisitor<_Digraph>, + typename _Traits = DfsDefaultTraits<_Digraph> > #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* what() const throw() + virtual const char* what() const throw() { - return "lemon::DfsVisit::UninitializedParameter"; + return "lemon::DfsVisit::UninitializedParameter"; } }; @@ -1262,15 +1262,15 @@ /// Creates the maps if necessary. void create_maps() { if(!_reached) { - local_reached = true; - _reached = Traits::createReachedMap(*_digraph); + local_reached = true; + _reached = Traits::createReachedMap(*_digraph); } } protected: DfsVisit() {} - + public: typedef DfsVisit Create; @@ -1282,22 +1282,22 @@ struct DefReachedMapTraits : public Traits { typedef T ReachedMap; static ReachedMap *createReachedMap(const Digraph &digraph) { - throw UninitializedParameter(); + throw UninitializedParameter(); } }; - /// \brief \ref named-templ-param "Named parameter" for setting + /// \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 DfsVisit< Digraph, Visitor, - DefReachedMapTraits > { + DefReachedMapTraits > { typedef DfsVisit< Digraph, Visitor, DefReachedMapTraits > Create; }; ///@} - public: - + public: + /// \brief Constructor. /// /// Constructor. @@ -1305,10 +1305,10 @@ /// \param digraph the digraph the algorithm will run on. /// \param visitor The visitor of the algorithm. /// - DfsVisit(const Digraph& digraph, Visitor& visitor) + DfsVisit(const Digraph& digraph, Visitor& visitor) : _digraph(&digraph), _visitor(&visitor), - _reached(0), local_reached(false) {} - + _reached(0), local_reached(false) {} + /// \brief Destructor. /// /// Destructor. @@ -1325,8 +1325,8 @@ /// \return (*this) DfsVisit &reachedMap(ReachedMap &m) { if(local_reached) { - delete _reached; - local_reached=false; + delete _reached; + local_reached=false; } _reached = &m; return *this; @@ -1353,28 +1353,28 @@ _stack.resize(countNodes(*_digraph)); _stack_head = -1; for (NodeIt u(*_digraph) ; u != INVALID ; ++u) { - _reached->set(u, false); + _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); - Arc e; - _digraph->firstOut(e, s); - if (e != INVALID) { - _stack[++_stack_head] = e; - } else { - _visitor->leave(s); - } - } + _reached->set(s,true); + _visitor->start(s); + _visitor->reach(s); + Arc e; + _digraph->firstOut(e, s); + if (e != INVALID) { + _stack[++_stack_head] = e; + } else { + _visitor->leave(s); + } + } } - + /// \brief Processes the next arc. /// /// Processes the next arc. @@ -1382,29 +1382,29 @@ /// \return The processed arc. /// /// \pre The stack must not be empty! - Arc processNextArc() { + Arc processNextArc() { Arc e = _stack[_stack_head]; Node m = _digraph->target(e); if(!(*_reached)[m]) { - _visitor->discover(e); - _visitor->reach(m); - _reached->set(m, true); - _digraph->firstOut(_stack[++_stack_head], m); + _visitor->discover(e); + _visitor->reach(m); + _reached->set(m, true); + _digraph->firstOut(_stack[++_stack_head], m); } else { - _visitor->examine(e); - m = _digraph->source(e); - _digraph->nextOut(_stack[_stack_head]); + _visitor->examine(e); + m = _digraph->source(e); + _digraph->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 = _digraph->source(_stack[_stack_head]); - _digraph->nextOut(_stack[_stack_head]); - } else { - _visitor->stop(m); - } + _visitor->leave(m); + --_stack_head; + if (_stack_head >= 0) { + _visitor->backtrack(_stack[_stack_head]); + m = _digraph->source(_stack[_stack_head]); + _digraph->nextOut(_stack[_stack_head]); + } else { + _visitor->stop(m); + } } return e; } @@ -1415,7 +1415,7 @@ /// /// \return The next arc to be processed or INVALID if the stack is /// empty. - Arc nextArc() { + Arc nextArc() { return _stack_head >= 0 ? _stack[_stack_head] : INVALID; } @@ -1430,7 +1430,7 @@ /// /// Returns the number of the nodes to be processed in the queue. int queueSize() { return _stack_head + 1; } - + /// \brief Executes the algorithm. /// /// Executes the algorithm. @@ -1440,7 +1440,7 @@ void start() { while ( !emptyQueue() ) processNextArc(); } - + /// \brief Executes the algorithm until \c dest is reached. /// /// Executes the algorithm until \c dest is reached. @@ -1448,10 +1448,10 @@ /// \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() && _digraph->target(_stack[_stack_head]) != dest ) - processNextArc(); + while ( !emptyQueue() && _digraph->target(_stack[_stack_head]) != dest ) + processNextArc(); } - + /// \brief Executes the algorithm until a condition is met. /// /// Executes the algorithm until a condition is met. @@ -1490,7 +1490,7 @@ } /// \brief Runs %DFSVisit algorithm to visit all nodes in the digraph. - + /// This method runs the %DFS algorithm in order to /// compute the %DFS path to each node. The algorithm computes /// - The %DFS tree.