COIN-OR::LEMON - Graph Library

source: lemon-1.2/lemon/dijkstra.h @ 340:0badf3bb38c2

Last change on this file since 340:0badf3bb38c2 was 313:64f8f7cc6168, checked in by Peter Kovacs <kpeter@…>, 12 years ago

Fix several doxygen warnings

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