Changeset 625:029a48052c67 in lemon-1.2
- Timestamp:
- 04/26/09 16:44:53 (15 years ago)
- Branch:
- default
- Phase:
- public
- Files:
-
- 2 edited
Legend:
- Unmodified
- Added
- Removed
-
lemon/min_cost_arborescence.h
r584 r625 37 37 /// Default traits class for MinCostArborescence class. 38 38 /// \param GR Digraph type. 39 /// \param CM Type of cost map.39 /// \param CM Type of the cost map. 40 40 template <class GR, class CM> 41 41 struct MinCostArborescenceDefaultTraits{ … … 47 47 /// 48 48 /// The type of the map that stores the arc costs. 49 /// It must meetthe \ref concepts::ReadMap "ReadMap" concept.49 /// It must conform to the \ref concepts::ReadMap "ReadMap" concept. 50 50 typedef CM CostMap; 51 51 … … 59 59 /// 60 60 /// The type of the map that stores which arcs are in the 61 /// arborescence. It must meet the \ref concepts::WriteMap 62 /// "WriteMap" concept. Initially it will be set to false on each 63 /// arc. After it will set all arborescence arcs once. 61 /// arborescence. It must conform to the \ref concepts::WriteMap 62 /// "WriteMap" concept, and its value type must be \c bool 63 /// (or convertible). Initially it will be set to \c false on each 64 /// arc, then it will be set on each arborescence arc once. 64 65 typedef typename Digraph::template ArcMap<bool> ArborescenceMap; 65 66 … … 67 68 /// 68 69 /// This function instantiates a \c ArborescenceMap. 69 /// \param digraph is the graph, to which we would like to70 /// calculatethe \c ArborescenceMap.70 /// \param digraph The digraph to which we would like to calculate 71 /// the \c ArborescenceMap. 71 72 static ArborescenceMap *createArborescenceMap(const Digraph &digraph){ 72 73 return new ArborescenceMap(digraph); … … 75 76 /// \brief The type of the \c PredMap 76 77 /// 77 /// The type of the \c PredMap. It is a node map with an arc value type. 78 /// The type of the \c PredMap. It must confrom to the 79 /// \ref concepts::WriteMap "WriteMap" concept, and its value type 80 /// must be the \c Arc type of the digraph. 78 81 typedef typename Digraph::template NodeMap<typename Digraph::Arc> PredMap; 79 82 … … 93 96 /// \brief Minimum Cost Arborescence algorithm class. 94 97 /// 95 /// This class provides an efficient implementation of 98 /// This class provides an efficient implementation of the 96 99 /// Minimum Cost Arborescence algorithm. The arborescence is a tree 97 100 /// which is directed from a given source node of the digraph. One or 98 /// more sources should be given forthe algorithm and it will calculate99 /// the minimum cost subgraph which are union of arborescences with the101 /// more sources should be given to the algorithm and it will calculate 102 /// the minimum cost subgraph that is the union of arborescences with the 100 103 /// given sources and spans all the nodes which are reachable from the 101 104 /// sources. The time complexity of the algorithm is O(n<sup>2</sup>+e). 102 105 /// 103 /// The algorithm provides alsoan optimal dual solution, therefore106 /// The algorithm also provides an optimal dual solution, therefore 104 107 /// the optimality of the solution can be checked. 105 108 /// 106 /// \param GR The digraph type the algorithm runs on. The default value 107 /// is \ref ListDigraph. 108 /// \param CM This read-only ArcMap determines the costs of the 109 /// \param GR The digraph type the algorithm runs on. 110 /// \param CM A read-only arc map storing the costs of the 109 111 /// arcs. It is read once for each arc, so the map may involve in 110 /// relatively time consuming process to compute the arc cost if112 /// relatively time consuming process to compute the arc costs if 111 113 /// it is necessary. The default map type is \ref 112 114 /// concepts::Digraph::ArcMap "Digraph::ArcMap<int>". … … 114 116 /// by the algorithm. The default traits class is 115 117 /// \ref MinCostArborescenceDefaultTraits 116 /// "MinCostArborescenceDefaultTraits<GR, CM>". See \ref 117 /// MinCostArborescenceDefaultTraits for the documentation of a 118 /// MinCostArborescence traits class. 118 /// "MinCostArborescenceDefaultTraits<GR, CM>". 119 119 #ifndef DOXYGEN 120 template <typename GR = ListDigraph,120 template <typename GR, 121 121 typename CM = typename GR::template ArcMap<int>, 122 122 typename TR = … … 128 128 public: 129 129 130 /// The traits. 130 /// \brief The \ref MinCostArborescenceDefaultTraits "traits class" 131 /// of the algorithm. 131 132 typedef TR Traits; 132 133 /// The type of the underlying digraph. … … 396 397 397 398 template <class T> 398 struct DefArborescenceMapTraits : public Traits {399 struct SetArborescenceMapTraits : public Traits { 399 400 typedef T ArborescenceMap; 400 401 static ArborescenceMap *createArborescenceMap(const Digraph &) … … 406 407 407 408 /// \brief \ref named-templ-param "Named parameter" for 408 /// setting ArborescenceMap type409 /// setting \c ArborescenceMap type 409 410 /// 410 411 /// \ref named-templ-param "Named parameter" for setting 411 /// ArborescenceMap type 412 /// \c ArborescenceMap type. 413 /// It must conform to the \ref concepts::WriteMap "WriteMap" concept, 414 /// and its value type must be \c bool (or convertible). 415 /// Initially it will be set to \c false on each arc, 416 /// then it will be set on each arborescence arc once. 412 417 template <class T> 413 struct DefArborescenceMap418 struct SetArborescenceMap 414 419 : public MinCostArborescence<Digraph, CostMap, 415 DefArborescenceMapTraits<T> > {420 SetArborescenceMapTraits<T> > { 416 421 }; 417 422 418 423 template <class T> 419 struct DefPredMapTraits : public Traits {424 struct SetPredMapTraits : public Traits { 420 425 typedef T PredMap; 421 426 static PredMap *createPredMap(const Digraph &) 422 427 { 423 428 LEMON_ASSERT(false, "PredMap is not initialized"); 429 return 0; // ignore warnings 424 430 } 425 431 }; 426 432 427 433 /// \brief \ref named-templ-param "Named parameter" for 428 /// setting PredMap type434 /// setting \c PredMap type 429 435 /// 430 436 /// \ref named-templ-param "Named parameter" for setting 431 /// PredMap type 437 /// \c PredMap type. 438 /// It must meet the \ref concepts::WriteMap "WriteMap" concept, 439 /// and its value type must be the \c Arc type of the digraph. 432 440 template <class T> 433 struct DefPredMap434 : public MinCostArborescence<Digraph, CostMap, DefPredMapTraits<T> > {441 struct SetPredMap 442 : public MinCostArborescence<Digraph, CostMap, SetPredMapTraits<T> > { 435 443 }; 436 444 … … 465 473 } 466 474 467 /// \brief Sets the arborescencemap.468 /// 469 /// Sets the arborescencemap.475 /// \brief Sets the predecessor map. 476 /// 477 /// Sets the predecessor map. 470 478 /// \return <tt>(*this)</tt> 471 479 MinCostArborescence& predMap(PredMap& m) { … … 477 485 return *this; 478 486 } 479 480 /// \name Query Functions481 /// The result of the %MinCostArborescence algorithm can be obtained482 /// using these functions.\n483 /// Before the use of these functions,484 /// either run() or start() must be called.485 486 /// @{487 488 /// \brief Returns a reference to the arborescence map.489 ///490 /// Returns a reference to the arborescence map.491 const ArborescenceMap& arborescenceMap() const {492 return *_arborescence;493 }494 495 /// \brief Returns true if the arc is in the arborescence.496 ///497 /// Returns true if the arc is in the arborescence.498 /// \param arc The arc of the digraph.499 /// \pre \ref run() must be called before using this function.500 bool arborescence(Arc arc) const {501 return (*_pred)[_digraph->target(arc)] == arc;502 }503 504 /// \brief Returns a reference to the pred map.505 ///506 /// Returns a reference to the pred map.507 const PredMap& predMap() const {508 return *_pred;509 }510 511 /// \brief Returns the predecessor arc of the given node.512 ///513 /// Returns the predecessor arc of the given node.514 Arc pred(Node node) const {515 return (*_pred)[node];516 }517 518 /// \brief Returns the cost of the arborescence.519 ///520 /// Returns the cost of the arborescence.521 Value arborescenceValue() const {522 Value sum = 0;523 for (ArcIt it(*_digraph); it != INVALID; ++it) {524 if (arborescence(it)) {525 sum += (*_cost)[it];526 }527 }528 return sum;529 }530 531 /// \brief Indicates that a node is reachable from the sources.532 ///533 /// Indicates that a node is reachable from the sources.534 bool reached(Node node) const {535 return (*_node_order)[node] != -3;536 }537 538 /// \brief Indicates that a node is processed.539 ///540 /// Indicates that a node is processed. The arborescence path exists541 /// from the source to the given node.542 bool processed(Node node) const {543 return (*_node_order)[node] == -1;544 }545 546 /// \brief Returns the number of the dual variables in basis.547 ///548 /// Returns the number of the dual variables in basis.549 int dualNum() const {550 return _dual_variables.size();551 }552 553 /// \brief Returns the value of the dual solution.554 ///555 /// Returns the value of the dual solution. It should be556 /// equal to the arborescence value.557 Value dualValue() const {558 Value sum = 0;559 for (int i = 0; i < int(_dual_variables.size()); ++i) {560 sum += _dual_variables[i].value;561 }562 return sum;563 }564 565 /// \brief Returns the number of the nodes in the dual variable.566 ///567 /// Returns the number of the nodes in the dual variable.568 int dualSize(int k) const {569 return _dual_variables[k].end - _dual_variables[k].begin;570 }571 572 /// \brief Returns the value of the dual variable.573 ///574 /// Returns the the value of the dual variable.575 const Value& dualValue(int k) const {576 return _dual_variables[k].value;577 }578 579 /// \brief Lemon iterator for get a dual variable.580 ///581 /// Lemon iterator for get a dual variable. This class provides582 /// a common style lemon iterator which gives back a subset of583 /// the nodes.584 class DualIt {585 public:586 587 /// \brief Constructor.588 ///589 /// Constructor for get the nodeset of the variable.590 DualIt(const MinCostArborescence& algorithm, int variable)591 : _algorithm(&algorithm)592 {593 _index = _algorithm->_dual_variables[variable].begin;594 _last = _algorithm->_dual_variables[variable].end;595 }596 597 /// \brief Conversion to node.598 ///599 /// Conversion to node.600 operator Node() const {601 return _algorithm->_dual_node_list[_index];602 }603 604 /// \brief Increment operator.605 ///606 /// Increment operator.607 DualIt& operator++() {608 ++_index;609 return *this;610 }611 612 /// \brief Validity checking613 ///614 /// Checks whether the iterator is invalid.615 bool operator==(Invalid) const {616 return _index == _last;617 }618 619 /// \brief Validity checking620 ///621 /// Checks whether the iterator is valid.622 bool operator!=(Invalid) const {623 return _index != _last;624 }625 626 private:627 const MinCostArborescence* _algorithm;628 int _index, _last;629 };630 631 /// @}632 487 633 488 /// \name Execution Control … … 690 545 /// \return The processed node. 691 546 /// 692 /// \warning The queue must not be empty !547 /// \warning The queue must not be empty. 693 548 Node processNextNode() { 694 549 Node node = queue.back(); … … 713 568 /// \brief Returns the number of the nodes to be processed. 714 569 /// 715 /// Returns the number of the nodes to be processed. 570 /// Returns the number of the nodes to be processed in the priority 571 /// queue. 716 572 int queueSize() const { 717 573 return queue.size(); … … 755 611 /// mca.start(); 756 612 /// \endcode 757 void run(Node node) {613 void run(Node s) { 758 614 init(); 759 addSource( node);615 addSource(s); 760 616 start(); 761 617 } 762 618 763 619 ///@} 620 621 /// \name Query Functions 622 /// The result of the %MinCostArborescence algorithm can be obtained 623 /// using these functions.\n 624 /// Either run() or start() must be called before using them. 625 626 /// @{ 627 628 /// \brief Returns the cost of the arborescence. 629 /// 630 /// Returns the cost of the arborescence. 631 Value arborescenceCost() const { 632 Value sum = 0; 633 for (ArcIt it(*_digraph); it != INVALID; ++it) { 634 if (arborescence(it)) { 635 sum += (*_cost)[it]; 636 } 637 } 638 return sum; 639 } 640 641 /// \brief Returns \c true if the arc is in the arborescence. 642 /// 643 /// Returns \c true if the given arc is in the arborescence. 644 /// \param arc An arc of the digraph. 645 /// \pre \ref run() must be called before using this function. 646 bool arborescence(Arc arc) const { 647 return (*_pred)[_digraph->target(arc)] == arc; 648 } 649 650 /// \brief Returns a const reference to the arborescence map. 651 /// 652 /// Returns a const reference to the arborescence map. 653 /// \pre \ref run() must be called before using this function. 654 const ArborescenceMap& arborescenceMap() const { 655 return *_arborescence; 656 } 657 658 /// \brief Returns the predecessor arc of the given node. 659 /// 660 /// Returns the predecessor arc of the given node. 661 /// \pre \ref run() must be called before using this function. 662 Arc pred(Node node) const { 663 return (*_pred)[node]; 664 } 665 666 /// \brief Returns a const reference to the pred map. 667 /// 668 /// Returns a const reference to the pred map. 669 /// \pre \ref run() must be called before using this function. 670 const PredMap& predMap() const { 671 return *_pred; 672 } 673 674 /// \brief Indicates that a node is reachable from the sources. 675 /// 676 /// Indicates that a node is reachable from the sources. 677 bool reached(Node node) const { 678 return (*_node_order)[node] != -3; 679 } 680 681 /// \brief Indicates that a node is processed. 682 /// 683 /// Indicates that a node is processed. The arborescence path exists 684 /// from the source to the given node. 685 bool processed(Node node) const { 686 return (*_node_order)[node] == -1; 687 } 688 689 /// \brief Returns the number of the dual variables in basis. 690 /// 691 /// Returns the number of the dual variables in basis. 692 int dualNum() const { 693 return _dual_variables.size(); 694 } 695 696 /// \brief Returns the value of the dual solution. 697 /// 698 /// Returns the value of the dual solution. It should be 699 /// equal to the arborescence value. 700 Value dualValue() const { 701 Value sum = 0; 702 for (int i = 0; i < int(_dual_variables.size()); ++i) { 703 sum += _dual_variables[i].value; 704 } 705 return sum; 706 } 707 708 /// \brief Returns the number of the nodes in the dual variable. 709 /// 710 /// Returns the number of the nodes in the dual variable. 711 int dualSize(int k) const { 712 return _dual_variables[k].end - _dual_variables[k].begin; 713 } 714 715 /// \brief Returns the value of the dual variable. 716 /// 717 /// Returns the the value of the dual variable. 718 Value dualValue(int k) const { 719 return _dual_variables[k].value; 720 } 721 722 /// \brief LEMON iterator for getting a dual variable. 723 /// 724 /// This class provides a common style LEMON iterator for getting a 725 /// dual variable of \ref MinCostArborescence algorithm. 726 /// It iterates over a subset of the nodes. 727 class DualIt { 728 public: 729 730 /// \brief Constructor. 731 /// 732 /// Constructor for getting the nodeset of the dual variable 733 /// of \ref MinCostArborescence algorithm. 734 DualIt(const MinCostArborescence& algorithm, int variable) 735 : _algorithm(&algorithm) 736 { 737 _index = _algorithm->_dual_variables[variable].begin; 738 _last = _algorithm->_dual_variables[variable].end; 739 } 740 741 /// \brief Conversion to \c Node. 742 /// 743 /// Conversion to \c Node. 744 operator Node() const { 745 return _algorithm->_dual_node_list[_index]; 746 } 747 748 /// \brief Increment operator. 749 /// 750 /// Increment operator. 751 DualIt& operator++() { 752 ++_index; 753 return *this; 754 } 755 756 /// \brief Validity checking 757 /// 758 /// Checks whether the iterator is invalid. 759 bool operator==(Invalid) const { 760 return _index == _last; 761 } 762 763 /// \brief Validity checking 764 /// 765 /// Checks whether the iterator is valid. 766 bool operator!=(Invalid) const { 767 return _index != _last; 768 } 769 770 private: 771 const MinCostArborescence* _algorithm; 772 int _index, _last; 773 }; 774 775 /// @} 764 776 765 777 }; … … 770 782 /// 771 783 /// Function type interface for MinCostArborescence algorithm. 772 /// \param digraph The Digraph that the algorithm runs on. 773 /// \param cost The CostMap of the arcs. 774 /// \param source The source of the arborescence. 775 /// \retval arborescence The bool ArcMap which stores the arborescence. 776 /// \return The cost of the arborescence. 784 /// \param digraph The digraph the algorithm runs on. 785 /// \param cost An arc map storing the costs. 786 /// \param source The source node of the arborescence. 787 /// \retval arborescence An arc map with \c bool (or convertible) value 788 /// type that stores the arborescence. 789 /// \return The total cost of the arborescence. 777 790 /// 778 791 /// \sa MinCostArborescence … … 783 796 ArborescenceMap& arborescence) { 784 797 typename MinCostArborescence<Digraph, CostMap> 785 ::template DefArborescenceMap<ArborescenceMap>798 ::template SetArborescenceMap<ArborescenceMap> 786 799 ::Create mca(digraph, cost); 787 800 mca.arborescenceMap(arborescence); 788 801 mca.run(source); 789 return mca.arborescence Value();802 return mca.arborescenceCost(); 790 803 } 791 804 -
test/min_cost_arborescence_test.cc
r490 r625 25 25 #include <lemon/min_cost_arborescence.h> 26 26 #include <lemon/lgf_reader.h> 27 #include <lemon/concepts/digraph.h> 27 28 28 29 #include "test_tools.h" … … 71 72 "source 0\n"; 72 73 74 75 void checkMinCostArborescenceCompile() 76 { 77 typedef double VType; 78 typedef concepts::Digraph Digraph; 79 typedef concepts::ReadMap<Digraph::Arc, VType> CostMap; 80 typedef Digraph::Node Node; 81 typedef Digraph::Arc Arc; 82 typedef concepts::WriteMap<Digraph::Arc, bool> ArbMap; 83 typedef concepts::ReadWriteMap<Digraph::Node, Digraph::Arc> PredMap; 84 85 typedef MinCostArborescence<Digraph, CostMap>:: 86 SetArborescenceMap<ArbMap>:: 87 SetPredMap<PredMap>::Create MinCostArbType; 88 89 Digraph g; 90 Node s, n; 91 Arc e; 92 VType c; 93 bool b; 94 int i; 95 CostMap cost; 96 ArbMap arb; 97 PredMap pred; 98 99 MinCostArbType mcarb_test(g, cost); 100 const MinCostArbType& const_mcarb_test = mcarb_test; 101 102 mcarb_test 103 .arborescenceMap(arb) 104 .predMap(pred) 105 .run(s); 106 107 mcarb_test.init(); 108 mcarb_test.addSource(s); 109 mcarb_test.start(); 110 n = mcarb_test.processNextNode(); 111 b = const_mcarb_test.emptyQueue(); 112 i = const_mcarb_test.queueSize(); 113 114 c = const_mcarb_test.arborescenceCost(); 115 b = const_mcarb_test.arborescence(e); 116 e = const_mcarb_test.pred(n); 117 const MinCostArbType::ArborescenceMap &am = 118 const_mcarb_test.arborescenceMap(); 119 const MinCostArbType::PredMap &pm = 120 const_mcarb_test.predMap(); 121 b = const_mcarb_test.reached(n); 122 b = const_mcarb_test.processed(n); 123 124 i = const_mcarb_test.dualNum(); 125 c = const_mcarb_test.dualValue(); 126 i = const_mcarb_test.dualSize(i); 127 c = const_mcarb_test.dualValue(i); 128 129 ignore_unused_variable_warning(am); 130 ignore_unused_variable_warning(pm); 131 } 132 73 133 int main() { 74 134 typedef SmartDigraph Digraph; … … 111 171 } 112 172 if (mca.arborescence(it)) { 113 check(sum == cost[it], "I NVALID DUAL");173 check(sum == cost[it], "Invalid dual solution"); 114 174 } 115 check(sum <= cost[it], "I NVALID DUAL");175 check(sum <= cost[it], "Invalid dual solution"); 116 176 } 117 177 } 118 178 119 179 120 check(mca.dualValue() == mca.arborescence Value(), "INVALID DUAL");121 122 check(mca.reached(source), "I NVALID ARBORESCENCE");180 check(mca.dualValue() == mca.arborescenceCost(), "Invalid dual solution"); 181 182 check(mca.reached(source), "Invalid arborescence"); 123 183 for (ArcIt a(digraph); a != INVALID; ++a) { 124 184 check(!mca.reached(digraph.source(a)) || 125 mca.reached(digraph.target(a)), "I NVALID ARBORESCENCE");185 mca.reached(digraph.target(a)), "Invalid arborescence"); 126 186 } 127 187 … … 131 191 for (InArcIt a(digraph, n); a != INVALID; ++a) { 132 192 if (mca.arborescence(a)) { 133 check(mca.pred(n) == a, "I NVALID ARBORESCENCE");193 check(mca.pred(n) == a, "Invalid arborescence"); 134 194 ++cnt; 135 195 } 136 196 } 137 check((n == source ? cnt == 0 : cnt == 1), "I NVALID ARBORESCENCE");197 check((n == source ? cnt == 0 : cnt == 1), "Invalid arborescence"); 138 198 } 139 199 140 200 Digraph::ArcMap<bool> arborescence(digraph); 141 check(mca.arborescence Value() ==201 check(mca.arborescenceCost() == 142 202 minCostArborescence(digraph, cost, source, arborescence), 143 "W RONG FUNCTION");203 "Wrong result of the function interface"); 144 204 145 205 return 0;
Note: See TracChangeset
for help on using the changeset viewer.