COIN-OR::LEMON - Graph Library

source: lemon-0.x/lemon/dfs.h @ 2391:14a343be7a5a

Last change on this file since 2391:14a343be7a5a was 2391:14a343be7a5a, checked in by Alpar Juttner, 12 years ago

Happy New Year to all source files!

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