diff --git a/lemon/bfs.h b/lemon/bfs.h --- a/lemon/bfs.h +++ b/lemon/bfs.h @@ -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 @@ -33,7 +33,7 @@ namespace lemon { - + ///Default traits class of Bfs class. ///Default traits class of Bfs class. @@ -41,34 +41,34 @@ template struct BfsDefaultTraits { - ///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 shortest paths. - /// + /// ///The type of the map that stores the last ///arcs of the shortest 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 @@ -80,14 +80,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) @@ -95,23 +95,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); } }; - + ///%BFS algorithm class. - + ///\ingroup search ///This class provides an efficient implementation of the %BFS algorithm. /// @@ -126,10 +126,10 @@ #ifdef DOXYGEN template + typename TR> #else template > + typename TR=BfsDefaultTraits > #endif class Bfs { public: @@ -142,14 +142,14 @@ class UninitializedParameter : public lemon::UninitializedParameter { public: virtual const char* what() const throw() { - return "lemon::Bfs::UninitializedParameter"; + return "lemon::Bfs::UninitializedParameter"; } }; typedef TR Traits; ///The type of the underlying digraph. typedef typename TR::Digraph Digraph; - + ///\brief The type of the map that stores the last ///arcs of the shortest paths. typedef typename TR::PredMap PredMap; @@ -190,34 +190,34 @@ int _curr_dist; ///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: - + Bfs() {} - + public: - + typedef Bfs Create; ///\name Named template parameters @@ -227,9 +227,9 @@ template struct DefPredMapTraits : public Traits { typedef T PredMap; - static PredMap *createPredMap(const Digraph &) + static PredMap *createPredMap(const Digraph &) { - throw UninitializedParameter(); + throw UninitializedParameter(); } }; ///\brief \ref named-templ-param "Named parameter" for setting @@ -238,16 +238,16 @@ ///\ref named-templ-param "Named parameter" for setting PredMap type /// template - struct DefPredMap : public Bfs< Digraph, DefPredMapTraits > { + struct DefPredMap : public Bfs< Digraph, DefPredMapTraits > { typedef Bfs< Digraph, DefPredMapTraits > 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 @@ -256,16 +256,16 @@ ///\ref named-templ-param "Named parameter" for setting DistMap type /// template - struct DefDistMap : public Bfs< Digraph, DefDistMapTraits > { + struct DefDistMap : public Bfs< Digraph, DefDistMapTraits > { typedef Bfs< Digraph, DefDistMapTraits > 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 @@ -274,16 +274,16 @@ ///\ref named-templ-param "Named parameter" for setting ReachedMap type /// template - struct DefReachedMap : public Bfs< Digraph, DefReachedMapTraits > { + struct DefReachedMap : public Bfs< Digraph, DefReachedMapTraits > { typedef Bfs< Digraph, DefReachedMapTraits > Create; }; - + 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,12 +295,12 @@ struct DefProcessedMap : public Bfs< Digraph, DefProcessedMapTraits > { typedef Bfs< 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" @@ -311,16 +311,16 @@ ///If you don't set it explicitly, it will be automatically allocated. template struct DefProcessedMapToBeDefaultMap : - public Bfs< Digraph, DefDigraphProcessedMapTraits> { + public Bfs< Digraph, DefDigraphProcessedMapTraits> { typedef Bfs< Digraph, DefDigraphProcessedMapTraits> Create; }; - + ///@} - public: - + public: + ///Constructor. - + ///\param _G the digraph the algorithm will run on. /// Bfs(const Digraph& _G) : @@ -330,9 +330,9 @@ _reached(NULL), local_reached(false), _processed(NULL), local_processed(false) { } - + ///Destructor. - ~Bfs() + ~Bfs() { if(local_pred) delete _pred; if(local_dist) delete _dist; @@ -347,11 +347,11 @@ ///it will allocate one. The destructor deallocates this ///automatically allocated map, of course. ///\return (*this) - Bfs &predMap(PredMap &m) + Bfs &predMap(PredMap &m) { if(local_pred) { - delete _pred; - local_pred=false; + delete _pred; + local_pred=false; } _pred = &m; return *this; @@ -364,11 +364,11 @@ ///it will allocate one. The destructor deallocates this ///automatically allocated map, of course. ///\return (*this) - Bfs &reachedMap(ReachedMap &m) + Bfs &reachedMap(ReachedMap &m) { if(local_reached) { - delete _reached; - local_reached=false; + delete _reached; + local_reached=false; } _reached = &m; return *this; @@ -381,11 +381,11 @@ ///it will allocate one. The destructor deallocates this ///automatically allocated map, of course. ///\return (*this) - Bfs &processedMap(ProcessedMap &m) + Bfs &processedMap(ProcessedMap &m) { if(local_processed) { - delete _processed; - local_processed=false; + delete _processed; + local_processed=false; } _processed = &m; return *this; @@ -398,11 +398,11 @@ ///it will allocate one. The destructor deallocates this ///automatically allocated map, of course. ///\return (*this) - Bfs &distMap(DistMap &m) + Bfs &distMap(DistMap &m) { if(local_dist) { - delete _dist; - local_dist=false; + delete _dist; + local_dist=false; } _dist = &m; return *this; @@ -432,12 +432,12 @@ _queue_head=_queue_tail=0; _curr_dist=1; for ( NodeIt u(*G) ; u!=INVALID ; ++u ) { - _pred->set(u,INVALID); - _reached->set(u,false); - _processed->set(u,false); + _pred->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. @@ -445,15 +445,15 @@ void addSource(Node s) { if(!(*_reached)[s]) - { - _reached->set(s,true); - _pred->set(s,INVALID); - _dist->set(s,0); - _queue[_queue_head++]=s; - _queue_next_dist=_queue_head; - } + { + _reached->set(s,true); + _pred->set(s,INVALID); + _dist->set(s,0); + _queue[_queue_head++]=s; + _queue_next_dist=_queue_head; + } } - + ///Processes the next node. ///Processes the next node. @@ -464,19 +464,19 @@ Node processNextNode() { if(_queue_tail==_queue_next_dist) { - _curr_dist++; - _queue_next_dist=_queue_head; + _curr_dist++; + _queue_next_dist=_queue_head; } Node n=_queue[_queue_tail++]; _processed->set(n,true); Node m; for(OutArcIt e(*G,n);e!=INVALID;++e) - if(!(*_reached)[m=G->target(e)]) { - _queue[_queue_head++]=m; - _reached->set(m,true); - _pred->set(m,e); - _dist->set(m,_curr_dist); - } + if(!(*_reached)[m=G->target(e)]) { + _queue[_queue_head++]=m; + _reached->set(m,true); + _pred->set(m,e); + _dist->set(m,_curr_dist); + } return n; } @@ -495,20 +495,20 @@ Node processNextNode(Node target, bool& reach) { if(_queue_tail==_queue_next_dist) { - _curr_dist++; - _queue_next_dist=_queue_head; + _curr_dist++; + _queue_next_dist=_queue_head; } Node n=_queue[_queue_tail++]; _processed->set(n,true); Node m; for(OutArcIt e(*G,n);e!=INVALID;++e) - if(!(*_reached)[m=G->target(e)]) { - _queue[_queue_head++]=m; - _reached->set(m,true); - _pred->set(m,e); - _dist->set(m,_curr_dist); + if(!(*_reached)[m=G->target(e)]) { + _queue[_queue_head++]=m; + _reached->set(m,true); + _pred->set(m,e); + _dist->set(m,_curr_dist); reach = reach || (target == m); - } + } return n; } @@ -528,23 +528,23 @@ Node processNextNode(const NM& nm, Node& rnode) { if(_queue_tail==_queue_next_dist) { - _curr_dist++; - _queue_next_dist=_queue_head; + _curr_dist++; + _queue_next_dist=_queue_head; } Node n=_queue[_queue_tail++]; _processed->set(n,true); Node m; for(OutArcIt e(*G,n);e!=INVALID;++e) - if(!(*_reached)[m=G->target(e)]) { - _queue[_queue_head++]=m; - _reached->set(m,true); - _pred->set(m,e); - _dist->set(m,_curr_dist); - if (nm[m] && rnode == INVALID) rnode = m; - } + if(!(*_reached)[m=G->target(e)]) { + _queue[_queue_head++]=m; + _reached->set(m,true); + _pred->set(m,e); + _dist->set(m,_curr_dist); + if (nm[m] && rnode == INVALID) rnode = m; + } return n; } - + ///Next node to be processed. ///Next node to be processed. @@ -552,10 +552,10 @@ ///\return The next node to be processed or INVALID if the queue is /// empty. Node nextNode() - { + { return _queue_tail<_queue_head?_queue[_queue_tail]:INVALID; } - + ///\brief Returns \c false if there are nodes ///to be processed in the queue /// @@ -563,10 +563,10 @@ ///to be processed in the queue bool emptyQueue() { return _queue_tail==_queue_head; } ///Returns the number of the nodes to be processed. - + ///Returns the number of the nodes to be processed in the queue. int queueSize() { return _queue_head-_queue_tail; } - + ///Executes the algorithm. ///Executes the algorithm. @@ -584,7 +584,7 @@ { while ( !emptyQueue() ) processNextNode(); } - + ///Executes the algorithm until \c dest is reached. ///Executes the algorithm until \c dest is reached. @@ -602,7 +602,7 @@ bool reach = false; while ( !emptyQueue() && !reach ) processNextNode(dest, reach); } - + ///Executes the algorithm until a condition is met. ///Executes the algorithm until a condition is met. @@ -621,13 +621,13 @@ { Node rnode = INVALID; while ( !emptyQueue() && rnode == INVALID ) { - processNextNode(nm, rnode); + processNextNode(nm, rnode); } return rnode; } - + ///Runs %BFS algorithm from node \c s. - + ///This method runs the %BFS algorithm from a root node \c s ///in order to ///compute the @@ -646,9 +646,9 @@ addSource(s); start(); } - + ///Finds the shortest path between \c s and \c t. - + ///Finds the shortest path between \c s and \c t. /// ///\return The length of the shortest s---t path if there exists one, @@ -666,7 +666,7 @@ start(t); return reached(t) ? _curr_dist : 0; } - + ///@} ///\name Query Functions @@ -674,16 +674,16 @@ ///functions.\n ///Before the use of these functions, ///either run() or start() must be calleb. - + ///@{ 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); } @@ -722,15 +722,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 shortest path tree map. ///Returns a reference to the NodeMap of the arcs of the @@ -738,7 +738,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. @@ -747,7 +747,7 @@ ///must be called before using this function. /// bool reached(Node v) { return (*_reached)[v]; } - + ///@} }; @@ -758,39 +758,39 @@ template struct BfsWizardDefaultTraits { - ///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 shortest paths. - /// + /// ///The type of the map that stores the last ///arcs of the shortest 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 @@ -802,14 +802,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) @@ -817,14 +817,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) @@ -835,7 +835,7 @@ return new DistMap(); } }; - + /// Default traits used by \ref BfsWizard /// To make it easier to use Bfs algorithm @@ -865,28 +865,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). BfsWizardBase() : _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 BfsWizardBase(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 Bfs algorithm easier /// This class is created to make it easier to use Bfs algorithm. @@ -921,7 +921,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; @@ -951,7 +951,7 @@ ~BfsWizard() {} ///Runs Bfs algorithm from a given node. - + ///Runs Bfs algorithm from a given node. ///The node can be given by the \ref source function. void run() @@ -959,12 +959,12 @@ if(Base::_source==INVALID) throw UninitializedParameter(); Bfs alg(*reinterpret_cast(Base::_g)); if(Base::_reached) - alg.reachedMap(*reinterpret_cast(Base::_reached)); - if(Base::_processed) + alg.reachedMap(*reinterpret_cast(Base::_reached)); + 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); } @@ -985,7 +985,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 /// @@ -993,20 +993,20 @@ ///function for setting PredMap /// template - BfsWizard > predMap(const T &t) + BfsWizard > predMap(const T &t) { Base::_pred=reinterpret_cast(const_cast(&t)); return BfsWizard >(*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 /// @@ -1014,12 +1014,12 @@ ///function for setting ReachedMap /// template - BfsWizard > reachedMap(const T &t) + BfsWizard > reachedMap(const T &t) { Base::_reached=reinterpret_cast(const_cast(&t)); return BfsWizard >(*this); } - + template struct DefProcessedMapBase : public Base { @@ -1027,7 +1027,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 /// @@ -1035,20 +1035,20 @@ ///function for setting ProcessedMap /// template - BfsWizard > processedMap(const T &t) + BfsWizard > processedMap(const T &t) { Base::_processed=reinterpret_cast(const_cast(&t)); return BfsWizard >(*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 /// @@ -1056,24 +1056,24 @@ ///function for setting DistMap type /// template - BfsWizard > distMap(const T &t) + BfsWizard > distMap(const T &t) { Base::_dist=reinterpret_cast(const_cast(&t)); return BfsWizard >(*this); } - + /// Sets the source node, from which the Bfs algorithm runs. /// Sets the source node, from which the Bfs algorithm runs. /// \param s is the source node. - BfsWizard &source(Node s) + BfsWizard &source(Node s) { Base::_source=s; return *this; } - + }; - + ///Function type interface for Bfs algorithm. /// \ingroup search @@ -1100,7 +1100,7 @@ #ifdef DOXYGEN /// \brief Visitor class for bfs. - /// + /// /// This class defines the interface of the BfsVisit events, and /// it could be the base of a real Visitor class. template @@ -1109,26 +1109,26 @@ typedef typename Digraph::Arc Arc; typedef typename Digraph::Node Node; /// \brief Called when the arc reach a node. - /// + /// /// It is called when the bfs 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 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 bfs. - /// + /// /// It is called for the source node of the bfs. void start(const Node& node) {} /// \brief Called when the node processed. - /// + /// /// It is Called when the node processed. void process(const Node& node) {} }; @@ -1147,12 +1147,12 @@ template struct Constraints { void constraints() { - Arc arc; - Node node; - visitor.discover(arc); - visitor.reach(node); - visitor.examine(arc); - visitor.start(node); + Arc arc; + Node node; + visitor.discover(arc); + visitor.reach(node); + visitor.examine(arc); + visitor.start(node); visitor.process(node); } _Visitor& visitor; @@ -1167,11 +1167,11 @@ template struct BfsVisitDefaultTraits { - /// \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. @@ -1179,7 +1179,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) { @@ -1189,24 +1189,24 @@ }; /// \ingroup search - /// + /// /// \brief %BFS Visit algorithm class. - /// + /// /// This class provides an efficient implementation of the %BFS algorithm /// with visitor interface. /// /// The %BfsVisit class provides an alternative interface to the Bfs /// class. It works with callback mechanism, the BfsVisit object calls - /// on every bfs event the \c Visitor class member functions. + /// on every bfs 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 Bfs, it /// is only passed to \ref BfsDefaultTraits. - /// \tparam _Visitor The Visitor object for the algorithm. The + /// \tparam _Visitor The Visitor object for the algorithm. The /// \ref BfsVisitor "BfsVisitor<_Digraph>" is an empty Visitor which /// does not observe the Bfs events. If you want to observe the bfs /// 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 BfsVisitDefaultTraits "BfsVisitDefaultTraits<_Digraph>". /// See \ref BfsVisitDefaultTraits for the documentation of @@ -1215,21 +1215,21 @@ template #else template , - typename _Traits = BfsDefaultTraits<_Digraph> > + typename _Visitor = BfsVisitor<_Digraph>, + typename _Traits = BfsDefaultTraits<_Digraph> > #endif class BfsVisit { 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::BfsVisit::UninitializedParameter"; + return "lemon::BfsVisit::UninitializedParameter"; } }; @@ -1266,15 +1266,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: BfsVisit() {} - + public: typedef BfsVisit Create; @@ -1286,22 +1286,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 BfsVisit< Digraph, Visitor, - DefReachedMapTraits > { + DefReachedMapTraits > { typedef BfsVisit< Digraph, Visitor, DefReachedMapTraits > Create; }; ///@} - public: - + public: + /// \brief Constructor. /// /// Constructor. @@ -1309,10 +1309,10 @@ /// \param digraph the digraph the algorithm will run on. /// \param visitor The visitor of the algorithm. /// - BfsVisit(const Digraph& digraph, Visitor& visitor) + BfsVisit(const Digraph& digraph, Visitor& visitor) : _digraph(&digraph), _visitor(&visitor), - _reached(0), local_reached(false) {} - + _reached(0), local_reached(false) {} + /// \brief Destructor. /// /// Destructor. @@ -1329,8 +1329,8 @@ /// \return (*this) BfsVisit &reachedMap(ReachedMap &m) { if(local_reached) { - delete _reached; - local_reached = false; + delete _reached; + local_reached = false; } _reached = &m; return *this; @@ -1357,22 +1357,22 @@ _list.resize(countNodes(*_digraph)); _list_front = _list_back = -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); + _reached->set(s,true); + _visitor->start(s); + _visitor->reach(s); _list[++_list_back] = s; - } + } } - + /// \brief Processes the next node. /// /// Processes the next node. @@ -1380,7 +1380,7 @@ /// \return The processed node. /// /// \pre The queue must not be empty! - Node processNextNode() { + Node processNextNode() { Node n = _list[++_list_front]; _visitor->process(n); Arc e; @@ -1467,7 +1467,7 @@ /// /// \return The next node to be processed or INVALID if the stack is /// empty. - Node nextNode() { + Node nextNode() { return _list_front != _list_back ? _list[_list_front + 1] : INVALID; } @@ -1482,7 +1482,7 @@ /// /// Returns the number of the nodes to be processed in the queue. int queueSize() { return _list_back - _list_front; } - + /// \brief Executes the algorithm. /// /// Executes the algorithm. @@ -1492,7 +1492,7 @@ void start() { while ( !emptyQueue() ) processNextNode(); } - + /// \brief Executes the algorithm until \c dest is reached. /// /// Executes the algorithm until \c dest is reached. @@ -1503,7 +1503,7 @@ bool reach = false; while ( !emptyQueue() && !reach ) processNextNode(dest, reach); } - + /// \brief Executes the algorithm until a condition is met. /// /// Executes the algorithm until a condition is met. @@ -1521,7 +1521,7 @@ Node start(const NM &nm) { Node rnode = INVALID; while ( !emptyQueue() && rnode == INVALID ) { - processNextNode(nm, rnode); + processNextNode(nm, rnode); } return rnode; } @@ -1542,7 +1542,7 @@ } /// \brief Runs %BFSVisit algorithm to visit all nodes in the digraph. - /// + /// /// This method runs the %BFS algorithm in order to /// compute the %BFS path to each node. The algorithm computes /// - The %BFS tree.