dijkstra.h

Go to the documentation of this file.
00001 /* -*- C++ -*-
00002  *
00003  * This file is a part of LEMON, a generic C++ optimization library
00004  *
00005  * Copyright (C) 2003-2006
00006  * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
00007  * (Egervary Research Group on Combinatorial Optimization, EGRES).
00008  *
00009  * Permission to use, modify and distribute this software is granted
00010  * provided that this copyright notice appears in all copies. For
00011  * precise terms see the accompanying LICENSE file.
00012  *
00013  * This software is provided "AS IS" with no warranty of any kind,
00014  * express or implied, and with no claim as to its suitability for any
00015  * purpose.
00016  *
00017  */
00018 
00019 #ifndef LEMON_DIJKSTRA_H
00020 #define LEMON_DIJKSTRA_H
00021 
00027 
00028 #include <lemon/list_graph.h>
00029 #include <lemon/bin_heap.h>
00030 #include <lemon/invalid.h>
00031 #include <lemon/error.h>
00032 #include <lemon/maps.h>
00033 
00034 namespace lemon {
00035 
00036   template<class T> T dijkstraZero() {return 0;}
00037   
00039 
00043   template<class GR, class LM>
00044   struct DijkstraDefaultTraits
00045   {
00047     typedef GR Graph;
00049 
00052     typedef LM LengthMap;
00053     //The type of the length of the edges.
00054     typedef typename LM::Value Value;
00056 
00059     typedef typename Graph::template NodeMap<int> HeapCrossRef;
00061 
00065     static HeapCrossRef *createHeapCrossRef(const GR &G) 
00066     {
00067       return new HeapCrossRef(G);
00068     }
00069     
00071 
00076     typedef BinHeap<typename Graph::Node, typename LM::Value,
00077                     HeapCrossRef, std::less<Value> > Heap;
00078 
00079     static Heap *createHeap(HeapCrossRef& R) 
00080     {
00081       return new Heap(R);
00082     }
00083 
00091     typedef typename Graph::template NodeMap<typename GR::Edge> PredMap;
00093  
00097     static PredMap *createPredMap(const GR &G) 
00098     {
00099       return new PredMap(G);
00100     }
00101 
00103  
00110     typedef NullMap<typename Graph::Node,bool> ProcessedMap;
00112  
00116 #ifdef DOXYGEN
00117     static ProcessedMap *createProcessedMap(const GR &g)
00118 #else
00119     static ProcessedMap *createProcessedMap(const GR &)
00120 #endif
00121     {
00122       return new ProcessedMap();
00123     }
00125  
00129     typedef typename Graph::template NodeMap<typename LM::Value> DistMap;
00131  
00134     static DistMap *createDistMap(const GR &G)
00135     {
00136       return new DistMap(G);
00137     }
00138   };
00139   
00141   
00170 
00171 #ifdef DOXYGEN
00172   template <typename GR,
00173             typename LM,
00174             typename TR>
00175 #else
00176   template <typename GR=ListGraph,
00177             typename LM=typename GR::template EdgeMap<int>,
00178             typename TR=DijkstraDefaultTraits<GR,LM> >
00179 #endif
00180   class Dijkstra {
00181   public:
00188     class UninitializedParameter : public lemon::UninitializedParameter {
00189     public:
00190       virtual const char* exceptionName() const {
00191         return "lemon::Dijkstra::UninitializedParameter";
00192       }
00193     };
00194 
00195     typedef TR Traits;
00197     typedef typename TR::Graph Graph;
00199     typedef typename Graph::Node Node;
00201     typedef typename Graph::NodeIt NodeIt;
00203     typedef typename Graph::Edge Edge;
00205     typedef typename Graph::OutEdgeIt OutEdgeIt;
00206     
00208     typedef typename TR::LengthMap::Value Value;
00210     typedef typename TR::LengthMap LengthMap;
00213     typedef typename TR::PredMap PredMap;
00215     typedef typename TR::ProcessedMap ProcessedMap;
00217     typedef typename TR::DistMap DistMap;
00219     typedef typename TR::HeapCrossRef HeapCrossRef;
00221     typedef typename TR::Heap Heap;
00222   private:
00224     const Graph *G;
00226     const LengthMap *length;
00228     PredMap *_pred;
00230     bool local_pred;
00232     DistMap *_dist;
00234     bool local_dist;
00236     ProcessedMap *_processed;
00238     bool local_processed;
00240     HeapCrossRef *_heap_cross_ref;
00242     bool local_heap_cross_ref;
00244     Heap *_heap;
00246     bool local_heap;
00247 
00249     
00251     void create_maps() 
00252     {
00253       if(!_pred) {
00254         local_pred = true;
00255         _pred = Traits::createPredMap(*G);
00256       }
00257       if(!_dist) {
00258         local_dist = true;
00259         _dist = Traits::createDistMap(*G);
00260       }
00261       if(!_processed) {
00262         local_processed = true;
00263         _processed = Traits::createProcessedMap(*G);
00264       }
00265       if (!_heap_cross_ref) {
00266         local_heap_cross_ref = true;
00267         _heap_cross_ref = Traits::createHeapCrossRef(*G);
00268       }
00269       if (!_heap) {
00270         local_heap = true;
00271         _heap = Traits::createHeap(*_heap_cross_ref);
00272       }
00273     }
00274     
00275   public :
00276 
00277     typedef Dijkstra Create;
00278  
00280 
00282 
00283     template <class T>
00284     struct DefPredMapTraits : public Traits {
00285       typedef T PredMap;
00286       static PredMap *createPredMap(const Graph &G) 
00287       {
00288         throw UninitializedParameter();
00289       }
00290     };
00292 
00295     template <class T>
00296     struct DefPredMap 
00297       : public Dijkstra< Graph, LengthMap, DefPredMapTraits<T> > {
00298       typedef Dijkstra< Graph,	LengthMap, DefPredMapTraits<T> > Create;
00299     };
00300     
00301     template <class T>
00302     struct DefDistMapTraits : public Traits {
00303       typedef T DistMap;
00304       static DistMap *createDistMap(const Graph &G) 
00305       {
00306         throw UninitializedParameter();
00307       }
00308     };
00310 
00313     template <class T>
00314     struct DefDistMap 
00315       : public Dijkstra< Graph, LengthMap, DefDistMapTraits<T> > { 
00316       typedef Dijkstra< Graph, LengthMap, DefDistMapTraits<T> > Create;
00317     };
00318     
00319     template <class T>
00320     struct DefProcessedMapTraits : public Traits {
00321       typedef T ProcessedMap;
00322       static ProcessedMap *createProcessedMap(const Graph &G) 
00323       {
00324         throw UninitializedParameter();
00325       }
00326     };
00328 
00331     template <class T>
00332     struct DefProcessedMap 
00333       : public Dijkstra< Graph, LengthMap, DefProcessedMapTraits<T> > { 
00334       typedef Dijkstra< Graph,	LengthMap, DefProcessedMapTraits<T> > Create;
00335     };
00336     
00337     struct DefGraphProcessedMapTraits : public Traits {
00338       typedef typename Graph::template NodeMap<bool> ProcessedMap;
00339       static ProcessedMap *createProcessedMap(const Graph &G) 
00340       {
00341         return new ProcessedMap(G);
00342       }
00343     };
00350     template <class T>
00351     struct DefProcessedMapToBeDefaultMap 
00352       : public Dijkstra< Graph, LengthMap, DefGraphProcessedMapTraits> {
00353       typedef Dijkstra< Graph, LengthMap, DefGraphProcessedMapTraits> Create;
00354     };
00355 
00356     template <class H, class CR>
00357     struct DefHeapTraits : public Traits {
00358       typedef CR HeapCrossRef;
00359       typedef H Heap;
00360       static HeapCrossRef *createHeapCrossRef(const Graph &) {
00361         throw UninitializedParameter();
00362       }
00363       static Heap *createHeap(HeapCrossRef &) 
00364       {
00365         throw UninitializedParameter();
00366       }
00367     };
00370 
00374     template <class H, class CR = typename Graph::template NodeMap<int> >
00375     struct DefHeap
00376       : public Dijkstra< Graph, LengthMap, DefHeapTraits<H, CR> > { 
00377       typedef Dijkstra< Graph,	LengthMap, DefHeapTraits<H, CR> > Create;
00378     };
00379 
00380     template <class H, class CR>
00381     struct DefStandardHeapTraits : public Traits {
00382       typedef CR HeapCrossRef;
00383       typedef H Heap;
00384       static HeapCrossRef *createHeapCrossRef(const Graph &G) {
00385         return new HeapCrossRef(G);
00386       }
00387       static Heap *createHeap(HeapCrossRef &R) 
00388       {
00389         return new Heap(R);
00390       }
00391     };
00394 
00399     template <class H, class CR = typename Graph::template NodeMap<int> >
00400     struct DefStandardHeap
00401       : public Dijkstra< Graph, LengthMap, DefStandardHeapTraits<H, CR> > { 
00402       typedef Dijkstra< Graph,	LengthMap, DefStandardHeapTraits<H, CR> > 
00403       Create;
00404     };
00405     
00407 
00408 
00409   protected:
00410 
00411     Dijkstra() {}
00412 
00413   public:      
00414     
00416     
00419     Dijkstra(const Graph& _G, const LengthMap& _length) :
00420       G(&_G), length(&_length),
00421       _pred(NULL), local_pred(false),
00422       _dist(NULL), local_dist(false),
00423       _processed(NULL), local_processed(false),
00424       _heap_cross_ref(NULL), local_heap_cross_ref(false),
00425       _heap(NULL), local_heap(false)
00426     { }
00427     
00429     ~Dijkstra() 
00430     {
00431       if(local_pred) delete _pred;
00432       if(local_dist) delete _dist;
00433       if(local_processed) delete _processed;
00434       if(local_heap_cross_ref) delete _heap_cross_ref;
00435       if(local_heap) delete _heap;
00436     }
00437 
00439 
00442     Dijkstra &lengthMap(const LengthMap &m) 
00443     {
00444       length = &m;
00445       return *this;
00446     }
00447 
00449 
00455     Dijkstra &predMap(PredMap &m) 
00456     {
00457       if(local_pred) {
00458         delete _pred;
00459         local_pred=false;
00460       }
00461       _pred = &m;
00462       return *this;
00463     }
00464 
00466 
00472     Dijkstra &distMap(DistMap &m) 
00473     {
00474       if(local_dist) {
00475         delete _dist;
00476         local_dist=false;
00477       }
00478       _dist = &m;
00479       return *this;
00480     }
00481 
00483 
00489     Dijkstra &heap(Heap& heap, HeapCrossRef &crossRef)
00490     {
00491       if(local_heap_cross_ref) {
00492         delete _heap_cross_ref;
00493         local_heap_cross_ref=false;
00494       }
00495       _heap_cross_ref = &crossRef;
00496       if(local_heap) {
00497         delete _heap;
00498         local_heap=false;
00499       }
00500       _heap = &heap;
00501       return *this;
00502     }
00503 
00504   private:
00505     void finalizeNodeData(Node v,Value dst)
00506     {
00507       _processed->set(v,true);
00508       _dist->set(v, dst);
00509     }
00510 
00511   public:
00521 
00523 
00525 
00528     void init()
00529     {
00530       create_maps();
00531       _heap->clear();
00532       for ( NodeIt u(*G) ; u!=INVALID ; ++u ) {
00533         _pred->set(u,INVALID);
00534         _processed->set(u,false);
00535         _heap_cross_ref->set(u,Heap::PRE_HEAP);
00536       }
00537     }
00538     
00540 
00548     void addSource(Node s,Value dst=dijkstraZero<Value>())
00549     {
00550       if(_heap->state(s) != Heap::IN_HEAP) {
00551         _heap->push(s,dst);
00552       } else if((*_heap)[s]<dst) {
00553         _heap->push(s,dst);
00554         _pred->set(s,INVALID);
00555       }
00556     }
00557     
00559 
00565     Node processNextNode()
00566     {
00567       Node v=_heap->top(); 
00568       Value oldvalue=_heap->prio();
00569       _heap->pop();
00570       finalizeNodeData(v,oldvalue);
00571       
00572       for(OutEdgeIt e(*G,v); e!=INVALID; ++e) {
00573         Node w=G->target(e); 
00574         switch(_heap->state(w)) {
00575         case Heap::PRE_HEAP:
00576           _heap->push(w,oldvalue+(*length)[e]); 
00577           _pred->set(w,e);
00578           break;
00579         case Heap::IN_HEAP:
00580           if ( oldvalue+(*length)[e] < (*_heap)[w] ) {
00581             _heap->decrease(w, oldvalue+(*length)[e]); 
00582             _pred->set(w,e);
00583           }
00584           break;
00585         case Heap::POST_HEAP:
00586           break;
00587         }
00588       }
00589       return v;
00590     }
00591 
00593     
00598     Node nextNode()
00599     { 
00600       return _heap->empty()?_heap->top():INVALID;
00601     }
00602  
00608     bool emptyQueue() { return _heap->empty(); }
00610 
00613     int queueSize() { return _heap->size(); }
00614     
00616 
00629     void start()
00630     {
00631       while ( !_heap->empty() ) processNextNode();
00632     }
00633     
00635 
00648     void start(Node dest)
00649     {
00650       while ( !_heap->empty() && _heap->top()!=dest ) processNextNode();
00651       if ( !_heap->empty() ) finalizeNodeData(_heap->top(),_heap->prio());
00652     }
00653     
00655 
00663     template<class NodeBoolMap>
00664     void start(const NodeBoolMap &nm)
00665     {
00666       while ( !_heap->empty() && !nm[_heap->top()] ) processNextNode();
00667       if ( !_heap->empty() ) finalizeNodeData(_heap->top(),_heap->prio());
00668     }
00669     
00671     
00685     void run(Node s) {
00686       init();
00687       addSource(s);
00688       start();
00689     }
00690     
00692     
00704     Value run(Node s,Node t) {
00705       init();
00706       addSource(s);
00707       start(t);
00708       return (*_pred)[t]==INVALID?dijkstraZero<Value>():(*_dist)[t];
00709     }
00710     
00712 
00718     
00720 
00722     
00729     template<class P>
00730     bool getPath(P &p,Node t) 
00731     {
00732       if(reached(t)) {
00733         p.clear();
00734         typename P::Builder b(p);
00735         for(b.setStartNode(t);predEdge(t)!=INVALID;t=predNode(t))
00736           b.pushFront(predEdge(t));
00737         b.commit();
00738         return true;
00739       }
00740       return false;
00741     }
00742           
00744 
00749     Value dist(Node v) const { return (*_dist)[v]; }
00750 
00752 
00760     Edge predEdge(Node v) const { return (*_pred)[v]; }
00761 
00763 
00770     Node predNode(Node v) const { return (*_pred)[v]==INVALID ? INVALID:
00771                                   G->source((*_pred)[v]); }
00772     
00774 
00777     const DistMap &distMap() const { return *_dist;}
00778  
00780 
00784     const PredMap &predMap() const { return *_pred;}
00785  
00787 
00792     bool reached(Node v) { return (*_heap_cross_ref)[v] != Heap::PRE_HEAP; }
00793 
00795 
00800     bool processed(Node v) { return (*_heap_cross_ref)[v] == Heap::POST_HEAP; }
00801     
00803   };
00804 
00805 
00806 
00807 
00808  
00810 
00814   template<class GR, class LM>
00815   struct DijkstraWizardDefaultTraits
00816   {
00818     typedef GR Graph;
00820 
00823     typedef LM LengthMap;
00824     //The type of the length of the edges.
00825     typedef typename LM::Value Value;
00827 
00829 
00832     typedef typename Graph::template NodeMap<int> HeapCrossRef;
00834 
00839     static HeapCrossRef *createHeapCrossRef(const GR &G) 
00840     {
00841       return new HeapCrossRef(G);
00842     }
00843     
00845 
00850     typedef BinHeap<typename Graph::Node, typename LM::Value,
00851                     typename GR::template NodeMap<int>,
00852                     std::less<Value> > Heap;
00853 
00854     static Heap *createHeap(HeapCrossRef& R) 
00855     {
00856       return new Heap(R);
00857     }
00858 
00866     typedef NullMap <typename GR::Node,typename GR::Edge> PredMap;
00868  
00872 #ifdef DOXYGEN
00873     static PredMap *createPredMap(const GR &g) 
00874 #else
00875     static PredMap *createPredMap(const GR &) 
00876 #endif
00877     {
00878       return new PredMap();
00879     }
00881  
00888     typedef NullMap<typename Graph::Node,bool> ProcessedMap;
00890  
00894 #ifdef DOXYGEN
00895     static ProcessedMap *createProcessedMap(const GR &g)
00896 #else
00897     static ProcessedMap *createProcessedMap(const GR &)
00898 #endif
00899     {
00900       return new ProcessedMap();
00901     }
00903  
00907     typedef NullMap<typename Graph::Node,typename LM::Value> DistMap;
00909  
00912 #ifdef DOXYGEN
00913     static DistMap *createDistMap(const GR &g)
00914 #else
00915     static DistMap *createDistMap(const GR &)
00916 #endif
00917     {
00918       return new DistMap();
00919     }
00920   };
00921   
00923 
00931   template<class GR,class LM>
00932   class DijkstraWizardBase : public DijkstraWizardDefaultTraits<GR,LM>
00933   {
00934 
00935     typedef DijkstraWizardDefaultTraits<GR,LM> Base;
00936   protected:
00938     typedef typename Base::Graph::Node Node;
00939 
00941     void *_g;
00943     void *_length;
00945     void *_pred;
00947     void *_dist;
00949     Node _source;
00950 
00951     public:
00953     
00956     DijkstraWizardBase() : _g(0), _length(0), _pred(0),
00957                            _dist(0), _source(INVALID) {}
00958 
00960     
00967     DijkstraWizardBase(const GR &g,const LM &l, Node s=INVALID) :
00968       _g((void *)&g), _length((void *)&l), _pred(0),
00969       _dist(0), _source(s) {}
00970 
00971   };
00972   
00974 
00992   template<class TR>
00993   class DijkstraWizard : public TR
00994   {
00995     typedef TR Base;
00996 
00998     typedef typename TR::Graph Graph;
00999     //\e
01000     typedef typename Graph::Node Node;
01001     //\e
01002     typedef typename Graph::NodeIt NodeIt;
01003     //\e
01004     typedef typename Graph::Edge Edge;
01005     //\e
01006     typedef typename Graph::OutEdgeIt OutEdgeIt;
01007     
01009     typedef typename TR::LengthMap LengthMap;
01011     typedef typename LengthMap::Value Value;
01014     typedef typename TR::PredMap PredMap;
01016     typedef typename TR::DistMap DistMap;
01018     typedef typename TR::Heap Heap;
01019 public:
01021     DijkstraWizard() : TR() {}
01022 
01024 
01027     DijkstraWizard(const Graph &g,const LengthMap &l, Node s=INVALID) :
01028       TR(g,l,s) {}
01029 
01031     DijkstraWizard(const TR &b) : TR(b) {}
01032 
01033     ~DijkstraWizard() {}
01034 
01036     
01039     void run()
01040     {
01041       if(Base::_source==INVALID) throw UninitializedParameter();
01042       Dijkstra<Graph,LengthMap,TR> 
01043         dij(*(Graph*)Base::_g,*(LengthMap*)Base::_length);
01044       if(Base::_pred) dij.predMap(*(PredMap*)Base::_pred);
01045       if(Base::_dist) dij.distMap(*(DistMap*)Base::_dist);
01046       dij.run(Base::_source);
01047     }
01048 
01050 
01053     void run(Node s)
01054     {
01055       Base::_source=s;
01056       run();
01057     }
01058 
01059     template<class T>
01060     struct DefPredMapBase : public Base {
01061       typedef T PredMap;
01062       static PredMap *createPredMap(const Graph &) { return 0; };
01063       DefPredMapBase(const TR &b) : TR(b) {}
01064     };
01065     
01072     template<class T>
01073     DijkstraWizard<DefPredMapBase<T> > predMap(const T &t) 
01074     {
01075       Base::_pred=(void *)&t;
01076       return DijkstraWizard<DefPredMapBase<T> >(*this);
01077     }
01078     
01079     template<class T>
01080     struct DefDistMapBase : public Base {
01081       typedef T DistMap;
01082       static DistMap *createDistMap(const Graph &) { return 0; };
01083       DefDistMapBase(const TR &b) : TR(b) {}
01084     };
01085     
01092     template<class T>
01093     DijkstraWizard<DefDistMapBase<T> > distMap(const T &t) 
01094     {
01095       Base::_dist=(void *)&t;
01096       return DijkstraWizard<DefDistMapBase<T> >(*this);
01097     }
01098     
01100 
01103     DijkstraWizard<TR> &source(Node s) 
01104     {
01105       Base::_source=s;
01106       return *this;
01107     }
01108     
01109   };
01110   
01112 
01128   template<class GR, class LM>
01129   DijkstraWizard<DijkstraWizardBase<GR,LM> >
01130   dijkstra(const GR &g,const LM &l,typename GR::Node s=INVALID)
01131   {
01132     return DijkstraWizard<DijkstraWizardBase<GR,LM> >(g,l,s);
01133   }
01134 
01135 } //END OF NAMESPACE LEMON
01136 
01137 #endif

Generated on Fri Feb 3 18:36:33 2006 for LEMON by  doxygen 1.4.6