COIN-OR::LEMON - Graph Library

source: lemon-0.x/src/lemon/dijkstra.h @ 1151:b217fc69f913

Last change on this file since 1151:b217fc69f913 was 1151:b217fc69f913, checked in by Alpar Juttner, 15 years ago

Several changes in the docs.

File size: 28.4 KB
Line 
1/* -*- C++ -*-
2 * src/lemon/dijkstra.h - Part of LEMON, a generic C++ optimization library
3 *
4 * Copyright (C) 2004 Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
5 * (Egervary Combinatorial Optimization Research Group, 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_DIJKSTRA_H
18#define LEMON_DIJKSTRA_H
19
20///\ingroup flowalgs
21///\file
22///\brief Dijkstra algorithm.
23
24#include <lemon/list_graph.h>
25#include <lemon/bin_heap.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 Dijkstra class.
35
36  ///Default traits class of Dijkstra class.
37  ///\param GR Graph type.
38  ///\param LM Type of length map.
39  template<class GR, class LM>
40  struct DijkstraDefaultTraits
41  {
42    ///The graph type the algorithm runs on.
43    typedef GR Graph;
44    ///The type of the map that stores the edge lengths.
45
46    ///The type of the map that stores the edge lengths.
47    ///It must meet the \ref concept::ReadMap "ReadMap" concept.
48    typedef LM LengthMap;
49    //The type of the length of the edges.
50    typedef typename LM::Value Value;
51    ///The heap type used by Dijkstra algorithm.
52
53    ///The heap type used by Dijkstra algorithm.
54    ///
55    ///\sa BinHeap
56    ///\sa Dijkstra
57    typedef BinHeap<typename Graph::Node,
58                    typename LM::Value,
59                    typename GR::template NodeMap<int>,
60                    std::less<Value> > Heap;
61
62    ///\brief The type of the map that stores the last
63    ///edges of the shortest paths.
64    ///
65    ///The type of the map that stores the last
66    ///edges of the shortest paths.
67    ///It must meet the \ref concept::WriteMap "WriteMap" concept.
68    ///
69    typedef typename Graph::template NodeMap<typename GR::Edge> PredMap;
70    ///Instantiates a PredMap.
71 
72    ///This function instantiates a \ref PredMap.
73    ///\param G is the graph, to which we would like to define the PredMap.
74    ///\todo The graph alone may be insufficient for the initialization
75    static PredMap *createPredMap(const GR &G)
76    {
77      return new PredMap(G);
78    }
79    ///\brief The type of the map that stores the last but one
80    ///nodes of the shortest paths.
81    ///
82    ///The type of the map that stores the last but one
83    ///nodes of the shortest paths.
84    ///It must meet the \ref concept::WriteMap "WriteMap" concept.
85    ///
86    typedef NullMap<typename Graph::Node,typename Graph::Node> PredNodeMap;
87    ///Instantiates a PredNodeMap.
88   
89    ///This function instantiates a \ref PredNodeMap.
90    ///\param G is the graph, to which we would like to define the \ref PredNodeMap
91    static PredNodeMap *createPredNodeMap(const GR &G)
92    {
93      return new PredNodeMap();
94    }
95
96    ///The type of the map that stores whether a nodes is reached.
97 
98    ///The type of the map that stores whether a nodes is reached.
99    ///It must meet the \ref concept::WriteMap "WriteMap" concept.
100    ///By default it is a NullMap.
101    ///\todo If it is set to a real map, Dijkstra::reached() should read this.
102    ///\todo named parameter to set this type, function to read and write.
103    typedef NullMap<typename Graph::Node,bool> ReachedMap;
104    ///Instantiates a ReachedMap.
105 
106    ///This function instantiates a \ref ReachedMap.
107    ///\param G is the graph, to which we would like to define the \ref ReachedMap
108    static ReachedMap *createReachedMap(const GR &G)
109    {
110      return new ReachedMap();
111    }
112    ///The type of the map that stores the dists of the nodes.
113 
114    ///The type of the map that stores the dists of the nodes.
115    ///It must meet the \ref concept::WriteMap "WriteMap" concept.
116    ///
117    typedef typename Graph::template NodeMap<typename LM::Value> DistMap;
118    ///Instantiates a DistMap.
119 
120    ///This function instantiates a \ref DistMap.
121    ///\param G is the graph, to which we would like to define the \ref DistMap
122    static DistMap *createDistMap(const GR &G)
123    {
124      return new DistMap(G);
125    }
126  };
127 
128  ///%Dijkstra algorithm class.
129 
130  /// \ingroup flowalgs
131  ///This class provides an efficient implementation of %Dijkstra algorithm.
132  ///The edge lengths are passed to the algorithm using a
133  ///\ref concept::ReadMap "ReadMap",
134  ///so it is easy to change it to any kind of length.
135  ///
136  ///The type of the length is determined by the
137  ///\ref concept::ReadMap::Value "Value" of the length map.
138  ///
139  ///It is also possible to change the underlying priority heap.
140  ///
141  ///\param GR The graph type the algorithm runs on. The default value is
142  ///\ref ListGraph. The value of GR is not used directly by Dijkstra, it
143  ///is only passed to \ref DijkstraDefaultTraits.
144  ///\param LM This read-only
145  ///EdgeMap
146  ///determines the
147  ///lengths of the edges. It is read once for each edge, so the map
148  ///may involve in relatively time consuming process to compute the edge
149  ///length if it is necessary. The default map type is
150  ///\ref concept::StaticGraph::EdgeMap "Graph::EdgeMap<int>".
151  ///The value of LM is not used directly by Dijkstra, it
152  ///is only passed to \ref DijkstraDefaultTraits.
153  ///\param TR Traits class to set various data types used by the algorithm.
154  ///The default traits class is
155  ///\ref DijkstraDefaultTraits "DijkstraDefaultTraits<GR,LM>".
156  ///See \ref DijkstraDefaultTraits for the documentation of
157  ///a Dijkstra traits class.
158  ///
159  ///\author Jacint Szabo and Alpar Juttner
160  ///\todo A compare object would be nice.
161
162#ifdef DOXYGEN
163  template <typename GR,
164            typename LM,
165            typename TR>
166#else
167  template <typename GR=ListGraph,
168            typename LM=typename GR::template EdgeMap<int>,
169            typename TR=DijkstraDefaultTraits<GR,LM> >
170#endif
171  class Dijkstra {
172  public:
173    /**
174     * \brief \ref Exception for uninitialized parameters.
175     *
176     * This error represents problems in the initialization
177     * of the parameters of the algorithms.
178     */
179    class UninitializedParameter : public lemon::UninitializedParameter {
180    public:
181      virtual const char* exceptionName() const {
182        return "lemon::Dijsktra::UninitializedParameter";
183      }
184    };
185
186    typedef TR Traits;
187    ///The type of the underlying graph.
188    typedef typename TR::Graph Graph;
189    ///\e
190    typedef typename Graph::Node Node;
191    ///\e
192    typedef typename Graph::NodeIt NodeIt;
193    ///\e
194    typedef typename Graph::Edge Edge;
195    ///\e
196    typedef typename Graph::OutEdgeIt OutEdgeIt;
197   
198    ///The type of the length of the edges.
199    typedef typename TR::LengthMap::Value Value;
200    ///The type of the map that stores the edge lengths.
201    typedef typename TR::LengthMap LengthMap;
202    ///\brief The type of the map that stores the last
203    ///edges of the shortest paths.
204    typedef typename TR::PredMap PredMap;
205    ///\brief The type of the map that stores the last but one
206    ///nodes of the shortest paths.
207    typedef typename TR::PredNodeMap PredNodeMap;
208    ///The type of the map indicating if a node is reached.
209    typedef typename TR::ReachedMap ReachedMap;
210    ///The type of the map that stores the dists of the nodes.
211    typedef typename TR::DistMap DistMap;
212    ///The heap type used by the dijkstra algorithm.
213    typedef typename TR::Heap Heap;
214  private:
215    /// Pointer to the underlying graph.
216    const Graph *G;
217    /// Pointer to the length map
218    const LengthMap *length;
219    ///Pointer to the map of predecessors edges.
220    PredMap *_pred;
221    ///Indicates if \ref _pred is locally allocated (\c true) or not.
222    bool local_pred;
223    ///Pointer to the map of predecessors nodes.
224    PredNodeMap *_predNode;
225    ///Indicates if \ref _predNode is locally allocated (\c true) or not.
226    bool local_predNode;
227    ///Pointer to the map of distances.
228    DistMap *_dist;
229    ///Indicates if \ref _dist is locally allocated (\c true) or not.
230    bool local_dist;
231    ///Pointer to the map of reached status of the nodes.
232    ReachedMap *_reached;
233    ///Indicates if \ref _reached is locally allocated (\c true) or not.
234    bool local_reached;
235
236    ///The source node of the last execution.
237    Node source;
238
239    ///Creates the maps if necessary.
240   
241    ///\todo Error if \c G or are \c NULL. What about \c length?
242    ///\todo Better memory allocation (instead of new).
243    void create_maps()
244    {
245      if(!_pred) {
246        local_pred = true;
247        _pred = Traits::createPredMap(*G);
248      }
249      if(!_predNode) {
250        local_predNode = true;
251        _predNode = Traits::createPredNodeMap(*G);
252      }
253      if(!_dist) {
254        local_dist = true;
255        _dist = Traits::createDistMap(*G);
256      }
257      if(!_reached) {
258        local_reached = true;
259        _reached = Traits::createReachedMap(*G);
260      }
261    }
262   
263  public :
264 
265    ///\name Named template parameters
266
267    ///@{
268
269    template <class T>
270    struct DefPredMapTraits : public Traits {
271      typedef T PredMap;
272      static PredMap *createPredMap(const Graph &G)
273      {
274        throw UninitializedParameter();
275      }
276    };
277    ///\ref named-templ-param "Named parameter" for setting PredMap type
278
279    ///\ref named-templ-param "Named parameter" for setting PredMap type
280    ///
281    template <class T>
282    class DefPredMap : public Dijkstra< Graph,
283                                        LengthMap,
284                                        DefPredMapTraits<T> > { };
285   
286    template <class T>
287    struct DefPredNodeMapTraits : public Traits {
288      typedef T PredNodeMap;
289      static PredNodeMap *createPredNodeMap(const Graph &G)
290      {
291        throw UninitializedParameter();
292      }
293    };
294    ///\ref named-templ-param "Named parameter" for setting PredNodeMap type
295
296    ///\ref named-templ-param "Named parameter" for setting PredNodeMap type
297    ///
298    template <class T>
299    class DefPredNodeMap : public Dijkstra< Graph,
300                                            LengthMap,
301                                            DefPredNodeMapTraits<T> > { };
302   
303    template <class T>
304    struct DefDistMapTraits : public Traits {
305      typedef T DistMap;
306      static DistMap *createDistMap(const Graph &G)
307      {
308        throw UninitializedParameter();
309      }
310    };
311    ///\ref named-templ-param "Named parameter" for setting DistMap type
312
313    ///\ref named-templ-param "Named parameter" for setting DistMap type
314    ///
315    template <class T>
316    class DefDistMap : public Dijkstra< Graph,
317                                        LengthMap,
318                                        DefDistMapTraits<T> > { };
319   
320    template <class T>
321    struct DefReachedMapTraits : public Traits {
322      typedef T ReachedMap;
323      static ReachedMap *createReachedMap(const Graph &G)
324      {
325        throw UninitializedParameter();
326      }
327    };
328    ///\ref named-templ-param "Named parameter" for setting ReachedMap type
329
330    ///\ref named-templ-param "Named parameter" for setting ReachedMap type
331    ///
332    template <class T>
333    class DefReachedMap : public Dijkstra< Graph,
334                                        LengthMap,
335                                        DefReachedMapTraits<T> > { };
336   
337    struct DefGraphReachedMapTraits : public Traits {
338      typedef typename Graph::NodeMap<bool> ReachedMap;
339      static ReachedMap *createReachedMap(const Graph &G)
340      {
341        return new ReachedMap(G);
342      }
343    };
344    ///\brief \ref named-templ-param "Named parameter"
345    ///for setting the ReachedMap type to be Graph::NodeMap<bool>.
346    ///
347    ///\ref named-templ-param "Named parameter"
348    ///for setting the ReachedMap type to be Graph::NodeMap<bool>.
349    ///If you don't set it explicitely, it will be automatically allocated.
350    template <class T>
351    class DefReachedMapToBeDefaultMap :
352      public Dijkstra< Graph,
353                       LengthMap,
354                       DefGraphReachedMapTraits> { };
355   
356    ///@}
357
358
359  private:
360    typename Graph::template NodeMap<int> _heap_map;
361    Heap _heap;
362  public:     
363   
364    ///Constructor.
365   
366    ///\param _G the graph the algorithm will run on.
367    ///\param _length the length map used by the algorithm.
368    Dijkstra(const Graph& _G, const LengthMap& _length) :
369      G(&_G), length(&_length),
370      _pred(NULL), local_pred(false),
371      _predNode(NULL), local_predNode(false),
372      _dist(NULL), local_dist(false),
373      _reached(NULL), local_reached(false),
374      _heap_map(*G,-1),_heap(_heap_map)
375    { }
376   
377    ///Destructor.
378    ~Dijkstra()
379    {
380      if(local_pred) delete _pred;
381      if(local_predNode) delete _predNode;
382      if(local_dist) delete _dist;
383      if(local_reached) delete _reached;
384    }
385
386    ///Sets the length map.
387
388    ///Sets the length map.
389    ///\return <tt> (*this) </tt>
390    Dijkstra &lengthMap(const LengthMap &m)
391    {
392      length = &m;
393      return *this;
394    }
395
396    ///Sets the map storing the predecessor edges.
397
398    ///Sets the map storing the predecessor edges.
399    ///If you don't use this function before calling \ref run(),
400    ///it will allocate one. The destuctor deallocates this
401    ///automatically allocated map, of course.
402    ///\return <tt> (*this) </tt>
403    Dijkstra &predMap(PredMap &m)
404    {
405      if(local_pred) {
406        delete _pred;
407        local_pred=false;
408      }
409      _pred = &m;
410      return *this;
411    }
412
413    ///Sets the map storing the predecessor nodes.
414
415    ///Sets the map storing the predecessor nodes.
416    ///If you don't use this function before calling \ref run(),
417    ///it will allocate one. The destuctor deallocates this
418    ///automatically allocated map, of course.
419    ///\return <tt> (*this) </tt>
420    Dijkstra &predNodeMap(PredNodeMap &m)
421    {
422      if(local_predNode) {
423        delete _predNode;
424        local_predNode=false;
425      }
426      _predNode = &m;
427      return *this;
428    }
429
430    ///Sets the map storing the distances calculated by the algorithm.
431
432    ///Sets the map storing the distances calculated by the algorithm.
433    ///If you don't use this function before calling \ref run(),
434    ///it will allocate one. The destuctor deallocates this
435    ///automatically allocated map, of course.
436    ///\return <tt> (*this) </tt>
437    Dijkstra &distMap(DistMap &m)
438    {
439      if(local_dist) {
440        delete _dist;
441        local_dist=false;
442      }
443      _dist = &m;
444      return *this;
445    }
446
447  private:
448    void finalizeNodeData(Node v,Value dst)
449    {
450      _reached->set(v,true);
451      _dist->set(v, dst);
452      _predNode->set(v,G->source((*_pred)[v]));
453    }
454
455  public:
456    ///\name Excetution control
457    ///The simplest way to execute the algorithm is to use
458    ///\ref run().
459    ///\n
460    ///It you need more control on the execution,
461    ///first you must call \ref init(), then you can add several source nodes
462    ///with \ref addSource(). Finally \ref start() will perform the actual path
463    ///computation.
464
465    ///@{
466
467    ///Initializes the internal data structures.
468
469    ///Initializes the internal data structures.
470    ///
471    ///\todo _heap_map's type could also be in the traits class.
472    void init()
473    {
474      create_maps();
475     
476      for ( NodeIt u(*G) ; u!=INVALID ; ++u ) {
477        _pred->set(u,INVALID);
478        _predNode->set(u,INVALID);
479        ///\todo *_reached is not set to false.
480        _heap_map.set(u,Heap::PRE_HEAP);
481      }
482    }
483   
484    ///Adds a new source node.
485
486    ///Adds a new source node the the priority heap.
487    ///It checks if the node has already been added to the heap.
488    ///
489    ///The optional second parameter is the initial distance of the node.
490    ///
491    ///\todo Do we really want to check it?
492    void addSource(Node s,Value dst=0)
493    {
494      source = s;
495      if(_heap.state(s) != Heap::IN_HEAP) _heap.push(s,dst);
496    }
497   
498    void processNextNode()
499    {
500      Node v=_heap.top();
501      Value oldvalue=_heap[v];
502      _heap.pop();
503      finalizeNodeData(v,oldvalue);
504     
505      for(OutEdgeIt e(*G,v); e!=INVALID; ++e) {
506        Node w=G->target(e);
507        switch(_heap.state(w)) {
508        case Heap::PRE_HEAP:
509          _heap.push(w,oldvalue+(*length)[e]);
510          _pred->set(w,e);
511//        _predNode->set(w,v);
512          break;
513        case Heap::IN_HEAP:
514          if ( oldvalue+(*length)[e] < _heap[w] ) {
515            _heap.decrease(w, oldvalue+(*length)[e]);
516            _pred->set(w,e);
517//          _predNode->set(w,v);
518          }
519          break;
520        case Heap::POST_HEAP:
521          break;
522        }
523      }
524    }
525
526    ///Executes the algorithm.
527
528    ///Executes the algorithm.
529    ///
530    ///\pre init() must be called and at least one node should be added
531    ///with addSource() before using this function.
532    ///
533    ///This method runs the %Dijkstra algorithm from the root node(s)
534    ///in order to
535    ///compute the
536    ///shortest path to each node. The algorithm computes
537    ///- The shortest path tree.
538    ///- The distance of each node from the root(s).
539    ///
540    void start()
541    {
542      while ( !_heap.empty() ) processNextNode();
543    }
544   
545    ///Executes the algorithm until \c dest is reached.
546
547    ///Executes the algorithm until \c dest is reached.
548    ///
549    ///\pre init() must be called and at least one node should be added
550    ///with addSource() before using this function.
551    ///
552    ///This method runs the %Dijkstra algorithm from the root node(s)
553    ///in order to
554    ///compute the
555    ///shortest path to \c dest. The algorithm computes
556    ///- The shortest path to \c  dest.
557    ///- The distance of \c dest from the root(s).
558    ///
559    void start(Node dest)
560    {
561      while ( !_heap.empty() && _heap.top()!=dest ) processNextNode();
562      if ( _heap.top()==dest ) finalizeNodeData(_heap.top());
563    }
564   
565    ///Executes the algorithm until a condition is met.
566
567    ///Executes the algorithm until a condition is met.
568    ///
569    ///\pre init() must be called and at least one node should be added
570    ///with addSource() before using this function.
571    ///
572    ///\param nm must be a bool (or convertible) node map. The algorithm
573    ///will stop when it reaches a node \c v with <tt>nm[v]==true</tt>.
574    template<class NM>
575    void start(const NM &nm)
576    {
577      while ( !_heap.empty() && !mn[_heap.top()] ) processNextNode();
578      if ( !_heap.empty() ) finalizeNodeData(_heap.top());
579    }
580   
581    ///Runs %Dijkstra algorithm from node \c s.
582   
583    ///This method runs the %Dijkstra algorithm from a root node \c s
584    ///in order to
585    ///compute the
586    ///shortest path to each node. The algorithm computes
587    ///- The shortest path tree.
588    ///- The distance of each node from the root.
589    ///
590    ///\note d.run(s) is just a shortcut of the following code.
591    ///\code
592    ///  d.init();
593    ///  d.addSource(s);
594    ///  d.start();
595    ///\endcode
596    void run(Node s) {
597      init();
598      addSource(s);
599      start();
600    }
601   
602    ///Finds the shortest path between \c s and \c t.
603   
604    ///Finds the shortest path between \c s and \c t.
605    ///
606    ///\return The length of the shortest s---t path if there exists one,
607    ///0 otherwise.
608    ///\note Apart from the return value, d.run(s) is
609    ///just a shortcut of the following code.
610    ///\code
611    ///  d.init();
612    ///  d.addSource(s);
613    ///  d.start(t);
614    ///\endcode
615    Value run(Node s,Node t) {
616      init();
617      addSource(s);
618      start(t);
619      return (*_pred)[t]==INVALID?0:(*_dist)[t];
620    }
621   
622    ///@}
623
624    ///\name Query Functions
625    ///The result of the %Dijkstra algorithm can be obtained using these
626    ///functions.\n
627    ///Before the use of these functions,
628    ///either run() or start() must be called.
629   
630    ///@{
631
632    ///The distance of a node from the root.
633
634    ///Returns the distance of a node from the root.
635    ///\pre \ref run() must be called before using this function.
636    ///\warning If node \c v in unreachable from the root the return value
637    ///of this funcion is undefined.
638    Value dist(Node v) const { return (*_dist)[v]; }
639
640    ///Returns the 'previous edge' of the shortest path tree.
641
642    ///For a node \c v it returns the 'previous edge' of the shortest path tree,
643    ///i.e. it returns the last edge of a shortest path from the root to \c
644    ///v. It is \ref INVALID
645    ///if \c v is unreachable from the root or if \c v=s. The
646    ///shortest path tree used here is equal to the shortest path tree used in
647    ///\ref predNode(Node v).  \pre \ref run() must be called before using
648    ///this function.
649    ///\todo predEdge could be a better name.
650    Edge pred(Node v) const { return (*_pred)[v]; }
651
652    ///Returns the 'previous node' of the shortest path tree.
653
654    ///For a node \c v it returns the 'previous node' of the shortest path tree,
655    ///i.e. it returns the last but one node from a shortest path from the
656    ///root to \c /v. It is INVALID if \c v is unreachable from the root or if
657    ///\c v=s. The shortest path tree used here is equal to the shortest path
658    ///tree used in \ref pred(Node v).  \pre \ref run() must be called before
659    ///using this function.
660    Node predNode(Node v) const { return (*_pred)[v]==INVALID ? INVALID:
661                                  G->source((*_pred)[v]); }
662   
663    ///Returns a reference to the NodeMap of distances.
664
665    ///Returns a reference to the NodeMap of distances. \pre \ref run() must
666    ///be called before using this function.
667    const DistMap &distMap() const { return *_dist;}
668 
669    ///Returns a reference to the shortest path tree map.
670
671    ///Returns a reference to the NodeMap of the edges of the
672    ///shortest path tree.
673    ///\pre \ref run() must be called before using this function.
674    const PredMap &predMap() const { return *_pred;}
675 
676    ///Returns a reference to the map of nodes of shortest paths.
677
678    ///Returns a reference to the NodeMap of the last but one nodes of the
679    ///shortest path tree.
680    ///\pre \ref run() must be called before using this function.
681    const PredNodeMap &predNodeMap() const { return *_predNode;}
682
683    ///Checks if a node is reachable from the root.
684
685    ///Returns \c true if \c v is reachable from the root.
686    ///\warning If the algorithm is started from multiple nodes,
687    ///this function may give false result for the source nodes.
688    ///\pre \ref run() must be called before using this function.
689    ///
690    bool reached(Node v) { return v==source || (*_pred)[v]!=INVALID; }
691   
692    ///@}
693  };
694
695  /// Default traits used by \ref DijkstraWizard
696
697  /// To make it easier to use Dijkstra algorithm
698  ///we have created a wizard class.
699  /// This \ref DijkstraWizard class needs default traits,
700  ///as well as the \ref Dijkstra class.
701  /// The \ref DijkstraWizardBase is a class to be the default traits of the
702  /// \ref DijkstraWizard class.
703  template<class GR,class LM>
704  class DijkstraWizardBase : public DijkstraDefaultTraits<GR,LM>
705  {
706
707    typedef DijkstraDefaultTraits<GR,LM> Base;
708  protected:
709    /// Pointer to the underlying graph.
710    void *_g;
711    /// Pointer to the length map
712    void *_length;
713    ///Pointer to the map of predecessors edges.
714    void *_pred;
715    ///Pointer to the map of predecessors nodes.
716    void *_predNode;
717    ///Pointer to the map of distances.
718    void *_dist;
719    ///Pointer to the source node.
720    void *_source;
721
722    /// Type of the nodes in the graph.
723    typedef typename Base::Graph::Node Node;
724
725    public:
726    /// Constructor.
727   
728    /// This constructor does not require parameters, therefore it initiates
729    /// all of the attributes to default values (0, INVALID).
730    DijkstraWizardBase() : _g(0), _length(0), _pred(0), _predNode(0),
731                       _dist(0), _source(INVALID) {}
732
733    /// Constructor.
734   
735    /// This constructor requires some parameters, listed in the parameters list.
736    /// Others are initiated to 0.
737    /// \param g is the initial value of  \ref _g
738    /// \param l is the initial value of  \ref _length
739    /// \param s is the initial value of  \ref _source
740    DijkstraWizardBase(const GR &g,const LM &l, Node s=INVALID) :
741      _g((void *)&g), _length((void *)&l), _pred(0), _predNode(0),
742                  _dist(0), _source((void *)&s) {}
743
744  };
745 
746  /// A class to make easier the usage of Dijkstra algorithm
747
748  /// \ingroup flowalgs
749  /// This class is created to make it easier to use Dijkstra algorithm.
750  /// It uses the functions and features of the plain \ref Dijkstra,
751  /// but it is much simpler to use it.
752  ///
753  /// Simplicity means that the way to change the types defined
754  /// in the traits class is based on functions that returns the new class
755  /// and not on templatable built-in classes.
756  /// When using the plain \ref Dijkstra
757  /// the new class with the modified type comes from
758  /// the original class by using the ::
759  /// operator. In the case of \ref DijkstraWizard only
760  /// a function have to be called and it will
761  /// return the needed class.
762  ///
763  /// It does not have own \ref run method. When its \ref run method is called
764  /// it initiates a plain \ref Dijkstra class, and calls the \ref Dijkstra::run
765  /// method of it.
766  template<class TR>
767  class DijkstraWizard : public TR
768  {
769    typedef TR Base;
770
771    ///The type of the underlying graph.
772    typedef typename TR::Graph Graph;
773    //\e
774    typedef typename Graph::Node Node;
775    //\e
776    typedef typename Graph::NodeIt NodeIt;
777    //\e
778    typedef typename Graph::Edge Edge;
779    //\e
780    typedef typename Graph::OutEdgeIt OutEdgeIt;
781   
782    ///The type of the map that stores the edge lengths.
783    typedef typename TR::LengthMap LengthMap;
784    ///The type of the length of the edges.
785    typedef typename LengthMap::Value Value;
786    ///\brief The type of the map that stores the last
787    ///edges of the shortest paths.
788    typedef typename TR::PredMap PredMap;
789    ///\brief The type of the map that stores the last but one
790    ///nodes of the shortest paths.
791    typedef typename TR::PredNodeMap PredNodeMap;
792    ///The type of the map that stores the dists of the nodes.
793    typedef typename TR::DistMap DistMap;
794
795    ///The heap type used by the dijkstra algorithm.
796    typedef typename TR::Heap Heap;
797public:
798    /// Constructor.
799    DijkstraWizard() : TR() {}
800
801    /// Constructor that requires parameters.
802
803    /// Constructor that requires parameters.
804    /// These parameters will be the default values for the traits class.
805    DijkstraWizard(const Graph &g,const LengthMap &l, Node s=INVALID) :
806      TR(g,l,s) {}
807
808    ///Copy constructor
809    DijkstraWizard(const TR &b) : TR(b) {}
810
811    ~DijkstraWizard() {}
812
813    ///Runs Dijkstra algorithm from a given node.
814   
815    ///Runs Dijkstra algorithm from a given node.
816    ///The node can be given by the \ref source function.
817    void run()
818    {
819      if(_source==0) throw UninitializedParameter();
820      Dijkstra<Graph,LengthMap,TR> Dij(*(Graph*)_g,*(LengthMap*)_length);
821      if(_pred) Dij.predMap(*(PredMap*)_pred);
822      if(_predNode) Dij.predNodeMap(*(PredNodeMap*)_predNode);
823      if(_dist) Dij.distMap(*(DistMap*)_dist);
824      Dij.run(*(Node*)_source);
825    }
826
827    ///Runs Dijkstra algorithm from the given node.
828
829    ///Runs Dijkstra algorithm from the given node.
830    ///\param s is the given source.
831    void run(Node s)
832    {
833      _source=(void *)&s;
834      run();
835    }
836
837    template<class T>
838    struct DefPredMapBase : public Base {
839      typedef T PredMap;
840      static PredMap *createPredMap(const Graph &G) { return 0; };
841      DefPredMapBase(const Base &b) : Base(b) {}
842    };
843   
844    /// \ref named-templ-param "Named parameter" function for setting PredMap type
845
846    /// \ref named-templ-param "Named parameter" function for setting PredMap type
847    ///
848    template<class T>
849    DijkstraWizard<DefPredMapBase<T> > predMap(const T &t)
850    {
851      _pred=(void *)&t;
852      return DijkstraWizard<DefPredMapBase<T> >(*this);
853    }
854   
855
856    template<class T>
857    struct DefPredNodeMapBase : public Base {
858      typedef T PredNodeMap;
859      static PredNodeMap *createPredNodeMap(const Graph &G) { return 0; };
860      DefPredNodeMapBase(const Base &b) : Base(b) {}
861    };
862   
863    /// \ref named-templ-param "Named parameter" function for setting PredNodeMap type
864
865    /// \ref named-templ-param "Named parameter" function for setting PredNodeMap type
866    ///
867    template<class T>
868    DijkstraWizard<DefPredNodeMapBase<T> > predNodeMap(const T &t)
869    {
870      _predNode=(void *)&t;
871      return DijkstraWizard<DefPredNodeMapBase<T> >(*this);
872    }
873   
874    template<class T>
875    struct DefDistMapBase : public Base {
876      typedef T DistMap;
877      static DistMap *createDistMap(const Graph &G) { return 0; };
878      DefDistMapBase(const Base &b) : Base(b) {}
879    };
880   
881    /// \ref named-templ-param "Named parameter" function for setting DistMap type
882
883    /// \ref named-templ-param "Named parameter" function for setting DistMap type
884    ///
885    template<class T>
886    DijkstraWizard<DefDistMapBase<T> > distMap(const T &t)
887    {
888      _dist=(void *)&t;
889      return DijkstraWizard<DefDistMapBase<T> >(*this);
890    }
891   
892    /// Sets the source node, from which the Dijkstra algorithm runs.
893
894    /// Sets the source node, from which the Dijkstra algorithm runs.
895    /// \param s is the source node.
896    DijkstraWizard<TR> &source(Node s)
897    {
898      source=(void *)&s;
899      return *this;
900    }
901   
902  };
903 
904  ///\e
905
906  /// \ingroup flowalgs
907  ///\todo Please document...
908  ///
909  template<class GR, class LM>
910  DijkstraWizard<DijkstraWizardBase<GR,LM> >
911  dijkstra(const GR &g,const LM &l,typename GR::Node s=INVALID)
912  {
913    return DijkstraWizard<DijkstraWizardBase<GR,LM> >(g,l,s);
914  }
915
916/// @}
917 
918} //END OF NAMESPACE LEMON
919
920#endif
921
Note: See TracBrowser for help on using the repository browser.