COIN-OR::LEMON - Graph Library

source: lemon-main/lemon/dijkstra.h @ 278:931190050520

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

Improve the function-type interface of bfs, dfs, and dijkstra (ticket #96)

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