COIN-OR::LEMON - Graph Library

source: lemon-0.x/lemon/dfs.h @ 1749:c13f6b4aa40e

Last change on this file since 1749:c13f6b4aa40e was 1749:c13f6b4aa40e, checked in by Balazs Dezso, 14 years ago

Visitor interface for the dfs algorithm.

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