COIN-OR::LEMON - Graph Library

source: lemon/lemon/dfs.h @ 314:2cc60866a0c9

Last change on this file since 314:2cc60866a0c9 was 313:64f8f7cc6168, checked in by Peter Kovacs <kpeter@…>, 15 years ago

Fix several doxygen warnings

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