COIN-OR::LEMON - Graph Library

source: lemon-1.2/lemon/dijkstra.h @ 521:3af83b6be1df

Last change on this file since 521:3af83b6be1df was 440:88ed40ad0d4f, checked in by Alpar Juttner <alpar@…>, 11 years ago

Happy New Year again

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