COIN-OR::LEMON - Graph Library

source: lemon-main/lemon/dijkstra.h @ 1051:4f9a45a6d6f0

Last change on this file since 1051:4f9a45a6d6f0 was 877:141f9c0db4a3, checked in by Alpar Juttner <alpar@…>, 15 years ago

Unify the sources (#339)

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