00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
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
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
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
01000 typedef typename Graph::Node Node;
01001
01002 typedef typename Graph::NodeIt NodeIt;
01003
01004 typedef typename Graph::Edge Edge;
01005
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 }
01136
01137 #endif