COIN-OR::LEMON - Graph Library

source: lemon-0.x/lemon/dfs.h @ 2456:717a5134ddeb

Last change on this file since 2456:717a5134ddeb was 2443:14abfa02bf42, checked in by Balazs Dezso, 17 years ago

Patch for retrieving reached/processed node in dijkstra, bfs and dfs

Patch from Peter Kovacs

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