COIN-OR::LEMON - Graph Library

source: lemon-1.2/lemon/dijkstra.h @ 157:2ccc1afc2c52

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

Using \tparam commands + removing \author commands (ticket #29, #39)

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