Context Navigation

← Previous Change
Next Change →

Changeset 209:765619b7cbb2 in lemon-main for lemon/bfs.h

Timestamp:

07/13/08 20:51:02 (16 years ago)

Author:

Alpar Juttner <alpar@…>

Branch:

default

Phase:

public

Message:

Apply unify-sources.sh to the source tree

File:

: 1 edited

lemon/bfs.h (modified) (92 diffs)

Legend:

: Unmodified
: Added
: Removed

lemon/bfs.h

-                      r158
+                      r209
 /* -*- 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
 …
   ///Default traits class of Bfs class.
 …
   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.
 …
     typedef typename Digraph::template NodeMap<typename GR::Arc> 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.
 …
     typedef NullMap<typename Digraph::Node,bool> 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
 …
+    }
     ///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.
 …
     typedef typename Digraph::template NodeMap<bool> 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.
 …
+    }
     ///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<int> 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)
 …
+    }
   };
   ///%BFS algorithm class.
   ///\ingroup search
   ///This class provides an efficient implementation of the %BFS algorithm.
 …
 #ifdef DOXYGEN
   template <typename GR,
             typename TR>
+            typename TR>
 #else
   template <typename GR=ListDigraph,
             typename TR=BfsDefaultTraits<GR> >
+            typename TR=BfsDefaultTraits<GR> >
 #endif
   class Bfs {
 …
     public:
       virtual const char* what() const throw() {
         return "lemon::Bfs::UninitializedParameter";
+        return "lemon::Bfs::UninitializedParameter";
+      }
     };
 …
     ///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.
 …
     ///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;
 …
     struct DefPredMapTraits : public Traits {
       typedef T PredMap;
       static PredMap *createPredMap(const Digraph &)
+      static PredMap *createPredMap(const Digraph &)
+      {
         throw UninitializedParameter();
+        throw UninitializedParameter();
+      }
     };
 …
     ///
     template <class T>
     struct DefPredMap : public Bfs< Digraph, DefPredMapTraits<T> > {
+    struct DefPredMap : public Bfs< Digraph, DefPredMapTraits<T> > {
       typedef Bfs< Digraph, DefPredMapTraits<T> > Create;
     };
     template <class T>
     struct DefDistMapTraits : public Traits {
       typedef T DistMap;
       static DistMap *createDistMap(const Digraph &)
+      static DistMap *createDistMap(const Digraph &)
+      {
         throw UninitializedParameter();
+        throw UninitializedParameter();
+      }
     };
 …
     ///
     template <class T>
     struct DefDistMap : public Bfs< Digraph, DefDistMapTraits<T> > {
+    struct DefDistMap : public Bfs< Digraph, DefDistMapTraits<T> > {
       typedef Bfs< Digraph, DefDistMapTraits<T> > Create;
     };
     template <class T>
     struct DefReachedMapTraits : public Traits {
       typedef T ReachedMap;
       static ReachedMap *createReachedMap(const Digraph &)
+      static ReachedMap *createReachedMap(const Digraph &)
+      {
         throw UninitializedParameter();
+        throw UninitializedParameter();
+      }
     };
 …
     ///
     template <class T>
     struct DefReachedMap : public Bfs< Digraph, DefReachedMapTraits<T> > {
+    struct DefReachedMap : public Bfs< Digraph, DefReachedMapTraits<T> > {
       typedef Bfs< Digraph, DefReachedMapTraits<T> > Create;
     };
     template <class T>
     struct DefProcessedMapTraits : public Traits {
       typedef T ProcessedMap;
       static ProcessedMap *createProcessedMap(const Digraph &)
+      static ProcessedMap *createProcessedMap(const Digraph &)
+      {
         throw UninitializedParameter();
+        throw UninitializedParameter();
+      }
     };
 …
       typedef Bfs< Digraph, DefProcessedMapTraits<T> > Create;
     };
     struct DefDigraphProcessedMapTraits : public Traits {
       typedef typename Digraph::template NodeMap<bool> ProcessedMap;
       static ProcessedMap *createProcessedMap(const Digraph &G)
+      static ProcessedMap *createProcessedMap(const Digraph &G)
+      {
         return new ProcessedMap(G);
+        return new ProcessedMap(G);
+      }
     };
 …
     template <class T>
     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.
     ///
 …
       _processed(NULL), local_processed(false)
     { }
     ///Destructor.
     ~Bfs()
+    ~Bfs()
+    {
       if(local_pred) delete _pred;
 …
     ///automatically allocated map, of course.
     ///\return <tt> (*this) </tt>
     Bfs &predMap(PredMap &m)
+    Bfs &predMap(PredMap &m)
+    {
       if(local_pred) {
         delete _pred;
         local_pred=false;
+        delete _pred;
+        local_pred=false;
+      }
       _pred = &m;
 …
     ///automatically allocated map, of course.
     ///\return <tt> (*this) </tt>
     Bfs &reachedMap(ReachedMap &m)
+    Bfs &reachedMap(ReachedMap &m)
+    {
       if(local_reached) {
         delete _reached;
         local_reached=false;
+        delete _reached;
+        local_reached=false;
+      }
       _reached = &m;
 …
     ///automatically allocated map, of course.
     ///\return <tt> (*this) </tt>
     Bfs &processedMap(ProcessedMap &m)
+    Bfs &processedMap(ProcessedMap &m)
+    {
       if(local_processed) {
         delete _processed;
         local_processed=false;
+        delete _processed;
+        local_processed=false;
+      }
       _processed = &m;
 …
     ///automatically allocated map, of course.
     ///\return <tt> (*this) </tt>
     Bfs &distMap(DistMap &m)
+    Bfs &distMap(DistMap &m)
+    {
       if(local_dist) {
         delete _dist;
         local_dist=false;
+        delete _dist;
+        local_dist=false;
+      }
       _dist = &m;
 …
       _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.
 …
+    {
       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.
 …
+    {
       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++];
 …
       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;
+    }
 …
+    {
       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++];
 …
       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;
+    }
 …
+    {
       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++];
 …
       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.
 …
     /// 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
 …
     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.
 …
       while ( !emptyQueue() ) processNextNode();
+    }
     ///Executes the algorithm until \c dest is reached.
 …
       while ( !emptyQueue() && !reach ) processNextNode(dest, reach);
+    }
     ///Executes the algorithm until a condition is met.
 …
       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
 …
       start();
+    }
     ///Finds the shortest path between \c s and \c t.
     ///Finds the shortest path between \c s and \c t.
     ///
 …
       return reached(t) ? _curr_dist : 0;
+    }
     ///@}
 …
     ///Before the use of these functions,
     ///either run() or start() must be calleb.
     ///@{
 …
     ///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);
 …
     ///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.
 …
     ///be called before using this function.
     const DistMap &distMap() const { return *_dist;}
     ///Returns a reference to the shortest path tree map.
 …
     ///must be called before using this function.
     const PredMap &predMap() const { return *_pred;}
     ///Checks if a node is reachable from the root.
 …
     ///
     bool reached(Node v) { return (*_reached)[v]; }
     ///@}
   };
 …
   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.
 …
     typedef NullMap<typename Digraph::Node,typename GR::Arc> 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
+    {
 …
     ///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.
 …
     typedef NullMap<typename Digraph::Node,bool> 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
 …
+    }
     ///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.
 …
     typedef typename Digraph::template NodeMap<bool> 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.
 …
+    }
     ///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<typename Digraph::Node,int> 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
 …
+    }
   };
   /// Default traits used by \ref BfsWizard
 …
     ///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.
 …
     /// \param s is the initial value of  \ref _source
     BfsWizardBase(const GR &g, Node s=INVALID) :
       _g(reinterpret_cast<void*>(const_cast<GR*>(&g))),
+      _g(reinterpret_cast<void*>(const_cast<GR*>(&g))),
       _reached(0), _processed(0), _pred(0), _dist(0), _source(s) {}
   };
   /// A class to make the usage of Bfs algorithm easier
 …
     //\e
     typedef typename Digraph::OutArcIt OutArcIt;
     ///\brief The type of the map that stores
     ///the reached nodes
 …
     ///Runs Bfs algorithm from a given node.
     ///Runs Bfs algorithm from a given node.
     ///The node can be given by the \ref source function.
 …
       Bfs<Digraph,TR> alg(*reinterpret_cast<const Digraph*>(Base::_g));
       if(Base::_reached)
         alg.reachedMap(*reinterpret_cast<ReachedMap*>(Base::_reached));
       if(Base::_processed)
+        alg.reachedMap(*reinterpret_cast<ReachedMap*>(Base::_reached));
+      if(Base::_processed)
         alg.processedMap(*reinterpret_cast<ProcessedMap*>(Base::_processed));
       if(Base::_pred)
+      if(Base::_pred)
         alg.predMap(*reinterpret_cast<PredMap*>(Base::_pred));
       if(Base::_dist)
+      if(Base::_dist)
         alg.distMap(*reinterpret_cast<DistMap*>(Base::_dist));
       alg.run(Base::_source);
 …
       DefPredMapBase(const TR &b) : TR(b) {}
     };
     ///\brief \ref named-templ-param "Named parameter"
     ///function for setting PredMap
 …
     ///
     template<class T>
     BfsWizard<DefPredMapBase<T> > predMap(const T &t)
+    BfsWizard<DefPredMapBase<T> > predMap(const T &t)
+    {
       Base::_pred=reinterpret_cast<void*>(const_cast<T*>(&t));
       return BfsWizard<DefPredMapBase<T> >(*this);
+    }
     template<class T>
     struct DefReachedMapBase : public Base {
 …
       DefReachedMapBase(const TR &b) : TR(b) {}
     };
     ///\brief \ref named-templ-param "Named parameter"
     ///function for setting ReachedMap
 …
     ///
     template<class T>
     BfsWizard<DefReachedMapBase<T> > reachedMap(const T &t)
+    BfsWizard<DefReachedMapBase<T> > reachedMap(const T &t)
+    {
       Base::_reached=reinterpret_cast<void*>(const_cast<T*>(&t));
       return BfsWizard<DefReachedMapBase<T> >(*this);
+    }
     template<class T>
 …
       DefProcessedMapBase(const TR &b) : TR(b) {}
     };
     ///\brief \ref named-templ-param "Named parameter"
     ///function for setting ProcessedMap
 …
     ///
     template<class T>
     BfsWizard<DefProcessedMapBase<T> > processedMap(const T &t)
+    BfsWizard<DefProcessedMapBase<T> > processedMap(const T &t)
+    {
       Base::_processed=reinterpret_cast<void*>(const_cast<T*>(&t));
       return BfsWizard<DefProcessedMapBase<T> >(*this);
+    }
     template<class T>
     struct DefDistMapBase : public Base {
 …
       DefDistMapBase(const TR &b) : TR(b) {}
     };
     ///\brief \ref named-templ-param "Named parameter"
     ///function for setting DistMap type
 …
     ///
     template<class T>
     BfsWizard<DefDistMapBase<T> > distMap(const T &t)
+    BfsWizard<DefDistMapBase<T> > distMap(const T &t)
+    {
       Base::_dist=reinterpret_cast<void*>(const_cast<T*>(&t));
       return BfsWizard<DefDistMapBase<T> >(*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<TR> &source(Node s)
+    BfsWizard<TR> &source(Node s)
+    {
       Base::_source=s;
       return *this;
+    }
   };
   ///Function type interface for Bfs algorithm.
 …
 #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.
 …
     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) {}
 …
     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);
+      }
 …
   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.
 …
     /// \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.
 …
   /// \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>".
 …
 #else
   template <typename _Digraph = ListDigraph,
             typename _Visitor = BfsVisitor<_Digraph>,
             typename _Traits = BfsDefaultTraits<_Digraph> >
+            typename _Visitor = BfsVisitor<_Digraph>,
+            typename _Traits = BfsDefaultTraits<_Digraph> >
 #endif
   class BfsVisit {
   public:
     /// \brief \ref Exception for uninitialized parameters.
     ///
 …
     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";
+      }
     };
 …
     void create_maps() {
       if(!_reached) {
         local_reached = true;
         _reached = Traits::createReachedMap(*_digraph);
+        local_reached = true;
+        _reached = Traits::createReachedMap(*_digraph);
+      }
+    }
 …
     BfsVisit() {}
   public:
 …
       typedef T ReachedMap;
       static ReachedMap *createReachedMap(const Digraph &digraph) {
         throw UninitializedParameter();
+      }
     };
     /// \brief \ref named-templ-param "Named parameter" for setting
+        throw UninitializedParameter();
+      }
+    };
+    /// \brief \ref named-templ-param "Named parameter" for setting
     /// ReachedMap type
     ///
 …
     template <class T>
     struct DefReachedMap : public BfsVisit< Digraph, Visitor,
                                             DefReachedMapTraits<T> > {
+                                            DefReachedMapTraits<T> > {
       typedef BfsVisit< Digraph, Visitor, DefReachedMapTraits<T> > Create;
     };
     ///@}
   public:
+  public:
     /// \brief Constructor.
     ///
 …
     /// \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.
     ///
 …
     BfsVisit &reachedMap(ReachedMap &m) {
       if(local_reached) {
         delete _reached;
         local_reached = false;
+        delete _reached;
+        local_reached = false;
+      }
       _reached = &m;
 …
       _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.
     ///
 …
     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.
     ///
 …
     ///
     /// \pre The queue must not be empty!
     Node processNextNode() {
+    Node processNextNode() {
       Node n = _list[++_list_front];
       _visitor->process(n);
 …
     /// \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;
+    }
 …
     /// Returns the number of the nodes to be processed in the queue.
     int queueSize() { return _list_back - _list_front; }
     /// \brief Executes the algorithm.
     ///
 …
       while ( !emptyQueue() ) processNextNode();
+    }
     /// \brief Executes the algorithm until \c dest is reached.
     ///
 …
       while ( !emptyQueue() && !reach ) processNextNode(dest, reach);
+    }
     /// \brief Executes the algorithm until a condition is met.
     ///
 …
       Node rnode = INVALID;
       while ( !emptyQueue() && rnode == INVALID ) {
         processNextNode(nm, rnode);
+        processNextNode(nm, rnode);
+      }
       return rnode;
 …
     /// \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

Note: See TracChangeset for help on using the changeset viewer.

Context Navigation

Changeset 209:765619b7cbb2 in lemon-main for lemon/bfs.h

Legend:

lemon/bfs.h

Download in other formats: