COIN-OR::LEMON - Graph Library

source: lemon-1.2/lemon/dfs.h @ 252:66644b9cd9eb

Last change on this file since 252:66644b9cd9eb was 252:66644b9cd9eb, checked in by Peter Kovacs <kpeter@…>, 11 years ago

Doc improvement for visitor classes (ticket #134)

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