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