Changeset 1123:a2e93889a604 in lemon0.x
 Timestamp:
 02/04/05 16:32:11 (20 years ago)
 Branch:
 default
 Phase:
 public
 Convert:
 svn:c9d7d8f590d60310b91f818b3a526b0e/lemon/trunk@1522
 File:

 1 edited
Legend:
 Unmodified
 Added
 Removed

src/work/alpar/dijkstra.h
r1119 r1123 73 73 ///Instantiates a PredMap. 74 74 75 ///\todo Please document... 75 ///This function instantiates a \ref PredMap. 76 ///\param G is the graph, to which we would like to define the PredMap. 76 77 ///\todo The graph alone may be insufficient for the initialization 77 78 static PredMap *createPredMap(const GR &G) … … 87 88 ///Instantiates a PredNodeMap. 88 89 89 /// \todo Please document...90 /// 90 ///This function instantiates a \ref PredNodeMap. 91 ///\param G is the graph, to which we would like to define the \ref PredNodeMap 91 92 static PredNodeMap *createPredNodeMap(const GR &G) 92 93 { … … 103 104 ///Instantiates a ReachedMap. 104 105 105 /// \todo Please document...106 /// 106 ///This function instantiates a \ref ReachedMap. 107 ///\param G is the graph, to which we would like to define the \ref ReachedMap 107 108 static ReachedMap *createReachedMap(const GR &G) 108 109 { … … 116 117 ///Instantiates a DistMap. 117 118 118 /// \todo Please document...119 /// 119 ///This function instantiates a \ref DistMap. 120 ///\param G is the graph, to which we would like to define the \ref DistMap 120 121 static DistMap *createDistMap(const GR &G) 121 122 { … … 507 508 }; 508 509 510 /// Default traits used by \ref DijkstraWizard 511 512 /// To make it easier to use Dijkstra algorithm we created a wizard class. 513 /// This \ref DijkstraWizard class also needs default traits. 514 /// The \ref DijkstraWizardBase is a class to be the default traits of the 515 /// \ref DijkstraWizard class. 509 516 template<class GR,class LM> 510 517 class DijkstraWizardBase : public DijkstraDefaultTraits<GR,LM> … … 526 533 void *_source; 527 534 535 /// Type of the nodes in the graph. 528 536 typedef typename Base::Graph::Node Node; 529 537 530 538 public: 539 /// Constructor. 540 541 /// This constructor does not require parameters, therefore it initiates 542 /// all of the attributes to default values (0, INVALID). 531 543 DijkstraWizardBase() : _g(0), _length(0), _pred(0), _predNode(0), 532 544 _dist(0), _source(INVALID) {} 533 545 546 /// Constructor. 547 548 /// This constructor requires some parameters, listed in the parameters list. 549 /// Others are initiated to 0. 550 /// \param g is the initial value of \ref _g 551 /// \param l is the initial value of \ref _length 552 /// \param s is the initial value of \ref _source 534 553 DijkstraWizardBase(const GR &g,const LM &l, Node s=INVALID) : 535 554 _g((void *)&g), _length((void *)&l), _pred(0), _predNode(0), … … 538 557 }; 539 558 540 ///\e 541 542 ///\e 559 /// A class to make easier the usage of Dijkstra algorithm 560 561 /// This class is created to make it easier to use Dijkstra algorithm. 562 /// It uses the functions and features of the plain \ref Dijkstra, 563 /// but it is much more simple to use it. 543 564 /// 565 /// Simplicity means that the way to change the types defined 566 /// in the traits class is based on functions that returns the new class 567 /// and not on templatable builtin classes. When using the plain \Dijkstra 568 /// the new class with the modified type comes from the original by using the :: 569 /// operator. In this case only a function have to be called and it will 570 /// return the needed class. 571 /// 572 /// It does not have own \ref run method. When its \ref run method is called 573 /// it initiates a plain \ref Dijkstra class, and calls the \ref Dijkstra::run 574 /// method of it. 544 575 template<class TR> 545 576 class DijkstraWizard : public TR … … 547 578 typedef TR Base; 548 579 549 // The type of the underlying graph.580 ///The type of the underlying graph. 550 581 typedef typename TR::Graph Graph; 551 582 //\e … … 558 589 typedef typename Graph::OutEdgeIt OutEdgeIt; 559 590 560 // The type of the map that stores the edge lengths.591 ///The type of the map that stores the edge lengths. 561 592 typedef typename TR::LengthMap LengthMap; 562 // The type of the length of the edges.593 ///The type of the length of the edges. 563 594 typedef typename LengthMap::Value Value; 564 // \brief The type of the map that stores the last565 // edges of the shortest paths.595 ///\brief The type of the map that stores the last 596 ///edges of the shortest paths. 566 597 typedef typename TR::PredMap PredMap; 567 // \brief The type of the map that stores the last but one568 // nodes of the shortest paths.598 ///\brief The type of the map that stores the last but one 599 ///nodes of the shortest paths. 569 600 typedef typename TR::PredNodeMap PredNodeMap; 570 // The type of the map that stores the dists of the nodes.601 ///The type of the map that stores the dists of the nodes. 571 602 typedef typename TR::DistMap DistMap; 572 603 573 // The heap type used by the dijkstra algorithm.604 ///The heap type used by the dijkstra algorithm. 574 605 typedef typename TR::Heap Heap; 575 606 public: 607 /// Constructor. 576 608 DijkstraWizard() : TR() {} 577 609 610 /// Constructor that requires parameters. 611 /// These parameters will be the default values for the traits class. 578 612 DijkstraWizard(const Graph &g,const LengthMap &l, Node s=INVALID) : 579 613 TR(g,l,s) {} 580 614 615 ///Copy constructor 581 616 DijkstraWizard(const TR &b) : TR(b) {} 582 617 583 618 ~DijkstraWizard() {} 584 619 585 ///\e 620 ///Runs Dijkstra algorithm from a given node. 621 622 ///Runs Dijkstra algorithm from a given node. 623 ///The node can be given by the \ref source function. 586 624 void run() 587 625 { … … 594 632 } 595 633 596 ///\e 634 ///Runs Dijkstra algorithm from a given node. 635 636 ///Runs Dijkstra algorithm from a given node. 637 ///\param s is the given source. 597 638 void run(Node s) 598 639 { … … 608 649 }; 609 650 610 ///\e 651 /// \ref namedtemplparam "Named parameter" function for setting PredMap type 652 653 /// \ref namedtemplparam "Named parameter" function for setting PredMap type 611 654 template<class T> 612 655 DijkstraWizard<DefPredMapBase<T> > predMap(const T &t) … … 624 667 }; 625 668 626 ///\e 669 /// \ref namedtemplparam "Named parameter" function for setting PredNodeMap type 670 671 /// \ref namedtemplparam "Named parameter" function for setting PredNodeMap type 627 672 template<class T> 628 673 DijkstraWizard<DefPredNodeMapBase<T> > predNodeMap(const T &t) … … 639 684 }; 640 685 641 ///\e 686 /// \ref namedtemplparam "Named parameter" function for setting DistMap type 687 688 /// \ref namedtemplparam "Named parameter" function for setting DistMap type 642 689 template<class T> 643 690 DijkstraWizard<DefDistMapBase<T> > distMap(const T &t) … … 647 694 } 648 695 649 ///\e 696 /// Sets the source node, from which the Dijkstra algorithm runs. 697 698 /// Sets the source node, from which the Dijkstra algorithm runs. 699 /// \param s is the source node. 650 700 DijkstraWizard<TR> &source(Node s) 651 701 {
Note: See TracChangeset
for help on using the changeset viewer.