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