lemon/bfs.h
author Peter Kovacs <kpeter@inf.elte.hu>
Fri, 03 Apr 2009 18:59:15 +0200
changeset 608 6ac5d9ae1d3d
parent 440 88ed40ad0d4f
child 713 4ac30454f1c1
child 716 f47b6c94577e
child 975 b873350e6258
permissions -rw-r--r--
Support real types + numerical stability fix in NS (#254)

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