COIN-OR::LEMON - Graph Library

source: lemon-0.x/src/lemon/dijkstra.h @ 1155:fe0fcdb5687b

Last change on this file since 1155:fe0fcdb5687b was 1155:fe0fcdb5687b, checked in by Alpar Juttner, 15 years ago
  • Better addSource()
  • More docs
File size: 29.2 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 to the priority heap.
487    ///
488    ///The optional second parameter is the initial distance of the node.
489    ///
490    ///It checks if the node has already been added to the heap and
491    ///It is pushed to the heap only if either it was not in the heap
492    ///or the shortest path found till then is longer then \c dst.
493    void addSource(Node s,Value dst=0)
494    {
495      source = s;
496      if(_heap.state(s) != Heap::IN_HEAP) _heap.push(s,dst);
497      else if(_heap[s]<dst) {
498        _heap.push(s,dst);
499        _pred->set(s,INVALID);
500      }
501    }
502   
503    ///Processes the next node in the priority heap
504
505    ///Processes the next node in the priority heap.
506    ///
507    ///\warning The priority heap must not be empty!
508    void processNextNode()
509    {
510      Node v=_heap.top();
511      Value oldvalue=_heap[v];
512      _heap.pop();
513      finalizeNodeData(v,oldvalue);
514     
515      for(OutEdgeIt e(*G,v); e!=INVALID; ++e) {
516        Node w=G->target(e);
517        switch(_heap.state(w)) {
518        case Heap::PRE_HEAP:
519          _heap.push(w,oldvalue+(*length)[e]);
520          _pred->set(w,e);
521//        _predNode->set(w,v);
522          break;
523        case Heap::IN_HEAP:
524          if ( oldvalue+(*length)[e] < _heap[w] ) {
525            _heap.decrease(w, oldvalue+(*length)[e]);
526            _pred->set(w,e);
527//          _predNode->set(w,v);
528          }
529          break;
530        case Heap::POST_HEAP:
531          break;
532        }
533      }
534    }
535
536    ///Returns \c false if there are nodes to be processed in the priority heap
537
538    ///Returns \c false if there are nodes to be processed in the priority heap
539    ///
540    bool emptyHeap() { return heap.empty(); }
541    ///Returns the number of the nodes to be processed in the priority heap
542
543    ///Returns the number of the nodes to be processed in the priority heap
544    ///
545    int heapSize() { return heap.size(); }
546   
547    ///Executes the algorithm.
548
549    ///Executes the algorithm.
550    ///
551    ///\pre init() must be called and at least one node should be added
552    ///with addSource() before using this function.
553    ///
554    ///This method runs the %Dijkstra algorithm from the root node(s)
555    ///in order to
556    ///compute the
557    ///shortest path to each node. The algorithm computes
558    ///- The shortest path tree.
559    ///- The distance of each node from the root(s).
560    ///
561    void start()
562    {
563      while ( !_heap.empty() ) processNextNode();
564    }
565   
566    ///Executes the algorithm until \c dest is reached.
567
568    ///Executes the algorithm until \c dest is reached.
569    ///
570    ///\pre init() must be called and at least one node should be added
571    ///with addSource() before using this function.
572    ///
573    ///This method runs the %Dijkstra algorithm from the root node(s)
574    ///in order to
575    ///compute the
576    ///shortest path to \c dest. The algorithm computes
577    ///- The shortest path to \c  dest.
578    ///- The distance of \c dest from the root(s).
579    ///
580    void start(Node dest)
581    {
582      while ( !_heap.empty() && _heap.top()!=dest ) processNextNode();
583      if ( _heap.top()==dest ) finalizeNodeData(_heap.top());
584    }
585   
586    ///Executes the algorithm until a condition is met.
587
588    ///Executes the algorithm until a condition is met.
589    ///
590    ///\pre init() must be called and at least one node should be added
591    ///with addSource() before using this function.
592    ///
593    ///\param nm must be a bool (or convertible) node map. The algorithm
594    ///will stop when it reaches a node \c v with <tt>nm[v]==true</tt>.
595    template<class NM>
596    void start(const NM &nm)
597    {
598      while ( !_heap.empty() && !mn[_heap.top()] ) processNextNode();
599      if ( !_heap.empty() ) finalizeNodeData(_heap.top());
600    }
601   
602    ///Runs %Dijkstra algorithm from node \c s.
603   
604    ///This method runs the %Dijkstra algorithm from a root node \c s
605    ///in order to
606    ///compute the
607    ///shortest path to each node. The algorithm computes
608    ///- The shortest path tree.
609    ///- The distance of each node from the root.
610    ///
611    ///\note d.run(s) is just a shortcut of the following code.
612    ///\code
613    ///  d.init();
614    ///  d.addSource(s);
615    ///  d.start();
616    ///\endcode
617    void run(Node s) {
618      init();
619      addSource(s);
620      start();
621    }
622   
623    ///Finds the shortest path between \c s and \c t.
624   
625    ///Finds the shortest path between \c s and \c t.
626    ///
627    ///\return The length of the shortest s---t path if there exists one,
628    ///0 otherwise.
629    ///\note Apart from the return value, d.run(s) is
630    ///just a shortcut of the following code.
631    ///\code
632    ///  d.init();
633    ///  d.addSource(s);
634    ///  d.start(t);
635    ///\endcode
636    Value run(Node s,Node t) {
637      init();
638      addSource(s);
639      start(t);
640      return (*_pred)[t]==INVALID?0:(*_dist)[t];
641    }
642   
643    ///@}
644
645    ///\name Query Functions
646    ///The result of the %Dijkstra algorithm can be obtained using these
647    ///functions.\n
648    ///Before the use of these functions,
649    ///either run() or start() must be called.
650   
651    ///@{
652
653    ///The distance of a node from the root.
654
655    ///Returns the distance of a node from the root.
656    ///\pre \ref run() must be called before using this function.
657    ///\warning If node \c v in unreachable from the root the return value
658    ///of this funcion is undefined.
659    Value dist(Node v) const { return (*_dist)[v]; }
660
661    ///Returns the 'previous edge' of the shortest path tree.
662
663    ///For a node \c v it returns the 'previous edge' of the shortest path tree,
664    ///i.e. it returns the last edge of a shortest path from the root to \c
665    ///v. It is \ref INVALID
666    ///if \c v is unreachable from the root or if \c v=s. The
667    ///shortest path tree used here is equal to the shortest path tree used in
668    ///\ref predNode(Node v).  \pre \ref run() must be called before using
669    ///this function.
670    ///\todo predEdge could be a better name.
671    Edge pred(Node v) const { return (*_pred)[v]; }
672
673    ///Returns the 'previous node' of the shortest path tree.
674
675    ///For a node \c v it returns the 'previous node' of the shortest path tree,
676    ///i.e. it returns the last but one node from a shortest path from the
677    ///root to \c /v. It is INVALID if \c v is unreachable from the root or if
678    ///\c v=s. The shortest path tree used here is equal to the shortest path
679    ///tree used in \ref pred(Node v).  \pre \ref run() must be called before
680    ///using this function.
681    Node predNode(Node v) const { return (*_pred)[v]==INVALID ? INVALID:
682                                  G->source((*_pred)[v]); }
683   
684    ///Returns a reference to the NodeMap of distances.
685
686    ///Returns a reference to the NodeMap of distances. \pre \ref run() must
687    ///be called before using this function.
688    const DistMap &distMap() const { return *_dist;}
689 
690    ///Returns a reference to the shortest path tree map.
691
692    ///Returns a reference to the NodeMap of the edges of the
693    ///shortest path tree.
694    ///\pre \ref run() must be called before using this function.
695    const PredMap &predMap() const { return *_pred;}
696 
697    ///Returns a reference to the map of nodes of shortest paths.
698
699    ///Returns a reference to the NodeMap of the last but one nodes of the
700    ///shortest path tree.
701    ///\pre \ref run() must be called before using this function.
702    const PredNodeMap &predNodeMap() const { return *_predNode;}
703
704    ///Checks if a node is reachable from the root.
705
706    ///Returns \c true if \c v is reachable from the root.
707    ///\warning If the algorithm is started from multiple nodes,
708    ///this function may give false result for the source nodes.
709    ///\pre \ref run() must be called before using this function.
710    ///
711    bool reached(Node v) { return v==source || (*_pred)[v]!=INVALID; }
712   
713    ///@}
714  };
715
716  /// Default traits used by \ref DijkstraWizard
717
718  /// To make it easier to use Dijkstra algorithm
719  ///we have created a wizard class.
720  /// This \ref DijkstraWizard class needs default traits,
721  ///as well as the \ref Dijkstra class.
722  /// The \ref DijkstraWizardBase is a class to be the default traits of the
723  /// \ref DijkstraWizard class.
724  template<class GR,class LM>
725  class DijkstraWizardBase : public DijkstraDefaultTraits<GR,LM>
726  {
727
728    typedef DijkstraDefaultTraits<GR,LM> Base;
729  protected:
730    /// Pointer to the underlying graph.
731    void *_g;
732    /// Pointer to the length map
733    void *_length;
734    ///Pointer to the map of predecessors edges.
735    void *_pred;
736    ///Pointer to the map of predecessors nodes.
737    void *_predNode;
738    ///Pointer to the map of distances.
739    void *_dist;
740    ///Pointer to the source node.
741    void *_source;
742
743    /// Type of the nodes in the graph.
744    typedef typename Base::Graph::Node Node;
745
746    public:
747    /// Constructor.
748   
749    /// This constructor does not require parameters, therefore it initiates
750    /// all of the attributes to default values (0, INVALID).
751    DijkstraWizardBase() : _g(0), _length(0), _pred(0), _predNode(0),
752                       _dist(0), _source(INVALID) {}
753
754    /// Constructor.
755   
756    /// This constructor requires some parameters, listed in the parameters list.
757    /// Others are initiated to 0.
758    /// \param g is the initial value of  \ref _g
759    /// \param l is the initial value of  \ref _length
760    /// \param s is the initial value of  \ref _source
761    DijkstraWizardBase(const GR &g,const LM &l, Node s=INVALID) :
762      _g((void *)&g), _length((void *)&l), _pred(0), _predNode(0),
763                  _dist(0), _source((void *)&s) {}
764
765  };
766 
767  /// A class to make easier the usage of Dijkstra algorithm
768
769  /// \ingroup flowalgs
770  /// This class is created to make it easier to use Dijkstra algorithm.
771  /// It uses the functions and features of the plain \ref Dijkstra,
772  /// but it is much simpler to use it.
773  ///
774  /// Simplicity means that the way to change the types defined
775  /// in the traits class is based on functions that returns the new class
776  /// and not on templatable built-in classes.
777  /// When using the plain \ref Dijkstra
778  /// the new class with the modified type comes from
779  /// the original class by using the ::
780  /// operator. In the case of \ref DijkstraWizard only
781  /// a function have to be called and it will
782  /// return the needed class.
783  ///
784  /// It does not have own \ref run method. When its \ref run method is called
785  /// it initiates a plain \ref Dijkstra class, and calls the \ref Dijkstra::run
786  /// method of it.
787  template<class TR>
788  class DijkstraWizard : public TR
789  {
790    typedef TR Base;
791
792    ///The type of the underlying graph.
793    typedef typename TR::Graph Graph;
794    //\e
795    typedef typename Graph::Node Node;
796    //\e
797    typedef typename Graph::NodeIt NodeIt;
798    //\e
799    typedef typename Graph::Edge Edge;
800    //\e
801    typedef typename Graph::OutEdgeIt OutEdgeIt;
802   
803    ///The type of the map that stores the edge lengths.
804    typedef typename TR::LengthMap LengthMap;
805    ///The type of the length of the edges.
806    typedef typename LengthMap::Value Value;
807    ///\brief The type of the map that stores the last
808    ///edges of the shortest paths.
809    typedef typename TR::PredMap PredMap;
810    ///\brief The type of the map that stores the last but one
811    ///nodes of the shortest paths.
812    typedef typename TR::PredNodeMap PredNodeMap;
813    ///The type of the map that stores the dists of the nodes.
814    typedef typename TR::DistMap DistMap;
815
816    ///The heap type used by the dijkstra algorithm.
817    typedef typename TR::Heap Heap;
818public:
819    /// Constructor.
820    DijkstraWizard() : TR() {}
821
822    /// Constructor that requires parameters.
823
824    /// Constructor that requires parameters.
825    /// These parameters will be the default values for the traits class.
826    DijkstraWizard(const Graph &g,const LengthMap &l, Node s=INVALID) :
827      TR(g,l,s) {}
828
829    ///Copy constructor
830    DijkstraWizard(const TR &b) : TR(b) {}
831
832    ~DijkstraWizard() {}
833
834    ///Runs Dijkstra algorithm from a given node.
835   
836    ///Runs Dijkstra algorithm from a given node.
837    ///The node can be given by the \ref source function.
838    void run()
839    {
840      if(_source==0) throw UninitializedParameter();
841      Dijkstra<Graph,LengthMap,TR> Dij(*(Graph*)_g,*(LengthMap*)_length);
842      if(_pred) Dij.predMap(*(PredMap*)_pred);
843      if(_predNode) Dij.predNodeMap(*(PredNodeMap*)_predNode);
844      if(_dist) Dij.distMap(*(DistMap*)_dist);
845      Dij.run(*(Node*)_source);
846    }
847
848    ///Runs Dijkstra algorithm from the given node.
849
850    ///Runs Dijkstra algorithm from the given node.
851    ///\param s is the given source.
852    void run(Node s)
853    {
854      _source=(void *)&s;
855      run();
856    }
857
858    template<class T>
859    struct DefPredMapBase : public Base {
860      typedef T PredMap;
861      static PredMap *createPredMap(const Graph &G) { return 0; };
862      DefPredMapBase(const Base &b) : Base(b) {}
863    };
864   
865    /// \ref named-templ-param "Named parameter" function for setting PredMap type
866
867    /// \ref named-templ-param "Named parameter" function for setting PredMap type
868    ///
869    template<class T>
870    DijkstraWizard<DefPredMapBase<T> > predMap(const T &t)
871    {
872      _pred=(void *)&t;
873      return DijkstraWizard<DefPredMapBase<T> >(*this);
874    }
875   
876
877    template<class T>
878    struct DefPredNodeMapBase : public Base {
879      typedef T PredNodeMap;
880      static PredNodeMap *createPredNodeMap(const Graph &G) { return 0; };
881      DefPredNodeMapBase(const Base &b) : Base(b) {}
882    };
883   
884    /// \ref named-templ-param "Named parameter" function for setting PredNodeMap type
885
886    /// \ref named-templ-param "Named parameter" function for setting PredNodeMap type
887    ///
888    template<class T>
889    DijkstraWizard<DefPredNodeMapBase<T> > predNodeMap(const T &t)
890    {
891      _predNode=(void *)&t;
892      return DijkstraWizard<DefPredNodeMapBase<T> >(*this);
893    }
894   
895    template<class T>
896    struct DefDistMapBase : public Base {
897      typedef T DistMap;
898      static DistMap *createDistMap(const Graph &G) { return 0; };
899      DefDistMapBase(const Base &b) : Base(b) {}
900    };
901   
902    /// \ref named-templ-param "Named parameter" function for setting DistMap type
903
904    /// \ref named-templ-param "Named parameter" function for setting DistMap type
905    ///
906    template<class T>
907    DijkstraWizard<DefDistMapBase<T> > distMap(const T &t)
908    {
909      _dist=(void *)&t;
910      return DijkstraWizard<DefDistMapBase<T> >(*this);
911    }
912   
913    /// Sets the source node, from which the Dijkstra algorithm runs.
914
915    /// Sets the source node, from which the Dijkstra algorithm runs.
916    /// \param s is the source node.
917    DijkstraWizard<TR> &source(Node s)
918    {
919      source=(void *)&s;
920      return *this;
921    }
922   
923  };
924 
925  ///\e
926
927  /// \ingroup flowalgs
928  ///\todo Please document...
929  ///
930  template<class GR, class LM>
931  DijkstraWizard<DijkstraWizardBase<GR,LM> >
932  dijkstra(const GR &g,const LM &l,typename GR::Node s=INVALID)
933  {
934    return DijkstraWizard<DijkstraWizardBase<GR,LM> >(g,l,s);
935  }
936
937/// @}
938 
939} //END OF NAMESPACE LEMON
940
941#endif
942
Note: See TracBrowser for help on using the repository browser.