Changeset 953:d9c115e2eeaf in lemon0.x for src
 Timestamp:
 11/01/04 18:57:19 (20 years ago)
 Branch:
 default
 Phase:
 public
 Convert:
 svn:c9d7d8f590d60310b91f818b3a526b0e/lemon/trunk@1333
 File:

 1 edited
Legend:
 Unmodified
 Added
 Removed

src/work/alpar/dijkstra.h
r952 r953 22 22 ///\brief Dijkstra algorithm. 23 23 24 #include <lemon/list_graph.h> 24 25 #include <lemon/bin_heap.h> 25 26 #include <lemon/invalid.h> … … 30 31 /// @{ 31 32 33 template<class GR, class LM> 34 struct DijkstraDefaultTraits 35 { 36 ///\e 37 typedef GR Graph; 38 ///\e 39 typedef typename Graph::Node Node; 40 ///\e 41 typedef typename Graph::Edge Edge; 42 ///The type of the map that stores the edge lengths. 43 44 ///It must meet the \ref ReadMap concept. 45 /// 46 typedef LM LengthMap; 47 ///The type of the length of the edges. 48 typedef typename LM::ValueType ValueType; 49 ///The heap type used by the dijkstra algorithm. 50 typedef BinHeap<typename Graph::Node, 51 typename LM::ValueType, 52 typename GR::template NodeMap<int>, 53 std::less<ValueType> > Heap; 54 55 ///\brief The type of the map that stores the last 56 ///edges of the shortest paths. 57 /// 58 ///It must meet the \ref WriteMap concept. 59 /// 60 typedef typename Graph::template NodeMap<Edge> PredMap; 61 /// 62 63 ///\todo Please document... 64 /// 65 static PredMap *createPredMap(const Graph &G) 66 { 67 return new PredMap(G); 68 } 69 ///\brief The type of the map that stores the last but one 70 ///nodes of the shortest paths. 71 /// 72 ///It must meet the \ref WriteMap concept. 73 /// 74 typedef typename Graph::template NodeMap<Node> PredNodeMap; 75 /// 76 77 ///\todo Please document... 78 /// 79 static PredNodeMap *createPredNodeMap(const Graph &G) 80 { 81 return new PredNodeMap(G); 82 } 83 ///The type of the map that stores the dists of the nodes. 84 85 ///It must meet the \ref WriteMap concept. 86 /// 87 typedef typename Graph::template NodeMap<ValueType> DistMap; 88 /// 89 90 ///\todo Please document... 91 /// 92 static DistMap *createDistMap(const Graph &G) 93 { 94 return new DistMap(G); 95 } 96 }; 97 32 98 ///%Dijkstra algorithm class. 33 99 … … 42 108 ///It is also possible to change the underlying priority heap. 43 109 /// 44 ///\param GR The graph type the algorithm runs on. 110 ///\param GR The graph type the algorithm runs on. The default value is 111 ///\ref ListGraph 45 112 ///\param LM This readonly 46 113 ///EdgeMap … … 62 129 template <typename GR, 63 130 typename LM, 64 typename Heap>131 typename TR> 65 132 #else 66 template <typename GR ,133 template <typename GR=ListGraph, 67 134 typename LM=typename GR::template EdgeMap<int>, 68 t emplate <class,class,class,class> class Heap = BinHeap>135 typename TR=DijkstraDefaultTraits<GR,LM> > 69 136 #endif 70 137 class Dijkstra{ 71 138 public: 139 typedef TR Traits; 72 140 ///The type of the underlying graph. 73 141 typedef GR Graph; … … 87 155 ///\brief The type of the map that stores the last 88 156 ///edges of the shortest paths. 89 typedef typename Graph::template NodeMap<Edge>PredMap;157 typedef typename TR::PredMap PredMap; 90 158 ///\brief The type of the map that stores the last but one 91 159 ///nodes of the shortest paths. 92 typedef typename Graph::template NodeMap<Node>PredNodeMap;160 typedef typename TR::PredNodeMap PredNodeMap; 93 161 ///The type of the map that stores the dists of the nodes. 94 typedef typename Graph::template NodeMap<ValueType> DistMap; 162 typedef typename TR::DistMap DistMap; 163 164 ///The heap type used by the dijkstra algorithm. 165 typedef typename TR::Heap Heap; 95 166 96 167 private: … … 123 194 if(!predecessor) { 124 195 local_predecessor = true; 125 predecessor = newPredMap(*G);196 predecessor = Traits::createPredMap(*G); 126 197 } 127 198 if(!pred_node) { 128 199 local_pred_node = true; 129 pred_node = newPredNodeMap(*G);200 pred_node = Traits::createPredNodeMap(*G); 130 201 } 131 202 if(!distance) { 132 203 local_distance = true; 133 distance = newDistMap(*G);204 distance = Traits::createDistMap(*G); 134 205 } 135 206 } 136 207 137 208 public : 209 210 template <class T> 211 struct SetPredMapTraits : public Traits { 212 typedef T PredMap; 213 ///\todo An exception should be thrown. 214 /// 215 static PredMap *createPredMap(const Graph &G) 216 { 217 std::cerr << __FILE__ ":" << __LINE__ << 218 ": error: Special maps should be manually created" << std::endl; 219 exit(1); 220 } 221 }; 222 ///\ref namedtemplparam "Named parameter" for setting PredMap's type 223 template <class T> 224 class SetPredMap : public Dijkstra< Graph, 225 LengthMap, 226 SetPredMapTraits<T> > { }; 227 228 template <class T> 229 struct SetPredNodeMapTraits : public Traits { 230 typedef T PredNodeMap; 231 ///\todo An exception should be thrown. 232 /// 233 static PredNodeMap *createPredNodeMap(const Graph &G) 234 { 235 std::cerr << __FILE__ ":" << __LINE__ << 236 ": error: Special maps should be manually created" << std::endl; 237 exit(1); 238 } 239 }; 240 ///\ref namedtemplparam "Named parameter" for setting PredNodeMap's type 241 template <class T> 242 class SetPredNodeMap : public Dijkstra< Graph, 243 LengthMap, 244 SetPredNodeMapTraits<T> > { }; 245 246 template <class T> 247 struct SetDistMapTraits : public Traits { 248 typedef T DistMap; 249 ///\todo An exception should be thrown. 250 /// 251 static DistMap *createDistMap(const Graph &G) 252 { 253 std::cerr << __FILE__ ":" << __LINE__ << 254 ": error: Special maps should be manually created" << std::endl; 255 exit(1); 256 } 257 }; 258 ///\ref namedtemplparam "Named parameter" for setting DistMap's type 259 template <class T> 260 class SetDistMap : public Dijkstra< Graph, 261 LengthMap, 262 SetDistMapTraits<T> > { }; 263 138 264 ///Constructor. 139 265 … … 238 364 typename GR::template NodeMap<int> heap_map(*G,1); 239 365 240 typedef Heap<Node, ValueType, typename GR::template NodeMap<int>, 241 std::less<ValueType> > 242 HeapType; 243 244 HeapType heap(heap_map); 366 Heap heap(heap_map); 245 367 246 368 heap.push(s,0); … … 257 379 Node w=G>head(e); 258 380 switch(heap.state(w)) { 259 case Heap Type::PRE_HEAP:381 case Heap::PRE_HEAP: 260 382 heap.push(w,oldvalue+(*length)[e]); 261 383 predecessor>set(w,e); 262 384 pred_node>set(w,v); 263 385 break; 264 case Heap Type::IN_HEAP:386 case Heap::IN_HEAP: 265 387 if ( oldvalue+(*length)[e] < heap[w] ) { 266 388 heap.decrease(w, oldvalue+(*length)[e]); … … 269 391 } 270 392 break; 271 case Heap Type::POST_HEAP:393 case Heap::POST_HEAP: 272 394 break; 273 395 } … … 335 457 336 458 }; 459 460 ///\e 461 462 ///\e 463 /// 464 template<class TR> 465 class _Dijkstra 466 { 467 typedef TR Traits; 468 469 ///The type of the underlying graph. 470 typedef typename TR::Graph Graph; 471 ///\e 472 typedef typename Graph::Node Node; 473 ///\e 474 typedef typename Graph::NodeIt NodeIt; 475 ///\e 476 typedef typename Graph::Edge Edge; 477 ///\e 478 typedef typename Graph::OutEdgeIt OutEdgeIt; 479 480 ///The type of the map that stores the edge lengths. 481 typedef typename TR::LengthMap LengthMap; 482 ///The type of the length of the edges. 483 typedef typename LengthMap::ValueType ValueType; 484 ///\brief The type of the map that stores the last 485 ///edges of the shortest paths. 486 typedef typename TR::PredMap PredMap; 487 ///\brief The type of the map that stores the last but one 488 ///nodes of the shortest paths. 489 typedef typename TR::PredNodeMap PredNodeMap; 490 ///The type of the map that stores the dists of the nodes. 491 typedef typename TR::DistMap DistMap; 492 493 ///The heap type used by the dijkstra algorithm. 494 typedef typename TR::Heap Heap; 495 496 /// Pointer to the underlying graph. 497 const Graph *G; 498 /// Pointer to the length map 499 const LengthMap *length; 500 ///Pointer to the map of predecessors edges. 501 PredMap *predecessor; 502 ///Pointer to the map of predecessors nodes. 503 PredNodeMap *pred_node; 504 ///Pointer to the map of distances. 505 DistMap *distance; 506 507 Node source; 508 509 public: 510 _Dijkstra() : G(0), length(0), predecessor(0), pred_node(0), 511 distance(0), source(INVALID) {} 512 513 _Dijkstra(const Graph &g,const LengthMap &l, Node s) : 514 G(&g), length(&l), predecessor(0), pred_node(0), 515 distance(0), source(s) {} 516 517 ~_Dijkstra() 518 { 519 Dijkstra<Graph,LengthMap,TR> Dij(*G,*length); 520 if(predecessor) Dij.setPredMap(*predecessor); 521 if(pred_node) Dij.setPredNodeMap(*pred_node); 522 if(distance) Dij.setDistMap(*distance); 523 Dij.run(source); 524 } 525 526 template<class T> 527 struct SetPredMapTraits : public Traits {typedef T PredMap;}; 528 529 ///\e 530 template<class T> 531 _Dijkstra<SetPredMapTraits<T> > setPredMap(const T &t) 532 { 533 _Dijkstra<SetPredMapTraits<T> > r; 534 r.G=G; 535 r.length=length; 536 r.predecessor=&t; 537 r.pred_node=pred_node; 538 r.distance=distance; 539 r.source=source; 540 return r; 541 } 542 543 template<class T> 544 struct SetPredNodeMapTraits :public Traits {typedef T PredNodeMap;}; 545 ///\e 546 template<class T> 547 _Dijkstra<SetPredNodeMapTraits<T> > setPredNodeMap(const T &t) 548 { 549 _Dijkstra<SetPredNodeMapTraits<T> > r; 550 r.G=G; 551 r.length=length; 552 r.predecessor=predecessor; 553 r.pred_node=&t; 554 r.distance=distance; 555 r.source=source; 556 return r; 557 } 558 559 template<class T> 560 struct SetDistMapTraits : public Traits {typedef T DistMap;}; 561 ///\e 562 template<class T> 563 _Dijkstra<SetDistMapTraits<T> > setDistMap(const T &t) 564 { 565 _Dijkstra<SetPredMapTraits<T> > r; 566 r.G=G; 567 r.length=length; 568 r.predecessor=predecessor; 569 r.pred_node=pred_node; 570 r.distance=&t; 571 r.source=source; 572 return r; 573 } 574 575 ///\e 576 _Dijkstra<TR> &setSource(Node s) 577 { 578 source=s; 579 return *this; 580 } 581 582 }; 337 583 584 ///\e 585 586 ///\e 587 /// 588 template<class GR, class LM> 589 _Dijkstra<DijkstraDefaultTraits<GR,LM> > 590 dijkstra(const GR &g,const LM &l,typename GR::Node s) 591 { 592 return _Dijkstra<DijkstraDefaultTraits<GR,LM> >(g,l,s); 593 } 594 338 595 /// @} 339 596
Note: See TracChangeset
for help on using the changeset viewer.