00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017 #ifndef LEMON_DIJKSTRA_H
00018 #define LEMON_DIJKSTRA_H
00019
00023
00024 #include <lemon/list_graph.h>
00025 #include <lemon/bin_heap.h>
00026 #include <lemon/invalid.h>
00027 #include <lemon/error.h>
00028 #include <lemon/maps.h>
00029
00030 namespace lemon {
00031
00032
00033
00035
00039 template<class GR, class LM>
00040 struct DijkstraDefaultTraits
00041 {
00043 typedef GR Graph;
00045
00048 typedef LM LengthMap;
00049
00050 typedef typename LM::Value Value;
00052
00057 typedef BinHeap<typename Graph::Node,
00058 typename LM::Value,
00059 typename GR::template NodeMap<int>,
00060 std::less<Value> > Heap;
00061
00069 typedef typename Graph::template NodeMap<typename GR::Edge> PredMap;
00071
00075 static PredMap *createPredMap(const GR &G)
00076 {
00077 return new PredMap(G);
00078 }
00086 typedef NullMap<typename Graph::Node,typename Graph::Node> PredNodeMap;
00088
00092 static PredNodeMap *createPredNodeMap(const GR &G)
00093 {
00094 return new PredNodeMap();
00095 }
00096
00098
00104 typedef NullMap<typename Graph::Node,bool> ReachedMap;
00106
00110 static ReachedMap *createReachedMap(const GR &G)
00111 {
00112 return new ReachedMap();
00113 }
00115
00119 typedef typename Graph::template NodeMap<typename LM::Value> DistMap;
00121
00124 static DistMap *createDistMap(const GR &G)
00125 {
00126 return new DistMap(G);
00127 }
00128 };
00129
00131
00163
00164 #ifdef DOXYGEN
00165 template <typename GR,
00166 typename LM,
00167 typename TR>
00168 #else
00169 template <typename GR=ListGraph,
00170 typename LM=typename GR::template EdgeMap<int>,
00171 typename TR=DijkstraDefaultTraits<GR,LM> >
00172 #endif
00173 class Dijkstra {
00174 public:
00181 class UninitializedParameter : public lemon::UninitializedParameter {
00182 public:
00183 virtual const char* exceptionName() const {
00184 return "lemon::Dijsktra::UninitializedParameter";
00185 }
00186 };
00187
00188 typedef TR Traits;
00190 typedef typename TR::Graph Graph;
00192 typedef typename Graph::Node Node;
00194 typedef typename Graph::NodeIt NodeIt;
00196 typedef typename Graph::Edge Edge;
00198 typedef typename Graph::OutEdgeIt OutEdgeIt;
00199
00201 typedef typename TR::LengthMap::Value Value;
00203 typedef typename TR::LengthMap LengthMap;
00206 typedef typename TR::PredMap PredMap;
00209 typedef typename TR::PredNodeMap PredNodeMap;
00211 typedef typename TR::ReachedMap ReachedMap;
00213 typedef typename TR::DistMap DistMap;
00215 typedef typename TR::Heap Heap;
00216 private:
00218 const Graph *G;
00220 const LengthMap *length;
00222 PredMap *_pred;
00224 bool local_pred;
00226 PredNodeMap *_predNode;
00228 bool local_predNode;
00230 DistMap *_dist;
00232 bool local_dist;
00234 ReachedMap *_reached;
00236 bool local_reached;
00237
00239 Node source;
00240
00242
00245 void create_maps()
00246 {
00247 if(!_pred) {
00248 local_pred = true;
00249 _pred = Traits::createPredMap(*G);
00250 }
00251 if(!_predNode) {
00252 local_predNode = true;
00253 _predNode = Traits::createPredNodeMap(*G);
00254 }
00255 if(!_dist) {
00256 local_dist = true;
00257 _dist = Traits::createDistMap(*G);
00258 }
00259 if(!_reached) {
00260 local_reached = true;
00261 _reached = Traits::createReachedMap(*G);
00262 }
00263 }
00264
00265 public :
00266
00268
00270
00271 template <class T>
00272 struct DefPredMapTraits : public Traits {
00273 typedef T PredMap;
00274 static PredMap *createPredMap(const Graph &G)
00275 {
00276 throw UninitializedParameter();
00277 }
00278 };
00280
00283 template <class T>
00284 class DefPredMap : public Dijkstra< Graph,
00285 LengthMap,
00286 DefPredMapTraits<T> > { };
00287
00288 template <class T>
00289 struct DefPredNodeMapTraits : public Traits {
00290 typedef T PredNodeMap;
00291 static PredNodeMap *createPredNodeMap(const Graph &G)
00292 {
00293 throw UninitializedParameter();
00294 }
00295 };
00297
00300 template <class T>
00301 class DefPredNodeMap : public Dijkstra< Graph,
00302 LengthMap,
00303 DefPredNodeMapTraits<T> > { };
00304
00305 template <class T>
00306 struct DefDistMapTraits : public Traits {
00307 typedef T DistMap;
00308 static DistMap *createDistMap(const Graph &G)
00309 {
00310 throw UninitializedParameter();
00311 }
00312 };
00314
00317 template <class T>
00318 class DefDistMap : public Dijkstra< Graph,
00319 LengthMap,
00320 DefDistMapTraits<T> > { };
00321
00322 template <class T>
00323 struct DefReachedMapTraits : public Traits {
00324 typedef T ReachedMap;
00325 static ReachedMap *createReachedMap(const Graph &G)
00326 {
00327 throw UninitializedParameter();
00328 }
00329 };
00331
00334 template <class T>
00335 class DefReachedMap : public Dijkstra< Graph,
00336 LengthMap,
00337 DefReachedMapTraits<T> > { };
00338
00339 struct DefGraphReachedMapTraits : public Traits {
00340 typedef typename Graph::NodeMap<bool> ReachedMap;
00341 static ReachedMap *createReachedMap(const Graph &G)
00342 {
00343 return new ReachedMap(G);
00344 }
00345 };
00352 template <class T>
00353 class DefReachedMapToBeDefaultMap :
00354 public Dijkstra< Graph,
00355 LengthMap,
00356 DefGraphReachedMapTraits> { };
00357
00359
00360
00361 private:
00362 typename Graph::template NodeMap<int> _heap_map;
00363 Heap _heap;
00364 public:
00365
00367
00370 Dijkstra(const Graph& _G, const LengthMap& _length) :
00371 G(&_G), length(&_length),
00372 _pred(NULL), local_pred(false),
00373 _predNode(NULL), local_predNode(false),
00374 _dist(NULL), local_dist(false),
00375 _reached(NULL), local_reached(false),
00376 _heap_map(*G,-1),_heap(_heap_map)
00377 { }
00378
00380 ~Dijkstra()
00381 {
00382 if(local_pred) delete _pred;
00383 if(local_predNode) delete _predNode;
00384 if(local_dist) delete _dist;
00385 if(local_reached) delete _reached;
00386 }
00387
00389
00392 Dijkstra &lengthMap(const LengthMap &m)
00393 {
00394 length = &m;
00395 return *this;
00396 }
00397
00399
00405 Dijkstra &predMap(PredMap &m)
00406 {
00407 if(local_pred) {
00408 delete _pred;
00409 local_pred=false;
00410 }
00411 _pred = &m;
00412 return *this;
00413 }
00414
00416
00422 Dijkstra &predNodeMap(PredNodeMap &m)
00423 {
00424 if(local_predNode) {
00425 delete _predNode;
00426 local_predNode=false;
00427 }
00428 _predNode = &m;
00429 return *this;
00430 }
00431
00433
00439 Dijkstra &distMap(DistMap &m)
00440 {
00441 if(local_dist) {
00442 delete _dist;
00443 local_dist=false;
00444 }
00445 _dist = &m;
00446 return *this;
00447 }
00448
00449 private:
00450 void finalizeNodeData(Node v,Value dst)
00451 {
00452 _reached->set(v,true);
00453 _dist->set(v, dst);
00454 _predNode->set(v,G->source((*_pred)[v]));
00455 }
00456
00457 public:
00466
00468
00470
00474 void init()
00475 {
00476 create_maps();
00477
00478 for ( NodeIt u(*G) ; u!=INVALID ; ++u ) {
00479 _pred->set(u,INVALID);
00480 _predNode->set(u,INVALID);
00482 _heap_map.set(u,Heap::PRE_HEAP);
00483 }
00484 }
00485
00487
00495 void addSource(Node s,Value dst=0)
00496 {
00497 source = s;
00498 if(_heap.state(s) != Heap::IN_HEAP) _heap.push(s,dst);
00499 else if(_heap[s]<dst) {
00500 _heap.push(s,dst);
00501 _pred->set(s,INVALID);
00502 }
00503 }
00504
00506
00510 void processNextNode()
00511 {
00512 Node v=_heap.top();
00513 Value oldvalue=_heap[v];
00514 _heap.pop();
00515 finalizeNodeData(v,oldvalue);
00516
00517 for(OutEdgeIt e(*G,v); e!=INVALID; ++e) {
00518 Node w=G->target(e);
00519 switch(_heap.state(w)) {
00520 case Heap::PRE_HEAP:
00521 _heap.push(w,oldvalue+(*length)[e]);
00522 _pred->set(w,e);
00523
00524 break;
00525 case Heap::IN_HEAP:
00526 if ( oldvalue+(*length)[e] < _heap[w] ) {
00527 _heap.decrease(w, oldvalue+(*length)[e]);
00528 _pred->set(w,e);
00529
00530 }
00531 break;
00532 case Heap::POST_HEAP:
00533 break;
00534 }
00535 }
00536 }
00537
00539
00542 bool emptyHeap() { return heap.empty(); }
00544
00547 int heapSize() { return heap.size(); }
00548
00550
00563 void start()
00564 {
00565 while ( !_heap.empty() ) processNextNode();
00566 }
00567
00569
00582 void start(Node dest)
00583 {
00584 while ( !_heap.empty() && _heap.top()!=dest ) processNextNode();
00585 if ( _heap.top()==dest ) finalizeNodeData(_heap.top());
00586 }
00587
00589
00597 template<class NM>
00598 void start(const NM &nm)
00599 {
00600 while ( !_heap.empty() && !mn[_heap.top()] ) processNextNode();
00601 if ( !_heap.empty() ) finalizeNodeData(_heap.top());
00602 }
00603
00605
00619 void run(Node s) {
00620 init();
00621 addSource(s);
00622 start();
00623 }
00624
00626
00638 Value run(Node s,Node t) {
00639 init();
00640 addSource(s);
00641 start(t);
00642 return (*_pred)[t]==INVALID?0:(*_dist)[t];
00643 }
00644
00646
00652
00654
00656
00661 Value dist(Node v) const { return (*_dist)[v]; }
00662
00664
00673 Edge pred(Node v) const { return (*_pred)[v]; }
00674
00676
00683 Node predNode(Node v) const { return (*_pred)[v]==INVALID ? INVALID:
00684 G->source((*_pred)[v]); }
00685
00687
00690 const DistMap &distMap() const { return *_dist;}
00691
00693
00697 const PredMap &predMap() const { return *_pred;}
00698
00700
00704 const PredNodeMap &predNodeMap() const { return *_predNode;}
00705
00707
00713 bool reached(Node v) { return v==source || (*_pred)[v]!=INVALID; }
00714
00716 };
00717
00719
00726 template<class GR,class LM>
00727 class DijkstraWizardBase : public DijkstraDefaultTraits<GR,LM>
00728 {
00729
00730 typedef DijkstraDefaultTraits<GR,LM> Base;
00731 protected:
00733 void *_g;
00735 void *_length;
00737 void *_pred;
00739 void *_predNode;
00741 void *_dist;
00743 void *_source;
00744
00746 typedef typename Base::Graph::Node Node;
00747
00748 public:
00750
00753 DijkstraWizardBase() : _g(0), _length(0), _pred(0), _predNode(0),
00754 _dist(0), _source(INVALID) {}
00755
00757
00764 DijkstraWizardBase(const GR &g,const LM &l, Node s=INVALID) :
00765 _g((void *)&g), _length((void *)&l), _pred(0), _predNode(0),
00766 _dist(0), _source((void *)&s) {}
00767
00768 };
00769
00771
00790 template<class TR>
00791 class DijkstraWizard : public TR
00792 {
00793 typedef TR Base;
00794
00796 typedef typename TR::Graph Graph;
00797
00798 typedef typename Graph::Node Node;
00799
00800 typedef typename Graph::NodeIt NodeIt;
00801
00802 typedef typename Graph::Edge Edge;
00803
00804 typedef typename Graph::OutEdgeIt OutEdgeIt;
00805
00807 typedef typename TR::LengthMap LengthMap;
00809 typedef typename LengthMap::Value Value;
00812 typedef typename TR::PredMap PredMap;
00815 typedef typename TR::PredNodeMap PredNodeMap;
00817 typedef typename TR::DistMap DistMap;
00818
00820 typedef typename TR::Heap Heap;
00821 public:
00823 DijkstraWizard() : TR() {}
00824
00826
00829 DijkstraWizard(const Graph &g,const LengthMap &l, Node s=INVALID) :
00830 TR(g,l,s) {}
00831
00833 DijkstraWizard(const TR &b) : TR(b) {}
00834
00835 ~DijkstraWizard() {}
00836
00838
00841 void run()
00842 {
00843 if(_source==0) throw UninitializedParameter();
00844 Dijkstra<Graph,LengthMap,TR> Dij(*(Graph*)_g,*(LengthMap*)_length);
00845 if(_pred) Dij.predMap(*(PredMap*)_pred);
00846 if(_predNode) Dij.predNodeMap(*(PredNodeMap*)_predNode);
00847 if(_dist) Dij.distMap(*(DistMap*)_dist);
00848 Dij.run(*(Node*)_source);
00849 }
00850
00852
00855 void run(Node s)
00856 {
00857 _source=(void *)&s;
00858 run();
00859 }
00860
00861 template<class T>
00862 struct DefPredMapBase : public Base {
00863 typedef T PredMap;
00864 static PredMap *createPredMap(const Graph &G) { return 0; };
00865 DefPredMapBase(const Base &b) : Base(b) {}
00866 };
00867
00874 template<class T>
00875 DijkstraWizard<DefPredMapBase<T> > predMap(const T &t)
00876 {
00877 _pred=(void *)&t;
00878 return DijkstraWizard<DefPredMapBase<T> >(*this);
00879 }
00880
00881
00882 template<class T>
00883 struct DefPredNodeMapBase : public Base {
00884 typedef T PredNodeMap;
00885 static PredNodeMap *createPredNodeMap(const Graph &G) { return 0; };
00886 DefPredNodeMapBase(const Base &b) : Base(b) {}
00887 };
00888
00895 template<class T>
00896 DijkstraWizard<DefPredNodeMapBase<T> > predNodeMap(const T &t)
00897 {
00898 _predNode=(void *)&t;
00899 return DijkstraWizard<DefPredNodeMapBase<T> >(*this);
00900 }
00901
00902 template<class T>
00903 struct DefDistMapBase : public Base {
00904 typedef T DistMap;
00905 static DistMap *createDistMap(const Graph &G) { return 0; };
00906 DefDistMapBase(const Base &b) : Base(b) {}
00907 };
00908
00915 template<class T>
00916 DijkstraWizard<DefDistMapBase<T> > distMap(const T &t)
00917 {
00918 _dist=(void *)&t;
00919 return DijkstraWizard<DefDistMapBase<T> >(*this);
00920 }
00921
00923
00926 DijkstraWizard<TR> &source(Node s)
00927 {
00928 source=(void *)&s;
00929 return *this;
00930 }
00931
00932 };
00933
00935
00939 template<class GR, class LM>
00940 DijkstraWizard<DijkstraWizardBase<GR,LM> >
00941 dijkstra(const GR &g,const LM &l,typename GR::Node s=INVALID)
00942 {
00943 return DijkstraWizard<DijkstraWizardBase<GR,LM> >(g,l,s);
00944 }
00945
00947
00948 }
00949
00950 #endif
00951