COIN-OR::LEMON - Graph Library

source: lemon-1.0/lemon/dfs.h @ 287:bb40b6db0a58

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

Merge

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