COIN-OR::LEMON - Graph Library

source: lemon-0.x/lemon/dfs.h @ 1978:ef2d00e46897

Last change on this file since 1978:ef2d00e46897 was 1956:a055123339d5, checked in by Alpar Juttner, 18 years ago

Unified copyright notices

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