lemon/bfs.h
author Alpar Juttner <alpar@cs.elte.hu>
Fri, 18 Jul 2008 16:36:54 +0100
changeset 223 cfadfeef706f
parent 209 765619b7cbb2
child 220 a5d8c039f218
child 244 c30731a37f91
permissions -rw-r--r--
Fix compilation error when NDEBUG is defined.
     1 /* -*- mode: C++; indent-tabs-mode: nil; -*-
     2  *
     3  * This file is a part of LEMON, a generic C++ optimization library.
     4  *
     5  * Copyright (C) 2003-2008
     6  * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
     7  * (Egervary Research Group on Combinatorial Optimization, EGRES).
     8  *
     9  * Permission to use, modify and distribute this software is granted
    10  * provided that this copyright notice appears in all copies. For
    11  * precise terms see the accompanying LICENSE file.
    12  *
    13  * This software is provided "AS IS" with no warranty of any kind,
    14  * express or implied, and with no claim as to its suitability for any
    15  * purpose.
    16  *
    17  */
    18 
    19 #ifndef LEMON_BFS_H
    20 #define LEMON_BFS_H
    21 
    22 ///\ingroup search
    23 ///\file
    24 ///\brief Bfs algorithm.
    25 
    26 #include <lemon/list_graph.h>
    27 #include <lemon/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
   107     ///the \ref DistMap
   108     static DistMap *createDistMap(const GR &G)
   109     {
   110       return new DistMap(G);
   111     }
   112   };
   113 
   114   ///%BFS algorithm class.
   115 
   116   ///\ingroup search
   117   ///This class provides an efficient implementation of the %BFS algorithm.
   118   ///
   119   ///\tparam GR The digraph type the algorithm runs on. The default value is
   120   ///\ref ListDigraph. The value of GR is not used directly by Bfs, it
   121   ///is only passed to \ref BfsDefaultTraits.
   122   ///\tparam TR Traits class to set various data types used by the algorithm.
   123   ///The default traits class is
   124   ///\ref BfsDefaultTraits "BfsDefaultTraits<GR>".
   125   ///See \ref BfsDefaultTraits for the documentation of
   126   ///a Bfs traits class.
   127 
   128 #ifdef DOXYGEN
   129   template <typename GR,
   130             typename TR>
   131 #else
   132   template <typename GR=ListDigraph,
   133             typename TR=BfsDefaultTraits<GR> >
   134 #endif
   135   class Bfs {
   136   public:
   137     /**
   138      * \brief \ref Exception for uninitialized parameters.
   139      *
   140      * This error represents problems in the initialization
   141      * of the parameters of the algorithms.
   142      */
   143     class UninitializedParameter : public lemon::UninitializedParameter {
   144     public:
   145       virtual const char* what() const throw() {
   146         return "lemon::Bfs::UninitializedParameter";
   147       }
   148     };
   149 
   150     typedef TR Traits;
   151     ///The type of the underlying digraph.
   152     typedef typename TR::Digraph Digraph;
   153 
   154     ///\brief The type of the map that stores the last
   155     ///arcs of the shortest paths.
   156     typedef typename TR::PredMap PredMap;
   157     ///The type of the map indicating which nodes are reached.
   158     typedef typename TR::ReachedMap ReachedMap;
   159     ///The type of the map indicating which nodes are processed.
   160     typedef typename TR::ProcessedMap ProcessedMap;
   161     ///The type of the map that stores the dists of the nodes.
   162     typedef typename TR::DistMap DistMap;
   163   private:
   164 
   165     typedef typename Digraph::Node Node;
   166     typedef typename Digraph::NodeIt NodeIt;
   167     typedef typename Digraph::Arc Arc;
   168     typedef typename Digraph::OutArcIt OutArcIt;
   169 
   170     /// Pointer to the underlying digraph.
   171     const Digraph *G;
   172     ///Pointer to the map of predecessors arcs.
   173     PredMap *_pred;
   174     ///Indicates if \ref _pred is locally allocated (\c true) or not.
   175     bool local_pred;
   176     ///Pointer to the map of distances.
   177     DistMap *_dist;
   178     ///Indicates if \ref _dist is locally allocated (\c true) or not.
   179     bool local_dist;
   180     ///Pointer to the map of reached status of the nodes.
   181     ReachedMap *_reached;
   182     ///Indicates if \ref _reached is locally allocated (\c true) or not.
   183     bool local_reached;
   184     ///Pointer to the map of processed status of the nodes.
   185     ProcessedMap *_processed;
   186     ///Indicates if \ref _processed is locally allocated (\c true) or not.
   187     bool local_processed;
   188 
   189     std::vector<typename Digraph::Node> _queue;
   190     int _queue_head,_queue_tail,_queue_next_dist;
   191     int _curr_dist;
   192 
   193     ///Creates the maps if necessary.
   194 
   195     ///\todo Better memory allocation (instead of new).
   196     void create_maps()
   197     {
   198       if(!_pred) {
   199         local_pred = true;
   200         _pred = Traits::createPredMap(*G);
   201       }
   202       if(!_dist) {
   203         local_dist = true;
   204         _dist = Traits::createDistMap(*G);
   205       }
   206       if(!_reached) {
   207         local_reached = true;
   208         _reached = Traits::createReachedMap(*G);
   209       }
   210       if(!_processed) {
   211         local_processed = true;
   212         _processed = Traits::createProcessedMap(*G);
   213       }
   214     }
   215 
   216   protected:
   217 
   218     Bfs() {}
   219 
   220   public:
   221 
   222     typedef Bfs Create;
   223 
   224     ///\name Named template parameters
   225 
   226     ///@{
   227 
   228     template <class T>
   229     struct DefPredMapTraits : public Traits {
   230       typedef T PredMap;
   231       static PredMap *createPredMap(const Digraph &)
   232       {
   233         throw UninitializedParameter();
   234       }
   235     };
   236     ///\brief \ref named-templ-param "Named parameter" for setting
   237     ///PredMap type
   238     ///
   239     ///\ref named-templ-param "Named parameter" for setting PredMap type
   240     ///
   241     template <class T>
   242     struct DefPredMap : public Bfs< Digraph, DefPredMapTraits<T> > {
   243       typedef Bfs< Digraph, DefPredMapTraits<T> > Create;
   244     };
   245 
   246     template <class T>
   247     struct DefDistMapTraits : public Traits {
   248       typedef T DistMap;
   249       static DistMap *createDistMap(const Digraph &)
   250       {
   251         throw UninitializedParameter();
   252       }
   253     };
   254     ///\brief \ref named-templ-param "Named parameter" for setting
   255     ///DistMap type
   256     ///
   257     ///\ref named-templ-param "Named parameter" for setting DistMap type
   258     ///
   259     template <class T>
   260     struct DefDistMap : public Bfs< Digraph, DefDistMapTraits<T> > {
   261       typedef Bfs< Digraph, DefDistMapTraits<T> > Create;
   262     };
   263 
   264     template <class T>
   265     struct DefReachedMapTraits : public Traits {
   266       typedef T ReachedMap;
   267       static ReachedMap *createReachedMap(const Digraph &)
   268       {
   269         throw UninitializedParameter();
   270       }
   271     };
   272     ///\brief \ref named-templ-param "Named parameter" for setting
   273     ///ReachedMap type
   274     ///
   275     ///\ref named-templ-param "Named parameter" for setting ReachedMap type
   276     ///
   277     template <class T>
   278     struct DefReachedMap : public Bfs< Digraph, DefReachedMapTraits<T> > {
   279       typedef Bfs< Digraph, DefReachedMapTraits<T> > Create;
   280     };
   281 
   282     template <class T>
   283     struct DefProcessedMapTraits : public Traits {
   284       typedef T ProcessedMap;
   285       static ProcessedMap *createProcessedMap(const Digraph &)
   286       {
   287         throw UninitializedParameter();
   288       }
   289     };
   290     ///\brief \ref named-templ-param "Named parameter" for setting
   291     ///ProcessedMap type
   292     ///
   293     ///\ref named-templ-param "Named parameter" for setting ProcessedMap type
   294     ///
   295     template <class T>
   296     struct DefProcessedMap : public Bfs< Digraph, DefProcessedMapTraits<T> > {
   297       typedef Bfs< Digraph, DefProcessedMapTraits<T> > Create;
   298     };
   299 
   300     struct DefDigraphProcessedMapTraits : public Traits {
   301       typedef typename Digraph::template NodeMap<bool> ProcessedMap;
   302       static ProcessedMap *createProcessedMap(const Digraph &G)
   303       {
   304         return new ProcessedMap(G);
   305       }
   306     };
   307     ///\brief \ref named-templ-param "Named parameter"
   308     ///for setting the ProcessedMap type to be Digraph::NodeMap<bool>.
   309     ///
   310     ///\ref named-templ-param "Named parameter"
   311     ///for setting the ProcessedMap type to be Digraph::NodeMap<bool>.
   312     ///If you don't set it explicitly, it will be automatically allocated.
   313     template <class T>
   314     struct DefProcessedMapToBeDefaultMap :
   315       public Bfs< Digraph, DefDigraphProcessedMapTraits> {
   316       typedef Bfs< Digraph, DefDigraphProcessedMapTraits> Create;
   317     };
   318 
   319     ///@}
   320 
   321   public:
   322 
   323     ///Constructor.
   324 
   325     ///\param _G the digraph the algorithm will run on.
   326     ///
   327     Bfs(const Digraph& _G) :
   328       G(&_G),
   329       _pred(NULL), local_pred(false),
   330       _dist(NULL), local_dist(false),
   331       _reached(NULL), local_reached(false),
   332       _processed(NULL), local_processed(false)
   333     { }
   334 
   335     ///Destructor.
   336     ~Bfs()
   337     {
   338       if(local_pred) delete _pred;
   339       if(local_dist) delete _dist;
   340       if(local_reached) delete _reached;
   341       if(local_processed) delete _processed;
   342     }
   343 
   344     ///Sets the map storing the predecessor arcs.
   345 
   346     ///Sets the map storing the predecessor arcs.
   347     ///If you don't use this function before calling \ref run(),
   348     ///it will allocate one. The destructor deallocates this
   349     ///automatically allocated map, of course.
   350     ///\return <tt> (*this) </tt>
   351     Bfs &predMap(PredMap &m)
   352     {
   353       if(local_pred) {
   354         delete _pred;
   355         local_pred=false;
   356       }
   357       _pred = &m;
   358       return *this;
   359     }
   360 
   361     ///Sets the map indicating the reached nodes.
   362 
   363     ///Sets the map indicating the reached nodes.
   364     ///If you don't use this function before calling \ref run(),
   365     ///it will allocate one. The destructor deallocates this
   366     ///automatically allocated map, of course.
   367     ///\return <tt> (*this) </tt>
   368     Bfs &reachedMap(ReachedMap &m)
   369     {
   370       if(local_reached) {
   371         delete _reached;
   372         local_reached=false;
   373       }
   374       _reached = &m;
   375       return *this;
   376     }
   377 
   378     ///Sets the map indicating the processed nodes.
   379 
   380     ///Sets the map indicating the processed nodes.
   381     ///If you don't use this function before calling \ref run(),
   382     ///it will allocate one. The destructor deallocates this
   383     ///automatically allocated map, of course.
   384     ///\return <tt> (*this) </tt>
   385     Bfs &processedMap(ProcessedMap &m)
   386     {
   387       if(local_processed) {
   388         delete _processed;
   389         local_processed=false;
   390       }
   391       _processed = &m;
   392       return *this;
   393     }
   394 
   395     ///Sets the map storing the distances calculated by the algorithm.
   396 
   397     ///Sets the map storing the distances calculated by the algorithm.
   398     ///If you don't use this function before calling \ref run(),
   399     ///it will allocate one. The destructor deallocates this
   400     ///automatically allocated map, of course.
   401     ///\return <tt> (*this) </tt>
   402     Bfs &distMap(DistMap &m)
   403     {
   404       if(local_dist) {
   405         delete _dist;
   406         local_dist=false;
   407       }
   408       _dist = &m;
   409       return *this;
   410     }
   411 
   412   public:
   413     ///\name Execution control
   414     ///The simplest way to execute the algorithm is to use
   415     ///one of the member functions called \c run(...).
   416     ///\n
   417     ///If you need more control on the execution,
   418     ///first you must call \ref init(), then you can add several source nodes
   419     ///with \ref addSource().
   420     ///Finally \ref start() will perform the actual path
   421     ///computation.
   422 
   423     ///@{
   424 
   425     ///\brief Initializes the internal data structures.
   426     ///
   427     ///Initializes the internal data structures.
   428     ///
   429     void init()
   430     {
   431       create_maps();
   432       _queue.resize(countNodes(*G));
   433       _queue_head=_queue_tail=0;
   434       _curr_dist=1;
   435       for ( NodeIt u(*G) ; u!=INVALID ; ++u ) {
   436         _pred->set(u,INVALID);
   437         _reached->set(u,false);
   438         _processed->set(u,false);
   439       }
   440     }
   441 
   442     ///Adds a new source node.
   443 
   444     ///Adds a new source node to the set of nodes to be processed.
   445     ///
   446     void addSource(Node s)
   447     {
   448       if(!(*_reached)[s])
   449         {
   450           _reached->set(s,true);
   451           _pred->set(s,INVALID);
   452           _dist->set(s,0);
   453           _queue[_queue_head++]=s;
   454           _queue_next_dist=_queue_head;
   455         }
   456     }
   457 
   458     ///Processes the next node.
   459 
   460     ///Processes the next node.
   461     ///
   462     ///\return The processed node.
   463     ///
   464     ///\warning The queue must not be empty!
   465     Node processNextNode()
   466     {
   467       if(_queue_tail==_queue_next_dist) {
   468         _curr_dist++;
   469         _queue_next_dist=_queue_head;
   470       }
   471       Node n=_queue[_queue_tail++];
   472       _processed->set(n,true);
   473       Node m;
   474       for(OutArcIt e(*G,n);e!=INVALID;++e)
   475         if(!(*_reached)[m=G->target(e)]) {
   476           _queue[_queue_head++]=m;
   477           _reached->set(m,true);
   478           _pred->set(m,e);
   479           _dist->set(m,_curr_dist);
   480         }
   481       return n;
   482     }
   483 
   484     ///Processes the next node.
   485 
   486     ///Processes the next node. And checks that the given target node
   487     ///is reached. If the target node is reachable from the processed
   488     ///node then the reached parameter will be set true. The reached
   489     ///parameter should be initially false.
   490     ///
   491     ///\param target The target node.
   492     ///\retval reach Indicates that the target node is reached.
   493     ///\return The processed node.
   494     ///
   495     ///\warning The queue must not be empty!
   496     Node processNextNode(Node target, bool& reach)
   497     {
   498       if(_queue_tail==_queue_next_dist) {
   499         _curr_dist++;
   500         _queue_next_dist=_queue_head;
   501       }
   502       Node n=_queue[_queue_tail++];
   503       _processed->set(n,true);
   504       Node m;
   505       for(OutArcIt e(*G,n);e!=INVALID;++e)
   506         if(!(*_reached)[m=G->target(e)]) {
   507           _queue[_queue_head++]=m;
   508           _reached->set(m,true);
   509           _pred->set(m,e);
   510           _dist->set(m,_curr_dist);
   511           reach = reach || (target == m);
   512         }
   513       return n;
   514     }
   515 
   516     ///Processes the next node.
   517 
   518     ///Processes the next node. And checks that at least one of
   519     ///reached node has true value in the \c nm node map. If one node
   520     ///with true value is reachable from the processed node then the
   521     ///rnode parameter will be set to the first of such nodes.
   522     ///
   523     ///\param nm The node map of possible targets.
   524     ///\retval rnode The reached target node.
   525     ///\return The processed node.
   526     ///
   527     ///\warning The queue must not be empty!
   528     template<class NM>
   529     Node processNextNode(const NM& nm, Node& rnode)
   530     {
   531       if(_queue_tail==_queue_next_dist) {
   532         _curr_dist++;
   533         _queue_next_dist=_queue_head;
   534       }
   535       Node n=_queue[_queue_tail++];
   536       _processed->set(n,true);
   537       Node m;
   538       for(OutArcIt e(*G,n);e!=INVALID;++e)
   539         if(!(*_reached)[m=G->target(e)]) {
   540           _queue[_queue_head++]=m;
   541           _reached->set(m,true);
   542           _pred->set(m,e);
   543           _dist->set(m,_curr_dist);
   544           if (nm[m] && rnode == INVALID) rnode = m;
   545         }
   546       return n;
   547     }
   548 
   549     ///Next node to be processed.
   550 
   551     ///Next node to be processed.
   552     ///
   553     ///\return The next node to be processed or INVALID if the queue is
   554     /// empty.
   555     Node nextNode()
   556     {
   557       return _queue_tail<_queue_head?_queue[_queue_tail]:INVALID;
   558     }
   559 
   560     ///\brief Returns \c false if there are nodes
   561     ///to be processed in the queue
   562     ///
   563     ///Returns \c false if there are nodes
   564     ///to be processed in the queue
   565     bool emptyQueue() { return _queue_tail==_queue_head; }
   566     ///Returns the number of the nodes to be processed.
   567 
   568     ///Returns the number of the nodes to be processed in the queue.
   569     int queueSize() { return _queue_head-_queue_tail; }
   570 
   571     ///Executes the algorithm.
   572 
   573     ///Executes the algorithm.
   574     ///
   575     ///\pre init() must be called and at least one node should be added
   576     ///with addSource() before using this function.
   577     ///
   578     ///This method runs the %BFS algorithm from the root node(s)
   579     ///in order to
   580     ///compute the
   581     ///shortest path to each node. The algorithm computes
   582     ///- The shortest path tree.
   583     ///- The distance of each node from the root(s).
   584     void start()
   585     {
   586       while ( !emptyQueue() ) processNextNode();
   587     }
   588 
   589     ///Executes the algorithm until \c dest is reached.
   590 
   591     ///Executes the algorithm until \c dest is reached.
   592     ///
   593     ///\pre init() must be called and at least one node should be added
   594     ///with addSource() before using this function.
   595     ///
   596     ///This method runs the %BFS algorithm from the root node(s)
   597     ///in order to compute the shortest path to \c dest.
   598     ///The algorithm computes
   599     ///- The shortest path to \c  dest.
   600     ///- The distance of \c dest from the root(s).
   601     void start(Node dest)
   602     {
   603       bool reach = false;
   604       while ( !emptyQueue() && !reach ) processNextNode(dest, reach);
   605     }
   606 
   607     ///Executes the algorithm until a condition is met.
   608 
   609     ///Executes the algorithm until a condition is met.
   610     ///
   611     ///\pre init() must be called and at least one node should be added
   612     ///with addSource() before using this function.
   613     ///
   614     ///\param nm must be a bool (or convertible) node map. The
   615     ///algorithm will stop when it reaches a node \c v with
   616     /// <tt>nm[v]</tt> true.
   617     ///
   618     ///\return The reached node \c v with <tt>nm[v]</tt> true or
   619     ///\c INVALID if no such node was found.
   620     template<class NM>
   621     Node start(const NM &nm)
   622     {
   623       Node rnode = INVALID;
   624       while ( !emptyQueue() && rnode == INVALID ) {
   625         processNextNode(nm, rnode);
   626       }
   627       return rnode;
   628     }
   629 
   630     ///Runs %BFS algorithm from node \c s.
   631 
   632     ///This method runs the %BFS algorithm from a root node \c s
   633     ///in order to
   634     ///compute the
   635     ///shortest path to each node. The algorithm computes
   636     ///- The shortest path tree.
   637     ///- The distance of each node from the root.
   638     ///
   639     ///\note b.run(s) is just a shortcut of the following code.
   640     ///\code
   641     ///  b.init();
   642     ///  b.addSource(s);
   643     ///  b.start();
   644     ///\endcode
   645     void run(Node s) {
   646       init();
   647       addSource(s);
   648       start();
   649     }
   650 
   651     ///Finds the shortest path between \c s and \c t.
   652 
   653     ///Finds the shortest path between \c s and \c t.
   654     ///
   655     ///\return The length of the shortest s---t path if there exists one,
   656     ///0 otherwise.
   657     ///\note Apart from the return value, b.run(s) is
   658     ///just a shortcut of the following code.
   659     ///\code
   660     ///  b.init();
   661     ///  b.addSource(s);
   662     ///  b.start(t);
   663     ///\endcode
   664     int run(Node s,Node t) {
   665       init();
   666       addSource(s);
   667       start(t);
   668       return reached(t) ? _curr_dist : 0;
   669     }
   670 
   671     ///@}
   672 
   673     ///\name Query Functions
   674     ///The result of the %BFS algorithm can be obtained using these
   675     ///functions.\n
   676     ///Before the use of these functions,
   677     ///either run() or start() must be calleb.
   678 
   679     ///@{
   680 
   681     typedef PredMapPath<Digraph, PredMap> Path;
   682 
   683     ///Gives back the shortest path.
   684 
   685     ///Gives back the shortest path.
   686     ///\pre The \c t should be reachable from the source.
   687     Path path(Node t)
   688     {
   689       return Path(*G, *_pred, t);
   690     }
   691 
   692     ///The distance of a node from the root(s).
   693 
   694     ///Returns the distance of a node from the root(s).
   695     ///\pre \ref run() must be called before using this function.
   696     ///\warning If node \c v in unreachable from the root(s) the return value
   697     ///of this function is undefined.
   698     int dist(Node v) const { return (*_dist)[v]; }
   699 
   700     ///Returns the 'previous arc' of the shortest path tree.
   701 
   702     ///For a node \c v it returns the 'previous arc'
   703     ///of the shortest path tree,
   704     ///i.e. it returns the last arc of a shortest path from the root(s) to \c
   705     ///v. It is \ref INVALID
   706     ///if \c v is unreachable from the root(s) or \c v is a root. The
   707     ///shortest path tree used here is equal to the shortest path tree used in
   708     ///\ref predNode().
   709     ///\pre Either \ref run() or \ref start() must be called before using
   710     ///this function.
   711     Arc predArc(Node v) const { return (*_pred)[v];}
   712 
   713     ///Returns the 'previous node' of the shortest path tree.
   714 
   715     ///For a node \c v it returns the 'previous node'
   716     ///of the shortest path tree,
   717     ///i.e. it returns the last but one node from a shortest path from the
   718     ///root(a) to \c /v.
   719     ///It is INVALID if \c v is unreachable from the root(s) or
   720     ///if \c v itself a root.
   721     ///The shortest path tree used here is equal to the shortest path
   722     ///tree used in \ref predArc().
   723     ///\pre Either \ref run() or \ref start() must be called before
   724     ///using this function.
   725     Node predNode(Node v) const { return (*_pred)[v]==INVALID ? INVALID:
   726                                   G->source((*_pred)[v]); }
   727 
   728     ///Returns a reference to the NodeMap of distances.
   729 
   730     ///Returns a reference to the NodeMap of distances.
   731     ///\pre Either \ref run() or \ref init() must
   732     ///be called before using this function.
   733     const DistMap &distMap() const { return *_dist;}
   734 
   735     ///Returns a reference to the shortest path tree map.
   736 
   737     ///Returns a reference to the NodeMap of the arcs of the
   738     ///shortest path tree.
   739     ///\pre Either \ref run() or \ref init()
   740     ///must be called before using this function.
   741     const PredMap &predMap() const { return *_pred;}
   742 
   743     ///Checks if a node is reachable from the root.
   744 
   745     ///Returns \c true if \c v is reachable from the root.
   746     ///\warning The source nodes are indicated as unreached.
   747     ///\pre Either \ref run() or \ref start()
   748     ///must be called before using this function.
   749     ///
   750     bool reached(Node v) { return (*_reached)[v]; }
   751 
   752     ///@}
   753   };
   754 
   755   ///Default traits class of Bfs function.
   756 
   757   ///Default traits class of Bfs function.
   758   ///\tparam GR Digraph type.
   759   template<class GR>
   760   struct BfsWizardDefaultTraits
   761   {
   762     ///The digraph type the algorithm runs on.
   763     typedef GR Digraph;
   764     ///\brief The type of the map that stores the last
   765     ///arcs of the shortest paths.
   766     ///
   767     ///The type of the map that stores the last
   768     ///arcs of the shortest paths.
   769     ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
   770     ///
   771     typedef NullMap<typename Digraph::Node,typename GR::Arc> PredMap;
   772     ///Instantiates a PredMap.
   773 
   774     ///This function instantiates a \ref PredMap.
   775     ///\param g is the digraph, to which we would like to define the PredMap.
   776     ///\todo The digraph alone may be insufficient to initialize
   777 #ifdef DOXYGEN
   778     static PredMap *createPredMap(const GR &g)
   779 #else
   780     static PredMap *createPredMap(const GR &)
   781 #endif
   782     {
   783       return new PredMap();
   784     }
   785 
   786     ///The type of the map that indicates which nodes are processed.
   787 
   788     ///The type of the map that indicates which nodes are processed.
   789     ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
   790     ///\todo named parameter to set this type, function to read and write.
   791     typedef NullMap<typename Digraph::Node,bool> ProcessedMap;
   792     ///Instantiates a ProcessedMap.
   793 
   794     ///This function instantiates a \ref ProcessedMap.
   795     ///\param g is the digraph, to which
   796     ///we would like to define the \ref ProcessedMap
   797 #ifdef DOXYGEN
   798     static ProcessedMap *createProcessedMap(const GR &g)
   799 #else
   800     static ProcessedMap *createProcessedMap(const GR &)
   801 #endif
   802     {
   803       return new ProcessedMap();
   804     }
   805     ///The type of the map that indicates which nodes are reached.
   806 
   807     ///The type of the map that indicates which nodes are reached.
   808     ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
   809     ///\todo named parameter to set this type, function to read and write.
   810     typedef typename Digraph::template NodeMap<bool> ReachedMap;
   811     ///Instantiates a ReachedMap.
   812 
   813     ///This function instantiates a \ref ReachedMap.
   814     ///\param G is the digraph, to which
   815     ///we would like to define the \ref ReachedMap.
   816     static ReachedMap *createReachedMap(const GR &G)
   817     {
   818       return new ReachedMap(G);
   819     }
   820     ///The type of the map that stores the dists of the nodes.
   821 
   822     ///The type of the map that stores the dists of the nodes.
   823     ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
   824     ///
   825     typedef NullMap<typename Digraph::Node,int> DistMap;
   826     ///Instantiates a DistMap.
   827 
   828     ///This function instantiates a \ref DistMap.
   829     ///\param g is the digraph, to which we would like to define
   830     ///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::_reached=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::_processed=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   /// \tparam _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   /// \tparam _Digraph The digraph type the algorithm runs on.
  1205   /// The default value is
  1206   /// \ref ListDigraph. The value of _Digraph is not used directly by Bfs, it
  1207   /// is only passed to \ref BfsDefaultTraits.
  1208   /// \tparam _Visitor The Visitor object for the algorithm. The
  1209   /// \ref BfsVisitor "BfsVisitor<_Digraph>" is an empty Visitor which
  1210   /// does not observe the Bfs events. If you want to observe the bfs
  1211   /// events you should implement your own Visitor class.
  1212   /// \tparam _Traits Traits class to set various data types used by the
  1213   /// algorithm. The default traits class is
  1214   /// \ref BfsVisitDefaultTraits "BfsVisitDefaultTraits<_Digraph>".
  1215   /// See \ref BfsVisitDefaultTraits for the documentation of
  1216   /// a Bfs visit traits class.
  1217 #ifdef DOXYGEN
  1218   template <typename _Digraph, typename _Visitor, typename _Traits>
  1219 #else
  1220   template <typename _Digraph = ListDigraph,
  1221             typename _Visitor = BfsVisitor<_Digraph>,
  1222             typename _Traits = BfsDefaultTraits<_Digraph> >
  1223 #endif
  1224   class BfsVisit {
  1225   public:
  1226 
  1227     /// \brief \ref Exception for uninitialized parameters.
  1228     ///
  1229     /// This error represents problems in the initialization
  1230     /// of the parameters of the algorithms.
  1231     class UninitializedParameter : public lemon::UninitializedParameter {
  1232     public:
  1233       virtual const char* what() const throw()
  1234       {
  1235         return "lemon::BfsVisit::UninitializedParameter";
  1236       }
  1237     };
  1238 
  1239     typedef _Traits Traits;
  1240 
  1241     typedef typename Traits::Digraph Digraph;
  1242 
  1243     typedef _Visitor Visitor;
  1244 
  1245     ///The type of the map indicating which nodes are reached.
  1246     typedef typename Traits::ReachedMap ReachedMap;
  1247 
  1248   private:
  1249 
  1250     typedef typename Digraph::Node Node;
  1251     typedef typename Digraph::NodeIt NodeIt;
  1252     typedef typename Digraph::Arc Arc;
  1253     typedef typename Digraph::OutArcIt OutArcIt;
  1254 
  1255     /// Pointer to the underlying digraph.
  1256     const Digraph *_digraph;
  1257     /// Pointer to the visitor object.
  1258     Visitor *_visitor;
  1259     ///Pointer to the map of reached status of the nodes.
  1260     ReachedMap *_reached;
  1261     ///Indicates if \ref _reached is locally allocated (\c true) or not.
  1262     bool local_reached;
  1263 
  1264     std::vector<typename Digraph::Node> _list;
  1265     int _list_front, _list_back;
  1266 
  1267     /// \brief Creates the maps if necessary.
  1268     ///
  1269     /// Creates the maps if necessary.
  1270     void create_maps() {
  1271       if(!_reached) {
  1272         local_reached = true;
  1273         _reached = Traits::createReachedMap(*_digraph);
  1274       }
  1275     }
  1276 
  1277   protected:
  1278 
  1279     BfsVisit() {}
  1280 
  1281   public:
  1282 
  1283     typedef BfsVisit Create;
  1284 
  1285     /// \name Named template parameters
  1286 
  1287     ///@{
  1288     template <class T>
  1289     struct DefReachedMapTraits : public Traits {
  1290       typedef T ReachedMap;
  1291       static ReachedMap *createReachedMap(const Digraph &digraph) {
  1292         throw UninitializedParameter();
  1293       }
  1294     };
  1295     /// \brief \ref named-templ-param "Named parameter" for setting
  1296     /// ReachedMap type
  1297     ///
  1298     /// \ref named-templ-param "Named parameter" for setting ReachedMap type
  1299     template <class T>
  1300     struct DefReachedMap : public BfsVisit< Digraph, Visitor,
  1301                                             DefReachedMapTraits<T> > {
  1302       typedef BfsVisit< Digraph, Visitor, DefReachedMapTraits<T> > Create;
  1303     };
  1304     ///@}
  1305 
  1306   public:
  1307 
  1308     /// \brief Constructor.
  1309     ///
  1310     /// Constructor.
  1311     ///
  1312     /// \param digraph the digraph the algorithm will run on.
  1313     /// \param visitor The visitor of the algorithm.
  1314     ///
  1315     BfsVisit(const Digraph& digraph, Visitor& visitor)
  1316       : _digraph(&digraph), _visitor(&visitor),
  1317         _reached(0), local_reached(false) {}
  1318 
  1319     /// \brief Destructor.
  1320     ///
  1321     /// Destructor.
  1322     ~BfsVisit() {
  1323       if(local_reached) delete _reached;
  1324     }
  1325 
  1326     /// \brief Sets the map indicating if a node is reached.
  1327     ///
  1328     /// Sets the map indicating if a node is reached.
  1329     /// If you don't use this function before calling \ref run(),
  1330     /// it will allocate one. The destuctor deallocates this
  1331     /// automatically allocated map, of course.
  1332     /// \return <tt> (*this) </tt>
  1333     BfsVisit &reachedMap(ReachedMap &m) {
  1334       if(local_reached) {
  1335         delete _reached;
  1336         local_reached = false;
  1337       }
  1338       _reached = &m;
  1339       return *this;
  1340     }
  1341 
  1342   public:
  1343     /// \name Execution control
  1344     /// The simplest way to execute the algorithm is to use
  1345     /// one of the member functions called \c run(...).
  1346     /// \n
  1347     /// If you need more control on the execution,
  1348     /// first you must call \ref init(), then you can adda source node
  1349     /// with \ref addSource().
  1350     /// Finally \ref start() will perform the actual path
  1351     /// computation.
  1352 
  1353     /// @{
  1354     /// \brief Initializes the internal data structures.
  1355     ///
  1356     /// Initializes the internal data structures.
  1357     ///
  1358     void init() {
  1359       create_maps();
  1360       _list.resize(countNodes(*_digraph));
  1361       _list_front = _list_back = -1;
  1362       for (NodeIt u(*_digraph) ; u != INVALID ; ++u) {
  1363         _reached->set(u, false);
  1364       }
  1365     }
  1366 
  1367     /// \brief Adds a new source node.
  1368     ///
  1369     /// Adds a new source node to the set of nodes to be processed.
  1370     void addSource(Node s) {
  1371       if(!(*_reached)[s]) {
  1372           _reached->set(s,true);
  1373           _visitor->start(s);
  1374           _visitor->reach(s);
  1375           _list[++_list_back] = s;
  1376         }
  1377     }
  1378 
  1379     /// \brief Processes the next node.
  1380     ///
  1381     /// Processes the next node.
  1382     ///
  1383     /// \return The processed node.
  1384     ///
  1385     /// \pre The queue must not be empty!
  1386     Node processNextNode() {
  1387       Node n = _list[++_list_front];
  1388       _visitor->process(n);
  1389       Arc e;
  1390       for (_digraph->firstOut(e, n); e != INVALID; _digraph->nextOut(e)) {
  1391         Node m = _digraph->target(e);
  1392         if (!(*_reached)[m]) {
  1393           _visitor->discover(e);
  1394           _visitor->reach(m);
  1395           _reached->set(m, true);
  1396           _list[++_list_back] = m;
  1397         } else {
  1398           _visitor->examine(e);
  1399         }
  1400       }
  1401       return n;
  1402     }
  1403 
  1404     /// \brief Processes the next node.
  1405     ///
  1406     /// Processes the next node. And checks that the given target node
  1407     /// is reached. If the target node is reachable from the processed
  1408     /// node then the reached parameter will be set true. The reached
  1409     /// parameter should be initially false.
  1410     ///
  1411     /// \param target The target node.
  1412     /// \retval reach Indicates that the target node is reached.
  1413     /// \return The processed node.
  1414     ///
  1415     /// \warning The queue must not be empty!
  1416     Node processNextNode(Node target, bool& reach) {
  1417       Node n = _list[++_list_front];
  1418       _visitor->process(n);
  1419       Arc e;
  1420       for (_digraph->firstOut(e, n); e != INVALID; _digraph->nextOut(e)) {
  1421         Node m = _digraph->target(e);
  1422         if (!(*_reached)[m]) {
  1423           _visitor->discover(e);
  1424           _visitor->reach(m);
  1425           _reached->set(m, true);
  1426           _list[++_list_back] = m;
  1427           reach = reach || (target == m);
  1428         } else {
  1429           _visitor->examine(e);
  1430         }
  1431       }
  1432       return n;
  1433     }
  1434 
  1435     /// \brief Processes the next node.
  1436     ///
  1437     /// Processes the next node. And checks that at least one of
  1438     /// reached node has true value in the \c nm node map. If one node
  1439     /// with true value is reachable from the processed node then the
  1440     /// rnode parameter will be set to the first of such nodes.
  1441     ///
  1442     /// \param nm The node map of possible targets.
  1443     /// \retval rnode The reached target node.
  1444     /// \return The processed node.
  1445     ///
  1446     /// \warning The queue must not be empty!
  1447     template <typename NM>
  1448     Node processNextNode(const NM& nm, Node& rnode) {
  1449       Node n = _list[++_list_front];
  1450       _visitor->process(n);
  1451       Arc e;
  1452       for (_digraph->firstOut(e, n); e != INVALID; _digraph->nextOut(e)) {
  1453         Node m = _digraph->target(e);
  1454         if (!(*_reached)[m]) {
  1455           _visitor->discover(e);
  1456           _visitor->reach(m);
  1457           _reached->set(m, true);
  1458           _list[++_list_back] = m;
  1459           if (nm[m] && rnode == INVALID) rnode = m;
  1460         } else {
  1461           _visitor->examine(e);
  1462         }
  1463       }
  1464       return n;
  1465     }
  1466 
  1467     /// \brief Next node to be processed.
  1468     ///
  1469     /// Next node to be processed.
  1470     ///
  1471     /// \return The next node to be processed or INVALID if the stack is
  1472     /// empty.
  1473     Node nextNode() {
  1474       return _list_front != _list_back ? _list[_list_front + 1] : INVALID;
  1475     }
  1476 
  1477     /// \brief Returns \c false if there are nodes
  1478     /// to be processed in the queue
  1479     ///
  1480     /// Returns \c false if there are nodes
  1481     /// to be processed in the queue
  1482     bool emptyQueue() { return _list_front == _list_back; }
  1483 
  1484     /// \brief Returns the number of the nodes to be processed.
  1485     ///
  1486     /// Returns the number of the nodes to be processed in the queue.
  1487     int queueSize() { return _list_back - _list_front; }
  1488 
  1489     /// \brief Executes the algorithm.
  1490     ///
  1491     /// Executes the algorithm.
  1492     ///
  1493     /// \pre init() must be called and at least one node should be added
  1494     /// with addSource() before using this function.
  1495     void start() {
  1496       while ( !emptyQueue() ) processNextNode();
  1497     }
  1498 
  1499     /// \brief Executes the algorithm until \c dest is reached.
  1500     ///
  1501     /// Executes the algorithm until \c dest is reached.
  1502     ///
  1503     /// \pre init() must be called and at least one node should be added
  1504     /// with addSource() before using this function.
  1505     void start(Node dest) {
  1506       bool reach = false;
  1507       while ( !emptyQueue() && !reach ) processNextNode(dest, reach);
  1508     }
  1509 
  1510     /// \brief Executes the algorithm until a condition is met.
  1511     ///
  1512     /// Executes the algorithm until a condition is met.
  1513     ///
  1514     /// \pre init() must be called and at least one node should be added
  1515     /// with addSource() before using this function.
  1516     ///
  1517     ///\param nm must be a bool (or convertible) node map. The
  1518     ///algorithm will stop when it reaches a node \c v with
  1519     /// <tt>nm[v]</tt> true.
  1520     ///
  1521     ///\return The reached node \c v with <tt>nm[v]</tt> true or
  1522     ///\c INVALID if no such node was found.
  1523     template <typename NM>
  1524     Node start(const NM &nm) {
  1525       Node rnode = INVALID;
  1526       while ( !emptyQueue() && rnode == INVALID ) {
  1527         processNextNode(nm, rnode);
  1528       }
  1529       return rnode;
  1530     }
  1531 
  1532     /// \brief Runs %BFSVisit algorithm from node \c s.
  1533     ///
  1534     /// This method runs the %BFS algorithm from a root node \c s.
  1535     /// \note b.run(s) is just a shortcut of the following code.
  1536     ///\code
  1537     ///   b.init();
  1538     ///   b.addSource(s);
  1539     ///   b.start();
  1540     ///\endcode
  1541     void run(Node s) {
  1542       init();
  1543       addSource(s);
  1544       start();
  1545     }
  1546 
  1547     /// \brief Runs %BFSVisit algorithm to visit all nodes in the digraph.
  1548     ///
  1549     /// This method runs the %BFS algorithm in order to
  1550     /// compute the %BFS path to each node. The algorithm computes
  1551     /// - The %BFS tree.
  1552     /// - The distance of each node from the root in the %BFS tree.
  1553     ///
  1554     ///\note b.run() is just a shortcut of the following code.
  1555     ///\code
  1556     ///  b.init();
  1557     ///  for (NodeIt it(digraph); it != INVALID; ++it) {
  1558     ///    if (!b.reached(it)) {
  1559     ///      b.addSource(it);
  1560     ///      b.start();
  1561     ///    }
  1562     ///  }
  1563     ///\endcode
  1564     void run() {
  1565       init();
  1566       for (NodeIt it(*_digraph); it != INVALID; ++it) {
  1567         if (!reached(it)) {
  1568           addSource(it);
  1569           start();
  1570         }
  1571       }
  1572     }
  1573     ///@}
  1574 
  1575     /// \name Query Functions
  1576     /// The result of the %BFS algorithm can be obtained using these
  1577     /// functions.\n
  1578     /// Before the use of these functions,
  1579     /// either run() or start() must be called.
  1580     ///@{
  1581 
  1582     /// \brief Checks if a node is reachable from the root.
  1583     ///
  1584     /// Returns \c true if \c v is reachable from the root(s).
  1585     /// \warning The source nodes are inditated as unreachable.
  1586     /// \pre Either \ref run() or \ref start()
  1587     /// must be called before using this function.
  1588     ///
  1589     bool reached(Node v) { return (*_reached)[v]; }
  1590     ///@}
  1591   };
  1592 
  1593 } //END OF NAMESPACE LEMON
  1594 
  1595 #endif
  1596