COIN-OR::LEMON - Graph Library

source: lemon/lemon/dijkstra.h @ 598:9d0d7e20f76d

Last change on this file since 598:9d0d7e20f76d was 525:9605e051942f, checked in by Peter Kovacs <kpeter@…>, 15 years ago

Various doc improvements

File size: 42.5 KB
RevLine 
[209]1/* -*- mode: C++; indent-tabs-mode: nil; -*-
[100]2 *
[209]3 * This file is a part of LEMON, a generic C++ optimization library.
[100]4 *
[463]5 * Copyright (C) 2003-2009
[100]6 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
7 * (Egervary Research Group on Combinatorial Optimization, EGRES).
8 *
9 * Permission to use, modify and distribute this software is granted
10 * provided that this copyright notice appears in all copies. For
11 * precise terms see the accompanying LICENSE file.
12 *
13 * This software is provided "AS IS" with no warranty of any kind,
14 * express or implied, and with no claim as to its suitability for any
15 * purpose.
16 *
17 */
18
19#ifndef LEMON_DIJKSTRA_H
20#define LEMON_DIJKSTRA_H
21
22///\ingroup shortest_path
23///\file
24///\brief Dijkstra algorithm.
25
[184]26#include <limits>
[169]27#include <lemon/list_graph.h>
[100]28#include <lemon/bin_heap.h>
29#include <lemon/bits/path_dump.h>
[220]30#include <lemon/core.h>
[100]31#include <lemon/error.h>
32#include <lemon/maps.h>
[278]33#include <lemon/path.h>
[100]34
35namespace lemon {
36
[244]37  /// \brief Default operation traits for the Dijkstra algorithm class.
[209]38  ///
[244]39  /// This operation traits class defines all computational operations and
40  /// constants which are used in the Dijkstra algorithm.
[100]41  template <typename Value>
42  struct DijkstraDefaultOperationTraits {
43    /// \brief Gives back the zero value of the type.
44    static Value zero() {
45      return static_cast<Value>(0);
46    }
47    /// \brief Gives back the sum of the given two elements.
48    static Value plus(const Value& left, const Value& right) {
49      return left + right;
50    }
[244]51    /// \brief Gives back true only if the first value is less than the second.
[100]52    static bool less(const Value& left, const Value& right) {
53      return left < right;
54    }
55  };
56
57  ///Default traits class of Dijkstra class.
58
59  ///Default traits class of Dijkstra class.
[244]60  ///\tparam GR The type of the digraph.
61  ///\tparam LM The type of the length map.
[100]62  template<class GR, class LM>
63  struct DijkstraDefaultTraits
64  {
[244]65    ///The type of the digraph the algorithm runs on.
[100]66    typedef GR Digraph;
[244]67
[100]68    ///The type of the map that stores the arc lengths.
69
70    ///The type of the map that stores the arc lengths.
71    ///It must meet the \ref concepts::ReadMap "ReadMap" concept.
72    typedef LM LengthMap;
[244]73    ///The type of the length of the arcs.
[100]74    typedef typename LM::Value Value;
[244]75
[525]76    /// Operation traits for %Dijkstra algorithm.
[100]77
[244]78    /// This class defines the operations that are used in the algorithm.
[100]79    /// \see DijkstraDefaultOperationTraits
80    typedef DijkstraDefaultOperationTraits<Value> OperationTraits;
81
[244]82    /// The cross reference type used by the heap.
[100]83
[244]84    /// The cross reference type used by the heap.
[100]85    /// Usually it is \c Digraph::NodeMap<int>.
86    typedef typename Digraph::template NodeMap<int> HeapCrossRef;
[525]87    ///Instantiates a \c HeapCrossRef.
[100]88
[244]89    ///This function instantiates a \ref HeapCrossRef.
90    /// \param g is the digraph, to which we would like to define the
91    /// \ref HeapCrossRef.
92    static HeapCrossRef *createHeapCrossRef(const Digraph &g)
[100]93    {
[244]94      return new HeapCrossRef(g);
[100]95    }
[209]96
[525]97    ///The heap type used by the %Dijkstra algorithm.
[100]98
[244]99    ///The heap type used by the Dijkstra algorithm.
[100]100    ///
101    ///\sa BinHeap
102    ///\sa Dijkstra
103    typedef BinHeap<typename LM::Value, HeapCrossRef, std::less<Value> > Heap;
[525]104    ///Instantiates a \c Heap.
[100]105
[244]106    ///This function instantiates a \ref Heap.
107    static Heap *createHeap(HeapCrossRef& r)
[100]108    {
[244]109      return new Heap(r);
[100]110    }
111
[244]112    ///\brief The type of the map that stores the predecessor
[100]113    ///arcs of the shortest paths.
[209]114    ///
[244]115    ///The type of the map that stores the predecessor
[100]116    ///arcs of the shortest paths.
117    ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
[244]118    typedef typename Digraph::template NodeMap<typename Digraph::Arc> PredMap;
[525]119    ///Instantiates a \c PredMap.
[209]120
[525]121    ///This function instantiates a \ref PredMap.
[244]122    ///\param g is the digraph, to which we would like to define the
[525]123    ///\ref PredMap.
[244]124    static PredMap *createPredMap(const Digraph &g)
[100]125    {
[244]126      return new PredMap(g);
[100]127    }
128
[244]129    ///The type of the map that indicates which nodes are processed.
[209]130
[244]131    ///The type of the map that indicates which nodes are processed.
[100]132    ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
133    ///By default it is a NullMap.
134    typedef NullMap<typename Digraph::Node,bool> ProcessedMap;
[525]135    ///Instantiates a \c ProcessedMap.
[209]136
[525]137    ///This function instantiates a \ref ProcessedMap.
[100]138    ///\param g is the digraph, to which
[525]139    ///we would like to define the \ref ProcessedMap.
[100]140#ifdef DOXYGEN
[244]141    static ProcessedMap *createProcessedMap(const Digraph &g)
[100]142#else
[244]143    static ProcessedMap *createProcessedMap(const Digraph &)
[100]144#endif
145    {
146      return new ProcessedMap();
147    }
[209]148
[244]149    ///The type of the map that stores the distances of the nodes.
150
151    ///The type of the map that stores the distances of the nodes.
[100]152    ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
153    typedef typename Digraph::template NodeMap<typename LM::Value> DistMap;
[525]154    ///Instantiates a \c DistMap.
[209]155
[525]156    ///This function instantiates a \ref DistMap.
[244]157    ///\param g is the digraph, to which we would like to define
[525]158    ///the \ref DistMap.
[244]159    static DistMap *createDistMap(const Digraph &g)
[100]160    {
[244]161      return new DistMap(g);
[100]162    }
163  };
[209]164
[100]165  ///%Dijkstra algorithm class.
[209]166
[100]167  /// \ingroup shortest_path
[244]168  ///This class provides an efficient implementation of the %Dijkstra algorithm.
169  ///
[100]170  ///The arc lengths are passed to the algorithm using a
171  ///\ref concepts::ReadMap "ReadMap",
172  ///so it is easy to change it to any kind of length.
173  ///The type of the length is determined by the
174  ///\ref concepts::ReadMap::Value "Value" of the length map.
175  ///It is also possible to change the underlying priority heap.
176  ///
[278]177  ///There is also a \ref dijkstra() "function-type interface" for the
[244]178  ///%Dijkstra algorithm, which is convenient in the simplier cases and
179  ///it can be used easier.
180  ///
181  ///\tparam GR The type of the digraph the algorithm runs on.
[421]182  ///The default type is \ref ListDigraph.
183  ///\tparam LM A \ref concepts::ReadMap "readable" arc map that specifies
184  ///the lengths of the arcs.
185  ///It is read once for each arc, so the map may involve in
[244]186  ///relatively time consuming process to compute the arc lengths if
[100]187  ///it is necessary. The default map type is \ref
[421]188  ///concepts::Digraph::ArcMap "GR::ArcMap<int>".
[100]189#ifdef DOXYGEN
190  template <typename GR, typename LM, typename TR>
191#else
192  template <typename GR=ListDigraph,
[209]193            typename LM=typename GR::template ArcMap<int>,
194            typename TR=DijkstraDefaultTraits<GR,LM> >
[100]195#endif
196  class Dijkstra {
197  public:
198
[244]199    ///The type of the digraph the algorithm runs on.
[100]200    typedef typename TR::Digraph Digraph;
[209]201
[100]202    ///The type of the length of the arcs.
203    typedef typename TR::LengthMap::Value Value;
204    ///The type of the map that stores the arc lengths.
205    typedef typename TR::LengthMap LengthMap;
[244]206    ///\brief The type of the map that stores the predecessor arcs of the
207    ///shortest paths.
[100]208    typedef typename TR::PredMap PredMap;
[244]209    ///The type of the map that stores the distances of the nodes.
210    typedef typename TR::DistMap DistMap;
211    ///The type of the map that indicates which nodes are processed.
[100]212    typedef typename TR::ProcessedMap ProcessedMap;
[244]213    ///The type of the paths.
214    typedef PredMapPath<Digraph, PredMap> Path;
[100]215    ///The cross reference type used for the current heap.
216    typedef typename TR::HeapCrossRef HeapCrossRef;
[244]217    ///The heap type used by the algorithm.
[100]218    typedef typename TR::Heap Heap;
[525]219    ///\brief The \ref DijkstraDefaultOperationTraits "operation traits class"
220    ///of the algorithm.
[100]221    typedef typename TR::OperationTraits OperationTraits;
[244]222
[421]223    ///The \ref DijkstraDefaultTraits "traits class" of the algorithm.
[244]224    typedef TR Traits;
225
[100]226  private:
[244]227
228    typedef typename Digraph::Node Node;
229    typedef typename Digraph::NodeIt NodeIt;
230    typedef typename Digraph::Arc Arc;
231    typedef typename Digraph::OutArcIt OutArcIt;
232
233    //Pointer to the underlying digraph.
[100]234    const Digraph *G;
[244]235    //Pointer to the length map.
[525]236    const LengthMap *_length;
[244]237    //Pointer to the map of predecessors arcs.
[100]238    PredMap *_pred;
[244]239    //Indicates if _pred is locally allocated (true) or not.
[100]240    bool local_pred;
[244]241    //Pointer to the map of distances.
[100]242    DistMap *_dist;
[244]243    //Indicates if _dist is locally allocated (true) or not.
[100]244    bool local_dist;
[244]245    //Pointer to the map of processed status of the nodes.
[100]246    ProcessedMap *_processed;
[244]247    //Indicates if _processed is locally allocated (true) or not.
[100]248    bool local_processed;
[244]249    //Pointer to the heap cross references.
[100]250    HeapCrossRef *_heap_cross_ref;
[244]251    //Indicates if _heap_cross_ref is locally allocated (true) or not.
[100]252    bool local_heap_cross_ref;
[244]253    //Pointer to the heap.
[100]254    Heap *_heap;
[244]255    //Indicates if _heap is locally allocated (true) or not.
[100]256    bool local_heap;
257
[280]258    //Creates the maps if necessary.
[209]259    void create_maps()
[100]260    {
261      if(!_pred) {
[209]262        local_pred = true;
263        _pred = Traits::createPredMap(*G);
[100]264      }
265      if(!_dist) {
[209]266        local_dist = true;
267        _dist = Traits::createDistMap(*G);
[100]268      }
269      if(!_processed) {
[209]270        local_processed = true;
271        _processed = Traits::createProcessedMap(*G);
[100]272      }
273      if (!_heap_cross_ref) {
[209]274        local_heap_cross_ref = true;
275        _heap_cross_ref = Traits::createHeapCrossRef(*G);
[100]276      }
277      if (!_heap) {
[209]278        local_heap = true;
279        _heap = Traits::createHeap(*_heap_cross_ref);
[100]280      }
281    }
[209]282
[244]283  public:
[100]284
285    typedef Dijkstra Create;
[209]286
[100]287    ///\name Named template parameters
288
289    ///@{
290
291    template <class T>
[257]292    struct SetPredMapTraits : public Traits {
[100]293      typedef T PredMap;
294      static PredMap *createPredMap(const Digraph &)
295      {
[290]296        LEMON_ASSERT(false, "PredMap is not initialized");
297        return 0; // ignore warnings
[100]298      }
299    };
[244]300    ///\brief \ref named-templ-param "Named parameter" for setting
[525]301    ///\c PredMap type.
[100]302    ///
[244]303    ///\ref named-templ-param "Named parameter" for setting
[525]304    ///\c PredMap type.
[421]305    ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
[100]306    template <class T>
[257]307    struct SetPredMap
308      : public Dijkstra< Digraph, LengthMap, SetPredMapTraits<T> > {
309      typedef Dijkstra< Digraph, LengthMap, SetPredMapTraits<T> > Create;
[100]310    };
[209]311
[100]312    template <class T>
[257]313    struct SetDistMapTraits : public Traits {
[100]314      typedef T DistMap;
315      static DistMap *createDistMap(const Digraph &)
316      {
[290]317        LEMON_ASSERT(false, "DistMap is not initialized");
318        return 0; // ignore warnings
[100]319      }
320    };
[244]321    ///\brief \ref named-templ-param "Named parameter" for setting
[525]322    ///\c DistMap type.
[100]323    ///
[244]324    ///\ref named-templ-param "Named parameter" for setting
[525]325    ///\c DistMap type.
[421]326    ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
[100]327    template <class T>
[257]328    struct SetDistMap
329      : public Dijkstra< Digraph, LengthMap, SetDistMapTraits<T> > {
330      typedef Dijkstra< Digraph, LengthMap, SetDistMapTraits<T> > Create;
[100]331    };
[209]332
[100]333    template <class T>
[257]334    struct SetProcessedMapTraits : public Traits {
[100]335      typedef T ProcessedMap;
[244]336      static ProcessedMap *createProcessedMap(const Digraph &)
[100]337      {
[290]338        LEMON_ASSERT(false, "ProcessedMap is not initialized");
339        return 0; // ignore warnings
[100]340      }
341    };
[244]342    ///\brief \ref named-templ-param "Named parameter" for setting
[525]343    ///\c ProcessedMap type.
[100]344    ///
[244]345    ///\ref named-templ-param "Named parameter" for setting
[525]346    ///\c ProcessedMap type.
[421]347    ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
[100]348    template <class T>
[257]349    struct SetProcessedMap
350      : public Dijkstra< Digraph, LengthMap, SetProcessedMapTraits<T> > {
351      typedef Dijkstra< Digraph, LengthMap, SetProcessedMapTraits<T> > Create;
[100]352    };
[209]353
[257]354    struct SetStandardProcessedMapTraits : public Traits {
[100]355      typedef typename Digraph::template NodeMap<bool> ProcessedMap;
[244]356      static ProcessedMap *createProcessedMap(const Digraph &g)
[100]357      {
[244]358        return new ProcessedMap(g);
[100]359      }
360    };
[244]361    ///\brief \ref named-templ-param "Named parameter" for setting
[525]362    ///\c ProcessedMap type to be <tt>Digraph::NodeMap<bool></tt>.
[100]363    ///
[244]364    ///\ref named-templ-param "Named parameter" for setting
[525]365    ///\c ProcessedMap type to be <tt>Digraph::NodeMap<bool></tt>.
[244]366    ///If you don't set it explicitly, it will be automatically allocated.
[257]367    struct SetStandardProcessedMap
368      : public Dijkstra< Digraph, LengthMap, SetStandardProcessedMapTraits > {
369      typedef Dijkstra< Digraph, LengthMap, SetStandardProcessedMapTraits >
[210]370      Create;
[100]371    };
372
373    template <class H, class CR>
[257]374    struct SetHeapTraits : public Traits {
[100]375      typedef CR HeapCrossRef;
376      typedef H Heap;
377      static HeapCrossRef *createHeapCrossRef(const Digraph &) {
[290]378        LEMON_ASSERT(false, "HeapCrossRef is not initialized");
379        return 0; // ignore warnings
[100]380      }
[209]381      static Heap *createHeap(HeapCrossRef &)
[100]382      {
[290]383        LEMON_ASSERT(false, "Heap is not initialized");
384        return 0; // ignore warnings
[100]385      }
386    };
387    ///\brief \ref named-templ-param "Named parameter" for setting
[421]388    ///heap and cross reference types
[100]389    ///
[209]390    ///\ref named-templ-param "Named parameter" for setting heap and cross
[421]391    ///reference types. If this named parameter is used, then external
392    ///heap and cross reference objects must be passed to the algorithm
393    ///using the \ref heap() function before calling \ref run(Node) "run()"
394    ///or \ref init().
395    ///\sa SetStandardHeap
[100]396    template <class H, class CR = typename Digraph::template NodeMap<int> >
[257]397    struct SetHeap
398      : public Dijkstra< Digraph, LengthMap, SetHeapTraits<H, CR> > {
399      typedef Dijkstra< Digraph, LengthMap, SetHeapTraits<H, CR> > Create;
[100]400    };
401
402    template <class H, class CR>
[257]403    struct SetStandardHeapTraits : public Traits {
[100]404      typedef CR HeapCrossRef;
405      typedef H Heap;
406      static HeapCrossRef *createHeapCrossRef(const Digraph &G) {
[209]407        return new HeapCrossRef(G);
[100]408      }
[209]409      static Heap *createHeap(HeapCrossRef &R)
[100]410      {
[209]411        return new Heap(R);
[100]412      }
413    };
414    ///\brief \ref named-templ-param "Named parameter" for setting
[421]415    ///heap and cross reference types with automatic allocation
[100]416    ///
[209]417    ///\ref named-templ-param "Named parameter" for setting heap and cross
[421]418    ///reference types with automatic allocation.
419    ///They should have standard constructor interfaces to be able to
420    ///automatically created by the algorithm (i.e. the digraph should be
421    ///passed to the constructor of the cross reference and the cross
422    ///reference should be passed to the constructor of the heap).
423    ///However external heap and cross reference objects could also be
424    ///passed to the algorithm using the \ref heap() function before
425    ///calling \ref run(Node) "run()" or \ref init().
426    ///\sa SetHeap
[100]427    template <class H, class CR = typename Digraph::template NodeMap<int> >
[257]428    struct SetStandardHeap
429      : public Dijkstra< Digraph, LengthMap, SetStandardHeapTraits<H, CR> > {
430      typedef Dijkstra< Digraph, LengthMap, SetStandardHeapTraits<H, CR> >
[100]431      Create;
432    };
433
434    template <class T>
[257]435    struct SetOperationTraitsTraits : public Traits {
[100]436      typedef T OperationTraits;
437    };
[209]438
439    /// \brief \ref named-templ-param "Named parameter" for setting
[313]440    ///\c OperationTraits type
[100]441    ///
[244]442    ///\ref named-templ-param "Named parameter" for setting
[525]443    ///\c OperationTraits type.
[100]444    template <class T>
[257]445    struct SetOperationTraits
446      : public Dijkstra<Digraph, LengthMap, SetOperationTraitsTraits<T> > {
447      typedef Dijkstra<Digraph, LengthMap, SetOperationTraitsTraits<T> >
[100]448      Create;
449    };
[209]450
[100]451    ///@}
452
453  protected:
454
455    Dijkstra() {}
456
[209]457  public:
458
[100]459    ///Constructor.
[209]460
[244]461    ///Constructor.
[525]462    ///\param g The digraph the algorithm runs on.
463    ///\param length The length map used by the algorithm.
464    Dijkstra(const Digraph& g, const LengthMap& length) :
465      G(&g), _length(&length),
[100]466      _pred(NULL), local_pred(false),
467      _dist(NULL), local_dist(false),
468      _processed(NULL), local_processed(false),
469      _heap_cross_ref(NULL), local_heap_cross_ref(false),
470      _heap(NULL), local_heap(false)
471    { }
[209]472
[100]473    ///Destructor.
[209]474    ~Dijkstra()
[100]475    {
476      if(local_pred) delete _pred;
477      if(local_dist) delete _dist;
478      if(local_processed) delete _processed;
479      if(local_heap_cross_ref) delete _heap_cross_ref;
480      if(local_heap) delete _heap;
481    }
482
483    ///Sets the length map.
484
485    ///Sets the length map.
486    ///\return <tt> (*this) </tt>
[209]487    Dijkstra &lengthMap(const LengthMap &m)
[100]488    {
[525]489      _length = &m;
[100]490      return *this;
491    }
492
[244]493    ///Sets the map that stores the predecessor arcs.
[100]494
[244]495    ///Sets the map that stores the predecessor arcs.
[421]496    ///If you don't use this function before calling \ref run(Node) "run()"
497    ///or \ref init(), an instance will be allocated automatically.
498    ///The destructor deallocates this automatically allocated map,
499    ///of course.
[100]500    ///\return <tt> (*this) </tt>
[209]501    Dijkstra &predMap(PredMap &m)
[100]502    {
503      if(local_pred) {
[209]504        delete _pred;
505        local_pred=false;
[100]506      }
507      _pred = &m;
508      return *this;
509    }
510
[244]511    ///Sets the map that indicates which nodes are processed.
[100]512
[244]513    ///Sets the map that indicates which nodes are processed.
[421]514    ///If you don't use this function before calling \ref run(Node) "run()"
515    ///or \ref init(), an instance will be allocated automatically.
516    ///The destructor deallocates this automatically allocated map,
517    ///of course.
[244]518    ///\return <tt> (*this) </tt>
519    Dijkstra &processedMap(ProcessedMap &m)
520    {
521      if(local_processed) {
522        delete _processed;
523        local_processed=false;
524      }
525      _processed = &m;
526      return *this;
527    }
528
529    ///Sets the map that stores the distances of the nodes.
530
531    ///Sets the map that stores the distances of the nodes calculated by the
532    ///algorithm.
[421]533    ///If you don't use this function before calling \ref run(Node) "run()"
534    ///or \ref init(), an instance will be allocated automatically.
535    ///The destructor deallocates this automatically allocated map,
536    ///of course.
[100]537    ///\return <tt> (*this) </tt>
[209]538    Dijkstra &distMap(DistMap &m)
[100]539    {
540      if(local_dist) {
[209]541        delete _dist;
542        local_dist=false;
[100]543      }
544      _dist = &m;
545      return *this;
546    }
547
548    ///Sets the heap and the cross reference used by algorithm.
549
550    ///Sets the heap and the cross reference used by algorithm.
[421]551    ///If you don't use this function before calling \ref run(Node) "run()"
552    ///or \ref init(), heap and cross reference instances will be
553    ///allocated automatically.
554    ///The destructor deallocates these automatically allocated objects,
555    ///of course.
[100]556    ///\return <tt> (*this) </tt>
557    Dijkstra &heap(Heap& hp, HeapCrossRef &cr)
558    {
559      if(local_heap_cross_ref) {
[209]560        delete _heap_cross_ref;
561        local_heap_cross_ref=false;
[100]562      }
563      _heap_cross_ref = &cr;
564      if(local_heap) {
[209]565        delete _heap;
566        local_heap=false;
[100]567      }
568      _heap = &hp;
569      return *this;
570    }
571
572  private:
[244]573
[100]574    void finalizeNodeData(Node v,Value dst)
575    {
576      _processed->set(v,true);
577      _dist->set(v, dst);
578    }
579
580  public:
581
[421]582    ///\name Execution Control
583    ///The simplest way to execute the %Dijkstra algorithm is to use
584    ///one of the member functions called \ref run(Node) "run()".\n
585    ///If you need more control on the execution, first you have to call
586    ///\ref init(), then you can add several source nodes with
587    ///\ref addSource(). Finally the actual path computation can be
588    ///performed with one of the \ref start() functions.
[100]589
590    ///@{
591
[421]592    ///\brief Initializes the internal data structures.
593    ///
[100]594    ///Initializes the internal data structures.
595    void init()
596    {
597      create_maps();
598      _heap->clear();
599      for ( NodeIt u(*G) ; u!=INVALID ; ++u ) {
[209]600        _pred->set(u,INVALID);
601        _processed->set(u,false);
602        _heap_cross_ref->set(u,Heap::PRE_HEAP);
[100]603      }
604    }
[209]605
[100]606    ///Adds a new source node.
607
608    ///Adds a new source node to the priority heap.
609    ///The optional second parameter is the initial distance of the node.
610    ///
[244]611    ///The function checks if the node has already been added to the heap and
[100]612    ///it is pushed to the heap only if either it was not in the heap
613    ///or the shortest path found till then is shorter than \c dst.
614    void addSource(Node s,Value dst=OperationTraits::zero())
615    {
616      if(_heap->state(s) != Heap::IN_HEAP) {
[209]617        _heap->push(s,dst);
[100]618      } else if(OperationTraits::less((*_heap)[s], dst)) {
[209]619        _heap->set(s,dst);
620        _pred->set(s,INVALID);
[100]621      }
622    }
[209]623
[100]624    ///Processes the next node in the priority heap
625
626    ///Processes the next node in the priority heap.
627    ///
628    ///\return The processed node.
629    ///
[244]630    ///\warning The priority heap must not be empty.
[100]631    Node processNextNode()
632    {
[209]633      Node v=_heap->top();
[100]634      Value oldvalue=_heap->prio();
635      _heap->pop();
636      finalizeNodeData(v,oldvalue);
[209]637
[100]638      for(OutArcIt e(*G,v); e!=INVALID; ++e) {
[209]639        Node w=G->target(e);
640        switch(_heap->state(w)) {
641        case Heap::PRE_HEAP:
[525]642          _heap->push(w,OperationTraits::plus(oldvalue, (*_length)[e]));
[209]643          _pred->set(w,e);
644          break;
645        case Heap::IN_HEAP:
646          {
[525]647            Value newvalue = OperationTraits::plus(oldvalue, (*_length)[e]);
[209]648            if ( OperationTraits::less(newvalue, (*_heap)[w]) ) {
649              _heap->decrease(w, newvalue);
650              _pred->set(w,e);
651            }
652          }
653          break;
654        case Heap::POST_HEAP:
655          break;
656        }
[100]657      }
658      return v;
659    }
660
[244]661    ///The next node to be processed.
[209]662
[244]663    ///Returns the next node to be processed or \c INVALID if the
664    ///priority heap is empty.
665    Node nextNode() const
[209]666    {
[100]667      return !_heap->empty()?_heap->top():INVALID;
668    }
[209]669
[421]670    ///Returns \c false if there are nodes to be processed.
671
672    ///Returns \c false if there are nodes to be processed
673    ///in the priority heap.
[244]674    bool emptyQueue() const { return _heap->empty(); }
675
[421]676    ///Returns the number of the nodes to be processed.
[100]677
[421]678    ///Returns the number of the nodes to be processed
679    ///in the priority heap.
[244]680    int queueSize() const { return _heap->size(); }
[209]681
[100]682    ///Executes the algorithm.
683
684    ///Executes the algorithm.
685    ///
[244]686    ///This method runs the %Dijkstra algorithm from the root node(s)
687    ///in order to compute the shortest path to each node.
688    ///
689    ///The algorithm computes
690    ///- the shortest path tree (forest),
691    ///- the distance of each node from the root(s).
692    ///
693    ///\pre init() must be called and at least one root node should be
694    ///added with addSource() before using this function.
695    ///
696    ///\note <tt>d.start()</tt> is just a shortcut of the following code.
697    ///\code
698    ///  while ( !d.emptyQueue() ) {
699    ///    d.processNextNode();
700    ///  }
701    ///\endcode
702    void start()
703    {
704      while ( !emptyQueue() ) processNextNode();
705    }
706
[286]707    ///Executes the algorithm until the given target node is processed.
[244]708
[286]709    ///Executes the algorithm until the given target node is processed.
[100]710    ///
711    ///This method runs the %Dijkstra algorithm from the root node(s)
[286]712    ///in order to compute the shortest path to \c t.
[100]713    ///
[244]714    ///The algorithm computes
[286]715    ///- the shortest path to \c t,
716    ///- the distance of \c t from the root(s).
[100]717    ///
[244]718    ///\pre init() must be called and at least one root node should be
719    ///added with addSource() before using this function.
[286]720    void start(Node t)
[100]721    {
[286]722      while ( !_heap->empty() && _heap->top()!=t ) processNextNode();
723      if ( !_heap->empty() ) {
724        finalizeNodeData(_heap->top(),_heap->prio());
725        _heap->pop();
726      }
[100]727    }
[209]728
[100]729    ///Executes the algorithm until a condition is met.
730
731    ///Executes the algorithm until a condition is met.
732    ///
[244]733    ///This method runs the %Dijkstra algorithm from the root node(s) in
734    ///order to compute the shortest path to a node \c v with
735    /// <tt>nm[v]</tt> true, if such a node can be found.
[100]736    ///
[244]737    ///\param nm A \c bool (or convertible) node map. The algorithm
[100]738    ///will stop when it reaches a node \c v with <tt>nm[v]</tt> true.
739    ///
740    ///\return The reached node \c v with <tt>nm[v]</tt> true or
741    ///\c INVALID if no such node was found.
[244]742    ///
743    ///\pre init() must be called and at least one root node should be
744    ///added with addSource() before using this function.
[100]745    template<class NodeBoolMap>
746    Node start(const NodeBoolMap &nm)
747    {
748      while ( !_heap->empty() && !nm[_heap->top()] ) processNextNode();
749      if ( _heap->empty() ) return INVALID;
750      finalizeNodeData(_heap->top(),_heap->prio());
751      return _heap->top();
752    }
[209]753
[286]754    ///Runs the algorithm from the given source node.
[209]755
[244]756    ///This method runs the %Dijkstra algorithm from node \c s
757    ///in order to compute the shortest path to each node.
[100]758    ///
[244]759    ///The algorithm computes
760    ///- the shortest path tree,
761    ///- the distance of each node from the root.
762    ///
763    ///\note <tt>d.run(s)</tt> is just a shortcut of the following code.
[100]764    ///\code
765    ///  d.init();
766    ///  d.addSource(s);
767    ///  d.start();
768    ///\endcode
769    void run(Node s) {
770      init();
771      addSource(s);
772      start();
773    }
[209]774
[100]775    ///Finds the shortest path between \c s and \c t.
[209]776
[244]777    ///This method runs the %Dijkstra algorithm from node \c s
[286]778    ///in order to compute the shortest path to node \c t
779    ///(it stops searching when \c t is processed).
[100]780    ///
[286]781    ///\return \c true if \c t is reachable form \c s.
[244]782    ///
783    ///\note Apart from the return value, <tt>d.run(s,t)</tt> is just a
784    ///shortcut of the following code.
[100]785    ///\code
786    ///  d.init();
787    ///  d.addSource(s);
788    ///  d.start(t);
789    ///\endcode
[286]790    bool run(Node s,Node t) {
[100]791      init();
792      addSource(s);
793      start(t);
[286]794      return (*_heap_cross_ref)[t] == Heap::POST_HEAP;
[100]795    }
[209]796
[100]797    ///@}
798
799    ///\name Query Functions
[421]800    ///The results of the %Dijkstra algorithm can be obtained using these
[100]801    ///functions.\n
[421]802    ///Either \ref run(Node) "run()" or \ref start() should be called
803    ///before using them.
[209]804
[100]805    ///@{
806
[244]807    ///The shortest path to a node.
[209]808
[244]809    ///Returns the shortest path to a node.
810    ///
[421]811    ///\warning \c t should be reached from the root(s).
[244]812    ///
[421]813    ///\pre Either \ref run(Node) "run()" or \ref init()
814    ///must be called before using this function.
[244]815    Path path(Node t) const { return Path(*G, *_pred, t); }
[100]816
[244]817    ///The distance of a node from the root(s).
[100]818
[244]819    ///Returns the distance of a node from the root(s).
820    ///
[421]821    ///\warning If node \c v is not reached from the root(s), then
[244]822    ///the return value of this function is undefined.
823    ///
[421]824    ///\pre Either \ref run(Node) "run()" or \ref init()
825    ///must be called before using this function.
[100]826    Value dist(Node v) const { return (*_dist)[v]; }
827
[244]828    ///Returns the 'previous arc' of the shortest path tree for a node.
[100]829
[244]830    ///This function returns the 'previous arc' of the shortest path
831    ///tree for the node \c v, i.e. it returns the last arc of a
[421]832    ///shortest path from a root to \c v. It is \c INVALID if \c v
833    ///is not reached from the root(s) or if \c v is a root.
[244]834    ///
835    ///The shortest path tree used here is equal to the shortest path
836    ///tree used in \ref predNode().
837    ///
[421]838    ///\pre Either \ref run(Node) "run()" or \ref init()
839    ///must be called before using this function.
[100]840    Arc predArc(Node v) const { return (*_pred)[v]; }
841
[244]842    ///Returns the 'previous node' of the shortest path tree for a node.
[100]843
[244]844    ///This function returns the 'previous node' of the shortest path
845    ///tree for the node \c v, i.e. it returns the last but one node
[421]846    ///from a shortest path from a root to \c v. It is \c INVALID
847    ///if \c v is not reached from the root(s) or if \c v is a root.
[244]848    ///
849    ///The shortest path tree used here is equal to the shortest path
850    ///tree used in \ref predArc().
851    ///
[421]852    ///\pre Either \ref run(Node) "run()" or \ref init()
853    ///must be called before using this function.
[100]854    Node predNode(Node v) const { return (*_pred)[v]==INVALID ? INVALID:
[209]855                                  G->source((*_pred)[v]); }
856
[244]857    ///\brief Returns a const reference to the node map that stores the
858    ///distances of the nodes.
859    ///
860    ///Returns a const reference to the node map that stores the distances
861    ///of the nodes calculated by the algorithm.
862    ///
[421]863    ///\pre Either \ref run(Node) "run()" or \ref init()
[244]864    ///must be called before using this function.
[100]865    const DistMap &distMap() const { return *_dist;}
[209]866
[244]867    ///\brief Returns a const reference to the node map that stores the
868    ///predecessor arcs.
869    ///
870    ///Returns a const reference to the node map that stores the predecessor
871    ///arcs, which form the shortest path tree.
872    ///
[421]873    ///\pre Either \ref run(Node) "run()" or \ref init()
[244]874    ///must be called before using this function.
[100]875    const PredMap &predMap() const { return *_pred;}
[209]876
[421]877    ///Checks if a node is reached from the root(s).
[100]878
[421]879    ///Returns \c true if \c v is reached from the root(s).
880    ///
881    ///\pre Either \ref run(Node) "run()" or \ref init()
[244]882    ///must be called before using this function.
883    bool reached(Node v) const { return (*_heap_cross_ref)[v] !=
884                                        Heap::PRE_HEAP; }
[100]885
886    ///Checks if a node is processed.
887
888    ///Returns \c true if \c v is processed, i.e. the shortest
889    ///path to \c v has already found.
[421]890    ///
891    ///\pre Either \ref run(Node) "run()" or \ref init()
[244]892    ///must be called before using this function.
893    bool processed(Node v) const { return (*_heap_cross_ref)[v] ==
894                                          Heap::POST_HEAP; }
895
896    ///The current distance of a node from the root(s).
897
898    ///Returns the current distance of a node from the root(s).
899    ///It may be decreased in the following processes.
[421]900    ///
901    ///\pre Either \ref run(Node) "run()" or \ref init()
[286]902    ///must be called before using this function and
903    ///node \c v must be reached but not necessarily processed.
904    Value currentDist(Node v) const {
905      return processed(v) ? (*_dist)[v] : (*_heap)[v];
906    }
[209]907
[100]908    ///@}
909  };
910
911
[244]912  ///Default traits class of dijkstra() function.
[100]913
[244]914  ///Default traits class of dijkstra() function.
915  ///\tparam GR The type of the digraph.
916  ///\tparam LM The type of the length map.
[100]917  template<class GR, class LM>
918  struct DijkstraWizardDefaultTraits
919  {
[244]920    ///The type of the digraph the algorithm runs on.
[100]921    typedef GR Digraph;
922    ///The type of the map that stores the arc lengths.
923
924    ///The type of the map that stores the arc lengths.
925    ///It must meet the \ref concepts::ReadMap "ReadMap" concept.
926    typedef LM LengthMap;
[244]927    ///The type of the length of the arcs.
[100]928    typedef typename LM::Value Value;
[244]929
[100]930    /// Operation traits for Dijkstra algorithm.
931
[244]932    /// This class defines the operations that are used in the algorithm.
[100]933    /// \see DijkstraDefaultOperationTraits
934    typedef DijkstraDefaultOperationTraits<Value> OperationTraits;
935
[244]936    /// The cross reference type used by the heap.
[100]937
[244]938    /// The cross reference type used by the heap.
[100]939    /// Usually it is \c Digraph::NodeMap<int>.
940    typedef typename Digraph::template NodeMap<int> HeapCrossRef;
[244]941    ///Instantiates a \ref HeapCrossRef.
[100]942
[209]943    ///This function instantiates a \ref HeapCrossRef.
[244]944    /// \param g is the digraph, to which we would like to define the
[100]945    /// HeapCrossRef.
[244]946    static HeapCrossRef *createHeapCrossRef(const Digraph &g)
[100]947    {
[244]948      return new HeapCrossRef(g);
[100]949    }
[209]950
[244]951    ///The heap type used by the Dijkstra algorithm.
[100]952
[244]953    ///The heap type used by the Dijkstra algorithm.
[100]954    ///
955    ///\sa BinHeap
956    ///\sa Dijkstra
[244]957    typedef BinHeap<Value, typename Digraph::template NodeMap<int>,
[209]958                    std::less<Value> > Heap;
[100]959
[244]960    ///Instantiates a \ref Heap.
961
962    ///This function instantiates a \ref Heap.
963    /// \param r is the HeapCrossRef which is used.
964    static Heap *createHeap(HeapCrossRef& r)
[100]965    {
[244]966      return new Heap(r);
[100]967    }
968
[244]969    ///\brief The type of the map that stores the predecessor
[100]970    ///arcs of the shortest paths.
[209]971    ///
[244]972    ///The type of the map that stores the predecessor
[100]973    ///arcs of the shortest paths.
974    ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
[278]975    typedef typename Digraph::template NodeMap<typename Digraph::Arc> PredMap;
[301]976    ///Instantiates a PredMap.
[209]977
[301]978    ///This function instantiates a PredMap.
[244]979    ///\param g is the digraph, to which we would like to define the
[301]980    ///PredMap.
[244]981    static PredMap *createPredMap(const Digraph &g)
[100]982    {
[278]983      return new PredMap(g);
[100]984    }
[209]985
[244]986    ///The type of the map that indicates which nodes are processed.
987
988    ///The type of the map that indicates which nodes are processed.
[100]989    ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
990    ///By default it is a NullMap.
991    typedef NullMap<typename Digraph::Node,bool> ProcessedMap;
[301]992    ///Instantiates a ProcessedMap.
[209]993
[301]994    ///This function instantiates a ProcessedMap.
[100]995    ///\param g is the digraph, to which
[301]996    ///we would like to define the ProcessedMap.
[100]997#ifdef DOXYGEN
[244]998    static ProcessedMap *createProcessedMap(const Digraph &g)
[100]999#else
[244]1000    static ProcessedMap *createProcessedMap(const Digraph &)
[100]1001#endif
1002    {
1003      return new ProcessedMap();
1004    }
[209]1005
[244]1006    ///The type of the map that stores the distances of the nodes.
1007
1008    ///The type of the map that stores the distances of the nodes.
[100]1009    ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
[278]1010    typedef typename Digraph::template NodeMap<typename LM::Value> DistMap;
[301]1011    ///Instantiates a DistMap.
[209]1012
[301]1013    ///This function instantiates a DistMap.
[210]1014    ///\param g is the digraph, to which we would like to define
[301]1015    ///the DistMap
[244]1016    static DistMap *createDistMap(const Digraph &g)
[100]1017    {
[278]1018      return new DistMap(g);
[100]1019    }
[278]1020
1021    ///The type of the shortest paths.
1022
1023    ///The type of the shortest paths.
1024    ///It must meet the \ref concepts::Path "Path" concept.
1025    typedef lemon::Path<Digraph> Path;
[100]1026  };
[209]1027
[313]1028  /// Default traits class used by DijkstraWizard
[100]1029
1030  /// To make it easier to use Dijkstra algorithm
[244]1031  /// we have created a wizard class.
[100]1032  /// This \ref DijkstraWizard class needs default traits,
[244]1033  /// as well as the \ref Dijkstra class.
[100]1034  /// The \ref DijkstraWizardBase is a class to be the default traits of the
1035  /// \ref DijkstraWizard class.
1036  template<class GR,class LM>
1037  class DijkstraWizardBase : public DijkstraWizardDefaultTraits<GR,LM>
1038  {
1039    typedef DijkstraWizardDefaultTraits<GR,LM> Base;
1040  protected:
[244]1041    //The type of the nodes in the digraph.
[100]1042    typedef typename Base::Digraph::Node Node;
1043
[244]1044    //Pointer to the digraph the algorithm runs on.
[100]1045    void *_g;
[278]1046    //Pointer to the length map.
[100]1047    void *_length;
[251]1048    //Pointer to the map of processed nodes.
1049    void *_processed;
[244]1050    //Pointer to the map of predecessors arcs.
[100]1051    void *_pred;
[244]1052    //Pointer to the map of distances.
[100]1053    void *_dist;
[278]1054    //Pointer to the shortest path to the target node.
1055    void *_path;
1056    //Pointer to the distance of the target node.
1057    void *_di;
[100]1058
[244]1059  public:
[100]1060    /// Constructor.
[209]1061
[100]1062    /// This constructor does not require parameters, therefore it initiates
[278]1063    /// all of the attributes to \c 0.
[251]1064    DijkstraWizardBase() : _g(0), _length(0), _processed(0), _pred(0),
[278]1065                           _dist(0), _path(0), _di(0) {}
[100]1066
1067    /// Constructor.
[209]1068
[278]1069    /// This constructor requires two parameters,
1070    /// others are initiated to \c 0.
[244]1071    /// \param g The digraph the algorithm runs on.
1072    /// \param l The length map.
[278]1073    DijkstraWizardBase(const GR &g,const LM &l) :
[209]1074      _g(reinterpret_cast<void*>(const_cast<GR*>(&g))),
1075      _length(reinterpret_cast<void*>(const_cast<LM*>(&l))),
[278]1076      _processed(0), _pred(0), _dist(0), _path(0), _di(0) {}
[100]1077
1078  };
[209]1079
[278]1080  /// Auxiliary class for the function-type interface of Dijkstra algorithm.
[100]1081
[278]1082  /// This auxiliary class is created to implement the
1083  /// \ref dijkstra() "function-type interface" of \ref Dijkstra algorithm.
[421]1084  /// It does not have own \ref run(Node) "run()" method, it uses the
1085  /// functions and features of the plain \ref Dijkstra.
[100]1086  ///
[278]1087  /// This class should only be used through the \ref dijkstra() function,
1088  /// which makes it easier to use the algorithm.
[100]1089  template<class TR>
1090  class DijkstraWizard : public TR
1091  {
1092    typedef TR Base;
1093
[244]1094    ///The type of the digraph the algorithm runs on.
[100]1095    typedef typename TR::Digraph Digraph;
[244]1096
[100]1097    typedef typename Digraph::Node Node;
1098    typedef typename Digraph::NodeIt NodeIt;
1099    typedef typename Digraph::Arc Arc;
1100    typedef typename Digraph::OutArcIt OutArcIt;
[209]1101
[100]1102    ///The type of the map that stores the arc lengths.
1103    typedef typename TR::LengthMap LengthMap;
1104    ///The type of the length of the arcs.
1105    typedef typename LengthMap::Value Value;
[244]1106    ///\brief The type of the map that stores the predecessor
[100]1107    ///arcs of the shortest paths.
1108    typedef typename TR::PredMap PredMap;
[244]1109    ///The type of the map that stores the distances of the nodes.
[100]1110    typedef typename TR::DistMap DistMap;
[244]1111    ///The type of the map that indicates which nodes are processed.
1112    typedef typename TR::ProcessedMap ProcessedMap;
[278]1113    ///The type of the shortest paths
1114    typedef typename TR::Path Path;
[100]1115    ///The heap type used by the dijkstra algorithm.
1116    typedef typename TR::Heap Heap;
[244]1117
[100]1118  public:
[244]1119
[100]1120    /// Constructor.
1121    DijkstraWizard() : TR() {}
1122
1123    /// Constructor that requires parameters.
1124
1125    /// Constructor that requires parameters.
1126    /// These parameters will be the default values for the traits class.
[278]1127    /// \param g The digraph the algorithm runs on.
1128    /// \param l The length map.
1129    DijkstraWizard(const Digraph &g, const LengthMap &l) :
1130      TR(g,l) {}
[100]1131
1132    ///Copy constructor
1133    DijkstraWizard(const TR &b) : TR(b) {}
1134
1135    ~DijkstraWizard() {}
1136
[278]1137    ///Runs Dijkstra algorithm from the given source node.
[209]1138
[278]1139    ///This method runs %Dijkstra algorithm from the given source node
1140    ///in order to compute the shortest path to each node.
1141    void run(Node s)
[100]1142    {
[209]1143      Dijkstra<Digraph,LengthMap,TR>
[278]1144        dijk(*reinterpret_cast<const Digraph*>(Base::_g),
1145             *reinterpret_cast<const LengthMap*>(Base::_length));
1146      if (Base::_pred)
1147        dijk.predMap(*reinterpret_cast<PredMap*>(Base::_pred));
1148      if (Base::_dist)
1149        dijk.distMap(*reinterpret_cast<DistMap*>(Base::_dist));
1150      if (Base::_processed)
1151        dijk.processedMap(*reinterpret_cast<ProcessedMap*>(Base::_processed));
1152      dijk.run(s);
[100]1153    }
1154
[278]1155    ///Finds the shortest path between \c s and \c t.
[100]1156
[278]1157    ///This method runs the %Dijkstra algorithm from node \c s
1158    ///in order to compute the shortest path to node \c t
1159    ///(it stops searching when \c t is processed).
1160    ///
1161    ///\return \c true if \c t is reachable form \c s.
1162    bool run(Node s, Node t)
[100]1163    {
[278]1164      Dijkstra<Digraph,LengthMap,TR>
1165        dijk(*reinterpret_cast<const Digraph*>(Base::_g),
1166             *reinterpret_cast<const LengthMap*>(Base::_length));
1167      if (Base::_pred)
1168        dijk.predMap(*reinterpret_cast<PredMap*>(Base::_pred));
1169      if (Base::_dist)
1170        dijk.distMap(*reinterpret_cast<DistMap*>(Base::_dist));
1171      if (Base::_processed)
1172        dijk.processedMap(*reinterpret_cast<ProcessedMap*>(Base::_processed));
1173      dijk.run(s,t);
1174      if (Base::_path)
1175        *reinterpret_cast<Path*>(Base::_path) = dijk.path(t);
1176      if (Base::_di)
1177        *reinterpret_cast<Value*>(Base::_di) = dijk.dist(t);
1178      return dijk.reached(t);
[244]1179    }
1180
[100]1181    template<class T>
[257]1182    struct SetPredMapBase : public Base {
[100]1183      typedef T PredMap;
1184      static PredMap *createPredMap(const Digraph &) { return 0; };
[257]1185      SetPredMapBase(const TR &b) : TR(b) {}
[100]1186    };
[278]1187    ///\brief \ref named-func-param "Named parameter"
[301]1188    ///for setting PredMap object.
[100]1189    ///
[278]1190    ///\ref named-func-param "Named parameter"
[301]1191    ///for setting PredMap object.
[100]1192    template<class T>
[257]1193    DijkstraWizard<SetPredMapBase<T> > predMap(const T &t)
[100]1194    {
1195      Base::_pred=reinterpret_cast<void*>(const_cast<T*>(&t));
[257]1196      return DijkstraWizard<SetPredMapBase<T> >(*this);
[100]1197    }
[209]1198
[100]1199    template<class T>
[278]1200    struct SetDistMapBase : public Base {
1201      typedef T DistMap;
1202      static DistMap *createDistMap(const Digraph &) { return 0; };
1203      SetDistMapBase(const TR &b) : TR(b) {}
1204    };
1205    ///\brief \ref named-func-param "Named parameter"
[301]1206    ///for setting DistMap object.
[278]1207    ///
1208    ///\ref named-func-param "Named parameter"
[301]1209    ///for setting DistMap object.
[278]1210    template<class T>
1211    DijkstraWizard<SetDistMapBase<T> > distMap(const T &t)
1212    {
1213      Base::_dist=reinterpret_cast<void*>(const_cast<T*>(&t));
1214      return DijkstraWizard<SetDistMapBase<T> >(*this);
1215    }
1216
1217    template<class T>
[257]1218    struct SetProcessedMapBase : public Base {
[244]1219      typedef T ProcessedMap;
1220      static ProcessedMap *createProcessedMap(const Digraph &) { return 0; };
[257]1221      SetProcessedMapBase(const TR &b) : TR(b) {}
[244]1222    };
[278]1223    ///\brief \ref named-func-param "Named parameter"
[301]1224    ///for setting ProcessedMap object.
[244]1225    ///
[278]1226    /// \ref named-func-param "Named parameter"
[301]1227    ///for setting ProcessedMap object.
[244]1228    template<class T>
[257]1229    DijkstraWizard<SetProcessedMapBase<T> > processedMap(const T &t)
[244]1230    {
1231      Base::_processed=reinterpret_cast<void*>(const_cast<T*>(&t));
[257]1232      return DijkstraWizard<SetProcessedMapBase<T> >(*this);
[244]1233    }
1234
1235    template<class T>
[278]1236    struct SetPathBase : public Base {
1237      typedef T Path;
1238      SetPathBase(const TR &b) : TR(b) {}
[100]1239    };
[278]1240    ///\brief \ref named-func-param "Named parameter"
1241    ///for getting the shortest path to the target node.
[100]1242    ///
[278]1243    ///\ref named-func-param "Named parameter"
1244    ///for getting the shortest path to the target node.
[100]1245    template<class T>
[278]1246    DijkstraWizard<SetPathBase<T> > path(const T &t)
[100]1247    {
[278]1248      Base::_path=reinterpret_cast<void*>(const_cast<T*>(&t));
1249      return DijkstraWizard<SetPathBase<T> >(*this);
1250    }
1251
1252    ///\brief \ref named-func-param "Named parameter"
1253    ///for getting the distance of the target node.
1254    ///
1255    ///\ref named-func-param "Named parameter"
1256    ///for getting the distance of the target node.
1257    DijkstraWizard dist(const Value &d)
1258    {
1259      Base::_di=reinterpret_cast<void*>(const_cast<Value*>(&d));
1260      return *this;
[100]1261    }
[209]1262
[100]1263  };
[209]1264
[278]1265  ///Function-type interface for Dijkstra algorithm.
[100]1266
1267  /// \ingroup shortest_path
[278]1268  ///Function-type interface for Dijkstra algorithm.
[100]1269  ///
[278]1270  ///This function also has several \ref named-func-param "named parameters",
[100]1271  ///they are declared as the members of class \ref DijkstraWizard.
[278]1272  ///The following examples show how to use these parameters.
[100]1273  ///\code
[278]1274  ///  // Compute shortest path from node s to each node
1275  ///  dijkstra(g,length).predMap(preds).distMap(dists).run(s);
1276  ///
1277  ///  // Compute shortest path from s to t
1278  ///  bool reached = dijkstra(g,length).path(p).dist(d).run(s,t);
[100]1279  ///\endcode
[421]1280  ///\warning Don't forget to put the \ref DijkstraWizard::run(Node) "run()"
[100]1281  ///to the end of the parameter list.
1282  ///\sa DijkstraWizard
1283  ///\sa Dijkstra
1284  template<class GR, class LM>
1285  DijkstraWizard<DijkstraWizardBase<GR,LM> >
[278]1286  dijkstra(const GR &digraph, const LM &length)
[100]1287  {
[278]1288    return DijkstraWizard<DijkstraWizardBase<GR,LM> >(digraph,length);
[100]1289  }
1290
1291} //END OF NAMESPACE LEMON
1292
1293#endif
Note: See TracBrowser for help on using the repository browser.