COIN-OR::LEMON - Graph Library

source: lemon-0.x/lemon/dfs.h @ 1709:a323456bf7c8

Last change on this file since 1709:a323456bf7c8 was 1709:a323456bf7c8, checked in by Balazs Dezso, 14 years ago

Template Named Parameter bugfix

File size: 34.1 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
30namespace lemon {
31
32
33 
34  ///Default traits class of Dfs class.
35
36  ///Default traits class of Dfs class.
37  ///\param GR Graph type.
38  template<class GR>
39  struct DfsDefaultTraits
40  {
41    ///The graph type the algorithm runs on.
42    typedef GR Graph;
43    ///\brief The type of the map that stores the last
44    ///edges of the %DFS paths.
45    ///
46    ///The type of the map that stores the last
47    ///edges of the %DFS paths.
48    ///It must meet the \ref concept::WriteMap "WriteMap" concept.
49    ///
50    typedef typename Graph::template NodeMap<typename GR::Edge> PredMap;
51    ///Instantiates a PredMap.
52 
53    ///This function instantiates a \ref PredMap.
54    ///\param G is the graph, to which we would like to define the PredMap.
55    ///\todo The graph alone may be insufficient to initialize
56    static PredMap *createPredMap(const GR &G)
57    {
58      return new PredMap(G);
59    }
60
61    ///The type of the map that indicates which nodes are processed.
62 
63    ///The type of the map that indicates which nodes are processed.
64    ///It must meet the \ref concept::WriteMap "WriteMap" concept.
65    ///\todo named parameter to set this type, function to read and write.
66    typedef NullMap<typename Graph::Node,bool> ProcessedMap;
67    ///Instantiates a ProcessedMap.
68 
69    ///This function instantiates a \ref ProcessedMap.
70    ///\param g is the graph, to which
71    ///we would like to define the \ref ProcessedMap
72#ifdef DOXYGEN
73    static ProcessedMap *createProcessedMap(const GR &g)
74#else
75    static ProcessedMap *createProcessedMap(const GR &)
76#endif
77    {
78      return new ProcessedMap();
79    }
80    ///The type of the map that indicates which nodes are reached.
81 
82    ///The type of the map that indicates which nodes are reached.
83    ///It must meet the \ref concept::WriteMap "WriteMap" concept.
84    ///\todo named parameter to set this type, function to read and write.
85    typedef typename Graph::template NodeMap<bool> ReachedMap;
86    ///Instantiates a ReachedMap.
87 
88    ///This function instantiates a \ref ReachedMap.
89    ///\param G is the graph, to which
90    ///we would like to define the \ref ReachedMap.
91    static ReachedMap *createReachedMap(const GR &G)
92    {
93      return new ReachedMap(G);
94    }
95    ///The type of the map that stores the dists of the nodes.
96 
97    ///The type of the map that stores the dists of the nodes.
98    ///It must meet the \ref concept::WriteMap "WriteMap" concept.
99    ///
100    typedef typename Graph::template NodeMap<int> DistMap;
101    ///Instantiates a DistMap.
102 
103    ///This function instantiates a \ref DistMap.
104    ///\param G is the graph, to which we would like to define the \ref DistMap
105    static DistMap *createDistMap(const GR &G)
106    {
107      return new DistMap(G);
108    }
109  };
110 
111  ///%DFS algorithm class.
112 
113  ///\ingroup flowalgs
114  ///This class provides an efficient implementation of the %DFS algorithm.
115  ///
116  ///\param GR The graph type the algorithm runs on. The default value is
117  ///\ref ListGraph. The value of GR is not used directly by Dfs, it
118  ///is only passed to \ref DfsDefaultTraits.
119  ///\param TR Traits class to set various data types used by the algorithm.
120  ///The default traits class is
121  ///\ref DfsDefaultTraits "DfsDefaultTraits<GR>".
122  ///See \ref DfsDefaultTraits for the documentation of
123  ///a Dfs traits class.
124  ///
125  ///\author Jacint Szabo and Alpar Juttner
126  ///\todo A compare object would be nice.
127
128#ifdef DOXYGEN
129  template <typename GR,
130            typename TR>
131#else
132  template <typename GR=ListGraph,
133            typename TR=DfsDefaultTraits<GR> >
134#endif
135  class Dfs {
136  public:
137    /**
138     * \brief \ref Exception for uninitialized parameters.
139     *
140     * This error represents problems in the initialization
141     * of the parameters of the algorithms.
142     */
143    class UninitializedParameter : public lemon::UninitializedParameter {
144    public:
145      virtual const char* exceptionName() const {
146        return "lemon::Dfs::UninitializedParameter";
147      }
148    };
149
150    typedef TR Traits;
151    ///The type of the underlying graph.
152    typedef typename TR::Graph Graph;
153    ///\e
154    typedef typename Graph::Node Node;
155    ///\e
156    typedef typename Graph::NodeIt NodeIt;
157    ///\e
158    typedef typename Graph::Edge Edge;
159    ///\e
160    typedef typename Graph::OutEdgeIt OutEdgeIt;
161   
162    ///\brief The type of the map that stores the last
163    ///edges of the %DFS paths.
164    typedef typename TR::PredMap PredMap;
165    ///The type of the map indicating which nodes are reached.
166    typedef typename TR::ReachedMap ReachedMap;
167    ///The type of the map indicating which nodes are processed.
168    typedef typename TR::ProcessedMap ProcessedMap;
169    ///The type of the map that stores the dists of the nodes.
170    typedef typename TR::DistMap DistMap;
171  private:
172    /// Pointer to the underlying graph.
173    const Graph *G;
174    ///Pointer to the map of predecessors edges.
175    PredMap *_pred;
176    ///Indicates if \ref _pred is locally allocated (\c true) or not.
177    bool local_pred;
178    ///Pointer to the map of distances.
179    DistMap *_dist;
180    ///Indicates if \ref _dist is locally allocated (\c true) or not.
181    bool local_dist;
182    ///Pointer to the map of reached status of the nodes.
183    ReachedMap *_reached;
184    ///Indicates if \ref _reached is locally allocated (\c true) or not.
185    bool local_reached;
186    ///Pointer to the map of processed status of the nodes.
187    ProcessedMap *_processed;
188    ///Indicates if \ref _processed is locally allocated (\c true) or not.
189    bool local_processed;
190
191    std::vector<typename Graph::OutEdgeIt> _stack;
192    int _stack_head;
193
194    ///Creates the maps if necessary.
195   
196    ///\todo Error if \c G are \c NULL.
197    ///\todo Better memory allocation (instead of new).
198    void create_maps()
199    {
200      if(!_pred) {
201        local_pred = true;
202        _pred = Traits::createPredMap(*G);
203      }
204      if(!_dist) {
205        local_dist = true;
206        _dist = Traits::createDistMap(*G);
207      }
208      if(!_reached) {
209        local_reached = true;
210        _reached = Traits::createReachedMap(*G);
211      }
212      if(!_processed) {
213        local_processed = true;
214        _processed = Traits::createProcessedMap(*G);
215      }
216    }
217   
218  public :
219
220    typedef Dfs Create;
221
222    ///\name Named template parameters
223
224    ///@{
225
226    template <class T>
227    struct DefPredMapTraits : public Traits {
228      typedef T PredMap;
229      static PredMap *createPredMap(const Graph &G)
230      {
231        throw UninitializedParameter();
232      }
233    };
234    ///\ref named-templ-param "Named parameter" for setting PredMap type
235
236    ///\ref named-templ-param "Named parameter" for setting PredMap type
237    ///
238    template <class T>
239    struct DefPredMap : public Dfs<Graph, DefPredMapTraits<T> > {
240      typedef Dfs<Graph, DefPredMapTraits<T> > Create;
241    };
242   
243   
244    template <class T>
245    struct DefDistMapTraits : public Traits {
246      typedef T DistMap;
247      static DistMap *createDistMap(const Graph &G)
248      {
249        throw UninitializedParameter();
250      }
251    };
252    ///\ref named-templ-param "Named parameter" for setting DistMap type
253
254    ///\ref named-templ-param "Named parameter" for setting DistMap type
255    ///
256    template <class T>
257    struct DefDistMap {
258      typedef Dfs<Graph, DefDistMapTraits<T> > Create;
259    };
260   
261    template <class T>
262    struct DefReachedMapTraits : public Traits {
263      typedef T ReachedMap;
264      static ReachedMap *createReachedMap(const Graph &G)
265      {
266        throw UninitializedParameter();
267      }
268    };
269    ///\ref named-templ-param "Named parameter" for setting ReachedMap type
270
271    ///\ref named-templ-param "Named parameter" for setting ReachedMap type
272    ///
273    template <class T>
274    struct DefReachedMap {
275      typedef Dfs< Graph, DefReachedMapTraits<T> > Create;
276    };
277
278    template <class T>
279    struct DefProcessedMapTraits : public Traits {
280      typedef T ProcessedMap;
281      static ProcessedMap *createProcessedMap(const Graph &G)
282      {
283        throw UninitializedParameter();
284      }
285    };
286    ///\ref named-templ-param "Named parameter" for setting ProcessedMap type
287
288    ///\ref named-templ-param "Named parameter" for setting ProcessedMap type
289    ///
290    template <class T>
291    struct DefProcessedMap : public Dfs< Graph, DefProcessedMapTraits<T> > {
292      typedef Dfs< Graph, DefProcessedMapTraits<T> > Create;
293    };
294   
295    struct DefGraphProcessedMapTraits : public Traits {
296      typedef typename Graph::template NodeMap<bool> ProcessedMap;
297      static ProcessedMap *createProcessedMap(const Graph &G)
298      {
299        return new ProcessedMap(G);
300      }
301    };
302    ///\brief \ref named-templ-param "Named parameter"
303    ///for setting the ProcessedMap type to be Graph::NodeMap<bool>.
304    ///
305    ///\ref named-templ-param "Named parameter"
306    ///for setting the ProcessedMap type to be Graph::NodeMap<bool>.
307    ///If you don't set it explicitely, it will be automatically allocated.
308    template <class T>
309    class DefProcessedMapToBeDefaultMap :
310      public Dfs< Graph, DefGraphProcessedMapTraits> {
311      typedef Dfs< Graph, DefGraphProcessedMapTraits> Create;
312    };
313   
314    ///@}
315
316  public:     
317   
318    ///Constructor.
319   
320    ///\param _G the graph the algorithm will run on.
321    ///
322    Dfs(const Graph& _G) :
323      G(&_G),
324      _pred(NULL), local_pred(false),
325//       _predNode(NULL), local_predNode(false),
326      _dist(NULL), local_dist(false),
327      _reached(NULL), local_reached(false),
328      _processed(NULL), local_processed(false)
329    { }
330   
331    ///Destructor.
332    ~Dfs()
333    {
334      if(local_pred) delete _pred;
335//       if(local_predNode) delete _predNode;
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 predecessor nodes.
359
360//     ///Sets the map storing the predecessor nodes.
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 &predNodeMap(PredNodeMap &m)
366//     {
367//       if(local_predNode) {
368//      delete _predNode;
369//      local_predNode=false;
370//       }
371//       _predNode = &m;
372//       return *this;
373//     }
374
375    ///Sets the map storing the distances calculated by the algorithm.
376
377    ///Sets the map storing the distances calculated by the algorithm.
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 &distMap(DistMap &m)
383    {
384      if(local_dist) {
385        delete _dist;
386        local_dist=false;
387      }
388      _dist = &m;
389      return *this;
390    }
391
392    ///Sets the map indicating if a node is reached.
393
394    ///Sets the map indicating if a node is reached.
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 &reachedMap(ReachedMap &m)
400    {
401      if(local_reached) {
402        delete _reached;
403        local_reached=false;
404      }
405      _reached = &m;
406      return *this;
407    }
408
409    ///Sets the map indicating if a node is processed.
410
411    ///Sets the map indicating if a node is processed.
412    ///If you don't use this function before calling \ref run(),
413    ///it will allocate one. The destuctor deallocates this
414    ///automatically allocated map, of course.
415    ///\return <tt> (*this) </tt>
416    Dfs &processedMap(ProcessedMap &m)
417    {
418      if(local_processed) {
419        delete _processed;
420        local_processed=false;
421      }
422      _processed = &m;
423      return *this;
424    }
425
426  public:
427    ///\name Execution control
428    ///The simplest way to execute the algorithm is to use
429    ///one of the member functions called \c run(...).
430    ///\n
431    ///If you need more control on the execution,
432    ///first you must call \ref init(), then you can add several source nodes
433    ///with \ref addSource().
434    ///Finally \ref start() will perform the actual path
435    ///computation.
436
437    ///@{
438
439    ///Initializes the internal data structures.
440
441    ///Initializes the internal data structures.
442    ///
443    void init()
444    {
445      create_maps();
446      _stack.resize(countNodes(*G));
447      _stack_head=-1;
448      for ( NodeIt u(*G) ; u!=INVALID ; ++u ) {
449        _pred->set(u,INVALID);
450        // _predNode->set(u,INVALID);
451        _reached->set(u,false);
452        _processed->set(u,false);
453      }
454    }
455   
456    ///Adds a new source node.
457
458    ///Adds a new source node to the set of nodes to be processed.
459    ///
460    ///\bug dists are wrong (or at least strange) in case of multiple sources.
461    void addSource(Node s)
462    {
463      if(!(*_reached)[s])
464        {
465          _reached->set(s,true);
466          _pred->set(s,INVALID);
467          // _predNode->set(u,INVALID);
468          OutEdgeIt e(*G,s);
469          if(e!=INVALID) {
470            _stack[++_stack_head]=e;
471            _dist->set(s,_stack_head);
472          }
473          else {
474            _processed->set(s,true);
475            _dist->set(s,0);
476          }
477        }
478    }
479   
480    ///Processes the next edge.
481
482    ///Processes the next edge.
483    ///
484    ///\return The processed edge.
485    ///
486    ///\pre The stack must not be empty!
487    Edge processNextEdge()
488    {
489      Node m;
490      Edge e=_stack[_stack_head];
491      if(!(*_reached)[m=G->target(e)]) {
492        _pred->set(m,e);
493        _reached->set(m,true);
494        //        _pred_node->set(m,G->source(e));
495        ++_stack_head;
496        _stack[_stack_head] = OutEdgeIt(*G, m);
497        _dist->set(m,_stack_head);
498      }
499      else {
500        m=G->source(e);
501        ++_stack[_stack_head];
502      }
503      //'m' is now the (original) source of the _stack[_stack_head]
504      while(_stack_head>=0 && _stack[_stack_head]==INVALID) {
505        _processed->set(m,true);
506        --_stack_head;
507        if(_stack_head>=0) {
508          m=G->source(_stack[_stack_head]);
509          ++_stack[_stack_head];
510        }
511      }
512      return e;
513    }
514    ///Next edge to be processed.
515
516    ///Next edge to be processed.
517    ///
518    ///\return The next edge to be processed or INVALID if the stack is
519    /// empty.
520    OutEdgeIt nextEdge()
521    {
522      return _stack_head>=0?_stack[_stack_head]:INVALID;
523    }
524
525    ///\brief Returns \c false if there are nodes
526    ///to be processed in the queue
527    ///
528    ///Returns \c false if there are nodes
529    ///to be processed in the queue
530    ///
531    ///\todo This should be called emptyStack() or some "neutral" name.
532    bool emptyQueue() { return _stack_head<0; }
533    ///Returns the number of the nodes to be processed.
534   
535    ///Returns the number of the nodes to be processed in the queue.
536    ///
537    ///\todo This should be called stackSize() or some "neutral" name.
538    int queueSize() { return _stack_head+1; }
539   
540    ///Executes the algorithm.
541
542    ///Executes the algorithm.
543    ///
544    ///\pre init() must be called and at least one node should be added
545    ///with addSource() before using this function.
546    ///
547    ///This method runs the %DFS algorithm from the root node(s)
548    ///in order to
549    ///compute the
550    ///%DFS path to each node. The algorithm computes
551    ///- The %DFS tree.
552    ///- The distance of each node from the root(s) in the %DFS tree.
553    ///
554    void start()
555    {
556      while ( !emptyQueue() ) processNextEdge();
557    }
558   
559    ///Executes the algorithm until \c dest is reached.
560
561    ///Executes the algorithm until \c dest is reached.
562    ///
563    ///\pre init() must be called and at least one node should be added
564    ///with addSource() before using this function.
565    ///
566    ///This method runs the %DFS algorithm from the root node(s)
567    ///in order to
568    ///compute the
569    ///%DFS path to \c dest. The algorithm computes
570    ///- The %DFS path to \c  dest.
571    ///- The distance of \c dest from the root(s) in the %DFS tree.
572    ///
573    void start(Node dest)
574    {
575      while ( !emptyQueue() && G->target(_stack[_stack_head])!=dest )
576        processNextEdge();
577    }
578   
579    ///Executes the algorithm until a condition is met.
580
581    ///Executes the algorithm until a condition is met.
582    ///
583    ///\pre init() must be called and at least one node should be added
584    ///with addSource() before using this function.
585    ///
586    ///\param nm must be a bool (or convertible) edge map. The algorithm
587    ///will stop when it reaches an edge \c e with <tt>nm[e]==true</tt>.
588    ///
589    ///\warning Contrary to \ref Dfs and \ref Dijkstra, \c nm is an edge map,
590    ///not a node map.
591    template<class NM>
592      void start(const NM &nm)
593      {
594        while ( !emptyQueue() && !nm[_stack[_stack_head]] ) processNextEdge();
595      }
596   
597    ///Runs %DFS algorithm from node \c s.
598   
599    ///This method runs the %DFS algorithm from a root node \c s
600    ///in order to
601    ///compute the
602    ///%DFS path to each node. The algorithm computes
603    ///- The %DFS tree.
604    ///- The distance of each node from the root in the %DFS tree.
605    ///
606    ///\note d.run(s) is just a shortcut of the following code.
607    ///\code
608    ///  d.init();
609    ///  d.addSource(s);
610    ///  d.start();
611    ///\endcode
612    void run(Node s) {
613      init();
614      addSource(s);
615      start();
616    }
617   
618    ///Finds the %DFS path between \c s and \c t.
619   
620    ///Finds the %DFS path between \c s and \c t.
621    ///
622    ///\return The length of the %DFS s---t path if there exists one,
623    ///0 otherwise.
624    ///\note Apart from the return value, d.run(s,t) is
625    ///just a shortcut of the following code.
626    ///\code
627    ///  d.init();
628    ///  d.addSource(s);
629    ///  d.start(t);
630    ///\endcode
631    int run(Node s,Node t) {
632      init();
633      addSource(s);
634      start(t);
635      return reached(t)?_stack_head+1:0;
636    }
637   
638    ///@}
639
640    ///\name Query Functions
641    ///The result of the %DFS algorithm can be obtained using these
642    ///functions.\n
643    ///Before the use of these functions,
644    ///either run() or start() must be called.
645   
646    ///@{
647
648    ///Copies the path to \c t on the DFS tree into \c p
649   
650    ///This function copies the path to \c t on the DFS tree  into \c p.
651    ///If \c t is a source itself or unreachable, then it does not
652    ///alter \c p.
653    ///\todo Is this the right way to handle unreachable nodes?
654    ///
655    ///\return Returns \c true if a path to \c t was actually copied to \c p,
656    ///\c false otherwise.
657    ///\sa DirPath
658    template<class P>
659    bool getPath(P &p,Node t)
660    {
661      if(reached(t)) {
662        p.clear();
663        typename P::Builder b(p);
664        for(b.setStartNode(t);pred(t)!=INVALID;t=predNode(t))
665          b.pushFront(pred(t));
666        b.commit();
667        return true;
668      }
669      return false;
670    }
671
672    ///The distance of a node from the root(s).
673
674    ///Returns the distance of a node from the root(s).
675    ///\pre \ref run() must be called before using this function.
676    ///\warning If node \c v is unreachable from the root(s) then the return value
677    ///of this funcion is undefined.
678    int dist(Node v) const { return (*_dist)[v]; }
679
680    ///Returns the 'previous edge' of the %DFS tree.
681
682    ///For a node \c v it returns the 'previous edge'
683    ///of the %DFS path,
684    ///i.e. it returns the last edge of a %DFS path from the root(s) to \c
685    ///v. It is \ref INVALID
686    ///if \c v is unreachable from the root(s) or \c v is a root. The
687    ///%DFS tree used here is equal to the %DFS tree used in
688    ///\ref predNode().
689    ///\pre Either \ref run() or \ref start() must be called before using
690    ///this function.
691    ///\todo predEdge could be a better name.
692    Edge pred(Node v) const { return (*_pred)[v];}
693
694    ///Returns the 'previous node' of the %DFS tree.
695
696    ///For a node \c v it returns the 'previous node'
697    ///of the %DFS tree,
698    ///i.e. it returns the last but one node from a %DFS path from the
699    ///root(a) to \c /v.
700    ///It is INVALID if \c v is unreachable from the root(s) or
701    ///if \c v itself a root.
702    ///The %DFS tree used here is equal to the %DFS
703    ///tree used in \ref pred().
704    ///\pre Either \ref run() or \ref start() must be called before
705    ///using this function.
706    Node predNode(Node v) const { return (*_pred)[v]==INVALID ? INVALID:
707                                  G->source((*_pred)[v]); }
708   
709    ///Returns a reference to the NodeMap of distances.
710
711    ///Returns a reference to the NodeMap of distances.
712    ///\pre Either \ref run() or \ref init() must
713    ///be called before using this function.
714    const DistMap &distMap() const { return *_dist;}
715 
716    ///Returns a reference to the %DFS edge-tree map.
717
718    ///Returns a reference to the NodeMap of the edges of the
719    ///%DFS tree.
720    ///\pre Either \ref run() or \ref init()
721    ///must be called before using this function.
722    const PredMap &predMap() const { return *_pred;}
723 
724//     ///Returns a reference to the map of nodes of %DFS paths.
725
726//     ///Returns a reference to the NodeMap of the last but one nodes of the
727//     ///%DFS tree.
728//     ///\pre \ref run() must be called before using this function.
729//     const PredNodeMap &predNodeMap() const { return *_predNode;}
730
731    ///Checks if a node is reachable from the root.
732
733    ///Returns \c true if \c v is reachable from the root(s).
734    ///\warning The source nodes are inditated as unreachable.
735    ///\pre Either \ref run() or \ref start()
736    ///must be called before using this function.
737    ///
738    bool reached(Node v) { return (*_reached)[v]; }
739   
740    ///@}
741  };
742
743  ///Default traits class of Dfs function.
744
745  ///Default traits class of Dfs function.
746  ///\param GR Graph type.
747  template<class GR>
748  struct DfsWizardDefaultTraits
749  {
750    ///The graph type the algorithm runs on.
751    typedef GR Graph;
752    ///\brief The type of the map that stores the last
753    ///edges of the %DFS paths.
754    ///
755    ///The type of the map that stores the last
756    ///edges of the %DFS paths.
757    ///It must meet the \ref concept::WriteMap "WriteMap" concept.
758    ///
759    typedef NullMap<typename Graph::Node,typename GR::Edge> PredMap;
760    ///Instantiates a PredMap.
761 
762    ///This function instantiates a \ref PredMap.
763    ///\param g is the graph, to which we would like to define the PredMap.
764    ///\todo The graph alone may be insufficient to initialize
765#ifdef DOXYGEN
766    static PredMap *createPredMap(const GR &g)
767#else
768    static PredMap *createPredMap(const GR &)
769#endif
770    {
771      return new PredMap();
772    }
773//     ///\brief The type of the map that stores the last but one
774//     ///nodes of the %DFS paths.
775//     ///
776//     ///The type of the map that stores the last but one
777//     ///nodes of the %DFS paths.
778//     ///It must meet the \ref concept::WriteMap "WriteMap" concept.
779//     ///
780//     typedef NullMap<typename Graph::Node,typename Graph::Node> PredNodeMap;
781//     ///Instantiates a PredNodeMap.
782   
783//     ///This function instantiates a \ref PredNodeMap.
784//     ///\param G is the graph, to which
785//     ///we would like to define the \ref PredNodeMap
786//     static PredNodeMap *createPredNodeMap(const GR &G)
787//     {
788//       return new PredNodeMap();
789//     }
790
791    ///The type of the map that indicates which nodes are processed.
792 
793    ///The type of the map that indicates which nodes are processed.
794    ///It must meet the \ref concept::WriteMap "WriteMap" concept.
795    ///\todo named parameter to set this type, function to read and write.
796    typedef NullMap<typename Graph::Node,bool> ProcessedMap;
797    ///Instantiates a ProcessedMap.
798 
799    ///This function instantiates a \ref ProcessedMap.
800    ///\param g is the graph, to which
801    ///we would like to define the \ref ProcessedMap
802#ifdef DOXYGEN
803    static ProcessedMap *createProcessedMap(const GR &g)
804#else
805    static ProcessedMap *createProcessedMap(const GR &)
806#endif
807    {
808      return new ProcessedMap();
809    }
810    ///The type of the map that indicates which nodes are reached.
811 
812    ///The type of the map that indicates which nodes are reached.
813    ///It must meet the \ref concept::WriteMap "WriteMap" concept.
814    ///\todo named parameter to set this type, function to read and write.
815    typedef typename Graph::template NodeMap<bool> ReachedMap;
816    ///Instantiates a ReachedMap.
817 
818    ///This function instantiates a \ref ReachedMap.
819    ///\param G is the graph, to which
820    ///we would like to define the \ref ReachedMap.
821    static ReachedMap *createReachedMap(const GR &G)
822    {
823      return new ReachedMap(G);
824    }
825    ///The type of the map that stores the dists of the nodes.
826 
827    ///The type of the map that stores the dists of the nodes.
828    ///It must meet the \ref concept::WriteMap "WriteMap" concept.
829    ///
830    typedef NullMap<typename Graph::Node,int> DistMap;
831    ///Instantiates a DistMap.
832 
833    ///This function instantiates a \ref DistMap.
834    ///\param g is the graph, to which we would like to define the \ref DistMap
835#ifdef DOXYGEN
836    static DistMap *createDistMap(const GR &g)
837#else
838    static DistMap *createDistMap(const GR &)
839#endif
840    {
841      return new DistMap();
842    }
843  };
844 
845  /// Default traits used by \ref DfsWizard
846
847  /// To make it easier to use Dfs algorithm
848  ///we have created a wizard class.
849  /// This \ref DfsWizard class needs default traits,
850  ///as well as the \ref Dfs class.
851  /// The \ref DfsWizardBase is a class to be the default traits of the
852  /// \ref DfsWizard class.
853  template<class GR>
854  class DfsWizardBase : public DfsWizardDefaultTraits<GR>
855  {
856
857    typedef DfsWizardDefaultTraits<GR> Base;
858  protected:
859    /// Type of the nodes in the graph.
860    typedef typename Base::Graph::Node Node;
861
862    /// Pointer to the underlying graph.
863    void *_g;
864    ///Pointer to the map of reached nodes.
865    void *_reached;
866    ///Pointer to the map of processed nodes.
867    void *_processed;
868    ///Pointer to the map of predecessors edges.
869    void *_pred;
870//     ///Pointer to the map of predecessors nodes.
871//     void *_predNode;
872    ///Pointer to the map of distances.
873    void *_dist;
874    ///Pointer to the source node.
875    Node _source;
876   
877    public:
878    /// Constructor.
879   
880    /// This constructor does not require parameters, therefore it initiates
881    /// all of the attributes to default values (0, INVALID).
882    DfsWizardBase() : _g(0), _reached(0), _processed(0), _pred(0),
883//                         _predNode(0),
884                           _dist(0), _source(INVALID) {}
885
886    /// Constructor.
887   
888    /// This constructor requires some parameters,
889    /// listed in the parameters list.
890    /// Others are initiated to 0.
891    /// \param g is the initial value of  \ref _g
892    /// \param s is the initial value of  \ref _source
893    DfsWizardBase(const GR &g, Node s=INVALID) :
894      _g((void *)&g), _reached(0), _processed(0), _pred(0),
895//       _predNode(0),
896      _dist(0), _source(s) {}
897
898  };
899 
900  /// A class to make the usage of the Dfs algorithm easier
901
902  /// This class is created to make it easier to use the Dfs algorithm.
903  /// It uses the functions and features of the plain \ref Dfs,
904  /// but it is much simpler to use it.
905  ///
906  /// Simplicity means that the way to change the types defined
907  /// in the traits class is based on functions that returns the new class
908  /// and not on templatable built-in classes.
909  /// When using the plain \ref Dfs
910  /// the new class with the modified type comes from
911  /// the original class by using the ::
912  /// operator. In the case of \ref DfsWizard only
913  /// a function have to be called and it will
914  /// return the needed class.
915  ///
916  /// It does not have own \ref run method. When its \ref run method is called
917  /// it initiates a plain \ref Dfs object, and calls the \ref Dfs::run
918  /// method of it.
919  template<class TR>
920  class DfsWizard : public TR
921  {
922    typedef TR Base;
923
924    ///The type of the underlying graph.
925    typedef typename TR::Graph Graph;
926    //\e
927    typedef typename Graph::Node Node;
928    //\e
929    typedef typename Graph::NodeIt NodeIt;
930    //\e
931    typedef typename Graph::Edge Edge;
932    //\e
933    typedef typename Graph::OutEdgeIt OutEdgeIt;
934   
935    ///\brief The type of the map that stores
936    ///the reached nodes
937    typedef typename TR::ReachedMap ReachedMap;
938    ///\brief The type of the map that stores
939    ///the processed nodes
940    typedef typename TR::ProcessedMap ProcessedMap;
941    ///\brief The type of the map that stores the last
942    ///edges of the %DFS paths.
943    typedef typename TR::PredMap PredMap;
944//     ///\brief The type of the map that stores the last but one
945//     ///nodes of the %DFS paths.
946//     typedef typename TR::PredNodeMap PredNodeMap;
947    ///The type of the map that stores the distances of the nodes.
948    typedef typename TR::DistMap DistMap;
949
950public:
951    /// Constructor.
952    DfsWizard() : TR() {}
953
954    /// Constructor that requires parameters.
955
956    /// Constructor that requires parameters.
957    /// These parameters will be the default values for the traits class.
958    DfsWizard(const Graph &g, Node s=INVALID) :
959      TR(g,s) {}
960
961    ///Copy constructor
962    DfsWizard(const TR &b) : TR(b) {}
963
964    ~DfsWizard() {}
965
966    ///Runs Dfs algorithm from a given node.
967   
968    ///Runs Dfs algorithm from a given node.
969    ///The node can be given by the \ref source function.
970    void run()
971    {
972      if(Base::_source==INVALID) throw UninitializedParameter();
973      Dfs<Graph,TR> alg(*(Graph*)Base::_g);
974      if(Base::_reached) alg.reachedMap(*(ReachedMap*)Base::_reached);
975      if(Base::_processed) alg.processedMap(*(ProcessedMap*)Base::_processed);
976      if(Base::_pred) alg.predMap(*(PredMap*)Base::_pred);
977//       if(Base::_predNode) alg.predNodeMap(*(PredNodeMap*)Base::_predNode);
978      if(Base::_dist) alg.distMap(*(DistMap*)Base::_dist);
979      alg.run(Base::_source);
980    }
981
982    ///Runs Dfs algorithm from the given node.
983
984    ///Runs Dfs algorithm from the given node.
985    ///\param s is the given source.
986    void run(Node s)
987    {
988      Base::_source=s;
989      run();
990    }
991
992    template<class T>
993    struct DefPredMapBase : public Base {
994      typedef T PredMap;
995      static PredMap *createPredMap(const Graph &) { return 0; };
996      DefPredMapBase(const TR &b) : TR(b) {}
997    };
998   
999    ///\brief \ref named-templ-param "Named parameter"
1000    ///function for setting PredMap type
1001    ///
1002    /// \ref named-templ-param "Named parameter"
1003    ///function for setting PredMap type
1004    ///
1005    template<class T>
1006    DfsWizard<DefPredMapBase<T> > predMap(const T &t)
1007    {
1008      Base::_pred=(void *)&t;
1009      return DfsWizard<DefPredMapBase<T> >(*this);
1010    }
1011   
1012 
1013    template<class T>
1014    struct DefReachedMapBase : public Base {
1015      typedef T ReachedMap;
1016      static ReachedMap *createReachedMap(const Graph &) { return 0; };
1017      DefReachedMapBase(const TR &b) : TR(b) {}
1018    };
1019   
1020    ///\brief \ref named-templ-param "Named parameter"
1021    ///function for setting ReachedMap
1022    ///
1023    /// \ref named-templ-param "Named parameter"
1024    ///function for setting ReachedMap
1025    ///
1026    template<class T>
1027    DfsWizard<DefReachedMapBase<T> > reachedMap(const T &t)
1028    {
1029      Base::_pred=(void *)&t;
1030      return DfsWizard<DefReachedMapBase<T> >(*this);
1031    }
1032   
1033
1034    template<class T>
1035    struct DefProcessedMapBase : public Base {
1036      typedef T ProcessedMap;
1037      static ProcessedMap *createProcessedMap(const Graph &) { return 0; };
1038      DefProcessedMapBase(const TR &b) : TR(b) {}
1039    };
1040   
1041    ///\brief \ref named-templ-param "Named parameter"
1042    ///function for setting ProcessedMap
1043    ///
1044    /// \ref named-templ-param "Named parameter"
1045    ///function for setting ProcessedMap
1046    ///
1047    template<class T>
1048    DfsWizard<DefProcessedMapBase<T> > processedMap(const T &t)
1049    {
1050      Base::_pred=(void *)&t;
1051      return DfsWizard<DefProcessedMapBase<T> >(*this);
1052    }
1053   
1054
1055//     template<class T>
1056//     struct DefPredNodeMapBase : public Base {
1057//       typedef T PredNodeMap;
1058//       static PredNodeMap *createPredNodeMap(const Graph &G) { return 0; };
1059//       DefPredNodeMapBase(const TR &b) : TR(b) {}
1060//     };
1061   
1062//     ///\brief \ref named-templ-param "Named parameter"
1063//     ///function for setting PredNodeMap type
1064//     ///
1065//     /// \ref named-templ-param "Named parameter"
1066//     ///function for setting PredNodeMap type
1067//     ///
1068//     template<class T>
1069//     DfsWizard<DefPredNodeMapBase<T> > predNodeMap(const T &t)
1070//     {
1071//       Base::_predNode=(void *)&t;
1072//       return DfsWizard<DefPredNodeMapBase<T> >(*this);
1073//     }
1074   
1075    template<class T>
1076    struct DefDistMapBase : public Base {
1077      typedef T DistMap;
1078      static DistMap *createDistMap(const Graph &) { return 0; };
1079      DefDistMapBase(const TR &b) : TR(b) {}
1080    };
1081   
1082    ///\brief \ref named-templ-param "Named parameter"
1083    ///function for setting DistMap type
1084    ///
1085    /// \ref named-templ-param "Named parameter"
1086    ///function for setting DistMap type
1087    ///
1088    template<class T>
1089    DfsWizard<DefDistMapBase<T> > distMap(const T &t)
1090    {
1091      Base::_dist=(void *)&t;
1092      return DfsWizard<DefDistMapBase<T> >(*this);
1093    }
1094   
1095    /// Sets the source node, from which the Dfs algorithm runs.
1096
1097    /// Sets the source node, from which the Dfs algorithm runs.
1098    /// \param s is the source node.
1099    DfsWizard<TR> &source(Node s)
1100    {
1101      Base::_source=s;
1102      return *this;
1103    }
1104   
1105  };
1106 
1107  ///Function type interface for Dfs algorithm.
1108
1109  /// \ingroup flowalgs
1110  ///Function type interface for Dfs algorithm.
1111  ///
1112  ///This function also has several
1113  ///\ref named-templ-func-param "named parameters",
1114  ///they are declared as the members of class \ref DfsWizard.
1115  ///The following
1116  ///example shows how to use these parameters.
1117  ///\code
1118  ///  dfs(g,source).predMap(preds).run();
1119  ///\endcode
1120  ///\warning Don't forget to put the \ref DfsWizard::run() "run()"
1121  ///to the end of the parameter list.
1122  ///\sa DfsWizard
1123  ///\sa Dfs
1124  template<class GR>
1125  DfsWizard<DfsWizardBase<GR> >
1126  dfs(const GR &g,typename GR::Node s=INVALID)
1127  {
1128    return DfsWizard<DfsWizardBase<GR> >(g,s);
1129  }
1130
1131} //END OF NAMESPACE LEMON
1132
1133#endif
1134
Note: See TracBrowser for help on using the repository browser.