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