COIN-OR::LEMON - Graph Library

source: lemon-1.2/lemon/bfs.h @ 278:931190050520

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

Improve the function-type interface of bfs, dfs, and dijkstra (ticket #96)

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