COIN-OR::LEMON - Graph Library

source: lemon-main/lemon/dfs.h

Last change on this file was 1199:15282595e6f4, checked in by Balazs Dezso <deba@…>, 11 years ago

Using Arc instead of ArcIt? in Dfs (#32)

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