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