COIN-OR::LEMON - Graph Library

source: lemon-0.x/lemon/dfs.h @ 2376:0ed45a6c74b1

Last change on this file since 2376:0ed45a6c74b1 was 2376:0ed45a6c74b1, checked in by Balazs Dezso, 17 years ago

Reorganization of the modules and groups

File size: 44.8 KB
Line 
1/* -*- C++ -*-
2 *
3 * This file is a part of LEMON, a generic C++ optimization library
4 *
5 * Copyright (C) 2003-2006
6 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
7 * (Egervary Research Group on Combinatorial Optimization, EGRES).
8 *
9 * Permission to use, modify and distribute this software is granted
10 * provided that this copyright notice appears in all copies. For
11 * precise terms see the accompanying LICENSE file.
12 *
13 * This software is provided "AS IS" with no warranty of any kind,
14 * express or implied, and with no claim as to its suitability for any
15 * purpose.
16 *
17 */
18
19#ifndef LEMON_DFS_H
20#define LEMON_DFS_H
21
22///\ingroup 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((void *)&g), _reached(0), _processed(0), _pred(0),
862      _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(*(Graph*)Base::_g);
937      if(Base::_reached) alg.reachedMap(*(ReachedMap*)Base::_reached);
938      if(Base::_processed) alg.processedMap(*(ProcessedMap*)Base::_processed);
939      if(Base::_pred) alg.predMap(*(PredMap*)Base::_pred);
940      if(Base::_dist) alg.distMap(*(DistMap*)Base::_dist);
941      alg.run(Base::_source);
942    }
943
944    ///Runs Dfs algorithm from the given node.
945
946    ///Runs Dfs algorithm from the given node.
947    ///\param s is the given source.
948    void run(Node s)
949    {
950      Base::_source=s;
951      run();
952    }
953
954    template<class T>
955    struct DefPredMapBase : public Base {
956      typedef T PredMap;
957      static PredMap *createPredMap(const Graph &) { return 0; };
958      DefPredMapBase(const TR &b) : TR(b) {}
959    };
960   
961    ///\brief \ref named-templ-param "Named parameter"
962    ///function for setting PredMap type
963    ///
964    /// \ref named-templ-param "Named parameter"
965    ///function for setting PredMap type
966    ///
967    template<class T>
968    DfsWizard<DefPredMapBase<T> > predMap(const T &t)
969    {
970      Base::_pred=(void *)&t;
971      return DfsWizard<DefPredMapBase<T> >(*this);
972    }
973   
974 
975    template<class T>
976    struct DefReachedMapBase : public Base {
977      typedef T ReachedMap;
978      static ReachedMap *createReachedMap(const Graph &) { return 0; };
979      DefReachedMapBase(const TR &b) : TR(b) {}
980    };
981   
982    ///\brief \ref named-templ-param "Named parameter"
983    ///function for setting ReachedMap
984    ///
985    /// \ref named-templ-param "Named parameter"
986    ///function for setting ReachedMap
987    ///
988    template<class T>
989    DfsWizard<DefReachedMapBase<T> > reachedMap(const T &t)
990    {
991      Base::_pred=(void *)&t;
992      return DfsWizard<DefReachedMapBase<T> >(*this);
993    }
994   
995
996    template<class T>
997    struct DefProcessedMapBase : public Base {
998      typedef T ProcessedMap;
999      static ProcessedMap *createProcessedMap(const Graph &) { return 0; };
1000      DefProcessedMapBase(const TR &b) : TR(b) {}
1001    };
1002   
1003    ///\brief \ref named-templ-param "Named parameter"
1004    ///function for setting ProcessedMap
1005    ///
1006    /// \ref named-templ-param "Named parameter"
1007    ///function for setting ProcessedMap
1008    ///
1009    template<class T>
1010    DfsWizard<DefProcessedMapBase<T> > processedMap(const T &t)
1011    {
1012      Base::_pred=(void *)&t;
1013      return DfsWizard<DefProcessedMapBase<T> >(*this);
1014    }
1015   
1016    template<class T>
1017    struct DefDistMapBase : public Base {
1018      typedef T DistMap;
1019      static DistMap *createDistMap(const Graph &) { return 0; };
1020      DefDistMapBase(const TR &b) : TR(b) {}
1021    };
1022   
1023    ///\brief \ref named-templ-param "Named parameter"
1024    ///function for setting DistMap type
1025    ///
1026    /// \ref named-templ-param "Named parameter"
1027    ///function for setting DistMap type
1028    ///
1029    template<class T>
1030    DfsWizard<DefDistMapBase<T> > distMap(const T &t)
1031    {
1032      Base::_dist=(void *)&t;
1033      return DfsWizard<DefDistMapBase<T> >(*this);
1034    }
1035   
1036    /// Sets the source node, from which the Dfs algorithm runs.
1037
1038    /// Sets the source node, from which the Dfs algorithm runs.
1039    /// \param s is the source node.
1040    DfsWizard<TR> &source(Node s)
1041    {
1042      Base::_source=s;
1043      return *this;
1044    }
1045   
1046  };
1047 
1048  ///Function type interface for Dfs algorithm.
1049
1050  ///\ingroup search
1051  ///Function type interface for Dfs algorithm.
1052  ///
1053  ///This function also has several
1054  ///\ref named-templ-func-param "named parameters",
1055  ///they are declared as the members of class \ref DfsWizard.
1056  ///The following
1057  ///example shows how to use these parameters.
1058  ///\code
1059  ///  dfs(g,source).predMap(preds).run();
1060  ///\endcode
1061  ///\warning Don't forget to put the \ref DfsWizard::run() "run()"
1062  ///to the end of the parameter list.
1063  ///\sa DfsWizard
1064  ///\sa Dfs
1065  template<class GR>
1066  DfsWizard<DfsWizardBase<GR> >
1067  dfs(const GR &g,typename GR::Node s=INVALID)
1068  {
1069    return DfsWizard<DfsWizardBase<GR> >(g,s);
1070  }
1071
1072#ifdef DOXYGEN
1073  /// \brief Visitor class for dfs.
1074  /// 
1075  /// It gives a simple interface for a functional interface for dfs
1076  /// traversal. The traversal on a linear data structure.
1077  template <typename _Graph>
1078  struct DfsVisitor {
1079    typedef _Graph Graph;
1080    typedef typename Graph::Edge Edge;
1081    typedef typename Graph::Node Node;
1082    /// \brief Called when the edge reach a node.
1083    ///
1084    /// It is called when the dfs find an edge which target is not
1085    /// reached yet.
1086    void discover(const Edge& edge) {}
1087    /// \brief Called when the node reached first time.
1088    ///
1089    /// It is Called when the node reached first time.
1090    void reach(const Node& node) {}
1091    /// \brief Called when we step back on an edge.
1092    ///
1093    /// It is called when the dfs should step back on the edge.
1094    void backtrack(const Edge& edge) {}
1095    /// \brief Called when we step back from the node.
1096    ///
1097    /// It is called when we step back from the node.
1098    void leave(const Node& node) {}
1099    /// \brief Called when the edge examined but target of the edge
1100    /// already discovered.
1101    ///
1102    /// It called when the edge examined but the target of the edge
1103    /// already discovered.
1104    void examine(const Edge& edge) {}
1105    /// \brief Called for the source node of the dfs.
1106    ///
1107    /// It is called for the source node of the dfs.
1108    void start(const Node& node) {}
1109    /// \brief Called when we leave the source node of the dfs.
1110    ///
1111    /// It is called when we leave the source node of the dfs.
1112    void stop(const Node& node) {}
1113
1114  };
1115#else
1116  template <typename _Graph>
1117  struct DfsVisitor {
1118    typedef _Graph Graph;
1119    typedef typename Graph::Edge Edge;
1120    typedef typename Graph::Node Node;
1121    void discover(const Edge&) {}
1122    void reach(const Node&) {}
1123    void backtrack(const Edge&) {}
1124    void leave(const Node&) {}
1125    void examine(const Edge&) {}
1126    void start(const Node&) {}
1127    void stop(const Node&) {}
1128
1129    template <typename _Visitor>
1130    struct Constraints {
1131      void constraints() {
1132        Edge edge;
1133        Node node;
1134        visitor.discover(edge);
1135        visitor.reach(node);
1136        visitor.backtrack(edge);
1137        visitor.leave(node);
1138        visitor.examine(edge);
1139        visitor.start(node);
1140        visitor.stop(edge);
1141      }
1142      _Visitor& visitor;
1143    };
1144  };
1145#endif
1146
1147  /// \brief Default traits class of DfsVisit class.
1148  ///
1149  /// Default traits class of DfsVisit class.
1150  /// \param _Graph Graph type.
1151  template<class _Graph>
1152  struct DfsVisitDefaultTraits {
1153
1154    /// \brief The graph type the algorithm runs on.
1155    typedef _Graph Graph;
1156
1157    /// \brief The type of the map that indicates which nodes are reached.
1158    ///
1159    /// The type of the map that indicates which nodes are reached.
1160    /// It must meet the \ref concepts::WriteMap "WriteMap" concept.
1161    /// \todo named parameter to set this type, function to read and write.
1162    typedef typename Graph::template NodeMap<bool> ReachedMap;
1163
1164    /// \brief Instantiates a ReachedMap.
1165    ///
1166    /// This function instantiates a \ref ReachedMap.
1167    /// \param graph is the graph, to which
1168    /// we would like to define the \ref ReachedMap.
1169    static ReachedMap *createReachedMap(const Graph &graph) {
1170      return new ReachedMap(graph);
1171    }
1172
1173  };
1174 
1175  /// %DFS Visit algorithm class.
1176 
1177  /// \ingroup search
1178  /// This class provides an efficient implementation of the %DFS algorithm
1179  /// with visitor interface.
1180  ///
1181  /// The %DfsVisit class provides an alternative interface to the Dfs
1182  /// class. It works with callback mechanism, the DfsVisit object calls
1183  /// on every dfs event the \c Visitor class member functions.
1184  ///
1185  /// \param _Graph The graph type the algorithm runs on. The default value is
1186  /// \ref ListGraph. The value of _Graph is not used directly by Dfs, it
1187  /// is only passed to \ref DfsDefaultTraits.
1188  /// \param _Visitor The Visitor object for the algorithm. The
1189  /// \ref DfsVisitor "DfsVisitor<_Graph>" is an empty Visitor which
1190  /// does not observe the Dfs events. If you want to observe the dfs
1191  /// events you should implement your own Visitor class.
1192  /// \param _Traits Traits class to set various data types used by the
1193  /// algorithm. The default traits class is
1194  /// \ref DfsVisitDefaultTraits "DfsVisitDefaultTraits<_Graph>".
1195  /// See \ref DfsVisitDefaultTraits for the documentation of
1196  /// a Dfs visit traits class.
1197  ///
1198  /// \author Jacint Szabo, Alpar Juttner and Balazs Dezso
1199#ifdef DOXYGEN
1200  template <typename _Graph, typename _Visitor, typename _Traits>
1201#else
1202  template <typename _Graph = ListGraph,
1203            typename _Visitor = DfsVisitor<_Graph>,
1204            typename _Traits = DfsDefaultTraits<_Graph> >
1205#endif
1206  class DfsVisit {
1207  public:
1208   
1209    /// \brief \ref Exception for uninitialized parameters.
1210    ///
1211    /// This error represents problems in the initialization
1212    /// of the parameters of the algorithms.
1213    class UninitializedParameter : public lemon::UninitializedParameter {
1214    public:
1215      virtual const char* what() const throw()
1216      {
1217        return "lemon::DfsVisit::UninitializedParameter";
1218      }
1219    };
1220
1221    typedef _Traits Traits;
1222
1223    typedef typename Traits::Graph Graph;
1224
1225    typedef _Visitor Visitor;
1226
1227    ///The type of the map indicating which nodes are reached.
1228    typedef typename Traits::ReachedMap ReachedMap;
1229
1230  private:
1231
1232    typedef typename Graph::Node Node;
1233    typedef typename Graph::NodeIt NodeIt;
1234    typedef typename Graph::Edge Edge;
1235    typedef typename Graph::OutEdgeIt OutEdgeIt;
1236
1237    /// Pointer to the underlying graph.
1238    const Graph *_graph;
1239    /// Pointer to the visitor object.
1240    Visitor *_visitor;
1241    ///Pointer to the map of reached status of the nodes.
1242    ReachedMap *_reached;
1243    ///Indicates if \ref _reached is locally allocated (\c true) or not.
1244    bool local_reached;
1245
1246    std::vector<typename Graph::Edge> _stack;
1247    int _stack_head;
1248
1249    /// \brief Creates the maps if necessary.
1250    ///
1251    /// Creates the maps if necessary.
1252    void create_maps() {
1253      if(!_reached) {
1254        local_reached = true;
1255        _reached = Traits::createReachedMap(*_graph);
1256      }
1257    }
1258
1259  protected:
1260
1261    DfsVisit() {}
1262   
1263  public:
1264
1265    typedef DfsVisit Create;
1266
1267    /// \name Named template parameters
1268
1269    ///@{
1270    template <class T>
1271    struct DefReachedMapTraits : public Traits {
1272      typedef T ReachedMap;
1273      static ReachedMap *createReachedMap(const Graph &graph) {
1274        throw UninitializedParameter();
1275      }
1276    };
1277    /// \brief \ref named-templ-param "Named parameter" for setting
1278    /// ReachedMap type
1279    ///
1280    /// \ref named-templ-param "Named parameter" for setting ReachedMap type
1281    template <class T>
1282    struct DefReachedMap : public DfsVisit< Graph, Visitor,
1283                                            DefReachedMapTraits<T> > {
1284      typedef DfsVisit< Graph, Visitor, DefReachedMapTraits<T> > Create;
1285    };
1286    ///@}
1287
1288  public:     
1289   
1290    /// \brief Constructor.
1291    ///
1292    /// Constructor.
1293    ///
1294    /// \param graph the graph the algorithm will run on.
1295    /// \param visitor The visitor of the algorithm.
1296    ///
1297    DfsVisit(const Graph& graph, Visitor& visitor)
1298      : _graph(&graph), _visitor(&visitor),
1299        _reached(0), local_reached(false) {}
1300   
1301    /// \brief Destructor.
1302    ///
1303    /// Destructor.
1304    ~DfsVisit() {
1305      if(local_reached) delete _reached;
1306    }
1307
1308    /// \brief Sets the map indicating if a node is reached.
1309    ///
1310    /// Sets the map indicating if a node is reached.
1311    /// If you don't use this function before calling \ref run(),
1312    /// it will allocate one. The destuctor deallocates this
1313    /// automatically allocated map, of course.
1314    /// \return <tt> (*this) </tt>
1315    DfsVisit &reachedMap(ReachedMap &m) {
1316      if(local_reached) {
1317        delete _reached;
1318        local_reached=false;
1319      }
1320      _reached = &m;
1321      return *this;
1322    }
1323
1324  public:
1325    /// \name Execution control
1326    /// The simplest way to execute the algorithm is to use
1327    /// one of the member functions called \c run(...).
1328    /// \n
1329    /// If you need more control on the execution,
1330    /// first you must call \ref init(), then you can adda source node
1331    /// with \ref addSource().
1332    /// Finally \ref start() will perform the actual path
1333    /// computation.
1334
1335    /// @{
1336    /// \brief Initializes the internal data structures.
1337    ///
1338    /// Initializes the internal data structures.
1339    ///
1340    void init() {
1341      create_maps();
1342      _stack.resize(countNodes(*_graph));
1343      _stack_head = -1;
1344      for (NodeIt u(*_graph) ; u != INVALID ; ++u) {
1345        _reached->set(u, false);
1346      }
1347    }
1348   
1349    /// \brief Adds a new source node.
1350    ///
1351    /// Adds a new source node to the set of nodes to be processed.
1352    void addSource(Node s) {
1353      if(!(*_reached)[s]) {
1354          _reached->set(s,true);
1355          _visitor->start(s);
1356          _visitor->reach(s);
1357          Edge e;
1358          _graph->firstOut(e, s);
1359          if (e != INVALID) {
1360            _stack[++_stack_head] = e;
1361          } else {
1362            _visitor->leave(s);
1363          }
1364        }
1365    }
1366   
1367    /// \brief Processes the next edge.
1368    ///
1369    /// Processes the next edge.
1370    ///
1371    /// \return The processed edge.
1372    ///
1373    /// \pre The stack must not be empty!
1374    Edge processNextEdge() {
1375      Edge e = _stack[_stack_head];
1376      Node m = _graph->target(e);
1377      if(!(*_reached)[m]) {
1378        _visitor->discover(e);
1379        _visitor->reach(m);
1380        _reached->set(m, true);
1381        _graph->firstOut(_stack[++_stack_head], m);
1382      } else {
1383        _visitor->examine(e);
1384        m = _graph->source(e);
1385        _graph->nextOut(_stack[_stack_head]);
1386      }
1387      while (_stack_head>=0 && _stack[_stack_head] == INVALID) {
1388        _visitor->leave(m);
1389        --_stack_head;
1390        if (_stack_head >= 0) {
1391          _visitor->backtrack(_stack[_stack_head]);
1392          m = _graph->source(_stack[_stack_head]);
1393          _graph->nextOut(_stack[_stack_head]);
1394        } else {
1395          _visitor->stop(m);     
1396        }
1397      }
1398      return e;
1399    }
1400
1401    /// \brief Next edge to be processed.
1402    ///
1403    /// Next edge to be processed.
1404    ///
1405    /// \return The next edge to be processed or INVALID if the stack is
1406    /// empty.
1407    Edge nextEdge() {
1408      return _stack_head >= 0 ? _stack[_stack_head] : INVALID;
1409    }
1410
1411    /// \brief Returns \c false if there are nodes
1412    /// to be processed in the queue
1413    ///
1414    /// Returns \c false if there are nodes
1415    /// to be processed in the queue
1416    bool emptyQueue() { return _stack_head < 0; }
1417
1418    /// \brief Returns the number of the nodes to be processed.
1419    ///
1420    /// Returns the number of the nodes to be processed in the queue.
1421    int queueSize() { return _stack_head + 1; }
1422   
1423    /// \brief Executes the algorithm.
1424    ///
1425    /// Executes the algorithm.
1426    ///
1427    /// \pre init() must be called and at least one node should be added
1428    /// with addSource() before using this function.
1429    void start() {
1430      while ( !emptyQueue() ) processNextEdge();
1431    }
1432   
1433    /// \brief Executes the algorithm until \c dest is reached.
1434    ///
1435    /// Executes the algorithm until \c dest is reached.
1436    ///
1437    /// \pre init() must be called and at least one node should be added
1438    /// with addSource() before using this function.
1439    void start(Node dest) {
1440      while ( !emptyQueue() && _graph->target(_stack[_stack_head]) != dest)
1441        processNextEdge();
1442    }
1443   
1444    /// \brief Executes the algorithm until a condition is met.
1445    ///
1446    /// Executes the algorithm until a condition is met.
1447    ///
1448    /// \pre init() must be called and at least one node should be added
1449    /// with addSource() before using this function.
1450    ///
1451    /// \param em must be a bool (or convertible) edge map. The algorithm
1452    /// will stop when it reaches an edge \c e with \code nm[e]==true \endcode.
1453    ///
1454    /// \warning Contrary to \ref Dfs and \ref Dijkstra, \c em is an edge map,
1455    /// not a node map.
1456    template <typename EM>
1457    void start(const EM &em) {
1458      while (!emptyQueue() && !em[_stack[_stack_head]]) processNextEdge();
1459    }
1460
1461    /// \brief Runs %DFSVisit algorithm from node \c s.
1462    ///
1463    /// This method runs the %DFS algorithm from a root node \c s.
1464    /// \note d.run(s) is just a shortcut of the following code.
1465    ///\code
1466    ///   d.init();
1467    ///   d.addSource(s);
1468    ///   d.start();
1469    ///\endcode
1470    void run(Node s) {
1471      init();
1472      addSource(s);
1473      start();
1474    }
1475
1476    /// \brief Runs %DFSVisit algorithm to visit all nodes in the graph.
1477   
1478    /// This method runs the %DFS algorithm in order to
1479    /// compute the %DFS path to each node. The algorithm computes
1480    /// - The %DFS tree.
1481    /// - The distance of each node from the root in the %DFS tree.
1482    ///
1483    ///\note d.run() is just a shortcut of the following code.
1484    ///\code
1485    ///  d.init();
1486    ///  for (NodeIt it(graph); it != INVALID; ++it) {
1487    ///    if (!d.reached(it)) {
1488    ///      d.addSource(it);
1489    ///      d.start();
1490    ///    }
1491    ///  }
1492    ///\endcode
1493    void run() {
1494      init();
1495      for (NodeIt it(*_graph); it != INVALID; ++it) {
1496        if (!reached(it)) {
1497          addSource(it);
1498          start();
1499        }
1500      }
1501    }
1502    ///@}
1503
1504    /// \name Query Functions
1505    /// The result of the %DFS algorithm can be obtained using these
1506    /// functions.\n
1507    /// Before the use of these functions,
1508    /// either run() or start() must be called.
1509    ///@{
1510    /// \brief Checks if a node is reachable from the root.
1511    ///
1512    /// Returns \c true if \c v is reachable from the root(s).
1513    /// \warning The source nodes are inditated as unreachable.
1514    /// \pre Either \ref run() or \ref start()
1515    /// must be called before using this function.
1516    ///
1517    bool reached(Node v) { return (*_reached)[v]; }
1518    ///@}
1519  };
1520
1521
1522} //END OF NAMESPACE LEMON
1523
1524#endif
1525
Note: See TracBrowser for help on using the repository browser.