lemon/bfs.h
changeset 408 69f33ef03334
parent 329 d900fd1e760f
child 420 6a2a33ad261b
equal deleted inserted replaced
20:c88fa5670f29 21:cba8485be580
    49     ///arcs of the shortest paths.
    49     ///arcs of the shortest paths.
    50     ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
    50     ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
    51     typedef typename Digraph::template NodeMap<typename Digraph::Arc> PredMap;
    51     typedef typename Digraph::template NodeMap<typename Digraph::Arc> PredMap;
    52     ///Instantiates a PredMap.
    52     ///Instantiates a PredMap.
    53 
    53 
    54     ///This function instantiates a PredMap.  
    54     ///This function instantiates a PredMap.
    55     ///\param g is the digraph, to which we would like to define the
    55     ///\param g is the digraph, to which we would like to define the
    56     ///PredMap.
    56     ///PredMap.
    57     static PredMap *createPredMap(const Digraph &g)
    57     static PredMap *createPredMap(const Digraph &g)
    58     {
    58     {
    59       return new PredMap(g);
    59       return new PredMap(g);
    78       return new ProcessedMap();
    78       return new ProcessedMap();
    79     }
    79     }
    80 
    80 
    81     ///The type of the map that indicates which nodes are reached.
    81     ///The type of the map that indicates which nodes are reached.
    82 
    82 
    83     ///The type of the map that indicates which nodes are reached.///It must meet the \ref concepts::ReadWriteMap "ReadWriteMap" concept.
    83     ///The type of the map that indicates which nodes are reached.
       
    84     ///It must meet the \ref concepts::ReadWriteMap "ReadWriteMap" concept.
    84     typedef typename Digraph::template NodeMap<bool> ReachedMap;
    85     typedef typename Digraph::template NodeMap<bool> ReachedMap;
    85     ///Instantiates a ReachedMap.
    86     ///Instantiates a ReachedMap.
    86 
    87 
    87     ///This function instantiates a ReachedMap.
    88     ///This function instantiates a ReachedMap.
    88     ///\param g is the digraph, to which
    89     ///\param g is the digraph, to which
   116   ///There is also a \ref bfs() "function-type interface" for the BFS
   117   ///There is also a \ref bfs() "function-type interface" for the BFS
   117   ///algorithm, which is convenient in the simplier cases and it can be
   118   ///algorithm, which is convenient in the simplier cases and it can be
   118   ///used easier.
   119   ///used easier.
   119   ///
   120   ///
   120   ///\tparam GR The type of the digraph the algorithm runs on.
   121   ///\tparam GR The type of the digraph the algorithm runs on.
   121   ///The default value is \ref ListDigraph. The value of GR is not used
   122   ///The default type is \ref ListDigraph.
   122   ///directly by \ref Bfs, it is only passed to \ref BfsDefaultTraits.
       
   123   ///\tparam TR Traits class to set various data types used by the algorithm.
       
   124   ///The default traits class is
       
   125   ///\ref BfsDefaultTraits "BfsDefaultTraits<GR>".
       
   126   ///See \ref BfsDefaultTraits for the documentation of
       
   127   ///a Bfs traits class.
       
   128 #ifdef DOXYGEN
   123 #ifdef DOXYGEN
   129   template <typename GR,
   124   template <typename GR,
   130             typename TR>
   125             typename TR>
   131 #else
   126 #else
   132   template <typename GR=ListDigraph,
   127   template <typename GR=ListDigraph,
   148     ///The type of the map that indicates which nodes are processed.
   143     ///The type of the map that indicates which nodes are processed.
   149     typedef typename TR::ProcessedMap ProcessedMap;
   144     typedef typename TR::ProcessedMap ProcessedMap;
   150     ///The type of the paths.
   145     ///The type of the paths.
   151     typedef PredMapPath<Digraph, PredMap> Path;
   146     typedef PredMapPath<Digraph, PredMap> Path;
   152 
   147 
   153     ///The traits class.
   148     ///The \ref BfsDefaultTraits "traits class" of the algorithm.
   154     typedef TR Traits;
   149     typedef TR Traits;
   155 
   150 
   156   private:
   151   private:
   157 
   152 
   158     typedef typename Digraph::Node Node;
   153     typedef typename Digraph::Node Node;
   210 
   205 
   211   public:
   206   public:
   212 
   207 
   213     typedef Bfs Create;
   208     typedef Bfs Create;
   214 
   209 
   215     ///\name Named template parameters
   210     ///\name Named Template Parameters
   216 
   211 
   217     ///@{
   212     ///@{
   218 
   213 
   219     template <class T>
   214     template <class T>
   220     struct SetPredMapTraits : public Traits {
   215     struct SetPredMapTraits : public Traits {
   228     ///\brief \ref named-templ-param "Named parameter" for setting
   223     ///\brief \ref named-templ-param "Named parameter" for setting
   229     ///PredMap type.
   224     ///PredMap type.
   230     ///
   225     ///
   231     ///\ref named-templ-param "Named parameter" for setting
   226     ///\ref named-templ-param "Named parameter" for setting
   232     ///PredMap type.
   227     ///PredMap type.
       
   228     ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
   233     template <class T>
   229     template <class T>
   234     struct SetPredMap : public Bfs< Digraph, SetPredMapTraits<T> > {
   230     struct SetPredMap : public Bfs< Digraph, SetPredMapTraits<T> > {
   235       typedef Bfs< Digraph, SetPredMapTraits<T> > Create;
   231       typedef Bfs< Digraph, SetPredMapTraits<T> > Create;
   236     };
   232     };
   237 
   233 
   247     ///\brief \ref named-templ-param "Named parameter" for setting
   243     ///\brief \ref named-templ-param "Named parameter" for setting
   248     ///DistMap type.
   244     ///DistMap type.
   249     ///
   245     ///
   250     ///\ref named-templ-param "Named parameter" for setting
   246     ///\ref named-templ-param "Named parameter" for setting
   251     ///DistMap type.
   247     ///DistMap type.
       
   248     ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
   252     template <class T>
   249     template <class T>
   253     struct SetDistMap : public Bfs< Digraph, SetDistMapTraits<T> > {
   250     struct SetDistMap : public Bfs< Digraph, SetDistMapTraits<T> > {
   254       typedef Bfs< Digraph, SetDistMapTraits<T> > Create;
   251       typedef Bfs< Digraph, SetDistMapTraits<T> > Create;
   255     };
   252     };
   256 
   253 
   266     ///\brief \ref named-templ-param "Named parameter" for setting
   263     ///\brief \ref named-templ-param "Named parameter" for setting
   267     ///ReachedMap type.
   264     ///ReachedMap type.
   268     ///
   265     ///
   269     ///\ref named-templ-param "Named parameter" for setting
   266     ///\ref named-templ-param "Named parameter" for setting
   270     ///ReachedMap type.
   267     ///ReachedMap type.
       
   268     ///It must meet the \ref concepts::ReadWriteMap "ReadWriteMap" concept.
   271     template <class T>
   269     template <class T>
   272     struct SetReachedMap : public Bfs< Digraph, SetReachedMapTraits<T> > {
   270     struct SetReachedMap : public Bfs< Digraph, SetReachedMapTraits<T> > {
   273       typedef Bfs< Digraph, SetReachedMapTraits<T> > Create;
   271       typedef Bfs< Digraph, SetReachedMapTraits<T> > Create;
   274     };
   272     };
   275 
   273 
   285     ///\brief \ref named-templ-param "Named parameter" for setting
   283     ///\brief \ref named-templ-param "Named parameter" for setting
   286     ///ProcessedMap type.
   284     ///ProcessedMap type.
   287     ///
   285     ///
   288     ///\ref named-templ-param "Named parameter" for setting
   286     ///\ref named-templ-param "Named parameter" for setting
   289     ///ProcessedMap type.
   287     ///ProcessedMap type.
       
   288     ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
   290     template <class T>
   289     template <class T>
   291     struct SetProcessedMap : public Bfs< Digraph, SetProcessedMapTraits<T> > {
   290     struct SetProcessedMap : public Bfs< Digraph, SetProcessedMapTraits<T> > {
   292       typedef Bfs< Digraph, SetProcessedMapTraits<T> > Create;
   291       typedef Bfs< Digraph, SetProcessedMapTraits<T> > Create;
   293     };
   292     };
   294 
   293 
   337     }
   336     }
   338 
   337 
   339     ///Sets the map that stores the predecessor arcs.
   338     ///Sets the map that stores the predecessor arcs.
   340 
   339 
   341     ///Sets the map that stores the predecessor arcs.
   340     ///Sets the map that stores the predecessor arcs.
   342     ///If you don't use this function before calling \ref run(),
   341     ///If you don't use this function before calling \ref run(Node) "run()"
   343     ///it will allocate one. The destructor deallocates this
   342     ///or \ref init(), an instance will be allocated automatically.
   344     ///automatically allocated map, of course.
   343     ///The destructor deallocates this automatically allocated map,
       
   344     ///of course.
   345     ///\return <tt> (*this) </tt>
   345     ///\return <tt> (*this) </tt>
   346     Bfs &predMap(PredMap &m)
   346     Bfs &predMap(PredMap &m)
   347     {
   347     {
   348       if(local_pred) {
   348       if(local_pred) {
   349         delete _pred;
   349         delete _pred;
   354     }
   354     }
   355 
   355 
   356     ///Sets the map that indicates which nodes are reached.
   356     ///Sets the map that indicates which nodes are reached.
   357 
   357 
   358     ///Sets the map that indicates which nodes are reached.
   358     ///Sets the map that indicates which nodes are reached.
   359     ///If you don't use this function before calling \ref run(),
   359     ///If you don't use this function before calling \ref run(Node) "run()"
   360     ///it will allocate one. The destructor deallocates this
   360     ///or \ref init(), an instance will be allocated automatically.
   361     ///automatically allocated map, of course.
   361     ///The destructor deallocates this automatically allocated map,
       
   362     ///of course.
   362     ///\return <tt> (*this) </tt>
   363     ///\return <tt> (*this) </tt>
   363     Bfs &reachedMap(ReachedMap &m)
   364     Bfs &reachedMap(ReachedMap &m)
   364     {
   365     {
   365       if(local_reached) {
   366       if(local_reached) {
   366         delete _reached;
   367         delete _reached;
   371     }
   372     }
   372 
   373 
   373     ///Sets the map that indicates which nodes are processed.
   374     ///Sets the map that indicates which nodes are processed.
   374 
   375 
   375     ///Sets the map that indicates which nodes are processed.
   376     ///Sets the map that indicates which nodes are processed.
   376     ///If you don't use this function before calling \ref run(),
   377     ///If you don't use this function before calling \ref run(Node) "run()"
   377     ///it will allocate one. The destructor deallocates this
   378     ///or \ref init(), an instance will be allocated automatically.
   378     ///automatically allocated map, of course.
   379     ///The destructor deallocates this automatically allocated map,
       
   380     ///of course.
   379     ///\return <tt> (*this) </tt>
   381     ///\return <tt> (*this) </tt>
   380     Bfs &processedMap(ProcessedMap &m)
   382     Bfs &processedMap(ProcessedMap &m)
   381     {
   383     {
   382       if(local_processed) {
   384       if(local_processed) {
   383         delete _processed;
   385         delete _processed;
   389 
   391 
   390     ///Sets the map that stores the distances of the nodes.
   392     ///Sets the map that stores the distances of the nodes.
   391 
   393 
   392     ///Sets the map that stores the distances of the nodes calculated by
   394     ///Sets the map that stores the distances of the nodes calculated by
   393     ///the algorithm.
   395     ///the algorithm.
   394     ///If you don't use this function before calling \ref run(),
   396     ///If you don't use this function before calling \ref run(Node) "run()"
   395     ///it will allocate one. The destructor deallocates this
   397     ///or \ref init(), an instance will be allocated automatically.
   396     ///automatically allocated map, of course.
   398     ///The destructor deallocates this automatically allocated map,
       
   399     ///of course.
   397     ///\return <tt> (*this) </tt>
   400     ///\return <tt> (*this) </tt>
   398     Bfs &distMap(DistMap &m)
   401     Bfs &distMap(DistMap &m)
   399     {
   402     {
   400       if(local_dist) {
   403       if(local_dist) {
   401         delete _dist;
   404         delete _dist;
   405       return *this;
   408       return *this;
   406     }
   409     }
   407 
   410 
   408   public:
   411   public:
   409 
   412 
   410     ///\name Execution control
   413     ///\name Execution Control
   411     ///The simplest way to execute the algorithm is to use
   414     ///The simplest way to execute the BFS algorithm is to use one of the
   412     ///one of the member functions called \ref lemon::Bfs::run() "run()".
   415     ///member functions called \ref run(Node) "run()".\n
   413     ///\n
   416     ///If you need more control on the execution, first you have to call
   414     ///If you need more control on the execution, first you must call
   417     ///\ref init(), then you can add several source nodes with
   415     ///\ref lemon::Bfs::init() "init()", then you can add several source
   418     ///\ref addSource(). Finally the actual path computation can be
   416     ///nodes with \ref lemon::Bfs::addSource() "addSource()".
   419     ///performed with one of the \ref start() functions.
   417     ///Finally \ref lemon::Bfs::start() "start()" will perform the
       
   418     ///actual path computation.
       
   419 
   420 
   420     ///@{
   421     ///@{
   421 
   422 
       
   423     ///\brief Initializes the internal data structures.
       
   424     ///
   422     ///Initializes the internal data structures.
   425     ///Initializes the internal data structures.
   423 
       
   424     ///Initializes the internal data structures.
       
   425     ///
       
   426     void init()
   426     void init()
   427     {
   427     {
   428       create_maps();
   428       create_maps();
   429       _queue.resize(countNodes(*G));
   429       _queue.resize(countNodes(*G));
   430       _queue_head=_queue_tail=0;
   430       _queue_head=_queue_tail=0;
   554     Node nextNode() const
   554     Node nextNode() const
   555     {
   555     {
   556       return _queue_tail<_queue_head?_queue[_queue_tail]:INVALID;
   556       return _queue_tail<_queue_head?_queue[_queue_tail]:INVALID;
   557     }
   557     }
   558 
   558 
   559     ///\brief Returns \c false if there are nodes
   559     ///Returns \c false if there are nodes to be processed.
   560     ///to be processed.
   560 
   561     ///
   561     ///Returns \c false if there are nodes to be processed
   562     ///Returns \c false if there are nodes
   562     ///in the queue.
   563     ///to be processed in the queue.
       
   564     bool emptyQueue() const { return _queue_tail==_queue_head; }
   563     bool emptyQueue() const { return _queue_tail==_queue_head; }
   565 
   564 
   566     ///Returns the number of the nodes to be processed.
   565     ///Returns the number of the nodes to be processed.
   567 
   566 
   568     ///Returns the number of the nodes to be processed in the queue.
   567     ///Returns the number of the nodes to be processed
       
   568     ///in the queue.
   569     int queueSize() const { return _queue_head-_queue_tail; }
   569     int queueSize() const { return _queue_head-_queue_tail; }
   570 
   570 
   571     ///Executes the algorithm.
   571     ///Executes the algorithm.
   572 
   572 
   573     ///Executes the algorithm.
   573     ///Executes the algorithm.
   728     }
   728     }
   729 
   729 
   730     ///@}
   730     ///@}
   731 
   731 
   732     ///\name Query Functions
   732     ///\name Query Functions
   733     ///The result of the %BFS algorithm can be obtained using these
   733     ///The results of the BFS algorithm can be obtained using these
   734     ///functions.\n
   734     ///functions.\n
   735     ///Either \ref lemon::Bfs::run() "run()" or \ref lemon::Bfs::start()
   735     ///Either \ref run(Node) "run()" or \ref start() should be called
   736     ///"start()" must be called before using them.
   736     ///before using them.
   737 
   737 
   738     ///@{
   738     ///@{
   739 
   739 
   740     ///The shortest path to a node.
   740     ///The shortest path to a node.
   741 
   741 
   742     ///Returns the shortest path to a node.
   742     ///Returns the shortest path to a node.
   743     ///
   743     ///
   744     ///\warning \c t should be reachable from the root(s).
   744     ///\warning \c t should be reached from the root(s).
   745     ///
   745     ///
   746     ///\pre Either \ref run() or \ref start() must be called before
   746     ///\pre Either \ref run(Node) "run()" or \ref init()
   747     ///using this function.
   747     ///must be called before using this function.
   748     Path path(Node t) const { return Path(*G, *_pred, t); }
   748     Path path(Node t) const { return Path(*G, *_pred, t); }
   749 
   749 
   750     ///The distance of a node from the root(s).
   750     ///The distance of a node from the root(s).
   751 
   751 
   752     ///Returns the distance of a node from the root(s).
   752     ///Returns the distance of a node from the root(s).
   753     ///
   753     ///
   754     ///\warning If node \c v is not reachable from the root(s), then
   754     ///\warning If node \c v is not reached from the root(s), then
   755     ///the return value of this function is undefined.
   755     ///the return value of this function is undefined.
   756     ///
   756     ///
   757     ///\pre Either \ref run() or \ref start() must be called before
   757     ///\pre Either \ref run(Node) "run()" or \ref init()
   758     ///using this function.
   758     ///must be called before using this function.
   759     int dist(Node v) const { return (*_dist)[v]; }
   759     int dist(Node v) const { return (*_dist)[v]; }
   760 
   760 
   761     ///Returns the 'previous arc' of the shortest path tree for a node.
   761     ///Returns the 'previous arc' of the shortest path tree for a node.
   762 
   762 
   763     ///This function returns the 'previous arc' of the shortest path
   763     ///This function returns the 'previous arc' of the shortest path
   764     ///tree for the node \c v, i.e. it returns the last arc of a
   764     ///tree for the node \c v, i.e. it returns the last arc of a
   765     ///shortest path from the root(s) to \c v. It is \c INVALID if \c v
   765     ///shortest path from a root to \c v. It is \c INVALID if \c v
   766     ///is not reachable from the root(s) or if \c v is a root.
   766     ///is not reached from the root(s) or if \c v is a root.
   767     ///
   767     ///
   768     ///The shortest path tree used here is equal to the shortest path
   768     ///The shortest path tree used here is equal to the shortest path
   769     ///tree used in \ref predNode().
   769     ///tree used in \ref predNode().
   770     ///
   770     ///
   771     ///\pre Either \ref run() or \ref start() must be called before
   771     ///\pre Either \ref run(Node) "run()" or \ref init()
   772     ///using this function.
   772     ///must be called before using this function.
   773     Arc predArc(Node v) const { return (*_pred)[v];}
   773     Arc predArc(Node v) const { return (*_pred)[v];}
   774 
   774 
   775     ///Returns the 'previous node' of the shortest path tree for a node.
   775     ///Returns the 'previous node' of the shortest path tree for a node.
   776 
   776 
   777     ///This function returns the 'previous node' of the shortest path
   777     ///This function returns the 'previous node' of the shortest path
   778     ///tree for the node \c v, i.e. it returns the last but one node
   778     ///tree for the node \c v, i.e. it returns the last but one node
   779     ///from a shortest path from the root(s) to \c v. It is \c INVALID
   779     ///from a shortest path from a root to \c v. It is \c INVALID
   780     ///if \c v is not reachable from the root(s) or if \c v is a root.
   780     ///if \c v is not reached from the root(s) or if \c v is a root.
   781     ///
   781     ///
   782     ///The shortest path tree used here is equal to the shortest path
   782     ///The shortest path tree used here is equal to the shortest path
   783     ///tree used in \ref predArc().
   783     ///tree used in \ref predArc().
   784     ///
   784     ///
   785     ///\pre Either \ref run() or \ref start() must be called before
   785     ///\pre Either \ref run(Node) "run()" or \ref init()
   786     ///using this function.
   786     ///must be called before using this function.
   787     Node predNode(Node v) const { return (*_pred)[v]==INVALID ? INVALID:
   787     Node predNode(Node v) const { return (*_pred)[v]==INVALID ? INVALID:
   788                                   G->source((*_pred)[v]); }
   788                                   G->source((*_pred)[v]); }
   789 
   789 
   790     ///\brief Returns a const reference to the node map that stores the
   790     ///\brief Returns a const reference to the node map that stores the
   791     /// distances of the nodes.
   791     /// distances of the nodes.
   792     ///
   792     ///
   793     ///Returns a const reference to the node map that stores the distances
   793     ///Returns a const reference to the node map that stores the distances
   794     ///of the nodes calculated by the algorithm.
   794     ///of the nodes calculated by the algorithm.
   795     ///
   795     ///
   796     ///\pre Either \ref run() or \ref init()
   796     ///\pre Either \ref run(Node) "run()" or \ref init()
   797     ///must be called before using this function.
   797     ///must be called before using this function.
   798     const DistMap &distMap() const { return *_dist;}
   798     const DistMap &distMap() const { return *_dist;}
   799 
   799 
   800     ///\brief Returns a const reference to the node map that stores the
   800     ///\brief Returns a const reference to the node map that stores the
   801     ///predecessor arcs.
   801     ///predecessor arcs.
   802     ///
   802     ///
   803     ///Returns a const reference to the node map that stores the predecessor
   803     ///Returns a const reference to the node map that stores the predecessor
   804     ///arcs, which form the shortest path tree.
   804     ///arcs, which form the shortest path tree.
   805     ///
   805     ///
   806     ///\pre Either \ref run() or \ref init()
   806     ///\pre Either \ref run(Node) "run()" or \ref init()
   807     ///must be called before using this function.
   807     ///must be called before using this function.
   808     const PredMap &predMap() const { return *_pred;}
   808     const PredMap &predMap() const { return *_pred;}
   809 
   809 
   810     ///Checks if a node is reachable from the root(s).
   810     ///Checks if a node is reached from the root(s).
   811 
   811 
   812     ///Returns \c true if \c v is reachable from the root(s).
   812     ///Returns \c true if \c v is reached from the root(s).
   813     ///\pre Either \ref run() or \ref start()
   813     ///
       
   814     ///\pre Either \ref run(Node) "run()" or \ref init()
   814     ///must be called before using this function.
   815     ///must be called before using this function.
   815     bool reached(Node v) const { return (*_reached)[v]; }
   816     bool reached(Node v) const { return (*_reached)[v]; }
   816 
   817 
   817     ///@}
   818     ///@}
   818   };
   819   };
   954 
   955 
   955   /// Auxiliary class for the function-type interface of BFS algorithm.
   956   /// Auxiliary class for the function-type interface of BFS algorithm.
   956 
   957 
   957   /// This auxiliary class is created to implement the
   958   /// This auxiliary class is created to implement the
   958   /// \ref bfs() "function-type interface" of \ref Bfs algorithm.
   959   /// \ref bfs() "function-type interface" of \ref Bfs algorithm.
   959   /// It does not have own \ref run() method, it uses the functions
   960   /// It does not have own \ref run(Node) "run()" method, it uses the
   960   /// and features of the plain \ref Bfs.
   961   /// functions and features of the plain \ref Bfs.
   961   ///
   962   ///
   962   /// This class should only be used through the \ref bfs() function,
   963   /// This class should only be used through the \ref bfs() function,
   963   /// which makes it easier to use the algorithm.
   964   /// which makes it easier to use the algorithm.
   964   template<class TR>
   965   template<class TR>
   965   class BfsWizard : public TR
   966   class BfsWizard : public TR
  1175   ///  bfs(g).predMap(preds).distMap(dists).run(s);
  1176   ///  bfs(g).predMap(preds).distMap(dists).run(s);
  1176   ///
  1177   ///
  1177   ///  // Compute shortest path from s to t
  1178   ///  // Compute shortest path from s to t
  1178   ///  bool reached = bfs(g).path(p).dist(d).run(s,t);
  1179   ///  bool reached = bfs(g).path(p).dist(d).run(s,t);
  1179   ///\endcode
  1180   ///\endcode
  1180   ///\warning Don't forget to put the \ref BfsWizard::run() "run()"
  1181   ///\warning Don't forget to put the \ref BfsWizard::run(Node) "run()"
  1181   ///to the end of the parameter list.
  1182   ///to the end of the parameter list.
  1182   ///\sa BfsWizard
  1183   ///\sa BfsWizard
  1183   ///\sa Bfs
  1184   ///\sa Bfs
  1184   template<class GR>
  1185   template<class GR>
  1185   BfsWizard<BfsWizardBase<GR> >
  1186   BfsWizard<BfsWizardBase<GR> >
  1361 
  1362 
  1362   public:
  1363   public:
  1363 
  1364 
  1364     typedef BfsVisit Create;
  1365     typedef BfsVisit Create;
  1365 
  1366 
  1366     /// \name Named template parameters
  1367     /// \name Named Template Parameters
  1367 
  1368 
  1368     ///@{
  1369     ///@{
  1369     template <class T>
  1370     template <class T>
  1370     struct SetReachedMapTraits : public Traits {
  1371     struct SetReachedMapTraits : public Traits {
  1371       typedef T ReachedMap;
  1372       typedef T ReachedMap;
  1403     }
  1404     }
  1404 
  1405 
  1405     /// \brief Sets the map that indicates which nodes are reached.
  1406     /// \brief Sets the map that indicates which nodes are reached.
  1406     ///
  1407     ///
  1407     /// Sets the map that indicates which nodes are reached.
  1408     /// Sets the map that indicates which nodes are reached.
  1408     /// If you don't use this function before calling \ref run(),
  1409     /// If you don't use this function before calling \ref run(Node) "run()"
  1409     /// it will allocate one. The destructor deallocates this
  1410     /// or \ref init(), an instance will be allocated automatically.
  1410     /// automatically allocated map, of course.
  1411     /// The destructor deallocates this automatically allocated map,
       
  1412     /// of course.
  1411     /// \return <tt> (*this) </tt>
  1413     /// \return <tt> (*this) </tt>
  1412     BfsVisit &reachedMap(ReachedMap &m) {
  1414     BfsVisit &reachedMap(ReachedMap &m) {
  1413       if(local_reached) {
  1415       if(local_reached) {
  1414         delete _reached;
  1416         delete _reached;
  1415         local_reached = false;
  1417         local_reached = false;
  1418       return *this;
  1420       return *this;
  1419     }
  1421     }
  1420 
  1422 
  1421   public:
  1423   public:
  1422 
  1424 
  1423     /// \name Execution control
  1425     /// \name Execution Control
  1424     /// The simplest way to execute the algorithm is to use
  1426     /// The simplest way to execute the BFS algorithm is to use one of the
  1425     /// one of the member functions called \ref lemon::BfsVisit::run()
  1427     /// member functions called \ref run(Node) "run()".\n
  1426     /// "run()".
  1428     /// If you need more control on the execution, first you have to call
  1427     /// \n
  1429     /// \ref init(), then you can add several source nodes with
  1428     /// If you need more control on the execution, first you must call
  1430     /// \ref addSource(). Finally the actual path computation can be
  1429     /// \ref lemon::BfsVisit::init() "init()", then you can add several
  1431     /// performed with one of the \ref start() functions.
  1430     /// source nodes with \ref lemon::BfsVisit::addSource() "addSource()".
       
  1431     /// Finally \ref lemon::BfsVisit::start() "start()" will perform the
       
  1432     /// actual path computation.
       
  1433 
  1432 
  1434     /// @{
  1433     /// @{
  1435 
  1434 
  1436     /// \brief Initializes the internal data structures.
  1435     /// \brief Initializes the internal data structures.
  1437     ///
  1436     ///
  1727     }
  1726     }
  1728 
  1727 
  1729     ///@}
  1728     ///@}
  1730 
  1729 
  1731     /// \name Query Functions
  1730     /// \name Query Functions
  1732     /// The result of the %BFS algorithm can be obtained using these
  1731     /// The results of the BFS algorithm can be obtained using these
  1733     /// functions.\n
  1732     /// functions.\n
  1734     /// Either \ref lemon::BfsVisit::run() "run()" or
  1733     /// Either \ref run(Node) "run()" or \ref start() should be called
  1735     /// \ref lemon::BfsVisit::start() "start()" must be called before
  1734     /// before using them.
  1736     /// using them.
  1735 
  1737     ///@{
  1736     ///@{
  1738 
  1737 
  1739     /// \brief Checks if a node is reachable from the root(s).
  1738     /// \brief Checks if a node is reached from the root(s).
  1740     ///
  1739     ///
  1741     /// Returns \c true if \c v is reachable from the root(s).
  1740     /// Returns \c true if \c v is reached from the root(s).
  1742     /// \pre Either \ref run() or \ref start()
  1741     ///
       
  1742     /// \pre Either \ref run(Node) "run()" or \ref init()
  1743     /// must be called before using this function.
  1743     /// must be called before using this function.
  1744     bool reached(Node v) { return (*_reached)[v]; }
  1744     bool reached(Node v) { return (*_reached)[v]; }
  1745 
  1745 
  1746     ///@}
  1746     ///@}
  1747 
  1747