COIN-OR::LEMON - Graph Library

source: lemon/lemon/dfs.h @ 728:532697c9fa53

Last change on this file since 728:532697c9fa53 was 631:33c6b6e755cd, checked in by Peter Kovacs <kpeter@…>, 16 years ago

Small doc improvements (#263)

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