COIN-OR::LEMON - Graph Library

source: lemon/lemon/dfs.h @ 210:81cfc04531e8

Last change on this file since 210:81cfc04531e8 was 210:81cfc04531e8, checked in by Alpar Juttner <alpar@…>, 11 years ago

Remove long lines (from all but one file)

File size: 46.2 KB
Line 
1/* -*- mode: C++; indent-tabs-mode: nil; -*-
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  ///\tparam 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
109    ///the \ref DistMap
110    static DistMap *createDistMap(const GR &G)
111    {
112      return new DistMap(G);
113    }
114  };
115
116  ///%DFS algorithm class.
117
118  ///\ingroup search
119  ///This class provides an efficient implementation of the %DFS algorithm.
120  ///
121  ///\tparam GR The digraph type the algorithm runs on. The default value is
122  ///\ref ListDigraph. The value of GR is not used directly by Dfs, it
123  ///is only passed to \ref DfsDefaultTraits.
124  ///\tparam TR Traits class to set various data types used by the algorithm.
125  ///The default traits class is
126  ///\ref DfsDefaultTraits "DfsDefaultTraits<GR>".
127  ///See \ref DfsDefaultTraits for the documentation of
128  ///a Dfs traits class.
129#ifdef DOXYGEN
130  template <typename GR,
131            typename TR>
132#else
133  template <typename GR=ListDigraph,
134            typename TR=DfsDefaultTraits<GR> >
135#endif
136  class Dfs {
137  public:
138    /**
139     * \brief \ref Exception for uninitialized parameters.
140     *
141     * This error represents problems in the initialization
142     * of the parameters of the algorithms.
143     */
144    class UninitializedParameter : public lemon::UninitializedParameter {
145    public:
146      virtual const char* what() const throw() {
147        return "lemon::Dfs::UninitializedParameter";
148      }
149    };
150
151    typedef TR Traits;
152    ///The type of the underlying digraph.
153    typedef typename TR::Digraph Digraph;
154    ///\e
155    typedef typename Digraph::Node Node;
156    ///\e
157    typedef typename Digraph::NodeIt NodeIt;
158    ///\e
159    typedef typename Digraph::Arc Arc;
160    ///\e
161    typedef typename Digraph::OutArcIt OutArcIt;
162
163    ///\brief The type of the map that stores the last
164    ///arcs of the %DFS paths.
165    typedef typename TR::PredMap PredMap;
166    ///The type of the map indicating which nodes are reached.
167    typedef typename TR::ReachedMap ReachedMap;
168    ///The type of the map indicating which nodes are processed.
169    typedef typename TR::ProcessedMap ProcessedMap;
170    ///The type of the map that stores the dists of the nodes.
171    typedef typename TR::DistMap DistMap;
172  private:
173    /// Pointer to the underlying digraph.
174    const Digraph *G;
175    ///Pointer to the map of predecessors arcs.
176    PredMap *_pred;
177    ///Indicates if \ref _pred is locally allocated (\c true) or not.
178    bool local_pred;
179    ///Pointer to the map of distances.
180    DistMap *_dist;
181    ///Indicates if \ref _dist is locally allocated (\c true) or not.
182    bool local_dist;
183    ///Pointer to the map of reached status of the nodes.
184    ReachedMap *_reached;
185    ///Indicates if \ref _reached is locally allocated (\c true) or not.
186    bool local_reached;
187    ///Pointer to the map of processed status of the nodes.
188    ProcessedMap *_processed;
189    ///Indicates if \ref _processed is locally allocated (\c true) or not.
190    bool local_processed;
191
192    std::vector<typename Digraph::OutArcIt> _stack;
193    int _stack_head;
194
195    ///Creates the maps if necessary.
196
197    ///\todo Better memory allocation (instead of new).
198    void create_maps()
199    {
200      if(!_pred) {
201        local_pred = true;
202        _pred = Traits::createPredMap(*G);
203      }
204      if(!_dist) {
205        local_dist = true;
206        _dist = Traits::createDistMap(*G);
207      }
208      if(!_reached) {
209        local_reached = true;
210        _reached = Traits::createReachedMap(*G);
211      }
212      if(!_processed) {
213        local_processed = true;
214        _processed = Traits::createProcessedMap(*G);
215      }
216    }
217
218  protected:
219
220    Dfs() {}
221
222  public:
223
224    typedef Dfs Create;
225
226    ///\name Named template parameters
227
228    ///@{
229
230    template <class T>
231    struct DefPredMapTraits : public Traits {
232      typedef T PredMap;
233      static PredMap *createPredMap(const Digraph &G)
234      {
235        throw UninitializedParameter();
236      }
237    };
238    ///\brief \ref named-templ-param "Named parameter" for setting
239    ///PredMap type
240    ///
241    ///\ref named-templ-param "Named parameter" for setting PredMap type
242    ///
243    template <class T>
244    struct DefPredMap : public Dfs<Digraph, DefPredMapTraits<T> > {
245      typedef Dfs<Digraph, DefPredMapTraits<T> > Create;
246    };
247
248
249    template <class T>
250    struct DefDistMapTraits : public Traits {
251      typedef T DistMap;
252      static DistMap *createDistMap(const Digraph &)
253      {
254        throw UninitializedParameter();
255      }
256    };
257    ///\brief \ref named-templ-param "Named parameter" for setting
258    ///DistMap type
259    ///
260    ///\ref named-templ-param "Named parameter" for setting DistMap
261    ///type
262    template <class T>
263    struct DefDistMap {
264      typedef Dfs<Digraph, DefDistMapTraits<T> > Create;
265    };
266
267    template <class T>
268    struct DefReachedMapTraits : public Traits {
269      typedef T ReachedMap;
270      static ReachedMap *createReachedMap(const Digraph &)
271      {
272        throw UninitializedParameter();
273      }
274    };
275    ///\brief \ref named-templ-param "Named parameter" for setting
276    ///ReachedMap type
277    ///
278    ///\ref named-templ-param "Named parameter" for setting ReachedMap type
279    ///
280    template <class T>
281    struct DefReachedMap : public Dfs< Digraph, DefReachedMapTraits<T> > {
282      typedef Dfs< Digraph, DefReachedMapTraits<T> > Create;
283    };
284
285    template <class T>
286    struct DefProcessedMapTraits : public Traits {
287      typedef T ProcessedMap;
288      static ProcessedMap *createProcessedMap(const Digraph &)
289      {
290        throw UninitializedParameter();
291      }
292    };
293    ///\brief \ref named-templ-param "Named parameter" for setting
294    ///ProcessedMap type
295    ///
296    ///\ref named-templ-param "Named parameter" for setting ProcessedMap type
297    ///
298    template <class T>
299    struct DefProcessedMap : public Dfs< Digraph, DefProcessedMapTraits<T> > {
300      typedef Dfs< Digraph, DefProcessedMapTraits<T> > Create;
301    };
302
303    struct DefDigraphProcessedMapTraits : public Traits {
304      typedef typename Digraph::template NodeMap<bool> ProcessedMap;
305      static ProcessedMap *createProcessedMap(const Digraph &G)
306      {
307        return new ProcessedMap(G);
308      }
309    };
310    ///\brief \ref named-templ-param "Named parameter"
311    ///for setting the ProcessedMap type to be Digraph::NodeMap<bool>.
312    ///
313    ///\ref named-templ-param "Named parameter"
314    ///for setting the ProcessedMap type to be Digraph::NodeMap<bool>.
315    ///If you don't set it explicitely, it will be automatically allocated.
316    template <class T>
317    class DefProcessedMapToBeDefaultMap :
318      public Dfs< Digraph, DefDigraphProcessedMapTraits> {
319      typedef Dfs< Digraph, DefDigraphProcessedMapTraits> Create;
320    };
321
322    ///@}
323
324  public:
325
326    ///Constructor.
327
328    ///\param _G the digraph the algorithm will run on.
329    ///
330    Dfs(const Digraph& _G) :
331      G(&_G),
332      _pred(NULL), local_pred(false),
333      _dist(NULL), local_dist(false),
334      _reached(NULL), local_reached(false),
335      _processed(NULL), local_processed(false)
336    { }
337
338    ///Destructor.
339    ~Dfs()
340    {
341      if(local_pred) delete _pred;
342      if(local_dist) delete _dist;
343      if(local_reached) delete _reached;
344      if(local_processed) delete _processed;
345    }
346
347    ///Sets the map storing the predecessor arcs.
348
349    ///Sets the map storing the predecessor arcs.
350    ///If you don't use this function before calling \ref run(),
351    ///it will allocate one. The destuctor deallocates this
352    ///automatically allocated map, of course.
353    ///\return <tt> (*this) </tt>
354    Dfs &predMap(PredMap &m)
355    {
356      if(local_pred) {
357        delete _pred;
358        local_pred=false;
359      }
360      _pred = &m;
361      return *this;
362    }
363
364    ///Sets the map storing the distances calculated by the algorithm.
365
366    ///Sets the map storing the distances calculated by the algorithm.
367    ///If you don't use this function before calling \ref run(),
368    ///it will allocate one. The destuctor deallocates this
369    ///automatically allocated map, of course.
370    ///\return <tt> (*this) </tt>
371    Dfs &distMap(DistMap &m)
372    {
373      if(local_dist) {
374        delete _dist;
375        local_dist=false;
376      }
377      _dist = &m;
378      return *this;
379    }
380
381    ///Sets the map indicating if a node is reached.
382
383    ///Sets the map indicating if a node is reached.
384    ///If you don't use this function before calling \ref run(),
385    ///it will allocate one. The destuctor deallocates this
386    ///automatically allocated map, of course.
387    ///\return <tt> (*this) </tt>
388    Dfs &reachedMap(ReachedMap &m)
389    {
390      if(local_reached) {
391        delete _reached;
392        local_reached=false;
393      }
394      _reached = &m;
395      return *this;
396    }
397
398    ///Sets the map indicating if a node is processed.
399
400    ///Sets the map indicating if a node is processed.
401    ///If you don't use this function before calling \ref run(),
402    ///it will allocate one. The destuctor deallocates this
403    ///automatically allocated map, of course.
404    ///\return <tt> (*this) </tt>
405    Dfs &processedMap(ProcessedMap &m)
406    {
407      if(local_processed) {
408        delete _processed;
409        local_processed=false;
410      }
411      _processed = &m;
412      return *this;
413    }
414
415  public:
416    ///\name Execution control
417    ///The simplest way to execute the algorithm is to use
418    ///one of the member functions called \c run(...).
419    ///\n
420    ///If you need more control on the execution,
421    ///first you must call \ref init(), then you can add a source node
422    ///with \ref addSource().
423    ///Finally \ref start() will perform the actual path
424    ///computation.
425
426    ///@{
427
428    ///Initializes the internal data structures.
429
430    ///Initializes the internal data structures.
431    ///
432    void init()
433    {
434      create_maps();
435      _stack.resize(countNodes(*G));
436      _stack_head=-1;
437      for ( NodeIt u(*G) ; u!=INVALID ; ++u ) {
438        _pred->set(u,INVALID);
439        // _predNode->set(u,INVALID);
440        _reached->set(u,false);
441        _processed->set(u,false);
442      }
443    }
444
445    ///Adds a new source node.
446
447    ///Adds a new source node to the set of nodes to be processed.
448    ///
449    ///\warning dists are wrong (or at least strange)
450    ///in case of multiple sources.
451    void addSource(Node s)
452    {
453      if(!(*_reached)[s])
454        {
455          _reached->set(s,true);
456          _pred->set(s,INVALID);
457          OutArcIt e(*G,s);
458          if(e!=INVALID) {
459            _stack[++_stack_head]=e;
460            _dist->set(s,_stack_head);
461          }
462          else {
463            _processed->set(s,true);
464            _dist->set(s,0);
465          }
466        }
467    }
468
469    ///Processes the next arc.
470
471    ///Processes the next arc.
472    ///
473    ///\return The processed arc.
474    ///
475    ///\pre The stack must not be empty!
476    Arc processNextArc()
477    {
478      Node m;
479      Arc e=_stack[_stack_head];
480      if(!(*_reached)[m=G->target(e)]) {
481        _pred->set(m,e);
482        _reached->set(m,true);
483        ++_stack_head;
484        _stack[_stack_head] = OutArcIt(*G, m);
485        _dist->set(m,_stack_head);
486      }
487      else {
488        m=G->source(e);
489        ++_stack[_stack_head];
490      }
491      while(_stack_head>=0 && _stack[_stack_head]==INVALID) {
492        _processed->set(m,true);
493        --_stack_head;
494        if(_stack_head>=0) {
495          m=G->source(_stack[_stack_head]);
496          ++_stack[_stack_head];
497        }
498      }
499      return e;
500    }
501    ///Next arc to be processed.
502
503    ///Next arc to be processed.
504    ///
505    ///\return The next arc to be processed or INVALID if the stack is
506    /// empty.
507    OutArcIt nextArc()
508    {
509      return _stack_head>=0?_stack[_stack_head]:INVALID;
510    }
511
512    ///\brief Returns \c false if there are nodes
513    ///to be processed in the queue
514    ///
515    ///Returns \c false if there are nodes
516    ///to be processed in the queue
517    bool emptyQueue() { return _stack_head<0; }
518    ///Returns the number of the nodes to be processed.
519
520    ///Returns the number of the nodes to be processed in the queue.
521    int queueSize() { return _stack_head+1; }
522
523    ///Executes the algorithm.
524
525    ///Executes the algorithm.
526    ///
527    ///\pre init() must be called and at least one node should be added
528    ///with addSource() before using this function.
529    ///
530    ///This method runs the %DFS algorithm from the root node(s)
531    ///in order to
532    ///compute the
533    ///%DFS path to each node. The algorithm computes
534    ///- The %DFS tree.
535    ///- The distance of each node from the root(s) in the %DFS tree.
536    ///
537    void start()
538    {
539      while ( !emptyQueue() ) processNextArc();
540    }
541
542    ///Executes the algorithm until \c dest is reached.
543
544    ///Executes the algorithm until \c dest is reached.
545    ///
546    ///\pre init() must be called and at least one node should be added
547    ///with addSource() before using this function.
548    ///
549    ///This method runs the %DFS algorithm from the root node(s)
550    ///in order to
551    ///compute the
552    ///%DFS path to \c dest. The algorithm computes
553    ///- The %DFS path to \c  dest.
554    ///- The distance of \c dest from the root(s) in the %DFS tree.
555    ///
556    void start(Node dest)
557    {
558      while ( !emptyQueue() && G->target(_stack[_stack_head])!=dest )
559        processNextArc();
560    }
561
562    ///Executes the algorithm until a condition is met.
563
564    ///Executes the algorithm until a condition is met.
565    ///
566    ///\pre init() must be called and at least one node should be added
567    ///with addSource() before using this function.
568    ///
569    ///\param em must be a bool (or convertible) arc map. The algorithm
570    ///will stop when it reaches an arc \c e with <tt>em[e]</tt> true.
571    ///
572    ///\return The reached arc \c e with <tt>em[e]</tt> true or
573    ///\c INVALID if no such arc was found.
574    ///
575    ///\warning Contrary to \ref Bfs and \ref Dijkstra, \c em is an arc map,
576    ///not a node map.
577    template<class EM>
578    Arc start(const EM &em)
579    {
580      while ( !emptyQueue() && !em[_stack[_stack_head]] )
581        processNextArc();
582      return emptyQueue() ? INVALID : _stack[_stack_head];
583    }
584
585    ///Runs %DFS algorithm to visit all nodes in the digraph.
586
587    ///This method runs the %DFS algorithm in order to
588    ///compute the
589    ///%DFS path to each node. The algorithm computes
590    ///- The %DFS tree.
591    ///- The distance of each node from the root in the %DFS tree.
592    ///
593    ///\note d.run() is just a shortcut of the following code.
594    ///\code
595    ///  d.init();
596    ///  for (NodeIt it(digraph); it != INVALID; ++it) {
597    ///    if (!d.reached(it)) {
598    ///      d.addSource(it);
599    ///      d.start();
600    ///    }
601    ///  }
602    ///\endcode
603    void run() {
604      init();
605      for (NodeIt it(*G); it != INVALID; ++it) {
606        if (!reached(it)) {
607          addSource(it);
608          start();
609        }
610      }
611    }
612
613    ///Runs %DFS algorithm from node \c s.
614
615    ///This method runs the %DFS algorithm from a root node \c s
616    ///in order to
617    ///compute the
618    ///%DFS path to each node. The algorithm computes
619    ///- The %DFS tree.
620    ///- The distance of each node from the root in the %DFS tree.
621    ///
622    ///\note d.run(s) is just a shortcut of the following code.
623    ///\code
624    ///  d.init();
625    ///  d.addSource(s);
626    ///  d.start();
627    ///\endcode
628    void run(Node s) {
629      init();
630      addSource(s);
631      start();
632    }
633
634    ///Finds the %DFS path between \c s and \c t.
635
636    ///Finds the %DFS path between \c s and \c t.
637    ///
638    ///\return The length of the %DFS s---t path if there exists one,
639    ///0 otherwise.
640    ///\note Apart from the return value, d.run(s,t) is
641    ///just a shortcut of the following code.
642    ///\code
643    ///  d.init();
644    ///  d.addSource(s);
645    ///  d.start(t);
646    ///\endcode
647    int run(Node s,Node t) {
648      init();
649      addSource(s);
650      start(t);
651      return reached(t)?_stack_head+1:0;
652    }
653
654    ///@}
655
656    ///\name Query Functions
657    ///The result of the %DFS algorithm can be obtained using these
658    ///functions.\n
659    ///Before the use of these functions,
660    ///either run() or start() must be called.
661
662    ///@{
663
664    typedef PredMapPath<Digraph, PredMap> Path;
665
666    ///Gives back the shortest path.
667
668    ///Gives back the shortest path.
669    ///\pre The \c t should be reachable from the source.
670    Path path(Node t)
671    {
672      return Path(*G, *_pred, t);
673    }
674
675    ///The distance of a node from the root(s).
676
677    ///Returns the distance of a node from the root(s).
678    ///\pre \ref run() must be called before using this function.
679    ///\warning If node \c v is unreachable from the root(s) then the return
680    ///value of this funcion is undefined.
681    int dist(Node v) const { return (*_dist)[v]; }
682
683    ///Returns the 'previous arc' of the %DFS tree.
684
685    ///For a node \c v it returns the 'previous arc'
686    ///of the %DFS path,
687    ///i.e. it returns the last arc of a %DFS path from the root(s) to \c
688    ///v. It is \ref INVALID
689    ///if \c v is unreachable from the root(s) or \c v is a root. The
690    ///%DFS tree used here is equal to the %DFS tree used in
691    ///\ref predNode().
692    ///\pre Either \ref run() or \ref start() must be called before using
693    ///this function.
694    Arc predArc(Node v) const { return (*_pred)[v];}
695
696    ///Returns the 'previous node' of the %DFS tree.
697
698    ///For a node \c v it returns the 'previous node'
699    ///of the %DFS tree,
700    ///i.e. it returns the last but one node from a %DFS path from the
701    ///root(s) to \c v.
702    ///It is INVALID if \c v is unreachable from the root(s) or
703    ///if \c v itself a root.
704    ///The %DFS tree used here is equal to the %DFS
705    ///tree used in \ref predArc().
706    ///\pre Either \ref run() or \ref start() must be called before
707    ///using this function.
708    Node predNode(Node v) const { return (*_pred)[v]==INVALID ? INVALID:
709                                  G->source((*_pred)[v]); }
710
711    ///Returns a reference to the NodeMap of distances.
712
713    ///Returns a reference to the NodeMap of distances.
714    ///\pre Either \ref run() or \ref init() must
715    ///be called before using this function.
716    const DistMap &distMap() const { return *_dist;}
717
718    ///Returns a reference to the %DFS arc-tree map.
719
720    ///Returns a reference to the NodeMap of the arcs of the
721    ///%DFS tree.
722    ///\pre Either \ref run() or \ref init()
723    ///must be called before using this function.
724    const PredMap &predMap() const { return *_pred;}
725
726    ///Checks if a node is reachable from the root.
727
728    ///Returns \c true if \c v is reachable from the root(s).
729    ///\warning The source nodes are inditated as unreachable.
730    ///\pre Either \ref run() or \ref start()
731    ///must be called before using this function.
732    ///
733    bool reached(Node v) { return (*_reached)[v]; }
734
735    ///@}
736  };
737
738  ///Default traits class of Dfs function.
739
740  ///Default traits class of Dfs function.
741  ///\tparam GR Digraph type.
742  template<class GR>
743  struct DfsWizardDefaultTraits
744  {
745    ///The digraph type the algorithm runs on.
746    typedef GR Digraph;
747    ///\brief The type of the map that stores the last
748    ///arcs of the %DFS paths.
749    ///
750    ///The type of the map that stores the last
751    ///arcs of the %DFS paths.
752    ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
753    ///
754    typedef NullMap<typename Digraph::Node,typename GR::Arc> PredMap;
755    ///Instantiates a PredMap.
756
757    ///This function instantiates a \ref PredMap.
758    ///\param g is the digraph, to which we would like to define the PredMap.
759    ///\todo The digraph alone may be insufficient to initialize
760#ifdef DOXYGEN
761    static PredMap *createPredMap(const GR &g)
762#else
763    static PredMap *createPredMap(const GR &)
764#endif
765    {
766      return new PredMap();
767    }
768
769    ///The type of the map that indicates which nodes are processed.
770
771    ///The type of the map that indicates which nodes are processed.
772    ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
773    ///\todo named parameter to set this type, function to read and write.
774    typedef NullMap<typename Digraph::Node,bool> ProcessedMap;
775    ///Instantiates a ProcessedMap.
776
777    ///This function instantiates a \ref ProcessedMap.
778    ///\param g is the digraph, to which
779    ///we would like to define the \ref ProcessedMap
780#ifdef DOXYGEN
781    static ProcessedMap *createProcessedMap(const GR &g)
782#else
783    static ProcessedMap *createProcessedMap(const GR &)
784#endif
785    {
786      return new ProcessedMap();
787    }
788    ///The type of the map that indicates which nodes are reached.
789
790    ///The type of the map that indicates which nodes are reached.
791    ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
792    ///\todo named parameter to set this type, function to read and write.
793    typedef typename Digraph::template NodeMap<bool> ReachedMap;
794    ///Instantiates a ReachedMap.
795
796    ///This function instantiates a \ref ReachedMap.
797    ///\param G is the digraph, to which
798    ///we would like to define the \ref ReachedMap.
799    static ReachedMap *createReachedMap(const GR &G)
800    {
801      return new ReachedMap(G);
802    }
803    ///The type of the map that stores the dists of the nodes.
804
805    ///The type of the map that stores the dists of the nodes.
806    ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
807    ///
808    typedef NullMap<typename Digraph::Node,int> DistMap;
809    ///Instantiates a DistMap.
810
811    ///This function instantiates a \ref DistMap.
812    ///\param g is the digraph, to which we would like to define
813    ///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::_reached=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::_processed=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  /// \tparam _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  /// \tparam _Digraph The digraph type the algorithm runs on.
1199  /// The default value is
1200  /// \ref ListDigraph. The value of _Digraph is not used directly by Dfs, it
1201  /// is only passed to \ref DfsDefaultTraits.
1202  /// \tparam _Visitor The Visitor object for the algorithm. The
1203  /// \ref DfsVisitor "DfsVisitor<_Digraph>" is an empty Visitor which
1204  /// does not observe the Dfs events. If you want to observe the dfs
1205  /// events you should implement your own Visitor class.
1206  /// \tparam _Traits Traits class to set various data types used by the
1207  /// algorithm. The default traits class is
1208  /// \ref DfsVisitDefaultTraits "DfsVisitDefaultTraits<_Digraph>".
1209  /// See \ref DfsVisitDefaultTraits for the documentation of
1210  /// a Dfs visit traits class.
1211  ///
1212  /// \author Jacint Szabo, Alpar Juttner and Balazs Dezso
1213#ifdef DOXYGEN
1214  template <typename _Digraph, typename _Visitor, typename _Traits>
1215#else
1216  template <typename _Digraph = ListDigraph,
1217            typename _Visitor = DfsVisitor<_Digraph>,
1218            typename _Traits = DfsDefaultTraits<_Digraph> >
1219#endif
1220  class DfsVisit {
1221  public:
1222
1223    /// \brief \ref Exception for uninitialized parameters.
1224    ///
1225    /// This error represents problems in the initialization
1226    /// of the parameters of the algorithms.
1227    class UninitializedParameter : public lemon::UninitializedParameter {
1228    public:
1229      virtual const char* what() const throw()
1230      {
1231        return "lemon::DfsVisit::UninitializedParameter";
1232      }
1233    };
1234
1235    typedef _Traits Traits;
1236
1237    typedef typename Traits::Digraph Digraph;
1238
1239    typedef _Visitor Visitor;
1240
1241    ///The type of the map indicating which nodes are reached.
1242    typedef typename Traits::ReachedMap ReachedMap;
1243
1244  private:
1245
1246    typedef typename Digraph::Node Node;
1247    typedef typename Digraph::NodeIt NodeIt;
1248    typedef typename Digraph::Arc Arc;
1249    typedef typename Digraph::OutArcIt OutArcIt;
1250
1251    /// Pointer to the underlying digraph.
1252    const Digraph *_digraph;
1253    /// Pointer to the visitor object.
1254    Visitor *_visitor;
1255    ///Pointer to the map of reached status of the nodes.
1256    ReachedMap *_reached;
1257    ///Indicates if \ref _reached is locally allocated (\c true) or not.
1258    bool local_reached;
1259
1260    std::vector<typename Digraph::Arc> _stack;
1261    int _stack_head;
1262
1263    /// \brief Creates the maps if necessary.
1264    ///
1265    /// Creates the maps if necessary.
1266    void create_maps() {
1267      if(!_reached) {
1268        local_reached = true;
1269        _reached = Traits::createReachedMap(*_digraph);
1270      }
1271    }
1272
1273  protected:
1274
1275    DfsVisit() {}
1276
1277  public:
1278
1279    typedef DfsVisit Create;
1280
1281    /// \name Named template parameters
1282
1283    ///@{
1284    template <class T>
1285    struct DefReachedMapTraits : public Traits {
1286      typedef T ReachedMap;
1287      static ReachedMap *createReachedMap(const Digraph &digraph) {
1288        throw UninitializedParameter();
1289      }
1290    };
1291    /// \brief \ref named-templ-param "Named parameter" for setting
1292    /// ReachedMap type
1293    ///
1294    /// \ref named-templ-param "Named parameter" for setting ReachedMap type
1295    template <class T>
1296    struct DefReachedMap : public DfsVisit< Digraph, Visitor,
1297                                            DefReachedMapTraits<T> > {
1298      typedef DfsVisit< Digraph, Visitor, DefReachedMapTraits<T> > Create;
1299    };
1300    ///@}
1301
1302  public:
1303
1304    /// \brief Constructor.
1305    ///
1306    /// Constructor.
1307    ///
1308    /// \param digraph the digraph the algorithm will run on.
1309    /// \param visitor The visitor of the algorithm.
1310    ///
1311    DfsVisit(const Digraph& digraph, Visitor& visitor)
1312      : _digraph(&digraph), _visitor(&visitor),
1313        _reached(0), local_reached(false) {}
1314
1315    /// \brief Destructor.
1316    ///
1317    /// Destructor.
1318    ~DfsVisit() {
1319      if(local_reached) delete _reached;
1320    }
1321
1322    /// \brief Sets the map indicating if a node is reached.
1323    ///
1324    /// Sets the map indicating if a node is reached.
1325    /// If you don't use this function before calling \ref run(),
1326    /// it will allocate one. The destuctor deallocates this
1327    /// automatically allocated map, of course.
1328    /// \return <tt> (*this) </tt>
1329    DfsVisit &reachedMap(ReachedMap &m) {
1330      if(local_reached) {
1331        delete _reached;
1332        local_reached=false;
1333      }
1334      _reached = &m;
1335      return *this;
1336    }
1337
1338  public:
1339    /// \name Execution control
1340    /// The simplest way to execute the algorithm is to use
1341    /// one of the member functions called \c run(...).
1342    /// \n
1343    /// If you need more control on the execution,
1344    /// first you must call \ref init(), then you can adda source node
1345    /// with \ref addSource().
1346    /// Finally \ref start() will perform the actual path
1347    /// computation.
1348
1349    /// @{
1350    /// \brief Initializes the internal data structures.
1351    ///
1352    /// Initializes the internal data structures.
1353    ///
1354    void init() {
1355      create_maps();
1356      _stack.resize(countNodes(*_digraph));
1357      _stack_head = -1;
1358      for (NodeIt u(*_digraph) ; u != INVALID ; ++u) {
1359        _reached->set(u, false);
1360      }
1361    }
1362
1363    /// \brief Adds a new source node.
1364    ///
1365    /// Adds a new source node to the set of nodes to be processed.
1366    void addSource(Node s) {
1367      if(!(*_reached)[s]) {
1368          _reached->set(s,true);
1369          _visitor->start(s);
1370          _visitor->reach(s);
1371          Arc e;
1372          _digraph->firstOut(e, s);
1373          if (e != INVALID) {
1374            _stack[++_stack_head] = e;
1375          } else {
1376            _visitor->leave(s);
1377          }
1378        }
1379    }
1380
1381    /// \brief Processes the next arc.
1382    ///
1383    /// Processes the next arc.
1384    ///
1385    /// \return The processed arc.
1386    ///
1387    /// \pre The stack must not be empty!
1388    Arc processNextArc() {
1389      Arc e = _stack[_stack_head];
1390      Node m = _digraph->target(e);
1391      if(!(*_reached)[m]) {
1392        _visitor->discover(e);
1393        _visitor->reach(m);
1394        _reached->set(m, true);
1395        _digraph->firstOut(_stack[++_stack_head], m);
1396      } else {
1397        _visitor->examine(e);
1398        m = _digraph->source(e);
1399        _digraph->nextOut(_stack[_stack_head]);
1400      }
1401      while (_stack_head>=0 && _stack[_stack_head] == INVALID) {
1402        _visitor->leave(m);
1403        --_stack_head;
1404        if (_stack_head >= 0) {
1405          _visitor->backtrack(_stack[_stack_head]);
1406          m = _digraph->source(_stack[_stack_head]);
1407          _digraph->nextOut(_stack[_stack_head]);
1408        } else {
1409          _visitor->stop(m);
1410        }
1411      }
1412      return e;
1413    }
1414
1415    /// \brief Next arc to be processed.
1416    ///
1417    /// Next arc to be processed.
1418    ///
1419    /// \return The next arc to be processed or INVALID if the stack is
1420    /// empty.
1421    Arc nextArc() {
1422      return _stack_head >= 0 ? _stack[_stack_head] : INVALID;
1423    }
1424
1425    /// \brief Returns \c false if there are nodes
1426    /// to be processed in the queue
1427    ///
1428    /// Returns \c false if there are nodes
1429    /// to be processed in the queue
1430    bool emptyQueue() { return _stack_head < 0; }
1431
1432    /// \brief Returns the number of the nodes to be processed.
1433    ///
1434    /// Returns the number of the nodes to be processed in the queue.
1435    int queueSize() { return _stack_head + 1; }
1436
1437    /// \brief Executes the algorithm.
1438    ///
1439    /// Executes the algorithm.
1440    ///
1441    /// \pre init() must be called and at least one node should be added
1442    /// with addSource() before using this function.
1443    void start() {
1444      while ( !emptyQueue() ) processNextArc();
1445    }
1446
1447    /// \brief Executes the algorithm until \c dest is reached.
1448    ///
1449    /// Executes the algorithm until \c dest is reached.
1450    ///
1451    /// \pre init() must be called and at least one node should be added
1452    /// with addSource() before using this function.
1453    void start(Node dest) {
1454      while ( !emptyQueue() && _digraph->target(_stack[_stack_head]) != dest )
1455        processNextArc();
1456    }
1457
1458    /// \brief Executes the algorithm until a condition is met.
1459    ///
1460    /// Executes the algorithm until a condition is met.
1461    ///
1462    /// \pre init() must be called and at least one node should be added
1463    /// with addSource() before using this function.
1464    ///
1465    /// \param em must be a bool (or convertible) arc map. The algorithm
1466    /// will stop when it reaches an arc \c e with <tt>em[e]</tt> true.
1467    ///
1468    ///\return The reached arc \c e with <tt>em[e]</tt> true or
1469    ///\c INVALID if no such arc was found.
1470    ///
1471    /// \warning Contrary to \ref Bfs and \ref Dijkstra, \c em is an arc map,
1472    /// not a node map.
1473    template <typename EM>
1474    Arc start(const EM &em) {
1475      while ( !emptyQueue() && !em[_stack[_stack_head]] )
1476        processNextArc();
1477      return emptyQueue() ? INVALID : _stack[_stack_head];
1478    }
1479
1480    /// \brief Runs %DFSVisit algorithm from node \c s.
1481    ///
1482    /// This method runs the %DFS algorithm from a root node \c s.
1483    /// \note d.run(s) is just a shortcut of the following code.
1484    ///\code
1485    ///   d.init();
1486    ///   d.addSource(s);
1487    ///   d.start();
1488    ///\endcode
1489    void run(Node s) {
1490      init();
1491      addSource(s);
1492      start();
1493    }
1494
1495    /// \brief Runs %DFSVisit algorithm to visit all nodes in the digraph.
1496
1497    /// This method runs the %DFS algorithm in order to
1498    /// compute the %DFS path to each node. The algorithm computes
1499    /// - The %DFS tree.
1500    /// - The distance of each node from the root in the %DFS tree.
1501    ///
1502    ///\note d.run() is just a shortcut of the following code.
1503    ///\code
1504    ///  d.init();
1505    ///  for (NodeIt it(digraph); it != INVALID; ++it) {
1506    ///    if (!d.reached(it)) {
1507    ///      d.addSource(it);
1508    ///      d.start();
1509    ///    }
1510    ///  }
1511    ///\endcode
1512    void run() {
1513      init();
1514      for (NodeIt it(*_digraph); it != INVALID; ++it) {
1515        if (!reached(it)) {
1516          addSource(it);
1517          start();
1518        }
1519      }
1520    }
1521    ///@}
1522
1523    /// \name Query Functions
1524    /// The result of the %DFS algorithm can be obtained using these
1525    /// functions.\n
1526    /// Before the use of these functions,
1527    /// either run() or start() must be called.
1528    ///@{
1529    /// \brief Checks if a node is reachable from the root.
1530    ///
1531    /// Returns \c true if \c v is reachable from the root(s).
1532    /// \warning The source nodes are inditated as unreachable.
1533    /// \pre Either \ref run() or \ref start()
1534    /// must be called before using this function.
1535    ///
1536    bool reached(Node v) { return (*_reached)[v]; }
1537    ///@}
1538  };
1539
1540
1541} //END OF NAMESPACE LEMON
1542
1543#endif
1544
Note: See TracBrowser for help on using the repository browser.