COIN-OR::LEMON - Graph Library

source: lemon/lemon/dfs.h @ 956:141f9c0db4a3

Last change on this file since 956:141f9c0db4a3 was 956:141f9c0db4a3, checked in by Alpar Juttner <alpar@…>, 14 years ago

Unify the sources (#339)

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