COIN-OR::LEMON - Graph Library

source: lemon-1.2/lemon/dfs.h @ 278:931190050520

Last change on this file since 278:931190050520 was 278:931190050520, checked in by Peter Kovacs <kpeter@…>, 11 years ago

Improve the function-type interface of bfs, dfs, and dijkstra (ticket #96)

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