COIN-OR::LEMON - Graph Library

source: lemon/lemon/dfs.h @ 1337:4add05447ca0

Last change on this file since 1337:4add05447ca0 was 1270:dceba191c00d, checked in by Alpar Juttner <alpar@…>, 11 years ago

Apply unify-sources.sh to the source tree

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