COIN-OR::LEMON - Graph Library

source: lemon-0.x/lemon/dfs.h @ 1773:ea5927cef15c

Last change on this file since 1773:ea5927cef15c was 1773:ea5927cef15c, checked in by Alpar Juttner, 14 years ago

Bugfix

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