COIN-OR::LEMON - Graph Library

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

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

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

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