COIN-OR::LEMON - Graph Library

source: lemon-0.x/src/work/alpar/dijkstra.h @ 1123:a2e93889a604

Last change on this file since 1123:a2e93889a604 was 1123:a2e93889a604, checked in by Hegyi Péter, 15 years ago

Documentation is developing itself, but is not ready yet.

File size: 22.6 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  class UninitializedData : public LogicError {};
34
35
36/// \addtogroup flowalgs
37/// @{
38
39  ///Default traits class of Dijkstra class.
40
41  ///Default traits class of Dijkstra class.
42  ///\param GR Graph type.
43  ///\param LM Type of length map.
44  template<class GR, class LM>
45  struct DijkstraDefaultTraits
46  {
47    ///The graph type the algorithm runs on.
48    typedef GR Graph;
49    ///The type of the map that stores the edge lengths.
50
51    ///It must meet the \ref concept::ReadMap "ReadMap" concept.
52    ///
53    typedef LM LengthMap;
54    //The type of the length of the edges.
55    typedef typename LM::Value Value;
56    ///The heap type used by Dijkstra algorithm.
57
58    ///The heap type used by Dijkstra algorithm.
59    ///
60    ///\sa BinHeap
61    ///\sa Dijkstra
62    typedef BinHeap<typename Graph::Node,
63                    typename LM::Value,
64                    typename GR::template NodeMap<int>,
65                    std::less<Value> > Heap;
66
67    ///\brief The type of the map that stores the last
68    ///edges of the shortest paths.
69    ///
70    ///It must meet the \ref concept::WriteMap "WriteMap" concept.
71    ///
72    typedef typename Graph::template NodeMap<typename GR::Edge> PredMap;
73    ///Instantiates a PredMap.
74 
75    ///This function instantiates a \ref PredMap.
76    ///\param G is the graph, to which we would like to define the PredMap.
77    ///\todo The graph alone may be insufficient for the initialization
78    static PredMap *createPredMap(const GR &G)
79    {
80      return new PredMap(G);
81    }
82    ///\brief The type of the map that stores the last but one
83    ///nodes of the shortest paths.
84    ///
85    ///It must meet the \ref concept::WriteMap "WriteMap" concept.
86    ///
87    typedef typename Graph::template NodeMap<typename GR::Node> PredNodeMap;
88    ///Instantiates a PredNodeMap.
89 
90    ///This function instantiates a \ref PredNodeMap.
91    ///\param G is the graph, to which we would like to define the \ref PredNodeMap
92    static PredNodeMap *createPredNodeMap(const GR &G)
93    {
94      return new PredNodeMap(G);
95    }
96
97    ///The type of the map that stores whether a nodes is reached.
98 
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    ///It must meet the \ref concept::WriteMap "WriteMap" concept.
115    ///
116    typedef typename Graph::template NodeMap<typename LM::Value> DistMap;
117    ///Instantiates a DistMap.
118 
119    ///This function instantiates a \ref DistMap.
120    ///\param G is the graph, to which we would like to define the \ref DistMap
121    static DistMap *createDistMap(const GR &G)
122    {
123      return new DistMap(G);
124    }
125  };
126 
127  ///%Dijkstra algorithm class.
128
129  ///This class provides an efficient implementation of %Dijkstra algorithm.
130  ///The edge lengths are passed to the algorithm using a
131  ///\ref concept::ReadMap "ReadMap",
132  ///so it is easy to change it to any kind of length.
133  ///
134  ///The type of the length is determined by the
135  ///\ref concept::ReadMap::Value "Value" of the length map.
136  ///
137  ///It is also possible to change the underlying priority heap.
138  ///
139  ///\param GR The graph type the algorithm runs on. The default value is
140  ///\ref ListGraph. The value of GR is not used directly by Dijkstra, it
141  ///is only passed to \ref DijkstraDefaultTraits.
142  ///\param LM This read-only
143  ///EdgeMap
144  ///determines the
145  ///lengths of the edges. It is read once for each edge, so the map
146  ///may involve in relatively time consuming process to compute the edge
147  ///length if it is necessary. The default map type is
148  ///\ref concept::StaticGraph::EdgeMap "Graph::EdgeMap<int>".
149  ///The value of LM is not used directly by Dijkstra, it
150  ///is only passed to \ref DijkstraDefaultTraits.
151  ///\param TR Traits class to set various data types used by the algorithm.
152  ///The default traits class is
153  ///\ref DijkstraDefaultTraits "DijkstraDefaultTraits<GR,LM>".
154  ///See \ref DijkstraDefaultTraits for the documentation of
155  ///a Dijkstra traits class.
156  ///
157  ///\author Jacint Szabo and Alpar Juttner
158  ///\todo We need a typedef-names should be standardized. (-:
159
160#ifdef DOXYGEN
161  template <typename GR,
162            typename LM,
163            typename TR>
164#else
165  template <typename GR=ListGraph,
166            typename LM=typename GR::template EdgeMap<int>,
167            typename TR=DijkstraDefaultTraits<GR,LM> >
168#endif
169  class Dijkstra {
170  public:
171    ///Exception thrown by dijkstra.
172    class UninitializedData : public lemon::UninitializedData {};
173
174    typedef TR Traits;
175    ///The type of the underlying graph.
176    typedef typename TR::Graph Graph;
177    ///\e
178    typedef typename Graph::Node Node;
179    ///\e
180    typedef typename Graph::NodeIt NodeIt;
181    ///\e
182    typedef typename Graph::Edge Edge;
183    ///\e
184    typedef typename Graph::OutEdgeIt OutEdgeIt;
185   
186    ///The type of the length of the edges.
187    typedef typename TR::LengthMap::Value Value;
188    ///The type of the map that stores the edge lengths.
189    typedef typename TR::LengthMap LengthMap;
190    ///\brief The type of the map that stores the last
191    ///edges of the shortest paths.
192    typedef typename TR::PredMap PredMap;
193    ///\brief The type of the map that stores the last but one
194    ///nodes of the shortest paths.
195    typedef typename TR::PredNodeMap PredNodeMap;
196    ///The type of the map indicating if a node is reached.
197    typedef typename TR::ReachedMap ReachedMap;
198    ///The type of the map that stores the dists of the nodes.
199    typedef typename TR::DistMap DistMap;
200    ///The heap type used by the dijkstra algorithm.
201    typedef typename TR::Heap Heap;
202  private:
203    /// Pointer to the underlying graph.
204    const Graph *G;
205    /// Pointer to the length map
206    const LengthMap *length;
207    ///Pointer to the map of predecessors edges.
208    PredMap *_pred;
209    ///Indicates if \ref _pred is locally allocated (\c true) or not.
210    bool local_pred;
211    ///Pointer to the map of predecessors nodes.
212    PredNodeMap *pred_node;
213    ///Indicates if \ref pred_node is locally allocated (\c true) or not.
214    bool local_pred_node;
215    ///Pointer to the map of distances.
216    DistMap *distance;
217    ///Indicates if \ref distance is locally allocated (\c true) or not.
218    bool local_distance;
219    ///Pointer to the map of reached status of the nodes.
220    ReachedMap *_reached;
221    ///Indicates if \ref _reached is locally allocated (\c true) or not.
222    bool local_reached;
223
224    ///The source node of the last execution.
225    Node source;
226
227    ///Initializes the maps.
228   
229    ///\todo Error if \c G or are \c NULL. What about \c length?
230    ///\todo Better memory allocation (instead of new).
231    void init_maps()
232    {
233      if(!_pred) {
234        local_pred = true;
235        _pred = Traits::createPredMap(*G);
236      }
237      if(!pred_node) {
238        local_pred_node = true;
239        pred_node = Traits::createPredNodeMap(*G);
240      }
241      if(!distance) {
242        local_distance = true;
243        distance = Traits::createDistMap(*G);
244      }
245      if(!_reached) {
246        local_reached = true;
247        _reached = Traits::createReachedMap(*G);
248      }
249    }
250   
251  public :
252 
253    template <class T>
254    struct DefPredMapTraits : public Traits {
255      typedef T PredMap;
256      ///\todo An exception should be thrown.
257      ///
258      static PredMap *createPredMap(const Graph &G)
259      {
260        throw UninitializedData();
261      }
262    };
263    ///\ref named-templ-param "Named parameter" for setting PredMap type
264
265    ///\ref named-templ-param "Named parameter" for setting PredMap type
266    ///
267    template <class T>
268    class DefPredMap : public Dijkstra< Graph,
269                                        LengthMap,
270                                        DefPredMapTraits<T> > { };
271   
272    template <class T>
273    struct DefPredNodeMapTraits : public Traits {
274      typedef T PredNodeMap;
275      ///\todo An exception should be thrown.
276      ///
277      static PredNodeMap *createPredNodeMap(const Graph &G)
278      {
279        throw UninitializedData();
280      }
281    };
282    ///\ref named-templ-param "Named parameter" for setting PredNodeMap type
283
284    ///\ref named-templ-param "Named parameter" for setting PredNodeMap type
285    ///
286    template <class T>
287    class DefPredNodeMap : public Dijkstra< Graph,
288                                            LengthMap,
289                                            DefPredNodeMapTraits<T> > { };
290   
291    template <class T>
292    struct DefDistMapTraits : public Traits {
293      typedef T DistMap;
294      ///\todo An exception should be thrown.
295      ///
296      static DistMap *createDistMap(const Graph &G)
297      {
298        throw UninitializedData();
299      }
300    };
301    ///\ref named-templ-param "Named parameter" for setting DistMap type
302
303    ///\ref named-templ-param "Named parameter" for setting DistMap type
304    ///
305    template <class T>
306    class DefDistMap : public Dijkstra< Graph,
307                                        LengthMap,
308                                        DefDistMapTraits<T> > { };
309   
310    ///Constructor.
311   
312    ///\param _G the graph the algorithm will run on.
313    ///\param _length the length map used by the algorithm.
314    Dijkstra(const Graph& _G, const LengthMap& _length) :
315      G(&_G), length(&_length),
316      _pred(NULL), local_pred(false),
317      pred_node(NULL), local_pred_node(false),
318      distance(NULL), local_distance(false),
319      _reached(NULL), local_reached(false)
320    { }
321   
322    ///Destructor.
323    ~Dijkstra()
324    {
325      if(local_pred) delete _pred;
326      if(local_pred_node) delete pred_node;
327      if(local_distance) delete distance;
328      if(local_reached) delete _reached;
329    }
330
331    ///Sets the length map.
332
333    ///Sets the length map.
334    ///\return <tt> (*this) </tt>
335    Dijkstra &lengthMap(const LengthMap &m)
336    {
337      length = &m;
338      return *this;
339    }
340
341    ///Sets the map storing the predecessor edges.
342
343    ///Sets the map storing the predecessor edges.
344    ///If you don't use this function before calling \ref run(),
345    ///it will allocate one. The destuctor deallocates this
346    ///automatically allocated map, of course.
347    ///\return <tt> (*this) </tt>
348    Dijkstra &predMap(PredMap &m)
349    {
350      if(local_pred) {
351        delete _pred;
352        local_pred=false;
353      }
354      _pred = &m;
355      return *this;
356    }
357
358    ///Sets the map storing the predecessor nodes.
359
360    ///Sets the map storing the predecessor nodes.
361    ///If you don't use this function before calling \ref run(),
362    ///it will allocate one. The destuctor deallocates this
363    ///automatically allocated map, of course.
364    ///\return <tt> (*this) </tt>
365    Dijkstra &predNodeMap(PredNodeMap &m)
366    {
367      if(local_pred_node) {
368        delete pred_node;
369        local_pred_node=false;
370      }
371      pred_node = &m;
372      return *this;
373    }
374
375    ///Sets the map storing the distances calculated by the algorithm.
376
377    ///Sets the map storing the distances calculated by the algorithm.
378    ///If you don't use this function before calling \ref run(),
379    ///it will allocate one. The destuctor deallocates this
380    ///automatically allocated map, of course.
381    ///\return <tt> (*this) </tt>
382    Dijkstra &distMap(DistMap &m)
383    {
384      if(local_distance) {
385        delete distance;
386        local_distance=false;
387      }
388      distance = &m;
389      return *this;
390    }
391   
392  ///Runs %Dijkstra algorithm from node \c s.
393
394  ///This method runs the %Dijkstra algorithm from a root node \c s
395  ///in order to
396  ///compute the
397  ///shortest path to each node. The algorithm computes
398  ///- The shortest path tree.
399  ///- The distance of each node from the root.
400  ///\todo heap_map's type could also be in the traits class.
401    void run(Node s) {
402     
403      init_maps();
404     
405      source = s;
406     
407      for ( NodeIt u(*G) ; u!=INVALID ; ++u ) {
408        _pred->set(u,INVALID);
409        pred_node->set(u,INVALID);
410        ///\todo *_reached is not set to false.
411      }
412     
413      typename Graph::template NodeMap<int> heap_map(*G,-1);
414     
415      Heap heap(heap_map);
416     
417      heap.push(s,0);
418     
419      while ( !heap.empty() ) {
420       
421        Node v=heap.top();
422        _reached->set(v,true);
423        Value oldvalue=heap[v];
424        heap.pop();
425        distance->set(v, oldvalue);
426       
427       
428        for(OutEdgeIt e(*G,v); e!=INVALID; ++e) {
429          Node w=G->target(e);
430          switch(heap.state(w)) {
431          case Heap::PRE_HEAP:
432            heap.push(w,oldvalue+(*length)[e]);
433            _pred->set(w,e);
434            pred_node->set(w,v);
435            break;
436          case Heap::IN_HEAP:
437            if ( oldvalue+(*length)[e] < heap[w] ) {
438              heap.decrease(w, oldvalue+(*length)[e]);
439              _pred->set(w,e);
440              pred_node->set(w,v);
441            }
442            break;
443          case Heap::POST_HEAP:
444            break;
445          }
446        }
447      }
448    }
449   
450    ///The distance of a node from the root.
451
452    ///Returns the distance of a node from the root.
453    ///\pre \ref run() must be called before using this function.
454    ///\warning If node \c v in unreachable from the root the return value
455    ///of this funcion is undefined.
456    Value dist(Node v) const { return (*distance)[v]; }
457
458    ///Returns the 'previous edge' of the shortest path tree.
459
460    ///For a node \c v it returns the 'previous edge' of the shortest path tree,
461    ///i.e. it returns the last edge of a shortest path from the root to \c
462    ///v. It is \ref INVALID
463    ///if \c v is unreachable from the root or if \c v=s. The
464    ///shortest path tree used here is equal to the shortest path tree used in
465    ///\ref predNode(Node v).  \pre \ref run() must be called before using
466    ///this function.
467    ///\todo predEdge could be a better name.
468    Edge pred(Node v) const { return (*_pred)[v]; }
469
470    ///Returns the 'previous node' of the shortest path tree.
471
472    ///For a node \c v it returns the 'previous node' of the shortest path tree,
473    ///i.e. it returns the last but one node from a shortest path from the
474    ///root to \c /v. It is INVALID if \c v is unreachable from the root or if
475    ///\c v=s. The shortest path tree used here is equal to the shortest path
476    ///tree used in \ref pred(Node v).  \pre \ref run() must be called before
477    ///using this function.
478    Node predNode(Node v) const { return (*pred_node)[v]; }
479   
480    ///Returns a reference to the NodeMap of distances.
481
482    ///Returns a reference to the NodeMap of distances. \pre \ref run() must
483    ///be called before using this function.
484    const DistMap &distMap() const { return *distance;}
485 
486    ///Returns a reference to the shortest path tree map.
487
488    ///Returns a reference to the NodeMap of the edges of the
489    ///shortest path tree.
490    ///\pre \ref run() must be called before using this function.
491    const PredMap &predMap() const { return *_pred;}
492 
493    ///Returns a reference to the map of nodes of shortest paths.
494
495    ///Returns a reference to the NodeMap of the last but one nodes of the
496    ///shortest path tree.
497    ///\pre \ref run() must be called before using this function.
498    const PredNodeMap &predNodeMap() const { return *pred_node;}
499
500    ///Checks if a node is reachable from the root.
501
502    ///Returns \c true if \c v is reachable from the root.
503    ///\note The root node is reported to be reached!
504    ///\pre \ref run() must be called before using this function.
505    ///
506    bool reached(Node v) { return v==source || (*_pred)[v]!=INVALID; }
507   
508  };
509
510  /// Default traits used by \ref DijkstraWizard
511
512  /// To make it easier to use Dijkstra algorithm we created a wizard class.
513  /// This \ref DijkstraWizard class also needs default traits.
514  /// The \ref DijkstraWizardBase is a class to be the default traits of the
515  /// \ref DijkstraWizard class.
516  template<class GR,class LM>
517  class DijkstraWizardBase : public DijkstraDefaultTraits<GR,LM>
518  {
519
520    typedef DijkstraDefaultTraits<GR,LM> Base;
521  protected:
522    /// Pointer to the underlying graph.
523    void *_g;
524    /// Pointer to the length map
525    void *_length;
526    ///Pointer to the map of predecessors edges.
527    void *_pred;
528    ///Pointer to the map of predecessors nodes.
529    void *_predNode;
530    ///Pointer to the map of distances.
531    void *_dist;
532    ///Pointer to the source node.
533    void *_source;
534
535    /// Type of the nodes in the graph.
536    typedef typename Base::Graph::Node Node;
537
538    public:
539    /// Constructor.
540   
541    /// This constructor does not require parameters, therefore it initiates
542    /// all of the attributes to default values (0, INVALID).
543    DijkstraWizardBase() : _g(0), _length(0), _pred(0), _predNode(0),
544                       _dist(0), _source(INVALID) {}
545
546    /// Constructor.
547   
548    /// This constructor requires some parameters, listed in the parameters list.
549    /// Others are initiated to 0.
550    /// \param g is the initial value of  \ref _g
551    /// \param l is the initial value of  \ref _length
552    /// \param s is the initial value of  \ref _source
553    DijkstraWizardBase(const GR &g,const LM &l, Node s=INVALID) :
554      _g((void *)&g), _length((void *)&l), _pred(0), _predNode(0),
555                  _dist(0), _source((void *)&s) {}
556
557  };
558 
559  /// A class to make easier the usage of Dijkstra algorithm
560
561  /// This class is created to make it easier to use Dijkstra algorithm.
562  /// It uses the functions and features of the plain \ref Dijkstra,
563  /// but it is much more simple to use it.
564  ///
565  /// Simplicity means that the way to change the types defined
566  /// in the traits class is based on functions that returns the new class
567  /// and not on templatable built-in classes. When using the plain \Dijkstra
568  /// the new class with the modified type comes from the original by using the ::
569  /// operator. In this case only a function have to be called and it will
570  /// return the needed class.
571  ///
572  /// It does not have own \ref run method. When its \ref run method is called
573  /// it initiates a plain \ref Dijkstra class, and calls the \ref Dijkstra::run
574  /// method of it.
575  template<class TR>
576  class DijkstraWizard : public TR
577  {
578    typedef TR Base;
579
580    ///The type of the underlying graph.
581    typedef typename TR::Graph Graph;
582    //\e
583    typedef typename Graph::Node Node;
584    //\e
585    typedef typename Graph::NodeIt NodeIt;
586    //\e
587    typedef typename Graph::Edge Edge;
588    //\e
589    typedef typename Graph::OutEdgeIt OutEdgeIt;
590   
591    ///The type of the map that stores the edge lengths.
592    typedef typename TR::LengthMap LengthMap;
593    ///The type of the length of the edges.
594    typedef typename LengthMap::Value Value;
595    ///\brief The type of the map that stores the last
596    ///edges of the shortest paths.
597    typedef typename TR::PredMap PredMap;
598    ///\brief The type of the map that stores the last but one
599    ///nodes of the shortest paths.
600    typedef typename TR::PredNodeMap PredNodeMap;
601    ///The type of the map that stores the dists of the nodes.
602    typedef typename TR::DistMap DistMap;
603
604    ///The heap type used by the dijkstra algorithm.
605    typedef typename TR::Heap Heap;
606public:
607    /// Constructor.
608    DijkstraWizard() : TR() {}
609
610    /// Constructor that requires parameters.
611    /// These parameters will be the default values for the traits class.
612    DijkstraWizard(const Graph &g,const LengthMap &l, Node s=INVALID) :
613      TR(g,l,s) {}
614
615    ///Copy constructor
616    DijkstraWizard(const TR &b) : TR(b) {}
617
618    ~DijkstraWizard() {}
619
620    ///Runs Dijkstra algorithm from a given node.
621   
622    ///Runs Dijkstra algorithm from a given node.
623    ///The node can be given by the \ref source function.
624    void run()
625    {
626      if(_source==0) throw UninitializedData();
627      Dijkstra<Graph,LengthMap,TR> Dij(*(Graph*)_g,*(LengthMap*)_length);
628      if(_pred) Dij.predMap(*(PredMap*)_pred);
629      if(_predNode) Dij.predNodeMap(*(PredNodeMap*)_predNode);
630      if(_dist) Dij.distMap(*(DistMap*)_dist);
631      Dij.run(*(Node*)_source);
632    }
633
634    ///Runs Dijkstra algorithm from a given node.
635
636    ///Runs Dijkstra algorithm from a given node.
637    ///\param s is the given source.
638    void run(Node s)
639    {
640      _source=(void *)&s;
641      run();
642    }
643
644    template<class T>
645    struct DefPredMapBase : public Base {
646      typedef T PredMap;
647      static PredMap *createPredMap(const Graph &G) { return 0; };
648      DefPredMapBase(const Base &b) : Base(b) {}
649    };
650   
651    /// \ref named-templ-param "Named parameter" function for setting PredMap type
652
653    /// \ref named-templ-param "Named parameter" function for setting PredMap type
654    template<class T>
655    DijkstraWizard<DefPredMapBase<T> > predMap(const T &t)
656    {
657      _pred=(void *)&t;
658      return DijkstraWizard<DefPredMapBase<T> >(*this);
659    }
660   
661
662    template<class T>
663    struct DefPredNodeMapBase : public Base {
664      typedef T PredNodeMap;
665      static PredNodeMap *createPredNodeMap(const Graph &G) { return 0; };
666      DefPredNodeMapBase(const Base &b) : Base(b) {}
667    };
668   
669    /// \ref named-templ-param "Named parameter" function for setting PredNodeMap type
670
671    /// \ref named-templ-param "Named parameter" function for setting PredNodeMap type
672    template<class T>
673    DijkstraWizard<DefPredNodeMapBase<T> > predNodeMap(const T &t)
674    {
675      _predNode=(void *)&t;
676      return DijkstraWizard<DefPredNodeMapBase<T> >(*this);
677    }
678   
679    template<class T>
680    struct DefDistMapBase : public Base {
681      typedef T DistMap;
682      static DistMap *createDistMap(const Graph &G) { return 0; };
683      DefDistMapBase(const Base &b) : Base(b) {}
684    };
685   
686    /// \ref named-templ-param "Named parameter" function for setting DistMap type
687
688    /// \ref named-templ-param "Named parameter" function for setting DistMap type
689    template<class T>
690    DijkstraWizard<DefDistMapBase<T> > distMap(const T &t)
691    {
692      _dist=(void *)&t;
693      return DijkstraWizard<DefDistMapBase<T> >(*this);
694    }
695   
696    /// Sets the source node, from which the Dijkstra algorithm runs.
697
698    /// Sets the source node, from which the Dijkstra algorithm runs.
699    /// \param s is the source node.
700    DijkstraWizard<TR> &source(Node s)
701    {
702      source=(void *)&s;
703      return *this;
704    }
705   
706  };
707 
708  ///\e
709
710  ///\todo Please document...
711  ///
712  template<class GR, class LM>
713  DijkstraWizard<DijkstraWizardBase<GR,LM> >
714  dijkstra(const GR &g,const LM &l,typename GR::Node s=INVALID)
715  {
716    return DijkstraWizard<DijkstraWizardBase<GR,LM> >(g,l,s);
717  }
718
719/// @}
720 
721} //END OF NAMESPACE LEMON
722
723#endif
724
Note: See TracBrowser for help on using the repository browser.