COIN-OR::LEMON - Graph Library

source: lemon-main/lemon/bfs.h @ 210:81cfc04531e8

Last change on this file since 210:81cfc04531e8 was 210:81cfc04531e8, checked in by Alpar Juttner <alpar@…>, 16 years ago

Remove long lines (from all but one file)

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