COIN-OR::LEMON - Graph Library

source: lemon-1.2/lemon/dfs.h @ 282:dc9e8d2c0df9

Last change on this file since 282:dc9e8d2c0df9 was 278:931190050520, checked in by Peter Kovacs <kpeter@…>, 16 years ago

Improve the function-type interface of bfs, dfs, and dijkstra (ticket #96)

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