COIN-OR::LEMON - Graph Library

source: lemon/lemon/dfs.h @ 240:bea328c5a8d3

Last change on this file since 240:bea328c5a8d3 was 220:a5d8c039f218, checked in by Balazs Dezso <deba@…>, 16 years ago

Reorganize header files (Ticket #97)

In addition on some places the DefaultMap?<G, K, V> is replaced with
ItemSetTraits?<G, K>::template Map<V>::Type, to decrease the dependencies
of different tools. It is obviously better solution.

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