COIN-OR::LEMON - Graph Library

source: lemon/lemon/dijkstra.h @ 956:141f9c0db4a3

Last change on this file since 956:141f9c0db4a3 was 956:141f9c0db4a3, checked in by Alpar Juttner <alpar@…>, 10 years ago

Unify the sources (#339)

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