COIN-OR::LEMON - Graph Library

source: lemon-1.2/lemon/dfs.h @ 954:be7dd3a8d6a3

1.2
Last change on this file since 954:be7dd3a8d6a3 was 954:be7dd3a8d6a3, checked in by Alpar Juttner <alpar@…>, 12 years ago

Merge Intel C++ compatibility fixes to branch 1.2

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 *
[877]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.
[716]50    ///It must conform to the \ref concepts::WriteMap "WriteMap" concept.
[244]51    typedef typename Digraph::template NodeMap<typename Digraph::Arc> PredMap;
[492]52    ///Instantiates a \c PredMap.
[209]53
[492]54    ///This function instantiates a \ref PredMap.
[244]55    ///\param g is the digraph, to which we would like to define the
[492]56    ///\ref PredMap.
[244]57    static PredMap *createPredMap(const Digraph &g)
[100]58    {
[244]59      return new PredMap(g);
[100]60    }
61
62    ///The type of the map that indicates which nodes are processed.
[209]63
[100]64    ///The type of the map that indicates which nodes are processed.
[716]65    ///It must conform to the \ref concepts::WriteMap "WriteMap" concept.
[786]66    ///By default, it is a NullMap.
[100]67    typedef NullMap<typename Digraph::Node,bool> ProcessedMap;
[492]68    ///Instantiates a \c ProcessedMap.
[209]69
[492]70    ///This function instantiates a \ref ProcessedMap.
[100]71    ///\param g is the digraph, to which
[492]72    ///we would like to define the \ref ProcessedMap.
[100]73#ifdef DOXYGEN
[244]74    static ProcessedMap *createProcessedMap(const Digraph &g)
[100]75#else
[244]76    static ProcessedMap *createProcessedMap(const Digraph &)
[100]77#endif
78    {
79      return new ProcessedMap();
80    }
[244]81
[100]82    ///The type of the map that indicates which nodes are reached.
[209]83
[100]84    ///The type of the map that indicates which nodes are reached.
[877]85    ///It must conform to
86    ///the \ref concepts::ReadWriteMap "ReadWriteMap" concept.
[100]87    typedef typename Digraph::template NodeMap<bool> ReachedMap;
[492]88    ///Instantiates a \c ReachedMap.
[209]89
[492]90    ///This function instantiates a \ref ReachedMap.
[244]91    ///\param g is the digraph, to which
[492]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.
[716]101    ///It must conform to the \ref concepts::WriteMap "WriteMap" concept.
[100]102    typedef typename Digraph::template NodeMap<int> DistMap;
[492]103    ///Instantiates a \c DistMap.
[209]104
[492]105    ///This function instantiates a \ref DistMap.
[244]106    ///\param g is the digraph, to which we would like to define the
[492]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.
[405]124  ///The default type is \ref ListDigraph.
[825]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
[405]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
[584]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
[492]230    ///\c PredMap type.
[100]231    ///
[244]232    ///\ref named-templ-param "Named parameter" for setting
[492]233    ///\c PredMap type.
[716]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
[492]250    ///\c DistMap type.
[100]251    ///
[244]252    ///\ref named-templ-param "Named parameter" for setting
[492]253    ///\c DistMap type.
[716]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
[492]270    ///\c ReachedMap type.
[100]271    ///
[244]272    ///\ref named-templ-param "Named parameter" for setting
[492]273    ///\c ReachedMap type.
[877]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
[492]291    ///\c ProcessedMap type.
[100]292    ///
[244]293    ///\ref named-templ-param "Named parameter" for setting
[492]294    ///\c ProcessedMap type.
[716]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
[492]309    ///\c ProcessedMap type to be <tt>Digraph::NodeMap<bool></tt>.
[100]310    ///
[244]311    ///\ref named-templ-param "Named parameter" for setting
[492]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.
[405]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.
[405]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.
[405]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.
[405]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
[405]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
[713]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()
[405]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
[405]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    ///
[405]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
[405]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
[405]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    {
[899]568      while ( !emptyQueue() && !(*_reached)[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
[787]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
[405]669    ///The results of the DFS algorithm can be obtained using these
[100]670    ///functions.\n
[405]671    ///Either \ref run(Node) "run()" or \ref start() should be called
672    ///before using them.
[209]673
[100]674    ///@{
675
[716]676    ///The DFS path to the given node.
[100]677
[716]678    ///Returns the DFS path to the given node from the root(s).
[244]679    ///
[405]680    ///\warning \c t should be reached from the root(s).
[244]681    ///
[405]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
[716]686    ///The distance of the given node from the root(s).
[100]687
[716]688    ///Returns the distance of the given node from the root(s).
[244]689    ///
[405]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    ///
[405]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
[716]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
[405]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
[716]705    ///\ref predNode() and \ref predMap().
[244]706    ///
[405]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
[716]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
[716]715    ///of a %DFS path from a root to \c v. It is \c INVALID
[405]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
[716]719    ///\ref predArc() and \ref predMap().
[244]720    ///
[405]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    ///
[405]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
[716]740    ///arcs, which form the DFS tree (forest).
[244]741    ///
[405]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
[716]746    ///Checks if the given node. node is reached from the root(s).
[100]747
[405]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.
[716]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.
[716]787    ///It must conform to the \ref concepts::WriteMap "WriteMap" concept.
[786]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.
[877]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.
[716]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.
[716]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
[716]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
[716]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.
[405]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.
[825]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
[787]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    };
[716]999
1000    ///\brief \ref named-templ-param "Named parameter" for setting
1001    ///the predecessor map.
[100]1002    ///
[716]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    };
[716]1018
1019    ///\brief \ref named-templ-param "Named parameter" for setting
1020    ///the reached map.
[100]1021    ///
[716]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    };
[716]1037
1038    ///\brief \ref named-templ-param "Named parameter" for setting
1039    ///the distance map.
[278]1040    ///
[716]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    };
[716]1057
1058    ///\brief \ref named-func-param "Named parameter" for setting
1059    ///the processed map.
[100]1060    ///
[716]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
[405]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.
[492]1131  template <typename GR>
[100]1132  struct DfsVisitor {
[492]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
[492]1169  template <typename GR>
[100]1170  struct DfsVisitor {
[492]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;
[953]1196      Constraints() {}
[100]1197    };
1198  };
1199#endif
1200
1201  /// \brief Default traits class of DfsVisit class.
1202  ///
1203  /// Default traits class of DfsVisit class.
[244]1204  /// \tparam _Digraph The type of the digraph the algorithm runs on.
[492]1205  template<class GR>
[100]1206  struct DfsVisitDefaultTraits {
1207
[244]1208    /// \brief The type of the digraph the algorithm runs on.
[492]1209    typedef GR Digraph;
[100]1210
1211    /// \brief The type of the map that indicates which nodes are reached.
[209]1212    ///
[100]1213    /// The type of the map that indicates which nodes are reached.
[877]1214    /// It must conform to the
1215    /// \ref concepts::ReadWriteMap "ReadWriteMap" concept.
[100]1216    typedef typename Digraph::template NodeMap<bool> ReachedMap;
1217
[301]1218    /// \brief Instantiates a ReachedMap.
[100]1219    ///
[301]1220    /// This function instantiates a ReachedMap.
[100]1221    /// \param digraph is the digraph, to which
[301]1222    /// we would like to define the ReachedMap.
[100]1223    static ReachedMap *createReachedMap(const Digraph &digraph) {
1224      return new ReachedMap(digraph);
1225    }
1226
1227  };
[209]1228
[100]1229  /// \ingroup search
[244]1230  ///
[492]1231  /// \brief DFS algorithm class with visitor interface.
[244]1232  ///
[492]1233  /// This class provides an efficient implementation of the DFS algorithm
[100]1234  /// with visitor interface.
1235  ///
[492]1236  /// The DfsVisit class provides an alternative interface to the Dfs
[100]1237  /// class. It works with callback mechanism, the DfsVisit object calls
[244]1238  /// the member functions of the \c Visitor class on every DFS event.
[100]1239  ///
[252]1240  /// This interface of the DFS algorithm should be used in special cases
1241  /// when extra actions have to be performed in connection with certain
1242  /// events of the DFS algorithm. Otherwise consider to use Dfs or dfs()
1243  /// instead.
1244  ///
[492]1245  /// \tparam GR The type of the digraph the algorithm runs on.
1246  /// The default type is \ref ListDigraph.
1247  /// The value of GR is not used directly by \ref DfsVisit,
1248  /// it is only passed to \ref DfsVisitDefaultTraits.
1249  /// \tparam VS The Visitor type that is used by the algorithm.
1250  /// \ref DfsVisitor "DfsVisitor<GR>" is an empty visitor, which
[244]1251  /// does not observe the DFS events. If you want to observe the DFS
1252  /// events, you should implement your own visitor class.
[825]1253  /// \tparam TR The traits class that defines various types used by the
1254  /// algorithm. By default, it is \ref DfsVisitDefaultTraits
1255  /// "DfsVisitDefaultTraits<GR>".
1256  /// In most cases, this parameter should not be set directly,
1257  /// consider to use the named template parameters instead.
[100]1258#ifdef DOXYGEN
[492]1259  template <typename GR, typename VS, typename TR>
[100]1260#else
[492]1261  template <typename GR = ListDigraph,
1262            typename VS = DfsVisitor<GR>,
1263            typename TR = DfsVisitDefaultTraits<GR> >
[100]1264#endif
1265  class DfsVisit {
1266  public:
[209]1267
[244]1268    ///The traits class.
[492]1269    typedef TR Traits;
[100]1270
[244]1271    ///The type of the digraph the algorithm runs on.
[100]1272    typedef typename Traits::Digraph Digraph;
1273
[244]1274    ///The visitor type used by the algorithm.
[492]1275    typedef VS Visitor;
[100]1276
[244]1277    ///The type of the map that indicates which nodes are reached.
[100]1278    typedef typename Traits::ReachedMap ReachedMap;
1279
1280  private:
1281
1282    typedef typename Digraph::Node Node;
1283    typedef typename Digraph::NodeIt NodeIt;
1284    typedef typename Digraph::Arc Arc;
1285    typedef typename Digraph::OutArcIt OutArcIt;
1286
[244]1287    //Pointer to the underlying digraph.
[100]1288    const Digraph *_digraph;
[244]1289    //Pointer to the visitor object.
[100]1290    Visitor *_visitor;
[244]1291    //Pointer to the map of reached status of the nodes.
[100]1292    ReachedMap *_reached;
[244]1293    //Indicates if _reached is locally allocated (true) or not.
[100]1294    bool local_reached;
1295
1296    std::vector<typename Digraph::Arc> _stack;
1297    int _stack_head;
1298
[280]1299    //Creates the maps if necessary.
[100]1300    void create_maps() {
1301      if(!_reached) {
[209]1302        local_reached = true;
1303        _reached = Traits::createReachedMap(*_digraph);
[100]1304      }
1305    }
1306
1307  protected:
1308
1309    DfsVisit() {}
[209]1310
[100]1311  public:
1312
1313    typedef DfsVisit Create;
1314
[405]1315    /// \name Named Template Parameters
[100]1316
1317    ///@{
1318    template <class T>
[257]1319    struct SetReachedMapTraits : public Traits {
[100]1320      typedef T ReachedMap;
1321      static ReachedMap *createReachedMap(const Digraph &digraph) {
[290]1322        LEMON_ASSERT(false, "ReachedMap is not initialized");
1323        return 0; // ignore warnings
[100]1324      }
1325    };
[209]1326    /// \brief \ref named-templ-param "Named parameter" for setting
[244]1327    /// ReachedMap type.
[100]1328    ///
[244]1329    /// \ref named-templ-param "Named parameter" for setting ReachedMap type.
[100]1330    template <class T>
[257]1331    struct SetReachedMap : public DfsVisit< Digraph, Visitor,
1332                                            SetReachedMapTraits<T> > {
1333      typedef DfsVisit< Digraph, Visitor, SetReachedMapTraits<T> > Create;
[100]1334    };
1335    ///@}
1336
[209]1337  public:
1338
[100]1339    /// \brief Constructor.
1340    ///
1341    /// Constructor.
1342    ///
[244]1343    /// \param digraph The digraph the algorithm runs on.
1344    /// \param visitor The visitor object of the algorithm.
[209]1345    DfsVisit(const Digraph& digraph, Visitor& visitor)
[100]1346      : _digraph(&digraph), _visitor(&visitor),
[209]1347        _reached(0), local_reached(false) {}
1348
[100]1349    /// \brief Destructor.
1350    ~DfsVisit() {
1351      if(local_reached) delete _reached;
1352    }
1353
[244]1354    /// \brief Sets the map that indicates which nodes are reached.
[100]1355    ///
[244]1356    /// Sets the map that indicates which nodes are reached.
[405]1357    /// If you don't use this function before calling \ref run(Node) "run()"
1358    /// or \ref init(), an instance will be allocated automatically.
1359    /// The destructor deallocates this automatically allocated map,
1360    /// of course.
[100]1361    /// \return <tt> (*this) </tt>
1362    DfsVisit &reachedMap(ReachedMap &m) {
1363      if(local_reached) {
[209]1364        delete _reached;
1365        local_reached=false;
[100]1366      }
1367      _reached = &m;
1368      return *this;
1369    }
1370
1371  public:
[244]1372
[405]1373    /// \name Execution Control
1374    /// The simplest way to execute the DFS algorithm is to use one of the
1375    /// member functions called \ref run(Node) "run()".\n
[713]1376    /// If you need better control on the execution, you have to call
1377    /// \ref init() first, then you can add a source node with \ref addSource()
[405]1378    /// and perform the actual computation with \ref start().
1379    /// This procedure can be repeated if there are nodes that have not
1380    /// been reached.
[100]1381
1382    /// @{
[244]1383
[100]1384    /// \brief Initializes the internal data structures.
1385    ///
1386    /// Initializes the internal data structures.
1387    void init() {
1388      create_maps();
1389      _stack.resize(countNodes(*_digraph));
1390      _stack_head = -1;
1391      for (NodeIt u(*_digraph) ; u != INVALID ; ++u) {
[209]1392        _reached->set(u, false);
[100]1393      }
1394    }
[209]1395
[405]1396    /// \brief Adds a new source node.
[100]1397    ///
[405]1398    /// Adds a new source node to the set of nodes to be processed.
[244]1399    ///
[405]1400    /// \pre The stack must be empty. Otherwise the algorithm gives
1401    /// wrong results. (One of the outgoing arcs of all the source nodes
1402    /// except for the last one will not be visited and distances will
1403    /// also be wrong.)
[244]1404    void addSource(Node s)
1405    {
1406      LEMON_DEBUG(emptyQueue(), "The stack is not empty.");
[100]1407      if(!(*_reached)[s]) {
[209]1408          _reached->set(s,true);
1409          _visitor->start(s);
1410          _visitor->reach(s);
1411          Arc e;
1412          _digraph->firstOut(e, s);
1413          if (e != INVALID) {
1414            _stack[++_stack_head] = e;
1415          } else {
1416            _visitor->leave(s);
[419]1417            _visitor->stop(s);
[209]1418          }
1419        }
[100]1420    }
[209]1421
[100]1422    /// \brief Processes the next arc.
1423    ///
1424    /// Processes the next arc.
1425    ///
1426    /// \return The processed arc.
1427    ///
[244]1428    /// \pre The stack must not be empty.
[209]1429    Arc processNextArc() {
[100]1430      Arc e = _stack[_stack_head];
1431      Node m = _digraph->target(e);
1432      if(!(*_reached)[m]) {
[209]1433        _visitor->discover(e);
1434        _visitor->reach(m);
1435        _reached->set(m, true);
1436        _digraph->firstOut(_stack[++_stack_head], m);
[100]1437      } else {
[209]1438        _visitor->examine(e);
1439        m = _digraph->source(e);
1440        _digraph->nextOut(_stack[_stack_head]);
[100]1441      }
1442      while (_stack_head>=0 && _stack[_stack_head] == INVALID) {
[209]1443        _visitor->leave(m);
1444        --_stack_head;
1445        if (_stack_head >= 0) {
1446          _visitor->backtrack(_stack[_stack_head]);
1447          m = _digraph->source(_stack[_stack_head]);
1448          _digraph->nextOut(_stack[_stack_head]);
1449        } else {
1450          _visitor->stop(m);
1451        }
[100]1452      }
1453      return e;
1454    }
1455
1456    /// \brief Next arc to be processed.
1457    ///
1458    /// Next arc to be processed.
1459    ///
1460    /// \return The next arc to be processed or INVALID if the stack is
1461    /// empty.
[244]1462    Arc nextArc() const {
[100]1463      return _stack_head >= 0 ? _stack[_stack_head] : INVALID;
1464    }
1465
1466    /// \brief Returns \c false if there are nodes
[244]1467    /// to be processed.
[100]1468    ///
1469    /// Returns \c false if there are nodes
[244]1470    /// to be processed in the queue (stack).
1471    bool emptyQueue() const { return _stack_head < 0; }
[100]1472
1473    /// \brief Returns the number of the nodes to be processed.
1474    ///
[244]1475    /// Returns the number of the nodes to be processed in the queue (stack).
1476    int queueSize() const { return _stack_head + 1; }
[209]1477
[100]1478    /// \brief Executes the algorithm.
1479    ///
1480    /// Executes the algorithm.
1481    ///
[244]1482    /// This method runs the %DFS algorithm from the root node
1483    /// in order to compute the %DFS path to each node.
1484    ///
1485    /// The algorithm computes
1486    /// - the %DFS tree,
1487    /// - the distance of each node from the root in the %DFS tree.
1488    ///
1489    /// \pre init() must be called and a root node should be
1490    /// added with addSource() before using this function.
1491    ///
1492    /// \note <tt>d.start()</tt> is just a shortcut of the following code.
1493    /// \code
1494    ///   while ( !d.emptyQueue() ) {
1495    ///     d.processNextArc();
1496    ///   }
1497    /// \endcode
[100]1498    void start() {
1499      while ( !emptyQueue() ) processNextArc();
1500    }
[209]1501
[244]1502    /// \brief Executes the algorithm until the given target node is reached.
[100]1503    ///
[244]1504    /// Executes the algorithm until the given target node is reached.
[100]1505    ///
[244]1506    /// This method runs the %DFS algorithm from the root node
[286]1507    /// in order to compute the DFS path to \c t.
[244]1508    ///
1509    /// The algorithm computes
[286]1510    /// - the %DFS path to \c t,
1511    /// - the distance of \c t from the root in the %DFS tree.
[244]1512    ///
1513    /// \pre init() must be called and a root node should be added
[100]1514    /// with addSource() before using this function.
[286]1515    void start(Node t) {
[899]1516      while ( !emptyQueue() && !(*_reached)[t] )
[209]1517        processNextArc();
[100]1518    }
[209]1519
[100]1520    /// \brief Executes the algorithm until a condition is met.
1521    ///
1522    /// Executes the algorithm until a condition is met.
1523    ///
[244]1524    /// This method runs the %DFS algorithm from the root node
1525    /// until an arc \c a with <tt>am[a]</tt> true is found.
1526    ///
1527    /// \param am A \c bool (or convertible) arc map. The algorithm
1528    /// will stop when it reaches an arc \c a with <tt>am[a]</tt> true.
1529    ///
1530    /// \return The reached arc \c a with <tt>am[a]</tt> true or
1531    /// \c INVALID if no such arc was found.
1532    ///
1533    /// \pre init() must be called and a root node should be added
[100]1534    /// with addSource() before using this function.
1535    ///
[244]1536    /// \warning Contrary to \ref Bfs and \ref Dijkstra, \c am is an arc map,
[100]1537    /// not a node map.
[244]1538    template <typename AM>
1539    Arc start(const AM &am) {
1540      while ( !emptyQueue() && !am[_stack[_stack_head]] )
[100]1541        processNextArc();
1542      return emptyQueue() ? INVALID : _stack[_stack_head];
1543    }
1544
[286]1545    /// \brief Runs the algorithm from the given source node.
[100]1546    ///
[244]1547    /// This method runs the %DFS algorithm from node \c s.
1548    /// in order to compute the DFS path to each node.
1549    ///
1550    /// The algorithm computes
1551    /// - the %DFS tree,
1552    /// - the distance of each node from the root in the %DFS tree.
1553    ///
1554    /// \note <tt>d.run(s)</tt> is just a shortcut of the following code.
[100]1555    ///\code
1556    ///   d.init();
1557    ///   d.addSource(s);
1558    ///   d.start();
1559    ///\endcode
1560    void run(Node s) {
1561      init();
1562      addSource(s);
1563      start();
1564    }
1565
[244]1566    /// \brief Finds the %DFS path between \c s and \c t.
1567
1568    /// This method runs the %DFS algorithm from node \c s
[286]1569    /// in order to compute the DFS path to node \c t
1570    /// (it stops searching when \c t is processed).
[244]1571    ///
[286]1572    /// \return \c true if \c t is reachable form \c s.
[244]1573    ///
1574    /// \note Apart from the return value, <tt>d.run(s,t)</tt> is
1575    /// just a shortcut of the following code.
1576    ///\code
1577    ///   d.init();
1578    ///   d.addSource(s);
1579    ///   d.start(t);
1580    ///\endcode
[286]1581    bool run(Node s,Node t) {
[244]1582      init();
1583      addSource(s);
1584      start(t);
[286]1585      return reached(t);
[244]1586    }
1587
1588    /// \brief Runs the algorithm to visit all nodes in the digraph.
[209]1589
[787]1590    /// This method runs the %DFS algorithm in order to visit all nodes
1591    /// in the digraph.
[244]1592    ///
1593    /// \note <tt>d.run()</tt> is just a shortcut of the following code.
[100]1594    ///\code
[244]1595    ///   d.init();
1596    ///   for (NodeIt n(digraph); n != INVALID; ++n) {
1597    ///     if (!d.reached(n)) {
1598    ///       d.addSource(n);
1599    ///       d.start();
1600    ///     }
1601    ///   }
[100]1602    ///\endcode
1603    void run() {
1604      init();
1605      for (NodeIt it(*_digraph); it != INVALID; ++it) {
1606        if (!reached(it)) {
1607          addSource(it);
1608          start();
1609        }
1610      }
1611    }
[244]1612
[100]1613    ///@}
1614
1615    /// \name Query Functions
[405]1616    /// The results of the DFS algorithm can be obtained using these
[100]1617    /// functions.\n
[405]1618    /// Either \ref run(Node) "run()" or \ref start() should be called
1619    /// before using them.
1620
[100]1621    ///@{
[244]1622
[716]1623    /// \brief Checks if the given node is reached from the root(s).
[100]1624    ///
[405]1625    /// Returns \c true if \c v is reached from the root(s).
1626    ///
1627    /// \pre Either \ref run(Node) "run()" or \ref init()
[100]1628    /// must be called before using this function.
[420]1629    bool reached(Node v) const { return (*_reached)[v]; }
[244]1630
[100]1631    ///@}
[244]1632
[100]1633  };
1634
1635} //END OF NAMESPACE LEMON
1636
1637#endif
Note: See TracBrowser for help on using the repository browser.