COIN-OR::LEMON - Graph Library

source: lemon-1.2/lemon/dfs.h @ 863:a93f1a27d831

Last change on this file since 863:a93f1a27d831 was 825:75e6020b19b1, checked in by Peter Kovacs <kpeter@…>, 14 years ago

Add doc for the traits class parameters (#315)

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