COIN-OR::LEMON - Graph Library

source: lemon-1.2/lemon/dfs.h @ 788:c92296660262

Last change on this file since 788:c92296660262 was 788:c92296660262, checked in by Alpar Juttner <alpar@…>, 10 years ago

Merge

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