COIN-OR::LEMON - Graph Library

source: lemon-0.x/lemon/dfs.h @ 1911:c925a077cf73

Last change on this file since 1911:c925a077cf73 was 1875:98698b69a902, checked in by Alpar Juttner, 18 years ago

Happy new year to LEMON

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