COIN-OR::LEMON - Graph Library

source: lemon-1.0/lemon/bfs.h @ 244:c30731a37f91

Last change on this file since 244:c30731a37f91 was 244:c30731a37f91, checked in by Peter Kovacs <kpeter@…>, 11 years ago

Many improvements in bfs.h, dfs.h and dijkstra.h

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