COIN-OR::LEMON - Graph Library

source: lemon-1.2/lemon/bfs.h @ 336:052cecabcb71

Last change on this file since 336:052cecabcb71 was 252:66644b9cd9eb, checked in by Peter Kovacs <kpeter@…>, 13 years ago

Doc improvement for visitor classes (ticket #134)

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