COIN-OR::LEMON - Graph Library

source: lemon-0.x/src/lemon/dijkstra.h @ 1196:4bebc22ab77c

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