COIN-OR::LEMON - Graph Library

source: lemon/lemon/dfs.h @ 280:e7f8647ce760

Last change on this file since 280:e7f8647ce760 was 280:e7f8647ce760, checked in by Alpar Juttner <alpar@…>, 11 years ago

Remove todo-s and convert them to trac tickets

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