Changeset 1116:f97e1cbbd453 in lemon0.x
 Timestamp:
 02/02/05 12:54:55 (15 years ago)
 Branch:
 default
 Phase:
 public
 Convert:
 svn:c9d7d8f590d60310b91f818b3a526b0e/lemon/trunk@1515
 File:

 1 edited
Legend:
 Unmodified
 Added
 Removed

src/work/alpar/dijkstra.h
r1043 r1116 144 144 typename TR=DijkstraDefaultTraits<GR,LM> > 145 145 #endif 146 class Dijkstra {146 class Dijkstra { 147 147 public: 148 148 typedef TR Traits; … … 214 214 215 215 public : 216 216 217 217 template <class T> 218 struct SetPredMapTraits : public Traits {218 struct DefPredMapTraits : public Traits { 219 219 typedef T PredMap; 220 220 ///\todo An exception should be thrown. … … 232 232 /// 233 233 template <class T> 234 class SetPredMap : public Dijkstra< Graph,234 class DefPredMap : public Dijkstra< Graph, 235 235 LengthMap, 236 SetPredMapTraits<T> > { };236 DefPredMapTraits<T> > { }; 237 237 238 238 template <class T> 239 struct SetPredNodeMapTraits : public Traits {239 struct DefPredNodeMapTraits : public Traits { 240 240 typedef T PredNodeMap; 241 241 ///\todo An exception should be thrown. … … 253 253 /// 254 254 template <class T> 255 class SetPredNodeMap : public Dijkstra< Graph,255 class DefPredNodeMap : public Dijkstra< Graph, 256 256 LengthMap, 257 SetPredNodeMapTraits<T> > { };257 DefPredNodeMapTraits<T> > { }; 258 258 259 259 template <class T> 260 struct SetDistMapTraits : public Traits {260 struct DefDistMapTraits : public Traits { 261 261 typedef T DistMap; 262 262 ///\todo An exception should be thrown. … … 274 274 /// 275 275 template <class T> 276 class SetDistMap : public Dijkstra< Graph,276 class DefDistMap : public Dijkstra< Graph, 277 277 LengthMap, 278 SetDistMapTraits<T> > { };278 DefDistMapTraits<T> > { }; 279 279 280 280 ///Constructor. … … 301 301 ///Sets the length map. 302 302 ///\return <tt> (*this) </tt> 303 Dijkstra & setLengthMap(const LengthMap &m)303 Dijkstra &lengthMap(const LengthMap &m) 304 304 { 305 305 length = &m; … … 314 314 ///automatically allocated map, of course. 315 315 ///\return <tt> (*this) </tt> 316 Dijkstra & setPredMap(PredMap &m)316 Dijkstra &predMap(PredMap &m) 317 317 { 318 318 if(local_predecessor) { … … 331 331 ///automatically allocated map, of course. 332 332 ///\return <tt> (*this) </tt> 333 Dijkstra & setPredNodeMap(PredNodeMap &m)333 Dijkstra &predNodeMap(PredNodeMap &m) 334 334 { 335 335 if(local_pred_node) { … … 348 348 ///automatically allocated map, of course. 349 349 ///\return <tt> (*this) </tt> 350 Dijkstra & setDistMap(DistMap &m)350 Dijkstra &distMap(DistMap &m) 351 351 { 352 352 if(local_distance) { … … 474 474 }; 475 475 476 template<class GR,class LM> 477 class DijkstraWizardBase : public DijkstraDefaultTraits<GR,LM> 478 { 479 480 typedef DijkstraDefaultTraits<GR,LM> Base; 481 protected: 482 /// Pointer to the underlying graph. 483 void *_g; 484 /// Pointer to the length map 485 void *_length; 486 ///Pointer to the map of predecessors edges. 487 void *_pred; 488 ///Pointer to the map of predecessors nodes. 489 void *_predNode; 490 ///Pointer to the map of distances. 491 void *_dist; 492 ///Pointer to the source node. 493 void *_source; 494 495 typedef typename Base::Graph::Node Node; 496 497 public: 498 DijkstraWizardBase() : _g(0), _length(0), _pred(0), _predNode(0), 499 _dist(0), _source(INVALID) {} 500 501 DijkstraWizardBase(const GR &g,const LM &l, Node s=INVALID) : 502 _g((void *)&g), _length((void *)&l), _pred(0), _predNode(0), 503 _dist(0), _source((void *)&s) {} 504 505 }; 506 476 507 ///\e 477 508 … … 479 510 /// 480 511 template<class TR> 481 class _Dijkstra512 class DijkstraWizard : public TR 482 513 { 483 typedef TR Traits;514 typedef TR Base; 484 515 485 516 ///The type of the underlying graph. … … 509 540 ///The heap type used by the dijkstra algorithm. 510 541 typedef typename TR::Heap Heap; 511 512 /// Pointer to the underlying graph.513 const Graph *G;514 /// Pointer to the length map515 const LengthMap *length;516 ///Pointer to the map of predecessors edges.517 PredMap *predecessor;518 ///Pointer to the map of predecessors nodes.519 PredNodeMap *pred_node;520 ///Pointer to the map of distances.521 DistMap *distance;522 523 Node source;524 525 542 public: 526 _Dijkstra() : G(0), length(0), predecessor(0), pred_node(0), 527 distance(0), source(INVALID) {} 528 529 _Dijkstra(const Graph &g,const LengthMap &l, Node s) : 530 G(&g), length(&l), predecessor(0), pred_node(0), 531 distance(0), source(s) {} 532 533 ~_Dijkstra() 534 { 535 Dijkstra<Graph,LengthMap,TR> Dij(*G,*length); 536 if(predecessor) Dij.setPredMap(*predecessor); 537 if(pred_node) Dij.setPredNodeMap(*pred_node); 538 if(distance) Dij.setDistMap(*distance); 539 Dij.run(source); 543 DijkstraWizard() : TR() {} 544 545 DijkstraWizard(const Graph &g,const LengthMap &l, Node s=INVALID) : 546 TR(g,l,s) {} 547 548 DijkstraWizard(const TR &b) : TR(b) {} 549 550 ~DijkstraWizard() {} 551 552 ///\e 553 void run() 554 { 555 Dijkstra<Graph,LengthMap,TR> Dij(*(Graph*)_g,*(LengthMap*)_length); 556 if(_pred) Dij.predMap(*(PredMap*)_pred); 557 if(_predNode) Dij.predNodeMap(*(PredNodeMap*)_predNode); 558 if(_dist) Dij.distMap(*(DistMap*)_dist); 559 Dij.run(*(Node*)_source); 560 } 561 562 ///\e 563 void run(Node s) 564 { 565 _source=(void *)&s; 566 run(); 540 567 } 541 568 542 569 template<class T> 543 struct SetPredMapTraits : public Traits {typedef T PredMap;}; 570 struct DefPredMapBase : public Base { 571 typedef T PredMap; 572 static PredMap *createPredMap(const Graph &G) {}; 573 }; 544 574 545 575 ///\e 546 576 template<class T> 547 _Dijkstra<SetPredMapTraits<T> > setPredMap(const T &t) 548 { 549 _Dijkstra<SetPredMapTraits<T> > r; 550 r.G=G; 551 r.length=length; 552 r.predecessor=&t; 553 r.pred_node=pred_node; 554 r.distance=distance; 555 r.source=source; 556 return r; 557 } 558 577 DijkstraWizard<DefPredMapBase<T> > predMap(const T &t) 578 { 579 _pred=(void *)&t; 580 return DijkstraWizard<DefPredMapBase<T> >(*this); 581 } 582 583 559 584 template<class T> 560 struct SetPredNodeMapTraits :public Traits {typedef T PredNodeMap;}; 585 struct DefPredNodeMapBase : public Base { 586 typedef T PredNodeMap; 587 static PredNodeMap *createPredNodeMap(const Graph &G) {}; 588 }; 589 561 590 ///\e 562 591 template<class T> 563 _Dijkstra<SetPredNodeMapTraits<T> > setPredNodeMap(const T &t) 564 { 565 _Dijkstra<SetPredNodeMapTraits<T> > r; 566 r.G=G; 567 r.length=length; 568 r.predecessor=predecessor; 569 r.pred_node=&t; 570 r.distance=distance; 571 r.source=source; 572 return r; 573 } 574 592 DijkstraWizard<DefPredNodeMapBase<T> > predNodeMap(const T &t) 593 { 594 _predNode=(void *)&t; 595 return DijkstraWizard<DefPredNodeMapBase<T> >(*this); 596 } 597 575 598 template<class T> 576 struct SetDistMapTraits : public Traits {typedef T DistMap;}; 599 struct DefDistMapBase : public Base { 600 typedef T DistMap; 601 static DistMap *createDistMap(const Graph &G) {}; 602 }; 603 577 604 ///\e 578 605 template<class T> 579 _Dijkstra<SetDistMapTraits<T> > setDistMap(const T &t) 580 { 581 _Dijkstra<SetPredMapTraits<T> > r; 582 r.G=G; 583 r.length=length; 584 r.predecessor=predecessor; 585 r.pred_node=pred_node; 586 r.distance=&t; 587 r.source=source; 588 return r; 589 } 590 591 ///\e 592 _Dijkstra<TR> &setSource(Node s) 593 { 594 source=s; 606 DijkstraWizard<DefDistMapBase<T> > distMap(const T &t) 607 { 608 _dist=(void *)&t; 609 return DijkstraWizard<DefDistMapBase<T> >(*this); 610 } 611 612 ///\e 613 DijkstraWizard<TR> &setSource(Node s) 614 { 615 source=(void *)&s; 595 616 return *this; 596 617 } … … 603 624 /// 604 625 template<class GR, class LM> 605 _Dijkstra<DijkstraDefaultTraits<GR,LM> >606 dijkstra(const GR &g,const LM &l,typename GR::Node s )626 DijkstraWizard<DijkstraWizardBase<GR,LM> > 627 dijkstra(const GR &g,const LM &l,typename GR::Node s=INVALID) 607 628 { 608 return _Dijkstra<DijkstraDefaultTraits<GR,LM> >(g,l,s);629 return DijkstraWizard<DijkstraWizardBase<GR,LM> >(g,l,s); 609 630 } 610 631
Note: See TracChangeset
for help on using the changeset viewer.