COIN-OR::LEMON - Graph Library

source: lemon-1.2/lemon/dfs.h @ 244:c30731a37f91

Last change on this file since 244:c30731a37f91 was 244:c30731a37f91, checked in by Peter Kovacs <kpeter@…>, 11 years ago

Many improvements in bfs.h, dfs.h and dijkstra.h

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