lemon/bfs.h
author Peter Kovacs <kpeter@inf.elte.hu>
Sat, 20 Feb 2010 18:39:03 +0100
changeset 839 f3bc4e9b5f3a
parent 787 c2230649a493
parent 786 e20173729589
child 825 75e6020b19b1
permissions -rw-r--r--
New heuristics for MCF algorithms (#340)
and some implementation improvements.

- A useful heuristic is added to NetworkSimplex to make the
initial pivots faster.
- A powerful global update heuristic is added to CostScaling
and the implementation is reworked with various improvements.
- Better relabeling in CostScaling to improve numerical stability
and make the code faster.
- A small improvement is made in CapacityScaling for better
delta computation.
- Add notes to the classes about the usage of vector<char> instead
of vector<bool> for efficiency reasons.
     1 /* -*- mode: C++; indent-tabs-mode: nil; -*-
     2  *
     3  * This file is a part of LEMON, a generic C++ optimization library.
     4  *
     5  * Copyright (C) 2003-2009
     6  * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
     7  * (Egervary Research Group on Combinatorial Optimization, EGRES).
     8  *
     9  * Permission to use, modify and distribute this software is granted
    10  * provided that this copyright notice appears in all copies. For
    11  * precise terms see the accompanying LICENSE file.
    12  *
    13  * This software is provided "AS IS" with no warranty of any kind,
    14  * express or implied, and with no claim as to its suitability for any
    15  * purpose.
    16  *
    17  */
    18 
    19 #ifndef LEMON_BFS_H
    20 #define LEMON_BFS_H
    21 
    22 ///\ingroup search
    23 ///\file
    24 ///\brief BFS algorithm.
    25 
    26 #include <lemon/list_graph.h>
    27 #include <lemon/bits/path_dump.h>
    28 #include <lemon/core.h>
    29 #include <lemon/error.h>
    30 #include <lemon/maps.h>
    31 #include <lemon/path.h>
    32 
    33 namespace lemon {
    34 
    35   ///Default traits class of Bfs class.
    36 
    37   ///Default traits class of Bfs class.
    38   ///\tparam GR Digraph type.
    39   template<class GR>
    40   struct BfsDefaultTraits
    41   {
    42     ///The type of the digraph the algorithm runs on.
    43     typedef GR Digraph;
    44 
    45     ///\brief The type of the map that stores the predecessor
    46     ///arcs of the shortest paths.
    47     ///
    48     ///The type of the map that stores the predecessor
    49     ///arcs of the shortest paths.
    50     ///It must conform to the \ref concepts::WriteMap "WriteMap" concept.
    51     typedef typename Digraph::template NodeMap<typename Digraph::Arc> PredMap;
    52     ///Instantiates a \c PredMap.
    53 
    54     ///This function instantiates a \ref PredMap.
    55     ///\param g is the digraph, to which we would like to define the
    56     ///\ref PredMap.
    57     static PredMap *createPredMap(const Digraph &g)
    58     {
    59       return new PredMap(g);
    60     }
    61 
    62     ///The type of the map that indicates which nodes are processed.
    63 
    64     ///The type of the map that indicates which nodes are processed.
    65     ///It must conform to the \ref concepts::WriteMap "WriteMap" concept.
    66     ///By default, it is a NullMap.
    67     typedef NullMap<typename Digraph::Node,bool> ProcessedMap;
    68     ///Instantiates a \c ProcessedMap.
    69 
    70     ///This function instantiates a \ref ProcessedMap.
    71     ///\param g is the digraph, to which
    72     ///we would like to define the \ref ProcessedMap
    73 #ifdef DOXYGEN
    74     static ProcessedMap *createProcessedMap(const Digraph &g)
    75 #else
    76     static ProcessedMap *createProcessedMap(const Digraph &)
    77 #endif
    78     {
    79       return new ProcessedMap();
    80     }
    81 
    82     ///The type of the map that indicates which nodes are reached.
    83 
    84     ///The type of the map that indicates which nodes are reached.
    85     ///It must conform to the \ref concepts::ReadWriteMap "ReadWriteMap" concept.
    86     typedef typename Digraph::template NodeMap<bool> ReachedMap;
    87     ///Instantiates a \c ReachedMap.
    88 
    89     ///This function instantiates a \ref ReachedMap.
    90     ///\param g is the digraph, to which
    91     ///we would like to define the \ref ReachedMap.
    92     static ReachedMap *createReachedMap(const Digraph &g)
    93     {
    94       return new ReachedMap(g);
    95     }
    96 
    97     ///The type of the map that stores the distances of the nodes.
    98 
    99     ///The type of the map that stores the distances of the nodes.
   100     ///It must conform to the \ref concepts::WriteMap "WriteMap" concept.
   101     typedef typename Digraph::template NodeMap<int> DistMap;
   102     ///Instantiates a \c DistMap.
   103 
   104     ///This function instantiates a \ref DistMap.
   105     ///\param g is the digraph, to which we would like to define the
   106     ///\ref DistMap.
   107     static DistMap *createDistMap(const Digraph &g)
   108     {
   109       return new DistMap(g);
   110     }
   111   };
   112 
   113   ///%BFS algorithm class.
   114 
   115   ///\ingroup search
   116   ///This class provides an efficient implementation of the %BFS algorithm.
   117   ///
   118   ///There is also a \ref bfs() "function-type interface" for the BFS
   119   ///algorithm, which is convenient in the simplier cases and it can be
   120   ///used easier.
   121   ///
   122   ///\tparam GR The type of the digraph the algorithm runs on.
   123   ///The default type is \ref ListDigraph.
   124 #ifdef DOXYGEN
   125   template <typename GR,
   126             typename TR>
   127 #else
   128   template <typename GR=ListDigraph,
   129             typename TR=BfsDefaultTraits<GR> >
   130 #endif
   131   class Bfs {
   132   public:
   133 
   134     ///The type of the digraph the algorithm runs on.
   135     typedef typename TR::Digraph Digraph;
   136 
   137     ///\brief The type of the map that stores the predecessor arcs of the
   138     ///shortest paths.
   139     typedef typename TR::PredMap PredMap;
   140     ///The type of the map that stores the distances of the nodes.
   141     typedef typename TR::DistMap DistMap;
   142     ///The type of the map that indicates which nodes are reached.
   143     typedef typename TR::ReachedMap ReachedMap;
   144     ///The type of the map that indicates which nodes are processed.
   145     typedef typename TR::ProcessedMap ProcessedMap;
   146     ///The type of the paths.
   147     typedef PredMapPath<Digraph, PredMap> Path;
   148 
   149     ///The \ref BfsDefaultTraits "traits class" of the algorithm.
   150     typedef TR Traits;
   151 
   152   private:
   153 
   154     typedef typename Digraph::Node Node;
   155     typedef typename Digraph::NodeIt NodeIt;
   156     typedef typename Digraph::Arc Arc;
   157     typedef typename Digraph::OutArcIt OutArcIt;
   158 
   159     //Pointer to the underlying digraph.
   160     const Digraph *G;
   161     //Pointer to the map of predecessor arcs.
   162     PredMap *_pred;
   163     //Indicates if _pred is locally allocated (true) or not.
   164     bool local_pred;
   165     //Pointer to the map of distances.
   166     DistMap *_dist;
   167     //Indicates if _dist is locally allocated (true) or not.
   168     bool local_dist;
   169     //Pointer to the map of reached status of the nodes.
   170     ReachedMap *_reached;
   171     //Indicates if _reached is locally allocated (true) or not.
   172     bool local_reached;
   173     //Pointer to the map of processed status of the nodes.
   174     ProcessedMap *_processed;
   175     //Indicates if _processed is locally allocated (true) or not.
   176     bool local_processed;
   177 
   178     std::vector<typename Digraph::Node> _queue;
   179     int _queue_head,_queue_tail,_queue_next_dist;
   180     int _curr_dist;
   181 
   182     //Creates the maps if necessary.
   183     void create_maps()
   184     {
   185       if(!_pred) {
   186         local_pred = true;
   187         _pred = Traits::createPredMap(*G);
   188       }
   189       if(!_dist) {
   190         local_dist = true;
   191         _dist = Traits::createDistMap(*G);
   192       }
   193       if(!_reached) {
   194         local_reached = true;
   195         _reached = Traits::createReachedMap(*G);
   196       }
   197       if(!_processed) {
   198         local_processed = true;
   199         _processed = Traits::createProcessedMap(*G);
   200       }
   201     }
   202 
   203   protected:
   204 
   205     Bfs() {}
   206 
   207   public:
   208 
   209     typedef Bfs Create;
   210 
   211     ///\name Named Template Parameters
   212 
   213     ///@{
   214 
   215     template <class T>
   216     struct SetPredMapTraits : public Traits {
   217       typedef T PredMap;
   218       static PredMap *createPredMap(const Digraph &)
   219       {
   220         LEMON_ASSERT(false, "PredMap is not initialized");
   221         return 0; // ignore warnings
   222       }
   223     };
   224     ///\brief \ref named-templ-param "Named parameter" for setting
   225     ///\c PredMap type.
   226     ///
   227     ///\ref named-templ-param "Named parameter" for setting
   228     ///\c PredMap type.
   229     ///It must conform to the \ref concepts::WriteMap "WriteMap" concept.
   230     template <class T>
   231     struct SetPredMap : public Bfs< Digraph, SetPredMapTraits<T> > {
   232       typedef Bfs< Digraph, SetPredMapTraits<T> > Create;
   233     };
   234 
   235     template <class T>
   236     struct SetDistMapTraits : public Traits {
   237       typedef T DistMap;
   238       static DistMap *createDistMap(const Digraph &)
   239       {
   240         LEMON_ASSERT(false, "DistMap is not initialized");
   241         return 0; // ignore warnings
   242       }
   243     };
   244     ///\brief \ref named-templ-param "Named parameter" for setting
   245     ///\c DistMap type.
   246     ///
   247     ///\ref named-templ-param "Named parameter" for setting
   248     ///\c DistMap type.
   249     ///It must conform to the \ref concepts::WriteMap "WriteMap" concept.
   250     template <class T>
   251     struct SetDistMap : public Bfs< Digraph, SetDistMapTraits<T> > {
   252       typedef Bfs< Digraph, SetDistMapTraits<T> > Create;
   253     };
   254 
   255     template <class T>
   256     struct SetReachedMapTraits : public Traits {
   257       typedef T ReachedMap;
   258       static ReachedMap *createReachedMap(const Digraph &)
   259       {
   260         LEMON_ASSERT(false, "ReachedMap is not initialized");
   261         return 0; // ignore warnings
   262       }
   263     };
   264     ///\brief \ref named-templ-param "Named parameter" for setting
   265     ///\c ReachedMap type.
   266     ///
   267     ///\ref named-templ-param "Named parameter" for setting
   268     ///\c ReachedMap type.
   269     ///It must conform to the \ref concepts::ReadWriteMap "ReadWriteMap" concept.
   270     template <class T>
   271     struct SetReachedMap : public Bfs< Digraph, SetReachedMapTraits<T> > {
   272       typedef Bfs< Digraph, SetReachedMapTraits<T> > Create;
   273     };
   274 
   275     template <class T>
   276     struct SetProcessedMapTraits : public Traits {
   277       typedef T ProcessedMap;
   278       static ProcessedMap *createProcessedMap(const Digraph &)
   279       {
   280         LEMON_ASSERT(false, "ProcessedMap is not initialized");
   281         return 0; // ignore warnings
   282       }
   283     };
   284     ///\brief \ref named-templ-param "Named parameter" for setting
   285     ///\c ProcessedMap type.
   286     ///
   287     ///\ref named-templ-param "Named parameter" for setting
   288     ///\c ProcessedMap type.
   289     ///It must conform to the \ref concepts::WriteMap "WriteMap" concept.
   290     template <class T>
   291     struct SetProcessedMap : public Bfs< Digraph, SetProcessedMapTraits<T> > {
   292       typedef Bfs< Digraph, SetProcessedMapTraits<T> > Create;
   293     };
   294 
   295     struct SetStandardProcessedMapTraits : public Traits {
   296       typedef typename Digraph::template NodeMap<bool> ProcessedMap;
   297       static ProcessedMap *createProcessedMap(const Digraph &g)
   298       {
   299         return new ProcessedMap(g);
   300         return 0; // ignore warnings
   301       }
   302     };
   303     ///\brief \ref named-templ-param "Named parameter" for setting
   304     ///\c ProcessedMap type to be <tt>Digraph::NodeMap<bool></tt>.
   305     ///
   306     ///\ref named-templ-param "Named parameter" for setting
   307     ///\c ProcessedMap type to be <tt>Digraph::NodeMap<bool></tt>.
   308     ///If you don't set it explicitly, it will be automatically allocated.
   309     struct SetStandardProcessedMap :
   310       public Bfs< Digraph, SetStandardProcessedMapTraits > {
   311       typedef Bfs< Digraph, SetStandardProcessedMapTraits > Create;
   312     };
   313 
   314     ///@}
   315 
   316   public:
   317 
   318     ///Constructor.
   319 
   320     ///Constructor.
   321     ///\param g The digraph the algorithm runs on.
   322     Bfs(const Digraph &g) :
   323       G(&g),
   324       _pred(NULL), local_pred(false),
   325       _dist(NULL), local_dist(false),
   326       _reached(NULL), local_reached(false),
   327       _processed(NULL), local_processed(false)
   328     { }
   329 
   330     ///Destructor.
   331     ~Bfs()
   332     {
   333       if(local_pred) delete _pred;
   334       if(local_dist) delete _dist;
   335       if(local_reached) delete _reached;
   336       if(local_processed) delete _processed;
   337     }
   338 
   339     ///Sets the map that stores the predecessor arcs.
   340 
   341     ///Sets the map that stores the predecessor arcs.
   342     ///If you don't use this function before calling \ref run(Node) "run()"
   343     ///or \ref init(), an instance will be allocated automatically.
   344     ///The destructor deallocates this automatically allocated map,
   345     ///of course.
   346     ///\return <tt> (*this) </tt>
   347     Bfs &predMap(PredMap &m)
   348     {
   349       if(local_pred) {
   350         delete _pred;
   351         local_pred=false;
   352       }
   353       _pred = &m;
   354       return *this;
   355     }
   356 
   357     ///Sets the map that indicates which nodes are reached.
   358 
   359     ///Sets the map that indicates which nodes are reached.
   360     ///If you don't use this function before calling \ref run(Node) "run()"
   361     ///or \ref init(), an instance will be allocated automatically.
   362     ///The destructor deallocates this automatically allocated map,
   363     ///of course.
   364     ///\return <tt> (*this) </tt>
   365     Bfs &reachedMap(ReachedMap &m)
   366     {
   367       if(local_reached) {
   368         delete _reached;
   369         local_reached=false;
   370       }
   371       _reached = &m;
   372       return *this;
   373     }
   374 
   375     ///Sets the map that indicates which nodes are processed.
   376 
   377     ///Sets the map that indicates which nodes are processed.
   378     ///If you don't use this function before calling \ref run(Node) "run()"
   379     ///or \ref init(), an instance will be allocated automatically.
   380     ///The destructor deallocates this automatically allocated map,
   381     ///of course.
   382     ///\return <tt> (*this) </tt>
   383     Bfs &processedMap(ProcessedMap &m)
   384     {
   385       if(local_processed) {
   386         delete _processed;
   387         local_processed=false;
   388       }
   389       _processed = &m;
   390       return *this;
   391     }
   392 
   393     ///Sets the map that stores the distances of the nodes.
   394 
   395     ///Sets the map that stores the distances of the nodes calculated by
   396     ///the algorithm.
   397     ///If you don't use this function before calling \ref run(Node) "run()"
   398     ///or \ref init(), an instance will be allocated automatically.
   399     ///The destructor deallocates this automatically allocated map,
   400     ///of course.
   401     ///\return <tt> (*this) </tt>
   402     Bfs &distMap(DistMap &m)
   403     {
   404       if(local_dist) {
   405         delete _dist;
   406         local_dist=false;
   407       }
   408       _dist = &m;
   409       return *this;
   410     }
   411 
   412   public:
   413 
   414     ///\name Execution Control
   415     ///The simplest way to execute the BFS algorithm is to use one of the
   416     ///member functions called \ref run(Node) "run()".\n
   417     ///If you need better control on the execution, you have to call
   418     ///\ref init() first, then you can add several source nodes with
   419     ///\ref addSource(). Finally the actual path computation can be
   420     ///performed with one of the \ref start() functions.
   421 
   422     ///@{
   423 
   424     ///\brief Initializes the internal data structures.
   425     ///
   426     ///Initializes the internal data structures.
   427     void init()
   428     {
   429       create_maps();
   430       _queue.resize(countNodes(*G));
   431       _queue_head=_queue_tail=0;
   432       _curr_dist=1;
   433       for ( NodeIt u(*G) ; u!=INVALID ; ++u ) {
   434         _pred->set(u,INVALID);
   435         _reached->set(u,false);
   436         _processed->set(u,false);
   437       }
   438     }
   439 
   440     ///Adds a new source node.
   441 
   442     ///Adds a new source node to the set of nodes to be processed.
   443     ///
   444     void addSource(Node s)
   445     {
   446       if(!(*_reached)[s])
   447         {
   448           _reached->set(s,true);
   449           _pred->set(s,INVALID);
   450           _dist->set(s,0);
   451           _queue[_queue_head++]=s;
   452           _queue_next_dist=_queue_head;
   453         }
   454     }
   455 
   456     ///Processes the next node.
   457 
   458     ///Processes the next node.
   459     ///
   460     ///\return The processed node.
   461     ///
   462     ///\pre The queue must not be empty.
   463     Node processNextNode()
   464     {
   465       if(_queue_tail==_queue_next_dist) {
   466         _curr_dist++;
   467         _queue_next_dist=_queue_head;
   468       }
   469       Node n=_queue[_queue_tail++];
   470       _processed->set(n,true);
   471       Node m;
   472       for(OutArcIt e(*G,n);e!=INVALID;++e)
   473         if(!(*_reached)[m=G->target(e)]) {
   474           _queue[_queue_head++]=m;
   475           _reached->set(m,true);
   476           _pred->set(m,e);
   477           _dist->set(m,_curr_dist);
   478         }
   479       return n;
   480     }
   481 
   482     ///Processes the next node.
   483 
   484     ///Processes the next node and checks if the given target node
   485     ///is reached. If the target node is reachable from the processed
   486     ///node, then the \c reach parameter will be set to \c true.
   487     ///
   488     ///\param target The target node.
   489     ///\retval reach Indicates if the target node is reached.
   490     ///It should be initially \c false.
   491     ///
   492     ///\return The processed node.
   493     ///
   494     ///\pre The queue must not be empty.
   495     Node processNextNode(Node target, bool& reach)
   496     {
   497       if(_queue_tail==_queue_next_dist) {
   498         _curr_dist++;
   499         _queue_next_dist=_queue_head;
   500       }
   501       Node n=_queue[_queue_tail++];
   502       _processed->set(n,true);
   503       Node m;
   504       for(OutArcIt e(*G,n);e!=INVALID;++e)
   505         if(!(*_reached)[m=G->target(e)]) {
   506           _queue[_queue_head++]=m;
   507           _reached->set(m,true);
   508           _pred->set(m,e);
   509           _dist->set(m,_curr_dist);
   510           reach = reach || (target == m);
   511         }
   512       return n;
   513     }
   514 
   515     ///Processes the next node.
   516 
   517     ///Processes the next node and checks if at least one of reached
   518     ///nodes has \c true value in the \c nm node map. If one node
   519     ///with \c true value is reachable from the processed node, then the
   520     ///\c rnode parameter will be set to the first of such nodes.
   521     ///
   522     ///\param nm A \c bool (or convertible) node map that indicates the
   523     ///possible targets.
   524     ///\retval rnode The reached target node.
   525     ///It should be initially \c INVALID.
   526     ///
   527     ///\return The processed node.
   528     ///
   529     ///\pre The queue must not be empty.
   530     template<class NM>
   531     Node processNextNode(const NM& nm, Node& rnode)
   532     {
   533       if(_queue_tail==_queue_next_dist) {
   534         _curr_dist++;
   535         _queue_next_dist=_queue_head;
   536       }
   537       Node n=_queue[_queue_tail++];
   538       _processed->set(n,true);
   539       Node m;
   540       for(OutArcIt e(*G,n);e!=INVALID;++e)
   541         if(!(*_reached)[m=G->target(e)]) {
   542           _queue[_queue_head++]=m;
   543           _reached->set(m,true);
   544           _pred->set(m,e);
   545           _dist->set(m,_curr_dist);
   546           if (nm[m] && rnode == INVALID) rnode = m;
   547         }
   548       return n;
   549     }
   550 
   551     ///The next node to be processed.
   552 
   553     ///Returns the next node to be processed or \c INVALID if the queue
   554     ///is empty.
   555     Node nextNode() const
   556     {
   557       return _queue_tail<_queue_head?_queue[_queue_tail]:INVALID;
   558     }
   559 
   560     ///Returns \c false if there are nodes to be processed.
   561 
   562     ///Returns \c false if there are nodes to be processed
   563     ///in the queue.
   564     bool emptyQueue() const { return _queue_tail==_queue_head; }
   565 
   566     ///Returns the number of the nodes to be processed.
   567 
   568     ///Returns the number of the nodes to be processed
   569     ///in the queue.
   570     int queueSize() const { return _queue_head-_queue_tail; }
   571 
   572     ///Executes the algorithm.
   573 
   574     ///Executes the algorithm.
   575     ///
   576     ///This method runs the %BFS algorithm from the root node(s)
   577     ///in order to compute the shortest path to each node.
   578     ///
   579     ///The algorithm computes
   580     ///- the shortest path tree (forest),
   581     ///- the distance of each node from the root(s).
   582     ///
   583     ///\pre init() must be called and at least one root node should be
   584     ///added with addSource() before using this function.
   585     ///
   586     ///\note <tt>b.start()</tt> is just a shortcut of the following code.
   587     ///\code
   588     ///  while ( !b.emptyQueue() ) {
   589     ///    b.processNextNode();
   590     ///  }
   591     ///\endcode
   592     void start()
   593     {
   594       while ( !emptyQueue() ) processNextNode();
   595     }
   596 
   597     ///Executes the algorithm until the given target node is reached.
   598 
   599     ///Executes the algorithm until the given target node is reached.
   600     ///
   601     ///This method runs the %BFS algorithm from the root node(s)
   602     ///in order to compute the shortest path to \c t.
   603     ///
   604     ///The algorithm computes
   605     ///- the shortest path to \c t,
   606     ///- the distance of \c t from the root(s).
   607     ///
   608     ///\pre init() must be called and at least one root node should be
   609     ///added with addSource() before using this function.
   610     ///
   611     ///\note <tt>b.start(t)</tt> is just a shortcut of the following code.
   612     ///\code
   613     ///  bool reach = false;
   614     ///  while ( !b.emptyQueue() && !reach ) {
   615     ///    b.processNextNode(t, reach);
   616     ///  }
   617     ///\endcode
   618     void start(Node t)
   619     {
   620       bool reach = false;
   621       while ( !emptyQueue() && !reach ) processNextNode(t, reach);
   622     }
   623 
   624     ///Executes the algorithm until a condition is met.
   625 
   626     ///Executes the algorithm until a condition is met.
   627     ///
   628     ///This method runs the %BFS algorithm from the root node(s) in
   629     ///order to compute the shortest path to a node \c v with
   630     /// <tt>nm[v]</tt> true, if such a node can be found.
   631     ///
   632     ///\param nm A \c bool (or convertible) node map. The algorithm
   633     ///will stop when it reaches a node \c v with <tt>nm[v]</tt> true.
   634     ///
   635     ///\return The reached node \c v with <tt>nm[v]</tt> true or
   636     ///\c INVALID if no such node was found.
   637     ///
   638     ///\pre init() must be called and at least one root node should be
   639     ///added with addSource() before using this function.
   640     ///
   641     ///\note <tt>b.start(nm)</tt> is just a shortcut of the following code.
   642     ///\code
   643     ///  Node rnode = INVALID;
   644     ///  while ( !b.emptyQueue() && rnode == INVALID ) {
   645     ///    b.processNextNode(nm, rnode);
   646     ///  }
   647     ///  return rnode;
   648     ///\endcode
   649     template<class NodeBoolMap>
   650     Node start(const NodeBoolMap &nm)
   651     {
   652       Node rnode = INVALID;
   653       while ( !emptyQueue() && rnode == INVALID ) {
   654         processNextNode(nm, rnode);
   655       }
   656       return rnode;
   657     }
   658 
   659     ///Runs the algorithm from the given source node.
   660 
   661     ///This method runs the %BFS algorithm from node \c s
   662     ///in order to compute the shortest path to each node.
   663     ///
   664     ///The algorithm computes
   665     ///- the shortest path tree,
   666     ///- the distance of each node from the root.
   667     ///
   668     ///\note <tt>b.run(s)</tt> is just a shortcut of the following code.
   669     ///\code
   670     ///  b.init();
   671     ///  b.addSource(s);
   672     ///  b.start();
   673     ///\endcode
   674     void run(Node s) {
   675       init();
   676       addSource(s);
   677       start();
   678     }
   679 
   680     ///Finds the shortest path between \c s and \c t.
   681 
   682     ///This method runs the %BFS algorithm from node \c s
   683     ///in order to compute the shortest path to node \c t
   684     ///(it stops searching when \c t is processed).
   685     ///
   686     ///\return \c true if \c t is reachable form \c s.
   687     ///
   688     ///\note Apart from the return value, <tt>b.run(s,t)</tt> is just a
   689     ///shortcut of the following code.
   690     ///\code
   691     ///  b.init();
   692     ///  b.addSource(s);
   693     ///  b.start(t);
   694     ///\endcode
   695     bool run(Node s,Node t) {
   696       init();
   697       addSource(s);
   698       start(t);
   699       return reached(t);
   700     }
   701 
   702     ///Runs the algorithm to visit all nodes in the digraph.
   703 
   704     ///This method runs the %BFS algorithm in order to visit all nodes
   705     ///in the digraph.
   706     ///
   707     ///\note <tt>b.run(s)</tt> is just a shortcut of the following code.
   708     ///\code
   709     ///  b.init();
   710     ///  for (NodeIt n(gr); n != INVALID; ++n) {
   711     ///    if (!b.reached(n)) {
   712     ///      b.addSource(n);
   713     ///      b.start();
   714     ///    }
   715     ///  }
   716     ///\endcode
   717     void run() {
   718       init();
   719       for (NodeIt n(*G); n != INVALID; ++n) {
   720         if (!reached(n)) {
   721           addSource(n);
   722           start();
   723         }
   724       }
   725     }
   726 
   727     ///@}
   728 
   729     ///\name Query Functions
   730     ///The results of the BFS algorithm can be obtained using these
   731     ///functions.\n
   732     ///Either \ref run(Node) "run()" or \ref start() should be called
   733     ///before using them.
   734 
   735     ///@{
   736 
   737     ///The shortest path to the given node.
   738 
   739     ///Returns the shortest path to the given node from the root(s).
   740     ///
   741     ///\warning \c t should be reached from the root(s).
   742     ///
   743     ///\pre Either \ref run(Node) "run()" or \ref init()
   744     ///must be called before using this function.
   745     Path path(Node t) const { return Path(*G, *_pred, t); }
   746 
   747     ///The distance of the given node from the root(s).
   748 
   749     ///Returns the distance of the given node from the root(s).
   750     ///
   751     ///\warning If node \c v is not reached from the root(s), then
   752     ///the return value of this function is undefined.
   753     ///
   754     ///\pre Either \ref run(Node) "run()" or \ref init()
   755     ///must be called before using this function.
   756     int dist(Node v) const { return (*_dist)[v]; }
   757 
   758     ///\brief Returns the 'previous arc' of the shortest path tree for
   759     ///the given node.
   760     ///
   761     ///This function returns the 'previous arc' of the shortest path
   762     ///tree for the node \c v, i.e. it returns the last arc of a
   763     ///shortest path from a root to \c v. It is \c INVALID if \c v
   764     ///is not reached from the root(s) or if \c v is a root.
   765     ///
   766     ///The shortest path tree used here is equal to the shortest path
   767     ///tree used in \ref predNode() and \ref predMap().
   768     ///
   769     ///\pre Either \ref run(Node) "run()" or \ref init()
   770     ///must be called before using this function.
   771     Arc predArc(Node v) const { return (*_pred)[v];}
   772 
   773     ///\brief Returns the 'previous node' of the shortest path tree for
   774     ///the given node.
   775     ///
   776     ///This function returns the 'previous node' of the shortest path
   777     ///tree for the node \c v, i.e. it returns the last but one node
   778     ///of a shortest path from a root to \c v. It is \c INVALID
   779     ///if \c v is not reached from the root(s) or if \c v is a root.
   780     ///
   781     ///The shortest path tree used here is equal to the shortest path
   782     ///tree used in \ref predArc() and \ref predMap().
   783     ///
   784     ///\pre Either \ref run(Node) "run()" or \ref init()
   785     ///must be called before using this function.
   786     Node predNode(Node v) const { return (*_pred)[v]==INVALID ? INVALID:
   787                                   G->source((*_pred)[v]); }
   788 
   789     ///\brief Returns a const reference to the node map that stores the
   790     /// distances of the nodes.
   791     ///
   792     ///Returns a const reference to the node map that stores the distances
   793     ///of the nodes calculated by the algorithm.
   794     ///
   795     ///\pre Either \ref run(Node) "run()" or \ref init()
   796     ///must be called before using this function.
   797     const DistMap &distMap() const { return *_dist;}
   798 
   799     ///\brief Returns a const reference to the node map that stores the
   800     ///predecessor arcs.
   801     ///
   802     ///Returns a const reference to the node map that stores the predecessor
   803     ///arcs, which form the shortest path tree (forest).
   804     ///
   805     ///\pre Either \ref run(Node) "run()" or \ref init()
   806     ///must be called before using this function.
   807     const PredMap &predMap() const { return *_pred;}
   808 
   809     ///Checks if the given node is reached from the root(s).
   810 
   811     ///Returns \c true if \c v is reached from the root(s).
   812     ///
   813     ///\pre Either \ref run(Node) "run()" or \ref init()
   814     ///must be called before using this function.
   815     bool reached(Node v) const { return (*_reached)[v]; }
   816 
   817     ///@}
   818   };
   819 
   820   ///Default traits class of bfs() function.
   821 
   822   ///Default traits class of bfs() function.
   823   ///\tparam GR Digraph type.
   824   template<class GR>
   825   struct BfsWizardDefaultTraits
   826   {
   827     ///The type of the digraph the algorithm runs on.
   828     typedef GR Digraph;
   829 
   830     ///\brief The type of the map that stores the predecessor
   831     ///arcs of the shortest paths.
   832     ///
   833     ///The type of the map that stores the predecessor
   834     ///arcs of the shortest paths.
   835     ///It must conform to the \ref concepts::WriteMap "WriteMap" concept.
   836     typedef typename Digraph::template NodeMap<typename Digraph::Arc> PredMap;
   837     ///Instantiates a PredMap.
   838 
   839     ///This function instantiates a PredMap.
   840     ///\param g is the digraph, to which we would like to define the
   841     ///PredMap.
   842     static PredMap *createPredMap(const Digraph &g)
   843     {
   844       return new PredMap(g);
   845     }
   846 
   847     ///The type of the map that indicates which nodes are processed.
   848 
   849     ///The type of the map that indicates which nodes are processed.
   850     ///It must conform to the \ref concepts::WriteMap "WriteMap" concept.
   851     ///By default, it is a NullMap.
   852     typedef NullMap<typename Digraph::Node,bool> ProcessedMap;
   853     ///Instantiates a ProcessedMap.
   854 
   855     ///This function instantiates a ProcessedMap.
   856     ///\param g is the digraph, to which
   857     ///we would like to define the ProcessedMap.
   858 #ifdef DOXYGEN
   859     static ProcessedMap *createProcessedMap(const Digraph &g)
   860 #else
   861     static ProcessedMap *createProcessedMap(const Digraph &)
   862 #endif
   863     {
   864       return new ProcessedMap();
   865     }
   866 
   867     ///The type of the map that indicates which nodes are reached.
   868 
   869     ///The type of the map that indicates which nodes are reached.
   870     ///It must conform to the \ref concepts::ReadWriteMap "ReadWriteMap" concept.
   871     typedef typename Digraph::template NodeMap<bool> ReachedMap;
   872     ///Instantiates a ReachedMap.
   873 
   874     ///This function instantiates a ReachedMap.
   875     ///\param g is the digraph, to which
   876     ///we would like to define the ReachedMap.
   877     static ReachedMap *createReachedMap(const Digraph &g)
   878     {
   879       return new ReachedMap(g);
   880     }
   881 
   882     ///The type of the map that stores the distances of the nodes.
   883 
   884     ///The type of the map that stores the distances of the nodes.
   885     ///It must conform to the \ref concepts::WriteMap "WriteMap" concept.
   886     typedef typename Digraph::template NodeMap<int> DistMap;
   887     ///Instantiates a DistMap.
   888 
   889     ///This function instantiates a DistMap.
   890     ///\param g is the digraph, to which we would like to define
   891     ///the DistMap
   892     static DistMap *createDistMap(const Digraph &g)
   893     {
   894       return new DistMap(g);
   895     }
   896 
   897     ///The type of the shortest paths.
   898 
   899     ///The type of the shortest paths.
   900     ///It must conform to the \ref concepts::Path "Path" concept.
   901     typedef lemon::Path<Digraph> Path;
   902   };
   903 
   904   /// Default traits class used by BfsWizard
   905 
   906   /// Default traits class used by BfsWizard.
   907   /// \tparam GR The type of the digraph.
   908   template<class GR>
   909   class BfsWizardBase : public BfsWizardDefaultTraits<GR>
   910   {
   911 
   912     typedef BfsWizardDefaultTraits<GR> Base;
   913   protected:
   914     //The type of the nodes in the digraph.
   915     typedef typename Base::Digraph::Node Node;
   916 
   917     //Pointer to the digraph the algorithm runs on.
   918     void *_g;
   919     //Pointer to the map of reached nodes.
   920     void *_reached;
   921     //Pointer to the map of processed nodes.
   922     void *_processed;
   923     //Pointer to the map of predecessors arcs.
   924     void *_pred;
   925     //Pointer to the map of distances.
   926     void *_dist;
   927     //Pointer to the shortest path to the target node.
   928     void *_path;
   929     //Pointer to the distance of the target node.
   930     int *_di;
   931 
   932     public:
   933     /// Constructor.
   934 
   935     /// This constructor does not require parameters, it initiates
   936     /// all of the attributes to \c 0.
   937     BfsWizardBase() : _g(0), _reached(0), _processed(0), _pred(0),
   938                       _dist(0), _path(0), _di(0) {}
   939 
   940     /// Constructor.
   941 
   942     /// This constructor requires one parameter,
   943     /// others are initiated to \c 0.
   944     /// \param g The digraph the algorithm runs on.
   945     BfsWizardBase(const GR &g) :
   946       _g(reinterpret_cast<void*>(const_cast<GR*>(&g))),
   947       _reached(0), _processed(0), _pred(0), _dist(0),  _path(0), _di(0) {}
   948 
   949   };
   950 
   951   /// Auxiliary class for the function-type interface of BFS algorithm.
   952 
   953   /// This auxiliary class is created to implement the
   954   /// \ref bfs() "function-type interface" of \ref Bfs algorithm.
   955   /// It does not have own \ref run(Node) "run()" method, it uses the
   956   /// functions and features of the plain \ref Bfs.
   957   ///
   958   /// This class should only be used through the \ref bfs() function,
   959   /// which makes it easier to use the algorithm.
   960   template<class TR>
   961   class BfsWizard : public TR
   962   {
   963     typedef TR Base;
   964 
   965     typedef typename TR::Digraph Digraph;
   966 
   967     typedef typename Digraph::Node Node;
   968     typedef typename Digraph::NodeIt NodeIt;
   969     typedef typename Digraph::Arc Arc;
   970     typedef typename Digraph::OutArcIt OutArcIt;
   971 
   972     typedef typename TR::PredMap PredMap;
   973     typedef typename TR::DistMap DistMap;
   974     typedef typename TR::ReachedMap ReachedMap;
   975     typedef typename TR::ProcessedMap ProcessedMap;
   976     typedef typename TR::Path Path;
   977 
   978   public:
   979 
   980     /// Constructor.
   981     BfsWizard() : TR() {}
   982 
   983     /// Constructor that requires parameters.
   984 
   985     /// Constructor that requires parameters.
   986     /// These parameters will be the default values for the traits class.
   987     /// \param g The digraph the algorithm runs on.
   988     BfsWizard(const Digraph &g) :
   989       TR(g) {}
   990 
   991     ///Copy constructor
   992     BfsWizard(const TR &b) : TR(b) {}
   993 
   994     ~BfsWizard() {}
   995 
   996     ///Runs BFS algorithm from the given source node.
   997 
   998     ///This method runs BFS algorithm from node \c s
   999     ///in order to compute the shortest path to each node.
  1000     void run(Node s)
  1001     {
  1002       Bfs<Digraph,TR> alg(*reinterpret_cast<const Digraph*>(Base::_g));
  1003       if (Base::_pred)
  1004         alg.predMap(*reinterpret_cast<PredMap*>(Base::_pred));
  1005       if (Base::_dist)
  1006         alg.distMap(*reinterpret_cast<DistMap*>(Base::_dist));
  1007       if (Base::_reached)
  1008         alg.reachedMap(*reinterpret_cast<ReachedMap*>(Base::_reached));
  1009       if (Base::_processed)
  1010         alg.processedMap(*reinterpret_cast<ProcessedMap*>(Base::_processed));
  1011       if (s!=INVALID)
  1012         alg.run(s);
  1013       else
  1014         alg.run();
  1015     }
  1016 
  1017     ///Finds the shortest path between \c s and \c t.
  1018 
  1019     ///This method runs BFS algorithm from node \c s
  1020     ///in order to compute the shortest path to node \c t
  1021     ///(it stops searching when \c t is processed).
  1022     ///
  1023     ///\return \c true if \c t is reachable form \c s.
  1024     bool run(Node s, Node t)
  1025     {
  1026       Bfs<Digraph,TR> alg(*reinterpret_cast<const Digraph*>(Base::_g));
  1027       if (Base::_pred)
  1028         alg.predMap(*reinterpret_cast<PredMap*>(Base::_pred));
  1029       if (Base::_dist)
  1030         alg.distMap(*reinterpret_cast<DistMap*>(Base::_dist));
  1031       if (Base::_reached)
  1032         alg.reachedMap(*reinterpret_cast<ReachedMap*>(Base::_reached));
  1033       if (Base::_processed)
  1034         alg.processedMap(*reinterpret_cast<ProcessedMap*>(Base::_processed));
  1035       alg.run(s,t);
  1036       if (Base::_path)
  1037         *reinterpret_cast<Path*>(Base::_path) = alg.path(t);
  1038       if (Base::_di)
  1039         *Base::_di = alg.dist(t);
  1040       return alg.reached(t);
  1041     }
  1042 
  1043     ///Runs BFS algorithm to visit all nodes in the digraph.
  1044 
  1045     ///This method runs BFS algorithm in order to visit all nodes
  1046     ///in the digraph.
  1047     void run()
  1048     {
  1049       run(INVALID);
  1050     }
  1051 
  1052     template<class T>
  1053     struct SetPredMapBase : public Base {
  1054       typedef T PredMap;
  1055       static PredMap *createPredMap(const Digraph &) { return 0; };
  1056       SetPredMapBase(const TR &b) : TR(b) {}
  1057     };
  1058 
  1059     ///\brief \ref named-templ-param "Named parameter" for setting
  1060     ///the predecessor map.
  1061     ///
  1062     ///\ref named-templ-param "Named parameter" function for setting
  1063     ///the map that stores the predecessor arcs of the nodes.
  1064     template<class T>
  1065     BfsWizard<SetPredMapBase<T> > predMap(const T &t)
  1066     {
  1067       Base::_pred=reinterpret_cast<void*>(const_cast<T*>(&t));
  1068       return BfsWizard<SetPredMapBase<T> >(*this);
  1069     }
  1070 
  1071     template<class T>
  1072     struct SetReachedMapBase : public Base {
  1073       typedef T ReachedMap;
  1074       static ReachedMap *createReachedMap(const Digraph &) { return 0; };
  1075       SetReachedMapBase(const TR &b) : TR(b) {}
  1076     };
  1077 
  1078     ///\brief \ref named-templ-param "Named parameter" for setting
  1079     ///the reached map.
  1080     ///
  1081     ///\ref named-templ-param "Named parameter" function for setting
  1082     ///the map that indicates which nodes are reached.
  1083     template<class T>
  1084     BfsWizard<SetReachedMapBase<T> > reachedMap(const T &t)
  1085     {
  1086       Base::_reached=reinterpret_cast<void*>(const_cast<T*>(&t));
  1087       return BfsWizard<SetReachedMapBase<T> >(*this);
  1088     }
  1089 
  1090     template<class T>
  1091     struct SetDistMapBase : public Base {
  1092       typedef T DistMap;
  1093       static DistMap *createDistMap(const Digraph &) { return 0; };
  1094       SetDistMapBase(const TR &b) : TR(b) {}
  1095     };
  1096 
  1097     ///\brief \ref named-templ-param "Named parameter" for setting
  1098     ///the distance map.
  1099     ///
  1100     ///\ref named-templ-param "Named parameter" function for setting
  1101     ///the map that stores the distances of the nodes calculated
  1102     ///by the algorithm.
  1103     template<class T>
  1104     BfsWizard<SetDistMapBase<T> > distMap(const T &t)
  1105     {
  1106       Base::_dist=reinterpret_cast<void*>(const_cast<T*>(&t));
  1107       return BfsWizard<SetDistMapBase<T> >(*this);
  1108     }
  1109 
  1110     template<class T>
  1111     struct SetProcessedMapBase : public Base {
  1112       typedef T ProcessedMap;
  1113       static ProcessedMap *createProcessedMap(const Digraph &) { return 0; };
  1114       SetProcessedMapBase(const TR &b) : TR(b) {}
  1115     };
  1116 
  1117     ///\brief \ref named-func-param "Named parameter" for setting
  1118     ///the processed map.
  1119     ///
  1120     ///\ref named-templ-param "Named parameter" function for setting
  1121     ///the map that indicates which nodes are processed.
  1122     template<class T>
  1123     BfsWizard<SetProcessedMapBase<T> > processedMap(const T &t)
  1124     {
  1125       Base::_processed=reinterpret_cast<void*>(const_cast<T*>(&t));
  1126       return BfsWizard<SetProcessedMapBase<T> >(*this);
  1127     }
  1128 
  1129     template<class T>
  1130     struct SetPathBase : public Base {
  1131       typedef T Path;
  1132       SetPathBase(const TR &b) : TR(b) {}
  1133     };
  1134     ///\brief \ref named-func-param "Named parameter"
  1135     ///for getting the shortest path to the target node.
  1136     ///
  1137     ///\ref named-func-param "Named parameter"
  1138     ///for getting the shortest path to the target node.
  1139     template<class T>
  1140     BfsWizard<SetPathBase<T> > path(const T &t)
  1141     {
  1142       Base::_path=reinterpret_cast<void*>(const_cast<T*>(&t));
  1143       return BfsWizard<SetPathBase<T> >(*this);
  1144     }
  1145 
  1146     ///\brief \ref named-func-param "Named parameter"
  1147     ///for getting the distance of the target node.
  1148     ///
  1149     ///\ref named-func-param "Named parameter"
  1150     ///for getting the distance of the target node.
  1151     BfsWizard dist(const int &d)
  1152     {
  1153       Base::_di=const_cast<int*>(&d);
  1154       return *this;
  1155     }
  1156 
  1157   };
  1158 
  1159   ///Function-type interface for BFS algorithm.
  1160 
  1161   /// \ingroup search
  1162   ///Function-type interface for BFS algorithm.
  1163   ///
  1164   ///This function also has several \ref named-func-param "named parameters",
  1165   ///they are declared as the members of class \ref BfsWizard.
  1166   ///The following examples show how to use these parameters.
  1167   ///\code
  1168   ///  // Compute shortest path from node s to each node
  1169   ///  bfs(g).predMap(preds).distMap(dists).run(s);
  1170   ///
  1171   ///  // Compute shortest path from s to t
  1172   ///  bool reached = bfs(g).path(p).dist(d).run(s,t);
  1173   ///\endcode
  1174   ///\warning Don't forget to put the \ref BfsWizard::run(Node) "run()"
  1175   ///to the end of the parameter list.
  1176   ///\sa BfsWizard
  1177   ///\sa Bfs
  1178   template<class GR>
  1179   BfsWizard<BfsWizardBase<GR> >
  1180   bfs(const GR &digraph)
  1181   {
  1182     return BfsWizard<BfsWizardBase<GR> >(digraph);
  1183   }
  1184 
  1185 #ifdef DOXYGEN
  1186   /// \brief Visitor class for BFS.
  1187   ///
  1188   /// This class defines the interface of the BfsVisit events, and
  1189   /// it could be the base of a real visitor class.
  1190   template <typename GR>
  1191   struct BfsVisitor {
  1192     typedef GR Digraph;
  1193     typedef typename Digraph::Arc Arc;
  1194     typedef typename Digraph::Node Node;
  1195     /// \brief Called for the source node(s) of the BFS.
  1196     ///
  1197     /// This function is called for the source node(s) of the BFS.
  1198     void start(const Node& node) {}
  1199     /// \brief Called when a node is reached first time.
  1200     ///
  1201     /// This function is called when a node is reached first time.
  1202     void reach(const Node& node) {}
  1203     /// \brief Called when a node is processed.
  1204     ///
  1205     /// This function is called when a node is processed.
  1206     void process(const Node& node) {}
  1207     /// \brief Called when an arc reaches a new node.
  1208     ///
  1209     /// This function is called when the BFS finds an arc whose target node
  1210     /// is not reached yet.
  1211     void discover(const Arc& arc) {}
  1212     /// \brief Called when an arc is examined but its target node is
  1213     /// already discovered.
  1214     ///
  1215     /// This function is called when an arc is examined but its target node is
  1216     /// already discovered.
  1217     void examine(const Arc& arc) {}
  1218   };
  1219 #else
  1220   template <typename GR>
  1221   struct BfsVisitor {
  1222     typedef GR Digraph;
  1223     typedef typename Digraph::Arc Arc;
  1224     typedef typename Digraph::Node Node;
  1225     void start(const Node&) {}
  1226     void reach(const Node&) {}
  1227     void process(const Node&) {}
  1228     void discover(const Arc&) {}
  1229     void examine(const Arc&) {}
  1230 
  1231     template <typename _Visitor>
  1232     struct Constraints {
  1233       void constraints() {
  1234         Arc arc;
  1235         Node node;
  1236         visitor.start(node);
  1237         visitor.reach(node);
  1238         visitor.process(node);
  1239         visitor.discover(arc);
  1240         visitor.examine(arc);
  1241       }
  1242       _Visitor& visitor;
  1243     };
  1244   };
  1245 #endif
  1246 
  1247   /// \brief Default traits class of BfsVisit class.
  1248   ///
  1249   /// Default traits class of BfsVisit class.
  1250   /// \tparam GR The type of the digraph the algorithm runs on.
  1251   template<class GR>
  1252   struct BfsVisitDefaultTraits {
  1253 
  1254     /// \brief The type of the digraph the algorithm runs on.
  1255     typedef GR Digraph;
  1256 
  1257     /// \brief The type of the map that indicates which nodes are reached.
  1258     ///
  1259     /// The type of the map that indicates which nodes are reached.
  1260     /// It must conform to the \ref concepts::ReadWriteMap "ReadWriteMap" concept.
  1261     typedef typename Digraph::template NodeMap<bool> ReachedMap;
  1262 
  1263     /// \brief Instantiates a ReachedMap.
  1264     ///
  1265     /// This function instantiates a ReachedMap.
  1266     /// \param digraph is the digraph, to which
  1267     /// we would like to define the ReachedMap.
  1268     static ReachedMap *createReachedMap(const Digraph &digraph) {
  1269       return new ReachedMap(digraph);
  1270     }
  1271 
  1272   };
  1273 
  1274   /// \ingroup search
  1275   ///
  1276   /// \brief BFS algorithm class with visitor interface.
  1277   ///
  1278   /// This class provides an efficient implementation of the BFS algorithm
  1279   /// with visitor interface.
  1280   ///
  1281   /// The BfsVisit class provides an alternative interface to the Bfs
  1282   /// class. It works with callback mechanism, the BfsVisit object calls
  1283   /// the member functions of the \c Visitor class on every BFS event.
  1284   ///
  1285   /// This interface of the BFS algorithm should be used in special cases
  1286   /// when extra actions have to be performed in connection with certain
  1287   /// events of the BFS algorithm. Otherwise consider to use Bfs or bfs()
  1288   /// instead.
  1289   ///
  1290   /// \tparam GR The type of the digraph the algorithm runs on.
  1291   /// The default type is \ref ListDigraph.
  1292   /// The value of GR is not used directly by \ref BfsVisit,
  1293   /// it is only passed to \ref BfsVisitDefaultTraits.
  1294   /// \tparam VS The Visitor type that is used by the algorithm.
  1295   /// \ref BfsVisitor "BfsVisitor<GR>" is an empty visitor, which
  1296   /// does not observe the BFS events. If you want to observe the BFS
  1297   /// events, you should implement your own visitor class.
  1298   /// \tparam TR Traits class to set various data types used by the
  1299   /// algorithm. The default traits class is
  1300   /// \ref BfsVisitDefaultTraits "BfsVisitDefaultTraits<GR>".
  1301   /// See \ref BfsVisitDefaultTraits for the documentation of
  1302   /// a BFS visit traits class.
  1303 #ifdef DOXYGEN
  1304   template <typename GR, typename VS, typename TR>
  1305 #else
  1306   template <typename GR = ListDigraph,
  1307             typename VS = BfsVisitor<GR>,
  1308             typename TR = BfsVisitDefaultTraits<GR> >
  1309 #endif
  1310   class BfsVisit {
  1311   public:
  1312 
  1313     ///The traits class.
  1314     typedef TR Traits;
  1315 
  1316     ///The type of the digraph the algorithm runs on.
  1317     typedef typename Traits::Digraph Digraph;
  1318 
  1319     ///The visitor type used by the algorithm.
  1320     typedef VS Visitor;
  1321 
  1322     ///The type of the map that indicates which nodes are reached.
  1323     typedef typename Traits::ReachedMap ReachedMap;
  1324 
  1325   private:
  1326 
  1327     typedef typename Digraph::Node Node;
  1328     typedef typename Digraph::NodeIt NodeIt;
  1329     typedef typename Digraph::Arc Arc;
  1330     typedef typename Digraph::OutArcIt OutArcIt;
  1331 
  1332     //Pointer to the underlying digraph.
  1333     const Digraph *_digraph;
  1334     //Pointer to the visitor object.
  1335     Visitor *_visitor;
  1336     //Pointer to the map of reached status of the nodes.
  1337     ReachedMap *_reached;
  1338     //Indicates if _reached is locally allocated (true) or not.
  1339     bool local_reached;
  1340 
  1341     std::vector<typename Digraph::Node> _list;
  1342     int _list_front, _list_back;
  1343 
  1344     //Creates the maps if necessary.
  1345     void create_maps() {
  1346       if(!_reached) {
  1347         local_reached = true;
  1348         _reached = Traits::createReachedMap(*_digraph);
  1349       }
  1350     }
  1351 
  1352   protected:
  1353 
  1354     BfsVisit() {}
  1355 
  1356   public:
  1357 
  1358     typedef BfsVisit Create;
  1359 
  1360     /// \name Named Template Parameters
  1361 
  1362     ///@{
  1363     template <class T>
  1364     struct SetReachedMapTraits : public Traits {
  1365       typedef T ReachedMap;
  1366       static ReachedMap *createReachedMap(const Digraph &digraph) {
  1367         LEMON_ASSERT(false, "ReachedMap is not initialized");
  1368         return 0; // ignore warnings
  1369       }
  1370     };
  1371     /// \brief \ref named-templ-param "Named parameter" for setting
  1372     /// ReachedMap type.
  1373     ///
  1374     /// \ref named-templ-param "Named parameter" for setting ReachedMap type.
  1375     template <class T>
  1376     struct SetReachedMap : public BfsVisit< Digraph, Visitor,
  1377                                             SetReachedMapTraits<T> > {
  1378       typedef BfsVisit< Digraph, Visitor, SetReachedMapTraits<T> > Create;
  1379     };
  1380     ///@}
  1381 
  1382   public:
  1383 
  1384     /// \brief Constructor.
  1385     ///
  1386     /// Constructor.
  1387     ///
  1388     /// \param digraph The digraph the algorithm runs on.
  1389     /// \param visitor The visitor object of the algorithm.
  1390     BfsVisit(const Digraph& digraph, Visitor& visitor)
  1391       : _digraph(&digraph), _visitor(&visitor),
  1392         _reached(0), local_reached(false) {}
  1393 
  1394     /// \brief Destructor.
  1395     ~BfsVisit() {
  1396       if(local_reached) delete _reached;
  1397     }
  1398 
  1399     /// \brief Sets the map that indicates which nodes are reached.
  1400     ///
  1401     /// Sets the map that indicates which nodes are reached.
  1402     /// If you don't use this function before calling \ref run(Node) "run()"
  1403     /// or \ref init(), an instance will be allocated automatically.
  1404     /// The destructor deallocates this automatically allocated map,
  1405     /// of course.
  1406     /// \return <tt> (*this) </tt>
  1407     BfsVisit &reachedMap(ReachedMap &m) {
  1408       if(local_reached) {
  1409         delete _reached;
  1410         local_reached = false;
  1411       }
  1412       _reached = &m;
  1413       return *this;
  1414     }
  1415 
  1416   public:
  1417 
  1418     /// \name Execution Control
  1419     /// The simplest way to execute the BFS algorithm is to use one of the
  1420     /// member functions called \ref run(Node) "run()".\n
  1421     /// If you need better control on the execution, you have to call
  1422     /// \ref init() first, then you can add several source nodes with
  1423     /// \ref addSource(). Finally the actual path computation can be
  1424     /// performed with one of the \ref start() functions.
  1425 
  1426     /// @{
  1427 
  1428     /// \brief Initializes the internal data structures.
  1429     ///
  1430     /// Initializes the internal data structures.
  1431     void init() {
  1432       create_maps();
  1433       _list.resize(countNodes(*_digraph));
  1434       _list_front = _list_back = -1;
  1435       for (NodeIt u(*_digraph) ; u != INVALID ; ++u) {
  1436         _reached->set(u, false);
  1437       }
  1438     }
  1439 
  1440     /// \brief Adds a new source node.
  1441     ///
  1442     /// Adds a new source node to the set of nodes to be processed.
  1443     void addSource(Node s) {
  1444       if(!(*_reached)[s]) {
  1445           _reached->set(s,true);
  1446           _visitor->start(s);
  1447           _visitor->reach(s);
  1448           _list[++_list_back] = s;
  1449         }
  1450     }
  1451 
  1452     /// \brief Processes the next node.
  1453     ///
  1454     /// Processes the next node.
  1455     ///
  1456     /// \return The processed node.
  1457     ///
  1458     /// \pre The queue must not be empty.
  1459     Node processNextNode() {
  1460       Node n = _list[++_list_front];
  1461       _visitor->process(n);
  1462       Arc e;
  1463       for (_digraph->firstOut(e, n); e != INVALID; _digraph->nextOut(e)) {
  1464         Node m = _digraph->target(e);
  1465         if (!(*_reached)[m]) {
  1466           _visitor->discover(e);
  1467           _visitor->reach(m);
  1468           _reached->set(m, true);
  1469           _list[++_list_back] = m;
  1470         } else {
  1471           _visitor->examine(e);
  1472         }
  1473       }
  1474       return n;
  1475     }
  1476 
  1477     /// \brief Processes the next node.
  1478     ///
  1479     /// Processes the next node and checks if the given target node
  1480     /// is reached. If the target node is reachable from the processed
  1481     /// node, then the \c reach parameter will be set to \c true.
  1482     ///
  1483     /// \param target The target node.
  1484     /// \retval reach Indicates if the target node is reached.
  1485     /// It should be initially \c false.
  1486     ///
  1487     /// \return The processed node.
  1488     ///
  1489     /// \pre The queue must not be empty.
  1490     Node processNextNode(Node target, bool& reach) {
  1491       Node n = _list[++_list_front];
  1492       _visitor->process(n);
  1493       Arc e;
  1494       for (_digraph->firstOut(e, n); e != INVALID; _digraph->nextOut(e)) {
  1495         Node m = _digraph->target(e);
  1496         if (!(*_reached)[m]) {
  1497           _visitor->discover(e);
  1498           _visitor->reach(m);
  1499           _reached->set(m, true);
  1500           _list[++_list_back] = m;
  1501           reach = reach || (target == m);
  1502         } else {
  1503           _visitor->examine(e);
  1504         }
  1505       }
  1506       return n;
  1507     }
  1508 
  1509     /// \brief Processes the next node.
  1510     ///
  1511     /// Processes the next node and checks if at least one of reached
  1512     /// nodes has \c true value in the \c nm node map. If one node
  1513     /// with \c true value is reachable from the processed node, then the
  1514     /// \c rnode parameter will be set to the first of such nodes.
  1515     ///
  1516     /// \param nm A \c bool (or convertible) node map that indicates the
  1517     /// possible targets.
  1518     /// \retval rnode The reached target node.
  1519     /// It should be initially \c INVALID.
  1520     ///
  1521     /// \return The processed node.
  1522     ///
  1523     /// \pre The queue must not be empty.
  1524     template <typename NM>
  1525     Node processNextNode(const NM& nm, Node& rnode) {
  1526       Node n = _list[++_list_front];
  1527       _visitor->process(n);
  1528       Arc e;
  1529       for (_digraph->firstOut(e, n); e != INVALID; _digraph->nextOut(e)) {
  1530         Node m = _digraph->target(e);
  1531         if (!(*_reached)[m]) {
  1532           _visitor->discover(e);
  1533           _visitor->reach(m);
  1534           _reached->set(m, true);
  1535           _list[++_list_back] = m;
  1536           if (nm[m] && rnode == INVALID) rnode = m;
  1537         } else {
  1538           _visitor->examine(e);
  1539         }
  1540       }
  1541       return n;
  1542     }
  1543 
  1544     /// \brief The next node to be processed.
  1545     ///
  1546     /// Returns the next node to be processed or \c INVALID if the queue
  1547     /// is empty.
  1548     Node nextNode() const {
  1549       return _list_front != _list_back ? _list[_list_front + 1] : INVALID;
  1550     }
  1551 
  1552     /// \brief Returns \c false if there are nodes
  1553     /// to be processed.
  1554     ///
  1555     /// Returns \c false if there are nodes
  1556     /// to be processed in the queue.
  1557     bool emptyQueue() const { return _list_front == _list_back; }
  1558 
  1559     /// \brief Returns the number of the nodes to be processed.
  1560     ///
  1561     /// Returns the number of the nodes to be processed in the queue.
  1562     int queueSize() const { return _list_back - _list_front; }
  1563 
  1564     /// \brief Executes the algorithm.
  1565     ///
  1566     /// Executes the algorithm.
  1567     ///
  1568     /// This method runs the %BFS algorithm from the root node(s)
  1569     /// in order to compute the shortest path to each node.
  1570     ///
  1571     /// The algorithm computes
  1572     /// - the shortest path tree (forest),
  1573     /// - the distance of each node from the root(s).
  1574     ///
  1575     /// \pre init() must be called and at least one root node should be added
  1576     /// with addSource() before using this function.
  1577     ///
  1578     /// \note <tt>b.start()</tt> is just a shortcut of the following code.
  1579     /// \code
  1580     ///   while ( !b.emptyQueue() ) {
  1581     ///     b.processNextNode();
  1582     ///   }
  1583     /// \endcode
  1584     void start() {
  1585       while ( !emptyQueue() ) processNextNode();
  1586     }
  1587 
  1588     /// \brief Executes the algorithm until the given target node is reached.
  1589     ///
  1590     /// Executes the algorithm until the given target node is reached.
  1591     ///
  1592     /// This method runs the %BFS algorithm from the root node(s)
  1593     /// in order to compute the shortest path to \c t.
  1594     ///
  1595     /// The algorithm computes
  1596     /// - the shortest path to \c t,
  1597     /// - the distance of \c t from the root(s).
  1598     ///
  1599     /// \pre init() must be called and at least one root node should be
  1600     /// added with addSource() before using this function.
  1601     ///
  1602     /// \note <tt>b.start(t)</tt> is just a shortcut of the following code.
  1603     /// \code
  1604     ///   bool reach = false;
  1605     ///   while ( !b.emptyQueue() && !reach ) {
  1606     ///     b.processNextNode(t, reach);
  1607     ///   }
  1608     /// \endcode
  1609     void start(Node t) {
  1610       bool reach = false;
  1611       while ( !emptyQueue() && !reach ) processNextNode(t, reach);
  1612     }
  1613 
  1614     /// \brief Executes the algorithm until a condition is met.
  1615     ///
  1616     /// Executes the algorithm until a condition is met.
  1617     ///
  1618     /// This method runs the %BFS algorithm from the root node(s) in
  1619     /// order to compute the shortest path to a node \c v with
  1620     /// <tt>nm[v]</tt> true, if such a node can be found.
  1621     ///
  1622     /// \param nm must be a bool (or convertible) node map. The
  1623     /// algorithm will stop when it reaches a node \c v with
  1624     /// <tt>nm[v]</tt> true.
  1625     ///
  1626     /// \return The reached node \c v with <tt>nm[v]</tt> true or
  1627     /// \c INVALID if no such node was found.
  1628     ///
  1629     /// \pre init() must be called and at least one root node should be
  1630     /// added with addSource() before using this function.
  1631     ///
  1632     /// \note <tt>b.start(nm)</tt> is just a shortcut of the following code.
  1633     /// \code
  1634     ///   Node rnode = INVALID;
  1635     ///   while ( !b.emptyQueue() && rnode == INVALID ) {
  1636     ///     b.processNextNode(nm, rnode);
  1637     ///   }
  1638     ///   return rnode;
  1639     /// \endcode
  1640     template <typename NM>
  1641     Node start(const NM &nm) {
  1642       Node rnode = INVALID;
  1643       while ( !emptyQueue() && rnode == INVALID ) {
  1644         processNextNode(nm, rnode);
  1645       }
  1646       return rnode;
  1647     }
  1648 
  1649     /// \brief Runs the algorithm from the given source node.
  1650     ///
  1651     /// This method runs the %BFS algorithm from node \c s
  1652     /// in order to compute the shortest path to each node.
  1653     ///
  1654     /// The algorithm computes
  1655     /// - the shortest path tree,
  1656     /// - the distance of each node from the root.
  1657     ///
  1658     /// \note <tt>b.run(s)</tt> is just a shortcut of the following code.
  1659     ///\code
  1660     ///   b.init();
  1661     ///   b.addSource(s);
  1662     ///   b.start();
  1663     ///\endcode
  1664     void run(Node s) {
  1665       init();
  1666       addSource(s);
  1667       start();
  1668     }
  1669 
  1670     /// \brief Finds the shortest path between \c s and \c t.
  1671     ///
  1672     /// This method runs the %BFS algorithm from node \c s
  1673     /// in order to compute the shortest path to node \c t
  1674     /// (it stops searching when \c t is processed).
  1675     ///
  1676     /// \return \c true if \c t is reachable form \c s.
  1677     ///
  1678     /// \note Apart from the return value, <tt>b.run(s,t)</tt> is just a
  1679     /// shortcut of the following code.
  1680     ///\code
  1681     ///   b.init();
  1682     ///   b.addSource(s);
  1683     ///   b.start(t);
  1684     ///\endcode
  1685     bool run(Node s,Node t) {
  1686       init();
  1687       addSource(s);
  1688       start(t);
  1689       return reached(t);
  1690     }
  1691 
  1692     /// \brief Runs the algorithm to visit all nodes in the digraph.
  1693     ///
  1694     /// This method runs the %BFS algorithm in order to visit all nodes
  1695     /// in the digraph.
  1696     ///
  1697     /// \note <tt>b.run(s)</tt> is just a shortcut of the following code.
  1698     ///\code
  1699     ///  b.init();
  1700     ///  for (NodeIt n(gr); n != INVALID; ++n) {
  1701     ///    if (!b.reached(n)) {
  1702     ///      b.addSource(n);
  1703     ///      b.start();
  1704     ///    }
  1705     ///  }
  1706     ///\endcode
  1707     void run() {
  1708       init();
  1709       for (NodeIt it(*_digraph); it != INVALID; ++it) {
  1710         if (!reached(it)) {
  1711           addSource(it);
  1712           start();
  1713         }
  1714       }
  1715     }
  1716 
  1717     ///@}
  1718 
  1719     /// \name Query Functions
  1720     /// The results of the BFS algorithm can be obtained using these
  1721     /// functions.\n
  1722     /// Either \ref run(Node) "run()" or \ref start() should be called
  1723     /// before using them.
  1724 
  1725     ///@{
  1726 
  1727     /// \brief Checks if the given node is reached from the root(s).
  1728     ///
  1729     /// Returns \c true if \c v is reached from the root(s).
  1730     ///
  1731     /// \pre Either \ref run(Node) "run()" or \ref init()
  1732     /// must be called before using this function.
  1733     bool reached(Node v) const { return (*_reached)[v]; }
  1734 
  1735     ///@}
  1736 
  1737   };
  1738 
  1739 } //END OF NAMESPACE LEMON
  1740 
  1741 #endif