COIN-OR::LEMON - Graph Library

source: lemon-1.2/lemon/dfs.h @ 708:5d313b76f323

Last change on this file since 708:5d313b76f323 was 584:33c6b6e755cd, checked in by Peter Kovacs <kpeter@…>, 11 years ago

Small doc improvements (#263)

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