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