COIN-OR::LEMON - Graph Library

source: lemon-0.x/lemon/dfs.h @ 1824:3a15b39a7c78

Last change on this file since 1824:3a15b39a7c78 was 1799:990ef198f64d, checked in by Balazs Dezso, 18 years ago

Warning because unused parameters

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