COIN-OR::LEMON - Graph Library

source: lemon/lemon/dfs.h @ 1007:e24922c56bc2

Last change on this file since 1007:e24922c56bc2 was 1007:e24922c56bc2, checked in by Alpar Juttner <alpar@…>, 9 years ago

Bug fix in Dfs::start(s,t) (#392)

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