COIN-OR::LEMON - Graph Library

source: lemon/lemon/dijkstra.h @ 173:b026e9779b28

Last change on this file since 173:b026e9779b28 was 169:5b507a86ad72, checked in by Peter Kovacs <kpeter@…>, 16 years ago

Fix various rename bugs

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