COIN-OR::LEMON - Graph Library

source: lemon-1.2/lemon/dfs.h @ 258:0310c8984732

Last change on this file since 258:0310c8984732 was 258:0310c8984732, checked in by Alpar Juttner <alpar@…>, 11 years ago

Merge

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