COIN-OR::LEMON - Graph Library

source: lemon/lemon/dfs.h @ 833:e20173729589

Last change on this file since 833:e20173729589 was 833:e20173729589, checked in by Peter Kovacs <kpeter@…>, 14 years ago

Small doc fixes in several files (#331)

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