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