COIN-OR::LEMON - Graph Library

source: lemon/lemon/bfs.h @ 258:0310c8984732

Last change on this file since 258:0310c8984732 was 258:0310c8984732, checked in by Alpar Juttner <alpar@…>, 11 years ago

Merge

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