COIN-OR::LEMON - Graph Library

source: lemon-1.0/lemon/dfs.h @ 142:8b703d177341

Last change on this file since 142:8b703d177341 was 100:4f754b4cf82b, checked in by Alpar Juttner <alpar@…>, 16 years ago

Bfs/Dfs/Dijkstra? and their deps ported from svn trung -r 3441.

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