COIN-OR::LEMON - Graph Library

source: lemon-1.2/lemon/dfs.h @ 947:cfdbf1574403

Last change on this file since 947:cfdbf1574403 was 942:2b6bffe0e7e8, checked in by Alpar Juttner <alpar@…>, 12 years ago

Merge

File size: 50.4 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-2010
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 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    };
1197  };
1198#endif
1199
1200  /// \brief Default traits class of DfsVisit class.
1201  ///
1202  /// Default traits class of DfsVisit class.
1203  /// \tparam _Digraph The type of the digraph the algorithm runs on.
1204  template<class GR>
1205  struct DfsVisitDefaultTraits {
1206
1207    /// \brief The type of the digraph the algorithm runs on.
1208    typedef GR Digraph;
1209
1210    /// \brief The type of the map that indicates which nodes are reached.
1211    ///
1212    /// The type of the map that indicates which nodes are reached.
1213    /// It must conform to the
1214    /// \ref concepts::ReadWriteMap "ReadWriteMap" concept.
1215    typedef typename Digraph::template NodeMap<bool> ReachedMap;
1216
1217    /// \brief Instantiates a ReachedMap.
1218    ///
1219    /// This function instantiates a ReachedMap.
1220    /// \param digraph is the digraph, to which
1221    /// we would like to define the ReachedMap.
1222    static ReachedMap *createReachedMap(const Digraph &digraph) {
1223      return new ReachedMap(digraph);
1224    }
1225
1226  };
1227
1228  /// \ingroup search
1229  ///
1230  /// \brief DFS algorithm class with visitor interface.
1231  ///
1232  /// This class provides an efficient implementation of the DFS algorithm
1233  /// with visitor interface.
1234  ///
1235  /// The DfsVisit class provides an alternative interface to the Dfs
1236  /// class. It works with callback mechanism, the DfsVisit object calls
1237  /// the member functions of the \c Visitor class on every DFS event.
1238  ///
1239  /// This interface of the DFS algorithm should be used in special cases
1240  /// when extra actions have to be performed in connection with certain
1241  /// events of the DFS algorithm. Otherwise consider to use Dfs or dfs()
1242  /// instead.
1243  ///
1244  /// \tparam GR The type of the digraph the algorithm runs on.
1245  /// The default type is \ref ListDigraph.
1246  /// The value of GR is not used directly by \ref DfsVisit,
1247  /// it is only passed to \ref DfsVisitDefaultTraits.
1248  /// \tparam VS The Visitor type that is used by the algorithm.
1249  /// \ref DfsVisitor "DfsVisitor<GR>" is an empty visitor, which
1250  /// does not observe the DFS events. If you want to observe the DFS
1251  /// events, you should implement your own visitor class.
1252  /// \tparam TR The traits class that defines various types used by the
1253  /// algorithm. By default, it is \ref DfsVisitDefaultTraits
1254  /// "DfsVisitDefaultTraits<GR>".
1255  /// In most cases, this parameter should not be set directly,
1256  /// consider to use the named template parameters instead.
1257#ifdef DOXYGEN
1258  template <typename GR, typename VS, typename TR>
1259#else
1260  template <typename GR = ListDigraph,
1261            typename VS = DfsVisitor<GR>,
1262            typename TR = DfsVisitDefaultTraits<GR> >
1263#endif
1264  class DfsVisit {
1265  public:
1266
1267    ///The traits class.
1268    typedef TR Traits;
1269
1270    ///The type of the digraph the algorithm runs on.
1271    typedef typename Traits::Digraph Digraph;
1272
1273    ///The visitor type used by the algorithm.
1274    typedef VS Visitor;
1275
1276    ///The type of the map that indicates which nodes are reached.
1277    typedef typename Traits::ReachedMap ReachedMap;
1278
1279  private:
1280
1281    typedef typename Digraph::Node Node;
1282    typedef typename Digraph::NodeIt NodeIt;
1283    typedef typename Digraph::Arc Arc;
1284    typedef typename Digraph::OutArcIt OutArcIt;
1285
1286    //Pointer to the underlying digraph.
1287    const Digraph *_digraph;
1288    //Pointer to the visitor object.
1289    Visitor *_visitor;
1290    //Pointer to the map of reached status of the nodes.
1291    ReachedMap *_reached;
1292    //Indicates if _reached is locally allocated (true) or not.
1293    bool local_reached;
1294
1295    std::vector<typename Digraph::Arc> _stack;
1296    int _stack_head;
1297
1298    //Creates the maps if necessary.
1299    void create_maps() {
1300      if(!_reached) {
1301        local_reached = true;
1302        _reached = Traits::createReachedMap(*_digraph);
1303      }
1304    }
1305
1306  protected:
1307
1308    DfsVisit() {}
1309
1310  public:
1311
1312    typedef DfsVisit Create;
1313
1314    /// \name Named Template Parameters
1315
1316    ///@{
1317    template <class T>
1318    struct SetReachedMapTraits : public Traits {
1319      typedef T ReachedMap;
1320      static ReachedMap *createReachedMap(const Digraph &digraph) {
1321        LEMON_ASSERT(false, "ReachedMap is not initialized");
1322        return 0; // ignore warnings
1323      }
1324    };
1325    /// \brief \ref named-templ-param "Named parameter" for setting
1326    /// ReachedMap type.
1327    ///
1328    /// \ref named-templ-param "Named parameter" for setting ReachedMap type.
1329    template <class T>
1330    struct SetReachedMap : public DfsVisit< Digraph, Visitor,
1331                                            SetReachedMapTraits<T> > {
1332      typedef DfsVisit< Digraph, Visitor, SetReachedMapTraits<T> > Create;
1333    };
1334    ///@}
1335
1336  public:
1337
1338    /// \brief Constructor.
1339    ///
1340    /// Constructor.
1341    ///
1342    /// \param digraph The digraph the algorithm runs on.
1343    /// \param visitor The visitor object of the algorithm.
1344    DfsVisit(const Digraph& digraph, Visitor& visitor)
1345      : _digraph(&digraph), _visitor(&visitor),
1346        _reached(0), local_reached(false) {}
1347
1348    /// \brief Destructor.
1349    ~DfsVisit() {
1350      if(local_reached) delete _reached;
1351    }
1352
1353    /// \brief Sets the map that indicates which nodes are reached.
1354    ///
1355    /// Sets the map that indicates which nodes are reached.
1356    /// If you don't use this function before calling \ref run(Node) "run()"
1357    /// or \ref init(), an instance will be allocated automatically.
1358    /// The destructor deallocates this automatically allocated map,
1359    /// of course.
1360    /// \return <tt> (*this) </tt>
1361    DfsVisit &reachedMap(ReachedMap &m) {
1362      if(local_reached) {
1363        delete _reached;
1364        local_reached=false;
1365      }
1366      _reached = &m;
1367      return *this;
1368    }
1369
1370  public:
1371
1372    /// \name Execution Control
1373    /// The simplest way to execute the DFS algorithm is to use one of the
1374    /// member functions called \ref run(Node) "run()".\n
1375    /// If you need better control on the execution, you have to call
1376    /// \ref init() first, then you can add a source node with \ref addSource()
1377    /// and perform the actual computation with \ref start().
1378    /// This procedure can be repeated if there are nodes that have not
1379    /// been reached.
1380
1381    /// @{
1382
1383    /// \brief Initializes the internal data structures.
1384    ///
1385    /// Initializes the internal data structures.
1386    void init() {
1387      create_maps();
1388      _stack.resize(countNodes(*_digraph));
1389      _stack_head = -1;
1390      for (NodeIt u(*_digraph) ; u != INVALID ; ++u) {
1391        _reached->set(u, false);
1392      }
1393    }
1394
1395    /// \brief Adds a new source node.
1396    ///
1397    /// Adds a new source node to the set of nodes to be processed.
1398    ///
1399    /// \pre The stack must be empty. Otherwise the algorithm gives
1400    /// wrong results. (One of the outgoing arcs of all the source nodes
1401    /// except for the last one will not be visited and distances will
1402    /// also be wrong.)
1403    void addSource(Node s)
1404    {
1405      LEMON_DEBUG(emptyQueue(), "The stack is not empty.");
1406      if(!(*_reached)[s]) {
1407          _reached->set(s,true);
1408          _visitor->start(s);
1409          _visitor->reach(s);
1410          Arc e;
1411          _digraph->firstOut(e, s);
1412          if (e != INVALID) {
1413            _stack[++_stack_head] = e;
1414          } else {
1415            _visitor->leave(s);
1416            _visitor->stop(s);
1417          }
1418        }
1419    }
1420
1421    /// \brief Processes the next arc.
1422    ///
1423    /// Processes the next arc.
1424    ///
1425    /// \return The processed arc.
1426    ///
1427    /// \pre The stack must not be empty.
1428    Arc processNextArc() {
1429      Arc e = _stack[_stack_head];
1430      Node m = _digraph->target(e);
1431      if(!(*_reached)[m]) {
1432        _visitor->discover(e);
1433        _visitor->reach(m);
1434        _reached->set(m, true);
1435        _digraph->firstOut(_stack[++_stack_head], m);
1436      } else {
1437        _visitor->examine(e);
1438        m = _digraph->source(e);
1439        _digraph->nextOut(_stack[_stack_head]);
1440      }
1441      while (_stack_head>=0 && _stack[_stack_head] == INVALID) {
1442        _visitor->leave(m);
1443        --_stack_head;
1444        if (_stack_head >= 0) {
1445          _visitor->backtrack(_stack[_stack_head]);
1446          m = _digraph->source(_stack[_stack_head]);
1447          _digraph->nextOut(_stack[_stack_head]);
1448        } else {
1449          _visitor->stop(m);
1450        }
1451      }
1452      return e;
1453    }
1454
1455    /// \brief Next arc to be processed.
1456    ///
1457    /// Next arc to be processed.
1458    ///
1459    /// \return The next arc to be processed or INVALID if the stack is
1460    /// empty.
1461    Arc nextArc() const {
1462      return _stack_head >= 0 ? _stack[_stack_head] : INVALID;
1463    }
1464
1465    /// \brief Returns \c false if there are nodes
1466    /// to be processed.
1467    ///
1468    /// Returns \c false if there are nodes
1469    /// to be processed in the queue (stack).
1470    bool emptyQueue() const { return _stack_head < 0; }
1471
1472    /// \brief Returns the number of the nodes to be processed.
1473    ///
1474    /// Returns the number of the nodes to be processed in the queue (stack).
1475    int queueSize() const { return _stack_head + 1; }
1476
1477    /// \brief Executes the algorithm.
1478    ///
1479    /// Executes the algorithm.
1480    ///
1481    /// This method runs the %DFS algorithm from the root node
1482    /// in order to compute the %DFS path to each node.
1483    ///
1484    /// The algorithm computes
1485    /// - the %DFS tree,
1486    /// - the distance of each node from the root in the %DFS tree.
1487    ///
1488    /// \pre init() must be called and a root node should be
1489    /// added with addSource() before using this function.
1490    ///
1491    /// \note <tt>d.start()</tt> is just a shortcut of the following code.
1492    /// \code
1493    ///   while ( !d.emptyQueue() ) {
1494    ///     d.processNextArc();
1495    ///   }
1496    /// \endcode
1497    void start() {
1498      while ( !emptyQueue() ) processNextArc();
1499    }
1500
1501    /// \brief Executes the algorithm until the given target node is reached.
1502    ///
1503    /// Executes the algorithm until the given target node is reached.
1504    ///
1505    /// This method runs the %DFS algorithm from the root node
1506    /// in order to compute the DFS path to \c t.
1507    ///
1508    /// The algorithm computes
1509    /// - the %DFS path to \c t,
1510    /// - the distance of \c t from the root in the %DFS tree.
1511    ///
1512    /// \pre init() must be called and a root node should be added
1513    /// with addSource() before using this function.
1514    void start(Node t) {
1515      while ( !emptyQueue() && !(*_reached)[t] )
1516        processNextArc();
1517    }
1518
1519    /// \brief Executes the algorithm until a condition is met.
1520    ///
1521    /// Executes the algorithm until a condition is met.
1522    ///
1523    /// This method runs the %DFS algorithm from the root node
1524    /// until an arc \c a with <tt>am[a]</tt> true is found.
1525    ///
1526    /// \param am A \c bool (or convertible) arc map. The algorithm
1527    /// will stop when it reaches an arc \c a with <tt>am[a]</tt> true.
1528    ///
1529    /// \return The reached arc \c a with <tt>am[a]</tt> true or
1530    /// \c INVALID if no such arc was found.
1531    ///
1532    /// \pre init() must be called and a root node should be added
1533    /// with addSource() before using this function.
1534    ///
1535    /// \warning Contrary to \ref Bfs and \ref Dijkstra, \c am is an arc map,
1536    /// not a node map.
1537    template <typename AM>
1538    Arc start(const AM &am) {
1539      while ( !emptyQueue() && !am[_stack[_stack_head]] )
1540        processNextArc();
1541      return emptyQueue() ? INVALID : _stack[_stack_head];
1542    }
1543
1544    /// \brief Runs the algorithm from the given source node.
1545    ///
1546    /// This method runs the %DFS algorithm from node \c s.
1547    /// in order to compute the DFS path to each node.
1548    ///
1549    /// The algorithm computes
1550    /// - the %DFS tree,
1551    /// - the distance of each node from the root in the %DFS tree.
1552    ///
1553    /// \note <tt>d.run(s)</tt> is just a shortcut of the following code.
1554    ///\code
1555    ///   d.init();
1556    ///   d.addSource(s);
1557    ///   d.start();
1558    ///\endcode
1559    void run(Node s) {
1560      init();
1561      addSource(s);
1562      start();
1563    }
1564
1565    /// \brief Finds the %DFS path between \c s and \c t.
1566
1567    /// This method runs the %DFS algorithm from node \c s
1568    /// in order to compute the DFS path to node \c t
1569    /// (it stops searching when \c t is processed).
1570    ///
1571    /// \return \c true if \c t is reachable form \c s.
1572    ///
1573    /// \note Apart from the return value, <tt>d.run(s,t)</tt> is
1574    /// just a shortcut of the following code.
1575    ///\code
1576    ///   d.init();
1577    ///   d.addSource(s);
1578    ///   d.start(t);
1579    ///\endcode
1580    bool run(Node s,Node t) {
1581      init();
1582      addSource(s);
1583      start(t);
1584      return reached(t);
1585    }
1586
1587    /// \brief Runs the algorithm to visit all nodes in the digraph.
1588
1589    /// This method runs the %DFS algorithm in order to visit all nodes
1590    /// in the digraph.
1591    ///
1592    /// \note <tt>d.run()</tt> is just a shortcut of the following code.
1593    ///\code
1594    ///   d.init();
1595    ///   for (NodeIt n(digraph); n != INVALID; ++n) {
1596    ///     if (!d.reached(n)) {
1597    ///       d.addSource(n);
1598    ///       d.start();
1599    ///     }
1600    ///   }
1601    ///\endcode
1602    void run() {
1603      init();
1604      for (NodeIt it(*_digraph); it != INVALID; ++it) {
1605        if (!reached(it)) {
1606          addSource(it);
1607          start();
1608        }
1609      }
1610    }
1611
1612    ///@}
1613
1614    /// \name Query Functions
1615    /// The results of the DFS algorithm can be obtained using these
1616    /// functions.\n
1617    /// Either \ref run(Node) "run()" or \ref start() should be called
1618    /// before using them.
1619
1620    ///@{
1621
1622    /// \brief Checks if the given node is reached from the root(s).
1623    ///
1624    /// Returns \c true if \c v is reached from the root(s).
1625    ///
1626    /// \pre Either \ref run(Node) "run()" or \ref init()
1627    /// must be called before using this function.
1628    bool reached(Node v) const { return (*_reached)[v]; }
1629
1630    ///@}
1631
1632  };
1633
1634} //END OF NAMESPACE LEMON
1635
1636#endif
Note: See TracBrowser for help on using the repository browser.