COIN-OR::LEMON - Graph Library

source: lemon-1.2/lemon/dijkstra.h @ 788:c92296660262

Last change on this file since 788:c92296660262 was 788:c92296660262, checked in by Alpar Juttner <alpar@…>, 14 years ago

Merge

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