COIN-OR::LEMON - Graph Library

source: lemon-1.2/lemon/dijkstra.h @ 491:39aaeea2d471

Last change on this file since 491:39aaeea2d471 was 397:62f9787c516c, checked in by Peter Kovacs <kpeter@…>, 15 years ago

Remove DijkstraWidestPathOperationTraits? (#187)

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