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