COIN-OR::LEMON - Graph Library

source: lemon-0.x/src/work/alpar/dijkstra.h @ 1124:12623f7ecb37

Last change on this file since 1124:12623f7ecb37 was 1124:12623f7ecb37, checked in by Hegyi Péter, 15 years ago

Dijkstra documentation is getting ready, but one decision is missing about naming conventions about named_params

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