COIN-OR::LEMON - Graph Library

source: lemon-0.x/lemon/dfs.h @ 1993:2115143eceea

Last change on this file since 1993:2115143eceea was 1993:2115143eceea, checked in by Balazs Dezso, 18 years ago

utility, invalid and traits moved to bits

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