COIN-OR::LEMON - Graph Library

source: lemon-1.0/lemon/dijkstra.h @ 286:da414906fe21

Last change on this file since 286:da414906fe21 was 286:da414906fe21, checked in by Peter Kovacs <kpeter@…>, 16 years ago

Improvements related to BFS/DFS/Dijkstra (ticket #96)

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