COIN-OR::LEMON - Graph Library

source: lemon-1.0/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
RevLine 
[209]1/* -*- mode: C++; indent-tabs-mode: nil; -*-
[100]2 *
[209]3 * This file is a part of LEMON, a generic C++ optimization library.
[100]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
[244]24///\brief DFS algorithm.
[100]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>
[244]31#include <lemon/assert.h>
[100]32#include <lemon/maps.h>
33
34namespace lemon {
35
36  ///Default traits class of Dfs class.
37
38  ///Default traits class of Dfs class.
[157]39  ///\tparam GR Digraph type.
[100]40  template<class GR>
41  struct DfsDefaultTraits
42  {
[244]43    ///The type of the digraph the algorithm runs on.
[100]44    typedef GR Digraph;
[244]45
46    ///\brief The type of the map that stores the predecessor
[100]47    ///arcs of the %DFS paths.
[209]48    ///
[244]49    ///The type of the map that stores the predecessor
[100]50    ///arcs of the %DFS paths.
51    ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
[244]52    typedef typename Digraph::template NodeMap<typename Digraph::Arc> PredMap;
53    ///Instantiates a \ref PredMap.
[209]54
55    ///This function instantiates a \ref PredMap.
[244]56    ///\param g is the digraph, to which we would like to define the
57    ///\ref PredMap.
[100]58    ///\todo The digraph alone may be insufficient to initialize
[244]59    static PredMap *createPredMap(const Digraph &g)
[100]60    {
[244]61      return new PredMap(g);
[100]62    }
63
64    ///The type of the map that indicates which nodes are processed.
[209]65
[100]66    ///The type of the map that indicates which nodes are processed.
67    ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
[244]68    ///By default it is a NullMap.
[100]69    typedef NullMap<typename Digraph::Node,bool> ProcessedMap;
[244]70    ///Instantiates a \ref ProcessedMap.
[209]71
72    ///This function instantiates a \ref ProcessedMap.
[100]73    ///\param g is the digraph, to which
74    ///we would like to define the \ref ProcessedMap
75#ifdef DOXYGEN
[244]76    static ProcessedMap *createProcessedMap(const Digraph &g)
[100]77#else
[244]78    static ProcessedMap *createProcessedMap(const Digraph &)
[100]79#endif
80    {
81      return new ProcessedMap();
82    }
[244]83
[100]84    ///The type of the map that indicates which nodes are reached.
[209]85
[100]86    ///The type of the map that indicates which nodes are reached.
[244]87    ///It must meet the \ref concepts::ReadWriteMap "ReadWriteMap" concept.
[100]88    typedef typename Digraph::template NodeMap<bool> ReachedMap;
[244]89    ///Instantiates a \ref ReachedMap.
[209]90
91    ///This function instantiates a \ref ReachedMap.
[244]92    ///\param g is the digraph, to which
[100]93    ///we would like to define the \ref ReachedMap.
[244]94    static ReachedMap *createReachedMap(const Digraph &g)
[100]95    {
[244]96      return new ReachedMap(g);
[100]97    }
[209]98
[244]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.
[100]102    ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
103    typedef typename Digraph::template NodeMap<int> DistMap;
[244]104    ///Instantiates a \ref DistMap.
[209]105
106    ///This function instantiates a \ref DistMap.
[244]107    ///\param g is the digraph, to which we would like to define the
108    ///\ref DistMap.
109    static DistMap *createDistMap(const Digraph &g)
[100]110    {
[244]111      return new DistMap(g);
[100]112    }
113  };
[209]114
[100]115  ///%DFS algorithm class.
[209]116
[100]117  ///\ingroup search
118  ///This class provides an efficient implementation of the %DFS algorithm.
119  ///
[244]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.
[157]127  ///\tparam TR Traits class to set various data types used by the algorithm.
[100]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,
[209]134            typename TR>
[100]135#else
136  template <typename GR=ListDigraph,
[209]137            typename TR=DfsDefaultTraits<GR> >
[100]138#endif
139  class Dfs {
140  public:
[244]141    ///\ref Exception for uninitialized parameters.
142
143    ///This error represents problems in the initialization of the
144    ///parameters of the algorithm.
[100]145    class UninitializedParameter : public lemon::UninitializedParameter {
146    public:
147      virtual const char* what() const throw() {
[209]148        return "lemon::Dfs::UninitializedParameter";
[100]149      }
150    };
151
[244]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.
[100]168    typedef TR Traits;
[244]169
170  private:
171
[100]172    typedef typename Digraph::Node Node;
173    typedef typename Digraph::NodeIt NodeIt;
174    typedef typename Digraph::Arc Arc;
175    typedef typename Digraph::OutArcIt OutArcIt;
[209]176
[244]177    //Pointer to the underlying digraph.
[100]178    const Digraph *G;
[244]179    //Pointer to the map of predecessor arcs.
[100]180    PredMap *_pred;
[244]181    //Indicates if _pred is locally allocated (true) or not.
[100]182    bool local_pred;
[244]183    //Pointer to the map of distances.
[100]184    DistMap *_dist;
[244]185    //Indicates if _dist is locally allocated (true) or not.
[100]186    bool local_dist;
[244]187    //Pointer to the map of reached status of the nodes.
[100]188    ReachedMap *_reached;
[244]189    //Indicates if _reached is locally allocated (true) or not.
[100]190    bool local_reached;
[244]191    //Pointer to the map of processed status of the nodes.
[100]192    ProcessedMap *_processed;
[244]193    //Indicates if _processed is locally allocated (true) or not.
[100]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).
[209]201    void create_maps()
[100]202    {
203      if(!_pred) {
[209]204        local_pred = true;
205        _pred = Traits::createPredMap(*G);
[100]206      }
207      if(!_dist) {
[209]208        local_dist = true;
209        _dist = Traits::createDistMap(*G);
[100]210      }
211      if(!_reached) {
[209]212        local_reached = true;
213        _reached = Traits::createReachedMap(*G);
[100]214      }
215      if(!_processed) {
[209]216        local_processed = true;
217        _processed = Traits::createProcessedMap(*G);
[100]218      }
219    }
220
221  protected:
222
223    Dfs() {}
[209]224
[100]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;
[244]236      static PredMap *createPredMap(const Digraph &)
[100]237      {
[209]238        throw UninitializedParameter();
[100]239      }
240    };
241    ///\brief \ref named-templ-param "Named parameter" for setting
[244]242    ///\ref PredMap type.
[100]243    ///
[244]244    ///\ref named-templ-param "Named parameter" for setting
245    ///\ref PredMap type.
[100]246    template <class T>
247    struct DefPredMap : public Dfs<Digraph, DefPredMapTraits<T> > {
248      typedef Dfs<Digraph, DefPredMapTraits<T> > Create;
249    };
[209]250
[100]251    template <class T>
252    struct DefDistMapTraits : public Traits {
253      typedef T DistMap;
[209]254      static DistMap *createDistMap(const Digraph &)
[100]255      {
[209]256        throw UninitializedParameter();
[100]257      }
258    };
259    ///\brief \ref named-templ-param "Named parameter" for setting
[244]260    ///\ref DistMap type.
[100]261    ///
[244]262    ///\ref named-templ-param "Named parameter" for setting
263    ///\ref DistMap type.
[100]264    template <class T>
[244]265    struct DefDistMap : public Dfs< Digraph, DefDistMapTraits<T> > {
[100]266      typedef Dfs<Digraph, DefDistMapTraits<T> > Create;
267    };
[209]268
[100]269    template <class T>
270    struct DefReachedMapTraits : public Traits {
271      typedef T ReachedMap;
[209]272      static ReachedMap *createReachedMap(const Digraph &)
[100]273      {
[209]274        throw UninitializedParameter();
[100]275      }
276    };
277    ///\brief \ref named-templ-param "Named parameter" for setting
[244]278    ///\ref ReachedMap type.
[100]279    ///
[244]280    ///\ref named-templ-param "Named parameter" for setting
281    ///\ref ReachedMap type.
[100]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;
[209]290      static ProcessedMap *createProcessedMap(const Digraph &)
[100]291      {
[209]292        throw UninitializedParameter();
[100]293      }
294    };
295    ///\brief \ref named-templ-param "Named parameter" for setting
[244]296    ///\ref ProcessedMap type.
[100]297    ///
[244]298    ///\ref named-templ-param "Named parameter" for setting
299    ///\ref ProcessedMap type.
[100]300    template <class T>
[209]301    struct DefProcessedMap : public Dfs< Digraph, DefProcessedMapTraits<T> > {
[100]302      typedef Dfs< Digraph, DefProcessedMapTraits<T> > Create;
303    };
[209]304
[100]305    struct DefDigraphProcessedMapTraits : public Traits {
306      typedef typename Digraph::template NodeMap<bool> ProcessedMap;
[244]307      static ProcessedMap *createProcessedMap(const Digraph &g)
[100]308      {
[244]309        return new ProcessedMap(g);
[100]310      }
311    };
[244]312    ///\brief \ref named-templ-param "Named parameter" for setting
313    ///\ref ProcessedMap type to be <tt>Digraph::NodeMap<bool></tt>.
[100]314    ///
[244]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.
[100]318    template <class T>
[244]319    struct DefProcessedMapToBeDefaultMap :
[209]320      public Dfs< Digraph, DefDigraphProcessedMapTraits> {
[100]321      typedef Dfs< Digraph, DefDigraphProcessedMapTraits> Create;
322    };
[209]323
[100]324    ///@}
325
[209]326  public:
327
[100]328    ///Constructor.
[209]329
[244]330    ///Constructor.
331    ///\param g The digraph the algorithm runs on.
332    Dfs(const Digraph &g) :
333      G(&g),
[100]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    { }
[209]339
[100]340    ///Destructor.
[209]341    ~Dfs()
[100]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
[244]349    ///Sets the map that stores the predecessor arcs.
[100]350
[244]351    ///Sets the map that stores the predecessor arcs.
[100]352    ///If you don't use this function before calling \ref run(),
[244]353    ///it will allocate one. The destructor deallocates this
[100]354    ///automatically allocated map, of course.
355    ///\return <tt> (*this) </tt>
[209]356    Dfs &predMap(PredMap &m)
[100]357    {
358      if(local_pred) {
[209]359        delete _pred;
360        local_pred=false;
[100]361      }
362      _pred = &m;
363      return *this;
364    }
365
[244]366    ///Sets the map that indicates which nodes are reached.
[100]367
[244]368    ///Sets the map that indicates which nodes are reached.
[100]369    ///If you don't use this function before calling \ref run(),
[244]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
[100]406    ///automatically allocated map, of course.
407    ///\return <tt> (*this) </tt>
[209]408    Dfs &distMap(DistMap &m)
[100]409    {
410      if(local_dist) {
[209]411        delete _dist;
412        local_dist=false;
[100]413      }
414      _dist = &m;
415      return *this;
416    }
417
[244]418  public:
[100]419
420    ///\name Execution control
421    ///The simplest way to execute the algorithm is to use
[244]422    ///one of the member functions called \ref lemon::Dfs::run() "run()".
[100]423    ///\n
[244]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.
[100]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 ) {
[209]442        _pred->set(u,INVALID);
443        _reached->set(u,false);
444        _processed->set(u,false);
[100]445      }
446    }
[209]447
[100]448    ///Adds a new source node.
449
450    ///Adds a new source node to the set of nodes to be processed.
451    ///
[244]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.
[100]457    void addSource(Node s)
458    {
[244]459      LEMON_DEBUG(emptyQueue(), "The stack is not empty.");
[100]460      if(!(*_reached)[s])
[209]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        }
[100]474    }
[209]475
[100]476    ///Processes the next arc.
477
478    ///Processes the next arc.
479    ///
480    ///\return The processed arc.
481    ///
[244]482    ///\pre The stack must not be empty.
[100]483    Arc processNextArc()
[209]484    {
[100]485      Node m;
486      Arc e=_stack[_stack_head];
487      if(!(*_reached)[m=G->target(e)]) {
[209]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);
[100]493      }
494      else {
[209]495        m=G->source(e);
496        ++_stack[_stack_head];
[100]497      }
498      while(_stack_head>=0 && _stack[_stack_head]==INVALID) {
[209]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        }
[100]505      }
506      return e;
507    }
[244]508
[100]509    ///Next arc to be processed.
510
511    ///Next arc to be processed.
512    ///
[244]513    ///\return The next arc to be processed or \c INVALID if the stack
514    ///is empty.
515    OutArcIt nextArc() const
[209]516    {
[100]517      return _stack_head>=0?_stack[_stack_head]:INVALID;
518    }
519
520    ///\brief Returns \c false if there are nodes
[244]521    ///to be processed.
[100]522    ///
523    ///Returns \c false if there are nodes
[244]524    ///to be processed in the queue (stack).
525    bool emptyQueue() const { return _stack_head<0; }
526
[100]527    ///Returns the number of the nodes to be processed.
[209]528
[244]529    ///Returns the number of the nodes to be processed in the queue (stack).
530    int queueSize() const { return _stack_head+1; }
[209]531
[100]532    ///Executes the algorithm.
533
534    ///Executes the algorithm.
535    ///
[244]536    ///This method runs the %DFS algorithm from the root node
537    ///in order to compute the DFS path to each node.
[100]538    ///
[244]539    /// The algorithm computes
540    ///- the %DFS tree,
541    ///- the distance of each node from the root in the %DFS tree.
[100]542    ///
[244]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
[100]552    void start()
553    {
554      while ( !emptyQueue() ) processNextArc();
555    }
[209]556
[244]557    ///Executes the algorithm until the given target node is reached.
[100]558
[244]559    ///Executes the algorithm until the given target node is reached.
[100]560    ///
[244]561    ///This method runs the %DFS algorithm from the root node
562    ///in order to compute the DFS path to \c dest.
[100]563    ///
[244]564    ///The algorithm computes
565    ///- the %DFS path to \c dest,
566    ///- the distance of \c dest from the root in the %DFS tree.
[100]567    ///
[244]568    ///\pre init() must be called and a root node should be
569    ///added with addSource() before using this function.
[100]570    void start(Node dest)
571    {
[209]572      while ( !emptyQueue() && G->target(_stack[_stack_head])!=dest )
573        processNextArc();
[100]574    }
[209]575
[100]576    ///Executes the algorithm until a condition is met.
577
578    ///Executes the algorithm until a condition is met.
579    ///
[244]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.
[100]582    ///
[244]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.
[100]585    ///
[244]586    ///\return The reached arc \c a with <tt>am[a]</tt> true or
[100]587    ///\c INVALID if no such arc was found.
588    ///
[244]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,
[100]593    ///not a node map.
[244]594    template<class ArcBoolMap>
595    Arc start(const ArcBoolMap &am)
[100]596    {
[244]597      while ( !emptyQueue() && !am[_stack[_stack_head]] )
[100]598        processNextArc();
599      return emptyQueue() ? INVALID : _stack[_stack_head];
600    }
601
[244]602    ///Runs the algorithm from the given node.
[209]603
[244]604    ///This method runs the %DFS algorithm from node \c s
605    ///in order to compute the DFS path to each node.
[100]606    ///
[244]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.
[100]612    ///\code
613    ///  d.init();
[244]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);
[100]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
[244]679    ///Either \ref lemon::Dfs::run() "run()" or \ref lemon::Dfs::start()
680    ///"start()" must be called before using them.
[209]681
[100]682    ///@{
683
[244]684    ///The DFS path to a node.
[100]685
[244]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); }
[209]693
[244]694    ///The distance of a node from the root.
[100]695
[244]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.
[100]703    int dist(Node v) const { return (*_dist)[v]; }
704
[244]705    ///Returns the 'previous arc' of the %DFS tree for a node.
[100]706
[244]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
[100]713    ///\ref predNode().
[244]714    ///
[100]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
[244]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    ///
[100]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:
[209]732                                  G->source((*_pred)[v]); }
733
[244]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.
[100]742    const DistMap &distMap() const { return *_dist;}
[209]743
[244]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    ///
[100]750    ///\pre Either \ref run() or \ref init()
751    ///must be called before using this function.
752    const PredMap &predMap() const { return *_pred;}
[209]753
[244]754    ///Checks if a node is reachable from the root(s).
[100]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.
[244]759    bool reached(Node v) const { return (*_reached)[v]; }
[209]760
[100]761    ///@}
762  };
763
[244]764  ///Default traits class of dfs() function.
[100]765
[244]766  ///Default traits class of dfs() function.
[157]767  ///\tparam GR Digraph type.
[100]768  template<class GR>
769  struct DfsWizardDefaultTraits
770  {
[244]771    ///The type of the digraph the algorithm runs on.
[100]772    typedef GR Digraph;
[244]773
774    ///\brief The type of the map that stores the predecessor
[100]775    ///arcs of the %DFS paths.
[209]776    ///
[244]777    ///The type of the map that stores the predecessor
[100]778    ///arcs of the %DFS paths.
779    ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
780    ///
[244]781    typedef NullMap<typename Digraph::Node,typename Digraph::Arc> PredMap;
782    ///Instantiates a \ref PredMap.
[209]783
784    ///This function instantiates a \ref PredMap.
[244]785    ///\param g is the digraph, to which we would like to define the
786    ///\ref PredMap.
[100]787    ///\todo The digraph alone may be insufficient to initialize
788#ifdef DOXYGEN
[244]789    static PredMap *createPredMap(const Digraph &g)
[100]790#else
[244]791    static PredMap *createPredMap(const Digraph &)
[100]792#endif
793    {
794      return new PredMap();
795    }
796
797    ///The type of the map that indicates which nodes are processed.
[209]798
[100]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;
[244]802    ///Instantiates a \ref ProcessedMap.
[209]803
804    ///This function instantiates a \ref ProcessedMap.
[100]805    ///\param g is the digraph, to which
[244]806    ///we would like to define the \ref ProcessedMap.
[100]807#ifdef DOXYGEN
[244]808    static ProcessedMap *createProcessedMap(const Digraph &g)
[100]809#else
[244]810    static ProcessedMap *createProcessedMap(const Digraph &)
[100]811#endif
812    {
813      return new ProcessedMap();
814    }
[244]815
[100]816    ///The type of the map that indicates which nodes are reached.
[209]817
[100]818    ///The type of the map that indicates which nodes are reached.
[244]819    ///It must meet the \ref concepts::ReadWriteMap "ReadWriteMap" concept.
[100]820    typedef typename Digraph::template NodeMap<bool> ReachedMap;
[244]821    ///Instantiates a \ref ReachedMap.
[209]822
823    ///This function instantiates a \ref ReachedMap.
[244]824    ///\param g is the digraph, to which
[100]825    ///we would like to define the \ref ReachedMap.
[244]826    static ReachedMap *createReachedMap(const Digraph &g)
[100]827    {
[244]828      return new ReachedMap(g);
[100]829    }
[209]830
[244]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.
[100]834    ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
835    ///
836    typedef NullMap<typename Digraph::Node,int> DistMap;
[244]837    ///Instantiates a \ref DistMap.
[209]838
839    ///This function instantiates a \ref DistMap.
[210]840    ///\param g is the digraph, to which we would like to define
841    ///the \ref DistMap
[100]842#ifdef DOXYGEN
[244]843    static DistMap *createDistMap(const Digraph &g)
[100]844#else
[244]845    static DistMap *createDistMap(const Digraph &)
[100]846#endif
847    {
848      return new DistMap();
849    }
850  };
[209]851
[244]852  /// Default traits class used by \ref DfsWizard
[100]853
854  /// To make it easier to use Dfs algorithm
[244]855  /// we have created a wizard class.
[100]856  /// This \ref DfsWizard class needs default traits,
[244]857  /// as well as the \ref Dfs class.
[100]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:
[244]866    //The type of the nodes in the digraph.
[100]867    typedef typename Base::Digraph::Node Node;
868
[244]869    //Pointer to the digraph the algorithm runs on.
[100]870    void *_g;
[244]871    //Pointer to the map of reached nodes.
[100]872    void *_reached;
[244]873    //Pointer to the map of processed nodes.
[100]874    void *_processed;
[244]875    //Pointer to the map of predecessors arcs.
[100]876    void *_pred;
[244]877    //Pointer to the map of distances.
[100]878    void *_dist;
[244]879    //Pointer to the source node.
[100]880    Node _source;
[209]881
[100]882    public:
883    /// Constructor.
[209]884
[100]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),
[244]888                      _dist(0), _source(INVALID) {}
[100]889
890    /// Constructor.
[209]891
[100]892    /// This constructor requires some parameters,
893    /// listed in the parameters list.
894    /// Others are initiated to 0.
[244]895    /// \param g The digraph the algorithm runs on.
896    /// \param s The source node.
[100]897    DfsWizardBase(const GR &g, Node s=INVALID) :
[209]898      _g(reinterpret_cast<void*>(const_cast<GR*>(&g))),
[100]899      _reached(0), _processed(0), _pred(0), _dist(0), _source(s) {}
900
901  };
[209]902
[244]903  /// Auxiliary class for the function type interface of DFS algorithm.
[100]904
[244]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.
[100]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
[244]918  /// a function have to be called, and it will
[100]919  /// return the needed class.
920  ///
[244]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.
[100]924  template<class TR>
925  class DfsWizard : public TR
926  {
927    typedef TR Base;
928
[244]929    ///The type of the digraph the algorithm runs on.
[100]930    typedef typename TR::Digraph Digraph;
[244]931
[100]932    typedef typename Digraph::Node Node;
933    typedef typename Digraph::NodeIt NodeIt;
934    typedef typename Digraph::Arc Arc;
935    typedef typename Digraph::OutArcIt OutArcIt;
[209]936
[244]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.
[100]943    typedef typename TR::ReachedMap ReachedMap;
[244]944    ///\brief The type of the map that indicates which nodes are processed.
[100]945    typedef typename TR::ProcessedMap ProcessedMap;
946
947  public:
[244]948
[100]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
[244]964    ///Runs DFS algorithm from a source node.
[209]965
[244]966    ///Runs DFS algorithm from a source node.
967    ///The node can be given with the \ref source() function.
[100]968    void run()
969    {
970      if(Base::_source==INVALID) throw UninitializedParameter();
971      Dfs<Digraph,TR> alg(*reinterpret_cast<const Digraph*>(Base::_g));
[209]972      if(Base::_reached)
[100]973        alg.reachedMap(*reinterpret_cast<ReachedMap*>(Base::_reached));
[209]974      if(Base::_processed)
[100]975        alg.processedMap(*reinterpret_cast<ProcessedMap*>(Base::_processed));
[209]976      if(Base::_pred)
[100]977        alg.predMap(*reinterpret_cast<PredMap*>(Base::_pred));
[209]978      if(Base::_dist)
[100]979        alg.distMap(*reinterpret_cast<DistMap*>(Base::_dist));
980      alg.run(Base::_source);
981    }
982
[244]983    ///Runs DFS algorithm from the given node.
[100]984
[244]985    ///Runs DFS algorithm from the given node.
[100]986    ///\param s is the given source.
987    void run(Node s)
988    {
989      Base::_source=s;
990      run();
991    }
992
[244]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
[100]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"
[244]1010    ///for setting \ref PredMap object.
[100]1011    ///
[244]1012    ///\ref named-templ-param "Named parameter"
1013    ///for setting \ref PredMap object.
[100]1014    template<class T>
[209]1015    DfsWizard<DefPredMapBase<T> > predMap(const T &t)
[100]1016    {
1017      Base::_pred=reinterpret_cast<void*>(const_cast<T*>(&t));
1018      return DfsWizard<DefPredMapBase<T> >(*this);
1019    }
[209]1020
[100]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"
[244]1028    ///for setting \ref ReachedMap object.
[100]1029    ///
1030    /// \ref named-templ-param "Named parameter"
[244]1031    ///for setting \ref ReachedMap object.
[100]1032    template<class T>
[209]1033    DfsWizard<DefReachedMapBase<T> > reachedMap(const T &t)
[100]1034    {
[158]1035      Base::_reached=reinterpret_cast<void*>(const_cast<T*>(&t));
[100]1036      return DfsWizard<DefReachedMapBase<T> >(*this);
1037    }
[209]1038
[100]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"
[244]1046    ///for setting \ref ProcessedMap object.
[100]1047    ///
1048    /// \ref named-templ-param "Named parameter"
[244]1049    ///for setting \ref ProcessedMap object.
[100]1050    template<class T>
[209]1051    DfsWizard<DefProcessedMapBase<T> > processedMap(const T &t)
[100]1052    {
[158]1053      Base::_processed=reinterpret_cast<void*>(const_cast<T*>(&t));
[100]1054      return DfsWizard<DefProcessedMapBase<T> >(*this);
1055    }
[209]1056
[100]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"
[244]1064    ///for setting \ref DistMap object.
[100]1065    ///
[244]1066    ///\ref named-templ-param "Named parameter"
1067    ///for setting \ref DistMap object.
[100]1068    template<class T>
[209]1069    DfsWizard<DefDistMapBase<T> > distMap(const T &t)
[100]1070    {
1071      Base::_dist=reinterpret_cast<void*>(const_cast<T*>(&t));
1072      return DfsWizard<DefDistMapBase<T> >(*this);
1073    }
[209]1074
[100]1075  };
[209]1076
[100]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
[244]1102  /// \brief Visitor class for DFS.
[209]1103  ///
[244]1104  /// This class defines the interface of the DfsVisit events, and
1105  /// it could be the base of a real visitor class.
[100]1106  template <typename _Digraph>
1107  struct DfsVisitor {
1108    typedef _Digraph Digraph;
1109    typedef typename Digraph::Arc Arc;
1110    typedef typename Digraph::Node Node;
[244]1111    /// \brief Called for the source node of the DFS.
[209]1112    ///
[244]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.
[100]1127    void discover(const Arc& arc) {}
[244]1128    /// \brief Called when an arc is examined but its target node is
[100]1129    /// already discovered.
[209]1130    ///
[244]1131    /// This function is called when an arc is examined but its target node is
[100]1132    /// already discovered.
1133    void examine(const Arc& arc) {}
[244]1134    /// \brief Called when the DFS steps back from a node.
[209]1135    ///
[244]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.
[209]1139    ///
[244]1140    /// This function is called when the DFS steps back on an arc.
1141    void backtrack(const Arc& arc) {}
[100]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&) {}
[244]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&) {}
[100]1156
1157    template <typename _Visitor>
1158    struct Constraints {
1159      void constraints() {
[209]1160        Arc arc;
1161        Node node;
1162        visitor.start(node);
1163        visitor.stop(arc);
[244]1164        visitor.reach(node);
1165        visitor.discover(arc);
1166        visitor.examine(arc);
1167        visitor.leave(node);
1168        visitor.backtrack(arc);
[100]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.
[244]1178  /// \tparam _Digraph The type of the digraph the algorithm runs on.
[100]1179  template<class _Digraph>
1180  struct DfsVisitDefaultTraits {
1181
[244]1182    /// \brief The type of the digraph the algorithm runs on.
[100]1183    typedef _Digraph Digraph;
1184
1185    /// \brief The type of the map that indicates which nodes are reached.
[209]1186    ///
[100]1187    /// The type of the map that indicates which nodes are reached.
[244]1188    /// It must meet the \ref concepts::ReadWriteMap "ReadWriteMap" concept.
[100]1189    typedef typename Digraph::template NodeMap<bool> ReachedMap;
1190
[244]1191    /// \brief Instantiates a \ref ReachedMap.
[100]1192    ///
[209]1193    /// This function instantiates a \ref ReachedMap.
[100]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  };
[209]1201
[100]1202  /// \ingroup search
[244]1203  ///
1204  /// \brief %DFS algorithm class with visitor interface.
1205  ///
[100]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
[244]1211  /// the member functions of the \c Visitor class on every DFS event.
[100]1212  ///
[244]1213  /// \tparam _Digraph The type of the digraph the algorithm runs on.
[210]1214  /// The default value is
[244]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.
[209]1221  /// \tparam _Traits Traits class to set various data types used by the
[100]1222  /// algorithm. The default traits class is
1223  /// \ref DfsVisitDefaultTraits "DfsVisitDefaultTraits<_Digraph>".
1224  /// See \ref DfsVisitDefaultTraits for the documentation of
[244]1225  /// a DFS visit traits class.
[100]1226#ifdef DOXYGEN
1227  template <typename _Digraph, typename _Visitor, typename _Traits>
1228#else
1229  template <typename _Digraph = ListDigraph,
[209]1230            typename _Visitor = DfsVisitor<_Digraph>,
1231            typename _Traits = DfsDefaultTraits<_Digraph> >
[100]1232#endif
1233  class DfsVisit {
1234  public:
[209]1235
[100]1236    /// \brief \ref Exception for uninitialized parameters.
1237    ///
1238    /// This error represents problems in the initialization
[244]1239    /// of the parameters of the algorithm.
[100]1240    class UninitializedParameter : public lemon::UninitializedParameter {
1241    public:
[209]1242      virtual const char* what() const throw()
[100]1243      {
[209]1244        return "lemon::DfsVisit::UninitializedParameter";
[100]1245      }
1246    };
1247
[244]1248    ///The traits class.
[100]1249    typedef _Traits Traits;
1250
[244]1251    ///The type of the digraph the algorithm runs on.
[100]1252    typedef typename Traits::Digraph Digraph;
1253
[244]1254    ///The visitor type used by the algorithm.
[100]1255    typedef _Visitor Visitor;
1256
[244]1257    ///The type of the map that indicates which nodes are reached.
[100]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
[244]1267    //Pointer to the underlying digraph.
[100]1268    const Digraph *_digraph;
[244]1269    //Pointer to the visitor object.
[100]1270    Visitor *_visitor;
[244]1271    //Pointer to the map of reached status of the nodes.
[100]1272    ReachedMap *_reached;
[244]1273    //Indicates if _reached is locally allocated (true) or not.
[100]1274    bool local_reached;
1275
1276    std::vector<typename Digraph::Arc> _stack;
1277    int _stack_head;
1278
[244]1279    ///Creates the maps if necessary.
1280    ///\todo Better memory allocation (instead of new).
[100]1281    void create_maps() {
1282      if(!_reached) {
[209]1283        local_reached = true;
1284        _reached = Traits::createReachedMap(*_digraph);
[100]1285      }
1286    }
1287
1288  protected:
1289
1290    DfsVisit() {}
[209]1291
[100]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) {
[209]1303        throw UninitializedParameter();
[100]1304      }
1305    };
[209]1306    /// \brief \ref named-templ-param "Named parameter" for setting
[244]1307    /// ReachedMap type.
[100]1308    ///
[244]1309    /// \ref named-templ-param "Named parameter" for setting ReachedMap type.
[100]1310    template <class T>
1311    struct DefReachedMap : public DfsVisit< Digraph, Visitor,
[209]1312                                            DefReachedMapTraits<T> > {
[100]1313      typedef DfsVisit< Digraph, Visitor, DefReachedMapTraits<T> > Create;
1314    };
1315    ///@}
1316
[209]1317  public:
1318
[100]1319    /// \brief Constructor.
1320    ///
1321    /// Constructor.
1322    ///
[244]1323    /// \param digraph The digraph the algorithm runs on.
1324    /// \param visitor The visitor object of the algorithm.
[209]1325    DfsVisit(const Digraph& digraph, Visitor& visitor)
[100]1326      : _digraph(&digraph), _visitor(&visitor),
[209]1327        _reached(0), local_reached(false) {}
1328
[100]1329    /// \brief Destructor.
1330    ~DfsVisit() {
1331      if(local_reached) delete _reached;
1332    }
1333
[244]1334    /// \brief Sets the map that indicates which nodes are reached.
[100]1335    ///
[244]1336    /// Sets the map that indicates which nodes are reached.
[100]1337    /// If you don't use this function before calling \ref run(),
[244]1338    /// it will allocate one. The destructor deallocates this
[100]1339    /// automatically allocated map, of course.
1340    /// \return <tt> (*this) </tt>
1341    DfsVisit &reachedMap(ReachedMap &m) {
1342      if(local_reached) {
[209]1343        delete _reached;
1344        local_reached=false;
[100]1345      }
1346      _reached = &m;
1347      return *this;
1348    }
1349
1350  public:
[244]1351
[100]1352    /// \name Execution control
1353    /// The simplest way to execute the algorithm is to use
[244]1354    /// one of the member functions called \ref lemon::DfsVisit::run()
1355    /// "run()".
[100]1356    /// \n
[244]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.
[100]1362
1363    /// @{
[244]1364
[100]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) {
[209]1373        _reached->set(u, false);
[100]1374      }
1375    }
[209]1376
[244]1377    ///Adds a new source node.
1378
1379    ///Adds a new source node to the set of nodes to be processed.
[100]1380    ///
[244]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.");
[100]1389      if(!(*_reached)[s]) {
[209]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        }
[100]1401    }
[209]1402
[100]1403    /// \brief Processes the next arc.
1404    ///
1405    /// Processes the next arc.
1406    ///
1407    /// \return The processed arc.
1408    ///
[244]1409    /// \pre The stack must not be empty.
[209]1410    Arc processNextArc() {
[100]1411      Arc e = _stack[_stack_head];
1412      Node m = _digraph->target(e);
1413      if(!(*_reached)[m]) {
[209]1414        _visitor->discover(e);
1415        _visitor->reach(m);
1416        _reached->set(m, true);
1417        _digraph->firstOut(_stack[++_stack_head], m);
[100]1418      } else {
[209]1419        _visitor->examine(e);
1420        m = _digraph->source(e);
1421        _digraph->nextOut(_stack[_stack_head]);
[100]1422      }
1423      while (_stack_head>=0 && _stack[_stack_head] == INVALID) {
[209]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        }
[100]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.
[244]1443    Arc nextArc() const {
[100]1444      return _stack_head >= 0 ? _stack[_stack_head] : INVALID;
1445    }
1446
1447    /// \brief Returns \c false if there are nodes
[244]1448    /// to be processed.
[100]1449    ///
1450    /// Returns \c false if there are nodes
[244]1451    /// to be processed in the queue (stack).
1452    bool emptyQueue() const { return _stack_head < 0; }
[100]1453
1454    /// \brief Returns the number of the nodes to be processed.
1455    ///
[244]1456    /// Returns the number of the nodes to be processed in the queue (stack).
1457    int queueSize() const { return _stack_head + 1; }
[209]1458
[100]1459    /// \brief Executes the algorithm.
1460    ///
1461    /// Executes the algorithm.
1462    ///
[244]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
[100]1479    void start() {
1480      while ( !emptyQueue() ) processNextArc();
1481    }
[209]1482
[244]1483    /// \brief Executes the algorithm until the given target node is reached.
[100]1484    ///
[244]1485    /// Executes the algorithm until the given target node is reached.
[100]1486    ///
[244]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
[100]1495    /// with addSource() before using this function.
1496    void start(Node dest) {
[209]1497      while ( !emptyQueue() && _digraph->target(_stack[_stack_head]) != dest )
1498        processNextArc();
[100]1499    }
[209]1500
[100]1501    /// \brief Executes the algorithm until a condition is met.
1502    ///
1503    /// Executes the algorithm until a condition is met.
1504    ///
[244]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
[100]1515    /// with addSource() before using this function.
1516    ///
[244]1517    /// \warning Contrary to \ref Bfs and \ref Dijkstra, \c am is an arc map,
[100]1518    /// not a node map.
[244]1519    template <typename AM>
1520    Arc start(const AM &am) {
1521      while ( !emptyQueue() && !am[_stack[_stack_head]] )
[100]1522        processNextArc();
1523      return emptyQueue() ? INVALID : _stack[_stack_head];
1524    }
1525
[244]1526    /// \brief Runs the algorithm from the given node.
[100]1527    ///
[244]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.
[100]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
[244]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.
[209]1570
[100]1571    /// This method runs the %DFS algorithm in order to
[244]1572    /// compute the %DFS path to each node.
[100]1573    ///
[244]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.
[100]1579    ///\code
[244]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    ///   }
[100]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    }
[244]1597
[100]1598    ///@}
1599
1600    /// \name Query Functions
1601    /// The result of the %DFS algorithm can be obtained using these
1602    /// functions.\n
[244]1603    /// Either \ref lemon::DfsVisit::run() "run()" or
1604    /// \ref lemon::DfsVisit::start() "start()" must be called before
1605    /// using them.
[100]1606    ///@{
[244]1607
1608    /// \brief Checks if a node is reachable from the root(s).
[100]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]; }
[244]1614
[100]1615    ///@}
[244]1616
[100]1617  };
1618
1619} //END OF NAMESPACE LEMON
1620
1621#endif
Note: See TracBrowser for help on using the repository browser.