COIN-OR::LEMON - Graph Library

source: lemon/lemon/dfs.h @ 954:07ec2b52e53d

Last change on this file since 954:07ec2b52e53d was 891:75e6020b19b1, checked in by Peter Kovacs <kpeter@…>, 14 years ago

Add doc for the traits class parameters (#315)

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