Changeset 652:5232721b3f14 in lemon
- Timestamp:
- 03/25/09 15:58:44 (16 years ago)
- Branch:
- default
- Phase:
- public
- Files:
-
- 3 edited
Legend:
- Unmodified
- Added
- Removed
-
lemon/network_simplex.h
r651 r652 23 23 /// 24 24 /// \file 25 /// \brief Network simplex algorithm for finding a minimum cost flow.25 /// \brief Network Simplex algorithm for finding a minimum cost flow. 26 26 27 27 #include <vector> … … 37 37 /// @{ 38 38 39 /// \brief Implementation of the primal network simplex algorithm39 /// \brief Implementation of the primal Network Simplex algorithm 40 40 /// for finding a \ref min_cost_flow "minimum cost flow". 41 41 /// 42 /// \ref NetworkSimplex implements the primal network simplex algorithm42 /// \ref NetworkSimplex implements the primal Network Simplex algorithm 43 43 /// for finding a \ref min_cost_flow "minimum cost flow". 44 44 /// 45 /// \tparam Digraph The digraph type the algorithm runs on. 46 /// \tparam LowerMap The type of the lower bound map. 47 /// \tparam CapacityMap The type of the capacity (upper bound) map. 48 /// \tparam CostMap The type of the cost (length) map. 49 /// \tparam SupplyMap The type of the supply map. 45 /// \tparam GR The digraph type the algorithm runs on. 46 /// \tparam V The value type used in the algorithm. 47 /// By default it is \c int. 50 48 /// 51 /// \warning 52 /// - Arc capacities and costs should be \e non-negative \e integers. 53 /// - Supply values should be \e signed \e integers. 54 /// - The value types of the maps should be convertible to each other. 55 /// - \c CostMap::Value must be signed type. 49 /// \warning \c V must be a signed integer type. 56 50 /// 57 /// \note \ref NetworkSimplex provides five different pivot rule 58 /// implementations that significantly affect the efficiency of the 59 /// algorithm. 60 /// By default "Block Search" pivot rule is used, which proved to be 61 /// by far the most efficient according to our benchmark tests. 62 /// However another pivot rule can be selected using \ref run() 63 /// function with the proper parameter. 64 #ifdef DOXYGEN 65 template < typename Digraph, 66 typename LowerMap, 67 typename CapacityMap, 68 typename CostMap, 69 typename SupplyMap > 70 71 #else 72 template < typename Digraph, 73 typename LowerMap = typename Digraph::template ArcMap<int>, 74 typename CapacityMap = typename Digraph::template ArcMap<int>, 75 typename CostMap = typename Digraph::template ArcMap<int>, 76 typename SupplyMap = typename Digraph::template NodeMap<int> > 77 #endif 51 /// \note %NetworkSimplex provides five different pivot rule 52 /// implementations. For more information see \ref PivotRule. 53 template <typename GR, typename V = int> 78 54 class NetworkSimplex 79 55 { 80 TEMPLATE_DIGRAPH_TYPEDEFS(Digraph); 81 82 typedef typename CapacityMap::Value Capacity; 83 typedef typename CostMap::Value Cost; 84 typedef typename SupplyMap::Value Supply; 56 public: 57 58 /// The value type of the algorithm 59 typedef V Value; 60 /// The type of the flow map 61 typedef typename GR::template ArcMap<Value> FlowMap; 62 /// The type of the potential map 63 typedef typename GR::template NodeMap<Value> PotentialMap; 64 65 public: 66 67 /// \brief Enum type for selecting the pivot rule. 68 /// 69 /// Enum type for selecting the pivot rule for the \ref run() 70 /// function. 71 /// 72 /// \ref NetworkSimplex provides five different pivot rule 73 /// implementations that significantly affect the running time 74 /// of the algorithm. 75 /// By default \ref BLOCK_SEARCH "Block Search" is used, which 76 /// proved to be the most efficient and the most robust on various 77 /// test inputs according to our benchmark tests. 78 /// However another pivot rule can be selected using the \ref run() 79 /// function with the proper parameter. 80 enum PivotRule { 81 82 /// The First Eligible pivot rule. 83 /// The next eligible arc is selected in a wraparound fashion 84 /// in every iteration. 85 FIRST_ELIGIBLE, 86 87 /// The Best Eligible pivot rule. 88 /// The best eligible arc is selected in every iteration. 89 BEST_ELIGIBLE, 90 91 /// The Block Search pivot rule. 92 /// A specified number of arcs are examined in every iteration 93 /// in a wraparound fashion and the best eligible arc is selected 94 /// from this block. 95 BLOCK_SEARCH, 96 97 /// The Candidate List pivot rule. 98 /// In a major iteration a candidate list is built from eligible arcs 99 /// in a wraparound fashion and in the following minor iterations 100 /// the best eligible arc is selected from this list. 101 CANDIDATE_LIST, 102 103 /// The Altering Candidate List pivot rule. 104 /// It is a modified version of the Candidate List method. 105 /// It keeps only the several best eligible arcs from the former 106 /// candidate list and extends this list in every iteration. 107 ALTERING_LIST 108 }; 109 110 private: 111 112 TEMPLATE_DIGRAPH_TYPEDEFS(GR); 113 114 typedef typename GR::template ArcMap<Value> ValueArcMap; 115 typedef typename GR::template NodeMap<Value> ValueNodeMap; 85 116 86 117 typedef std::vector<Arc> ArcVector; … … 88 119 typedef std::vector<int> IntVector; 89 120 typedef std::vector<bool> BoolVector; 90 typedef std::vector<Capacity> CapacityVector; 91 typedef std::vector<Cost> CostVector; 92 typedef std::vector<Supply> SupplyVector; 93 94 public: 95 96 /// The type of the flow map 97 typedef typename Digraph::template ArcMap<Capacity> FlowMap; 98 /// The type of the potential map 99 typedef typename Digraph::template NodeMap<Cost> PotentialMap; 100 101 public: 102 103 /// Enum type for selecting the pivot rule used by \ref run() 104 enum PivotRuleEnum { 105 FIRST_ELIGIBLE_PIVOT, 106 BEST_ELIGIBLE_PIVOT, 107 BLOCK_SEARCH_PIVOT, 108 CANDIDATE_LIST_PIVOT, 109 ALTERING_LIST_PIVOT 110 }; 111 112 private: 121 typedef std::vector<Value> ValueVector; 113 122 114 123 // State constants for arcs … … 121 130 private: 122 131 123 // References for the original data 124 const Digraph &_graph; 125 const LowerMap *_orig_lower; 126 const CapacityMap &_orig_cap; 127 const CostMap &_orig_cost; 128 const SupplyMap *_orig_supply; 129 Node _orig_source; 130 Node _orig_target; 131 Capacity _orig_flow_value; 132 // Data related to the underlying digraph 133 const GR &_graph; 134 int _node_num; 135 int _arc_num; 136 137 // Parameters of the problem 138 ValueArcMap *_plower; 139 ValueArcMap *_pupper; 140 ValueArcMap *_pcost; 141 ValueNodeMap *_psupply; 142 bool _pstsup; 143 Node _psource, _ptarget; 144 Value _pstflow; 132 145 133 146 // Result maps … … 137 150 bool _local_potential; 138 151 139 // The number of nodes and arcs in the original graph 140 int _node_num; 141 int _arc_num; 142 143 // Data structures for storing the graph 152 // Data structures for storing the digraph 144 153 IntNodeMap _node_id; 145 154 ArcVector _arc_ref; … … 147 156 IntVector _target; 148 157 149 // Node and arc maps150 CapacityVector _cap;151 CostVector _cost;152 CostVector _supply;153 CapacityVector _flow;154 CostVector _pi;158 // Node and arc data 159 ValueVector _cap; 160 ValueVector _cost; 161 ValueVector _supply; 162 ValueVector _flow; 163 ValueVector _pi; 155 164 156 165 // Data for storing the spanning tree structure … … 170 179 int first, second, right, last; 171 180 int stem, par_stem, new_stem; 172 Capacitydelta;181 Value delta; 173 182 174 183 private: 175 184 176 /// \brief Implementation of the "First Eligible" pivot rule for the 177 /// \ref NetworkSimplex "network simplex" algorithm. 178 /// 179 /// This class implements the "First Eligible" pivot rule 180 /// for the \ref NetworkSimplex "network simplex" algorithm. 181 /// 182 /// For more information see \ref NetworkSimplex::run(). 185 // Implementation of the First Eligible pivot rule 183 186 class FirstEligiblePivotRule 184 187 { … … 188 191 const IntVector &_source; 189 192 const IntVector &_target; 190 const CostVector &_cost;193 const ValueVector &_cost; 191 194 const IntVector &_state; 192 const CostVector &_pi;195 const ValueVector &_pi; 193 196 int &_in_arc; 194 197 int _arc_num; … … 199 202 public: 200 203 201 // /Constructor204 // Constructor 202 205 FirstEligiblePivotRule(NetworkSimplex &ns) : 203 206 _source(ns._source), _target(ns._target), … … 206 209 {} 207 210 208 // /Find next entering arc211 // Find next entering arc 209 212 bool findEnteringArc() { 210 Costc;213 Value c; 211 214 for (int e = _next_arc; e < _arc_num; ++e) { 212 215 c = _state[e] * (_cost[e] + _pi[_source[e]] - _pi[_target[e]]); … … 231 234 232 235 233 /// \brief Implementation of the "Best Eligible" pivot rule for the 234 /// \ref NetworkSimplex "network simplex" algorithm. 235 /// 236 /// This class implements the "Best Eligible" pivot rule 237 /// for the \ref NetworkSimplex "network simplex" algorithm. 238 /// 239 /// For more information see \ref NetworkSimplex::run(). 236 // Implementation of the Best Eligible pivot rule 240 237 class BestEligiblePivotRule 241 238 { … … 245 242 const IntVector &_source; 246 243 const IntVector &_target; 247 const CostVector &_cost;244 const ValueVector &_cost; 248 245 const IntVector &_state; 249 const CostVector &_pi;246 const ValueVector &_pi; 250 247 int &_in_arc; 251 248 int _arc_num; … … 253 250 public: 254 251 255 // /Constructor252 // Constructor 256 253 BestEligiblePivotRule(NetworkSimplex &ns) : 257 254 _source(ns._source), _target(ns._target), … … 260 257 {} 261 258 262 // /Find next entering arc259 // Find next entering arc 263 260 bool findEnteringArc() { 264 Costc, min = 0;261 Value c, min = 0; 265 262 for (int e = 0; e < _arc_num; ++e) { 266 263 c = _state[e] * (_cost[e] + _pi[_source[e]] - _pi[_target[e]]); … … 276 273 277 274 278 /// \brief Implementation of the "Block Search" pivot rule for the 279 /// \ref NetworkSimplex "network simplex" algorithm. 280 /// 281 /// This class implements the "Block Search" pivot rule 282 /// for the \ref NetworkSimplex "network simplex" algorithm. 283 /// 284 /// For more information see \ref NetworkSimplex::run(). 275 // Implementation of the Block Search pivot rule 285 276 class BlockSearchPivotRule 286 277 { … … 290 281 const IntVector &_source; 291 282 const IntVector &_target; 292 const CostVector &_cost;283 const ValueVector &_cost; 293 284 const IntVector &_state; 294 const CostVector &_pi;285 const ValueVector &_pi; 295 286 int &_in_arc; 296 287 int _arc_num; … … 302 293 public: 303 294 304 // /Constructor295 // Constructor 305 296 BlockSearchPivotRule(NetworkSimplex &ns) : 306 297 _source(ns._source), _target(ns._target), … … 316 307 } 317 308 318 // /Find next entering arc309 // Find next entering arc 319 310 bool findEnteringArc() { 320 Costc, min = 0;311 Value c, min = 0; 321 312 int cnt = _block_size; 322 313 int e, min_arc = _next_arc; … … 354 345 355 346 356 /// \brief Implementation of the "Candidate List" pivot rule for the 357 /// \ref NetworkSimplex "network simplex" algorithm. 358 /// 359 /// This class implements the "Candidate List" pivot rule 360 /// for the \ref NetworkSimplex "network simplex" algorithm. 361 /// 362 /// For more information see \ref NetworkSimplex::run(). 347 // Implementation of the Candidate List pivot rule 363 348 class CandidateListPivotRule 364 349 { … … 368 353 const IntVector &_source; 369 354 const IntVector &_target; 370 const CostVector &_cost;355 const ValueVector &_cost; 371 356 const IntVector &_state; 372 const CostVector &_pi;357 const ValueVector &_pi; 373 358 int &_in_arc; 374 359 int _arc_num; … … 404 389 /// Find next entering arc 405 390 bool findEnteringArc() { 406 Costmin, c;391 Value min, c; 407 392 int e, min_arc = _next_arc; 408 393 if (_curr_length > 0 && _minor_count < _minor_limit) { … … 465 450 466 451 467 /// \brief Implementation of the "Altering Candidate List" pivot rule 468 /// for the \ref NetworkSimplex "network simplex" algorithm. 469 /// 470 /// This class implements the "Altering Candidate List" pivot rule 471 /// for the \ref NetworkSimplex "network simplex" algorithm. 472 /// 473 /// For more information see \ref NetworkSimplex::run(). 452 // Implementation of the Altering Candidate List pivot rule 474 453 class AlteringListPivotRule 475 454 { … … 479 458 const IntVector &_source; 480 459 const IntVector &_target; 481 const CostVector &_cost;460 const ValueVector &_cost; 482 461 const IntVector &_state; 483 const CostVector &_pi;462 const ValueVector &_pi; 484 463 int &_in_arc; 485 464 int _arc_num; … … 489 468 int _next_arc; 490 469 IntVector _candidates; 491 CostVector _cand_cost;470 ValueVector _cand_cost; 492 471 493 472 // Functor class to compare arcs during sort of the candidate list … … 495 474 { 496 475 private: 497 const CostVector &_map;476 const ValueVector &_map; 498 477 public: 499 SortFunc(const CostVector &map) : _map(map) {}478 SortFunc(const ValueVector &map) : _map(map) {} 500 479 bool operator()(int left, int right) { 501 480 return _map[left] > _map[right]; … … 507 486 public: 508 487 509 // /Constructor488 // Constructor 510 489 AlteringListPivotRule(NetworkSimplex &ns) : 511 490 _source(ns._source), _target(ns._target), … … 528 507 } 529 508 530 // /Find next entering arc509 // Find next entering arc 531 510 bool findEnteringArc() { 532 511 // Check the current candidate list … … 593 572 public: 594 573 595 /// \brief General constructor (with lower bounds).596 /// 597 /// General constructor (with lower bounds).574 /// \brief Constructor. 575 /// 576 /// Constructor. 598 577 /// 599 578 /// \param graph The digraph the algorithm runs on. 600 /// \param lower The lower bounds of the arcs. 601 /// \param capacity The capacities (upper bounds) of the arcs. 602 /// \param cost The cost (length) values of the arcs. 603 /// \param supply The supply values of the nodes (signed). 604 NetworkSimplex( const Digraph &graph, 605 const LowerMap &lower, 606 const CapacityMap &capacity, 607 const CostMap &cost, 608 const SupplyMap &supply ) : 609 _graph(graph), _orig_lower(&lower), _orig_cap(capacity), 610 _orig_cost(cost), _orig_supply(&supply), 579 NetworkSimplex(const GR& graph) : 580 _graph(graph), 581 _plower(NULL), _pupper(NULL), _pcost(NULL), 582 _psupply(NULL), _pstsup(false), 611 583 _flow_map(NULL), _potential_map(NULL), 612 584 _local_flow(false), _local_potential(false), 613 585 _node_id(graph) 614 {} 615 616 /// \brief General constructor (without lower bounds). 617 /// 618 /// General constructor (without lower bounds). 619 /// 620 /// \param graph The digraph the algorithm runs on. 621 /// \param capacity The capacities (upper bounds) of the arcs. 622 /// \param cost The cost (length) values of the arcs. 623 /// \param supply The supply values of the nodes (signed). 624 NetworkSimplex( const Digraph &graph, 625 const CapacityMap &capacity, 626 const CostMap &cost, 627 const SupplyMap &supply ) : 628 _graph(graph), _orig_lower(NULL), _orig_cap(capacity), 629 _orig_cost(cost), _orig_supply(&supply), 630 _flow_map(NULL), _potential_map(NULL), 631 _local_flow(false), _local_potential(false), 632 _node_id(graph) 633 {} 634 635 /// \brief Simple constructor (with lower bounds). 636 /// 637 /// Simple constructor (with lower bounds). 638 /// 639 /// \param graph The digraph the algorithm runs on. 640 /// \param lower The lower bounds of the arcs. 641 /// \param capacity The capacities (upper bounds) of the arcs. 642 /// \param cost The cost (length) values of the arcs. 643 /// \param s The source node. 644 /// \param t The target node. 645 /// \param flow_value The required amount of flow from node \c s 646 /// to node \c t (i.e. the supply of \c s and the demand of \c t). 647 NetworkSimplex( const Digraph &graph, 648 const LowerMap &lower, 649 const CapacityMap &capacity, 650 const CostMap &cost, 651 Node s, Node t, 652 Capacity flow_value ) : 653 _graph(graph), _orig_lower(&lower), _orig_cap(capacity), 654 _orig_cost(cost), _orig_supply(NULL), 655 _orig_source(s), _orig_target(t), _orig_flow_value(flow_value), 656 _flow_map(NULL), _potential_map(NULL), 657 _local_flow(false), _local_potential(false), 658 _node_id(graph) 659 {} 660 661 /// \brief Simple constructor (without lower bounds). 662 /// 663 /// Simple constructor (without lower bounds). 664 /// 665 /// \param graph The digraph the algorithm runs on. 666 /// \param capacity The capacities (upper bounds) of the arcs. 667 /// \param cost The cost (length) values of the arcs. 668 /// \param s The source node. 669 /// \param t The target node. 670 /// \param flow_value The required amount of flow from node \c s 671 /// to node \c t (i.e. the supply of \c s and the demand of \c t). 672 NetworkSimplex( const Digraph &graph, 673 const CapacityMap &capacity, 674 const CostMap &cost, 675 Node s, Node t, 676 Capacity flow_value ) : 677 _graph(graph), _orig_lower(NULL), _orig_cap(capacity), 678 _orig_cost(cost), _orig_supply(NULL), 679 _orig_source(s), _orig_target(t), _orig_flow_value(flow_value), 680 _flow_map(NULL), _potential_map(NULL), 681 _local_flow(false), _local_potential(false), 682 _node_id(graph) 683 {} 586 { 587 LEMON_ASSERT(std::numeric_limits<Value>::is_integer && 588 std::numeric_limits<Value>::is_signed, 589 "The value type of NetworkSimplex must be a signed integer"); 590 } 684 591 685 592 /// Destructor. … … 689 596 } 690 597 598 /// \brief Set the lower bounds on the arcs. 599 /// 600 /// This function sets the lower bounds on the arcs. 601 /// If neither this function nor \ref boundMaps() is used before 602 /// calling \ref run(), the lower bounds will be set to zero 603 /// on all arcs. 604 /// 605 /// \param map An arc map storing the lower bounds. 606 /// Its \c Value type must be convertible to the \c Value type 607 /// of the algorithm. 608 /// 609 /// \return <tt>(*this)</tt> 610 template <typename LOWER> 611 NetworkSimplex& lowerMap(const LOWER& map) { 612 delete _plower; 613 _plower = new ValueArcMap(_graph); 614 for (ArcIt a(_graph); a != INVALID; ++a) { 615 (*_plower)[a] = map[a]; 616 } 617 return *this; 618 } 619 620 /// \brief Set the upper bounds (capacities) on the arcs. 621 /// 622 /// This function sets the upper bounds (capacities) on the arcs. 623 /// If none of the functions \ref upperMap(), \ref capacityMap() 624 /// and \ref boundMaps() is used before calling \ref run(), 625 /// the upper bounds (capacities) will be set to 626 /// \c std::numeric_limits<Value>::max() on all arcs. 627 /// 628 /// \param map An arc map storing the upper bounds. 629 /// Its \c Value type must be convertible to the \c Value type 630 /// of the algorithm. 631 /// 632 /// \return <tt>(*this)</tt> 633 template<typename UPPER> 634 NetworkSimplex& upperMap(const UPPER& map) { 635 delete _pupper; 636 _pupper = new ValueArcMap(_graph); 637 for (ArcIt a(_graph); a != INVALID; ++a) { 638 (*_pupper)[a] = map[a]; 639 } 640 return *this; 641 } 642 643 /// \brief Set the upper bounds (capacities) on the arcs. 644 /// 645 /// This function sets the upper bounds (capacities) on the arcs. 646 /// It is just an alias for \ref upperMap(). 647 /// 648 /// \return <tt>(*this)</tt> 649 template<typename CAP> 650 NetworkSimplex& capacityMap(const CAP& map) { 651 return upperMap(map); 652 } 653 654 /// \brief Set the lower and upper bounds on the arcs. 655 /// 656 /// This function sets the lower and upper bounds on the arcs. 657 /// If neither this function nor \ref lowerMap() is used before 658 /// calling \ref run(), the lower bounds will be set to zero 659 /// on all arcs. 660 /// If none of the functions \ref upperMap(), \ref capacityMap() 661 /// and \ref boundMaps() is used before calling \ref run(), 662 /// the upper bounds (capacities) will be set to 663 /// \c std::numeric_limits<Value>::max() on all arcs. 664 /// 665 /// \param lower An arc map storing the lower bounds. 666 /// \param upper An arc map storing the upper bounds. 667 /// 668 /// The \c Value type of the maps must be convertible to the 669 /// \c Value type of the algorithm. 670 /// 671 /// \note This function is just a shortcut of calling \ref lowerMap() 672 /// and \ref upperMap() separately. 673 /// 674 /// \return <tt>(*this)</tt> 675 template <typename LOWER, typename UPPER> 676 NetworkSimplex& boundMaps(const LOWER& lower, const UPPER& upper) { 677 return lowerMap(lower).upperMap(upper); 678 } 679 680 /// \brief Set the costs of the arcs. 681 /// 682 /// This function sets the costs of the arcs. 683 /// If it is not used before calling \ref run(), the costs 684 /// will be set to \c 1 on all arcs. 685 /// 686 /// \param map An arc map storing the costs. 687 /// Its \c Value type must be convertible to the \c Value type 688 /// of the algorithm. 689 /// 690 /// \return <tt>(*this)</tt> 691 template<typename COST> 692 NetworkSimplex& costMap(const COST& map) { 693 delete _pcost; 694 _pcost = new ValueArcMap(_graph); 695 for (ArcIt a(_graph); a != INVALID; ++a) { 696 (*_pcost)[a] = map[a]; 697 } 698 return *this; 699 } 700 701 /// \brief Set the supply values of the nodes. 702 /// 703 /// This function sets the supply values of the nodes. 704 /// If neither this function nor \ref stSupply() is used before 705 /// calling \ref run(), the supply of each node will be set to zero. 706 /// (It makes sense only if non-zero lower bounds are given.) 707 /// 708 /// \param map A node map storing the supply values. 709 /// Its \c Value type must be convertible to the \c Value type 710 /// of the algorithm. 711 /// 712 /// \return <tt>(*this)</tt> 713 template<typename SUP> 714 NetworkSimplex& supplyMap(const SUP& map) { 715 delete _psupply; 716 _pstsup = false; 717 _psupply = new ValueNodeMap(_graph); 718 for (NodeIt n(_graph); n != INVALID; ++n) { 719 (*_psupply)[n] = map[n]; 720 } 721 return *this; 722 } 723 724 /// \brief Set single source and target nodes and a supply value. 725 /// 726 /// This function sets a single source node and a single target node 727 /// and the required flow value. 728 /// If neither this function nor \ref supplyMap() is used before 729 /// calling \ref run(), the supply of each node will be set to zero. 730 /// (It makes sense only if non-zero lower bounds are given.) 731 /// 732 /// \param s The source node. 733 /// \param t The target node. 734 /// \param k The required amount of flow from node \c s to node \c t 735 /// (i.e. the supply of \c s and the demand of \c t). 736 /// 737 /// \return <tt>(*this)</tt> 738 NetworkSimplex& stSupply(const Node& s, const Node& t, Value k) { 739 delete _psupply; 740 _psupply = NULL; 741 _pstsup = true; 742 _psource = s; 743 _ptarget = t; 744 _pstflow = k; 745 return *this; 746 } 747 691 748 /// \brief Set the flow map. 692 749 /// 693 750 /// This function sets the flow map. 751 /// If it is not used before calling \ref run(), an instance will 752 /// be allocated automatically. The destructor deallocates this 753 /// automatically allocated map, of course. 694 754 /// 695 755 /// \return <tt>(*this)</tt> 696 NetworkSimplex& flowMap(FlowMap &map) {756 NetworkSimplex& flowMap(FlowMap& map) { 697 757 if (_local_flow) { 698 758 delete _flow_map; … … 705 765 /// \brief Set the potential map. 706 766 /// 707 /// This function sets the potential map. 767 /// This function sets the potential map, which is used for storing 768 /// the dual solution. 769 /// If it is not used before calling \ref run(), an instance will 770 /// be allocated automatically. The destructor deallocates this 771 /// automatically allocated map, of course. 708 772 /// 709 773 /// \return <tt>(*this)</tt> 710 NetworkSimplex& potentialMap(PotentialMap &map) {774 NetworkSimplex& potentialMap(PotentialMap& map) { 711 775 if (_local_potential) { 712 776 delete _potential_map; … … 717 781 } 718 782 719 /// \name Execution control720 /// The algorithm can be executed using the721 /// \ref lemon::NetworkSimplex::run() "run()" function. 783 /// \name Execution Control 784 /// The algorithm can be executed using \ref run(). 785 722 786 /// @{ 723 787 … … 725 789 /// 726 790 /// This function runs the algorithm. 727 /// 728 /// \param pivot_rule The pivot rule that is used during the 729 /// algorithm. 730 /// 731 /// The available pivot rules: 732 /// 733 /// - FIRST_ELIGIBLE_PIVOT The next eligible arc is selected in 734 /// a wraparound fashion in every iteration 735 /// (\ref FirstEligiblePivotRule). 736 /// 737 /// - BEST_ELIGIBLE_PIVOT The best eligible arc is selected in 738 /// every iteration (\ref BestEligiblePivotRule). 739 /// 740 /// - BLOCK_SEARCH_PIVOT A specified number of arcs are examined in 741 /// every iteration in a wraparound fashion and the best eligible 742 /// arc is selected from this block (\ref BlockSearchPivotRule). 743 /// 744 /// - CANDIDATE_LIST_PIVOT In a major iteration a candidate list is 745 /// built from eligible arcs in a wraparound fashion and in the 746 /// following minor iterations the best eligible arc is selected 747 /// from this list (\ref CandidateListPivotRule). 748 /// 749 /// - ALTERING_LIST_PIVOT It is a modified version of the 750 /// "Candidate List" pivot rule. It keeps only the several best 751 /// eligible arcs from the former candidate list and extends this 752 /// list in every iteration (\ref AlteringListPivotRule). 753 /// 754 /// According to our comprehensive benchmark tests the "Block Search" 755 /// pivot rule proved to be the fastest and the most robust on 756 /// various test inputs. Thus it is the default option. 791 /// The paramters can be specified using \ref lowerMap(), 792 /// \ref upperMap(), \ref capacityMap(), \ref boundMaps(), 793 /// \ref costMap(), \ref supplyMap() and \ref stSupply() 794 /// functions. For example, 795 /// \code 796 /// NetworkSimplex<ListDigraph> ns(graph); 797 /// ns.boundMaps(lower, upper).costMap(cost) 798 /// .supplyMap(sup).run(); 799 /// \endcode 800 /// 801 /// \param pivot_rule The pivot rule that will be used during the 802 /// algorithm. For more information see \ref PivotRule. 757 803 /// 758 804 /// \return \c true if a feasible flow can be found. 759 bool run(PivotRule Enum pivot_rule = BLOCK_SEARCH_PIVOT) {805 bool run(PivotRule pivot_rule = BLOCK_SEARCH) { 760 806 return init() && start(pivot_rule); 761 807 } … … 766 812 /// The results of the algorithm can be obtained using these 767 813 /// functions.\n 768 /// \ref lemon::NetworkSimplex::run() "run()" must be called before769 /// using them. 814 /// The \ref run() function must be called before using them. 815 770 816 /// @{ 817 818 /// \brief Return the total cost of the found flow. 819 /// 820 /// This function returns the total cost of the found flow. 821 /// The complexity of the function is \f$ O(e) \f$. 822 /// 823 /// \note The return type of the function can be specified as a 824 /// template parameter. For example, 825 /// \code 826 /// ns.totalCost<double>(); 827 /// \endcode 828 /// It is useful if the total cost cannot be stored in the \c Value 829 /// type of the algorithm, which is the default return type of the 830 /// function. 831 /// 832 /// \pre \ref run() must be called before using this function. 833 template <typename Num> 834 Num totalCost() const { 835 Num c = 0; 836 if (_pcost) { 837 for (ArcIt e(_graph); e != INVALID; ++e) 838 c += (*_flow_map)[e] * (*_pcost)[e]; 839 } else { 840 for (ArcIt e(_graph); e != INVALID; ++e) 841 c += (*_flow_map)[e]; 842 } 843 return c; 844 } 845 846 #ifndef DOXYGEN 847 Value totalCost() const { 848 return totalCost<Value>(); 849 } 850 #endif 851 852 /// \brief Return the flow on the given arc. 853 /// 854 /// This function returns the flow on the given arc. 855 /// 856 /// \pre \ref run() must be called before using this function. 857 Value flow(const Arc& a) const { 858 return (*_flow_map)[a]; 859 } 771 860 772 861 /// \brief Return a const reference to the flow map. … … 780 869 } 781 870 871 /// \brief Return the potential (dual value) of the given node. 872 /// 873 /// This function returns the potential (dual value) of the 874 /// given node. 875 /// 876 /// \pre \ref run() must be called before using this function. 877 Value potential(const Node& n) const { 878 return (*_potential_map)[n]; 879 } 880 782 881 /// \brief Return a const reference to the potential map 783 882 /// (the dual solution). 784 883 /// 785 884 /// This function returns a const reference to a node map storing 786 /// the found potentials (the dual solution). 885 /// the found potentials, which form the dual solution of the 886 /// \ref min_cost_flow "minimum cost flow" problem. 787 887 /// 788 888 /// \pre \ref run() must be called before using this function. 789 889 const PotentialMap& potentialMap() const { 790 890 return *_potential_map; 791 }792 793 /// \brief Return the flow on the given arc.794 ///795 /// This function returns the flow on the given arc.796 ///797 /// \pre \ref run() must be called before using this function.798 Capacity flow(const Arc& arc) const {799 return (*_flow_map)[arc];800 }801 802 /// \brief Return the potential of the given node.803 ///804 /// This function returns the potential of the given node.805 ///806 /// \pre \ref run() must be called before using this function.807 Cost potential(const Node& node) const {808 return (*_potential_map)[node];809 }810 811 /// \brief Return the total cost of the found flow.812 ///813 /// This function returns the total cost of the found flow.814 /// The complexity of the function is \f$ O(e) \f$.815 ///816 /// \pre \ref run() must be called before using this function.817 Cost totalCost() const {818 Cost c = 0;819 for (ArcIt e(_graph); e != INVALID; ++e)820 c += (*_flow_map)[e] * _orig_cost[e];821 return c;822 891 } 823 892 … … 843 912 int all_node_num = _node_num + 1; 844 913 int all_arc_num = _arc_num + _node_num; 914 if (_node_num == 0) return false; 845 915 846 916 _arc_ref.resize(_arc_num); … … 865 935 // Initialize node related data 866 936 bool valid_supply = true; 867 if (_orig_supply) { 868 Supply sum = 0; 937 if (!_pstsup && !_psupply) { 938 _pstsup = true; 939 _psource = _ptarget = NodeIt(_graph); 940 _pstflow = 0; 941 } 942 if (_psupply) { 943 Value sum = 0; 869 944 int i = 0; 870 945 for (NodeIt n(_graph); n != INVALID; ++n, ++i) { 871 946 _node_id[n] = i; 872 _supply[i] = (*_ orig_supply)[n];947 _supply[i] = (*_psupply)[n]; 873 948 sum += _supply[i]; 874 949 } … … 880 955 _supply[i] = 0; 881 956 } 882 _supply[_node_id[_ orig_source]] = _orig_flow_value;883 _supply[_node_id[_ orig_target]] = -_orig_flow_value;957 _supply[_node_id[_psource]] = _pstflow; 958 _supply[_node_id[_ptarget]] = -_pstflow; 884 959 } 885 960 if (!valid_supply) return false; … … 905 980 906 981 // Initialize arc maps 907 for (int i = 0; i != _arc_num; ++i) { 908 Arc e = _arc_ref[i]; 909 _source[i] = _node_id[_graph.source(e)]; 910 _target[i] = _node_id[_graph.target(e)]; 911 _cost[i] = _orig_cost[e]; 912 _cap[i] = _orig_cap[e]; 982 if (_pupper && _pcost) { 983 for (int i = 0; i != _arc_num; ++i) { 984 Arc e = _arc_ref[i]; 985 _source[i] = _node_id[_graph.source(e)]; 986 _target[i] = _node_id[_graph.target(e)]; 987 _cap[i] = (*_pupper)[e]; 988 _cost[i] = (*_pcost)[e]; 989 } 990 } else { 991 for (int i = 0; i != _arc_num; ++i) { 992 Arc e = _arc_ref[i]; 993 _source[i] = _node_id[_graph.source(e)]; 994 _target[i] = _node_id[_graph.target(e)]; 995 } 996 if (_pupper) { 997 for (int i = 0; i != _arc_num; ++i) 998 _cap[i] = (*_pupper)[_arc_ref[i]]; 999 } else { 1000 Value val = std::numeric_limits<Value>::max(); 1001 for (int i = 0; i != _arc_num; ++i) 1002 _cap[i] = val; 1003 } 1004 if (_pcost) { 1005 for (int i = 0; i != _arc_num; ++i) 1006 _cost[i] = (*_pcost)[_arc_ref[i]]; 1007 } else { 1008 for (int i = 0; i != _arc_num; ++i) 1009 _cost[i] = 1; 1010 } 913 1011 } 914 1012 915 1013 // Remove non-zero lower bounds 916 if (_ orig_lower) {1014 if (_plower) { 917 1015 for (int i = 0; i != _arc_num; ++i) { 918 Capacity c = (*_orig_lower)[_arc_ref[i]];1016 Value c = (*_plower)[_arc_ref[i]]; 919 1017 if (c != 0) { 920 1018 _cap[i] -= c; … … 926 1024 927 1025 // Add artificial arcs and initialize the spanning tree data structure 928 Cost max_cost = std::numeric_limits<Cost>::max() / 4;929 Capacity max_cap = std::numeric_limits<Capacity>::max();1026 Value max_cap = std::numeric_limits<Value>::max(); 1027 Value max_cost = std::numeric_limits<Value>::max() / 4; 930 1028 for (int u = 0, e = _arc_num; u != _node_num; ++u, ++e) { 931 1029 _thread[u] = u + 1; … … 980 1078 delta = _cap[in_arc]; 981 1079 int result = 0; 982 Capacityd;1080 Value d; 983 1081 int e; 984 1082 … … 1018 1116 // Augment along the cycle 1019 1117 if (delta > 0) { 1020 Capacityval = _state[in_arc] * delta;1118 Value val = _state[in_arc] * delta; 1021 1119 _flow[in_arc] += val; 1022 1120 for (int u = _source[in_arc]; u != join; u = _parent[u]) { … … 1159 1257 // Update potentials 1160 1258 void updatePotential() { 1161 Costsigma = _forward[u_in] ?1259 Value sigma = _forward[u_in] ? 1162 1260 _pi[v_in] - _pi[u_in] - _cost[_pred[u_in]] : 1163 1261 _pi[v_in] - _pi[u_in] + _cost[_pred[u_in]]; … … 1182 1280 1183 1281 // Execute the algorithm 1184 bool start(PivotRule Enumpivot_rule) {1282 bool start(PivotRule pivot_rule) { 1185 1283 // Select the pivot rule implementation 1186 1284 switch (pivot_rule) { 1187 case FIRST_ELIGIBLE _PIVOT:1285 case FIRST_ELIGIBLE: 1188 1286 return start<FirstEligiblePivotRule>(); 1189 case BEST_ELIGIBLE _PIVOT:1287 case BEST_ELIGIBLE: 1190 1288 return start<BestEligiblePivotRule>(); 1191 case BLOCK_SEARCH _PIVOT:1289 case BLOCK_SEARCH: 1192 1290 return start<BlockSearchPivotRule>(); 1193 case CANDIDATE_LIST _PIVOT:1291 case CANDIDATE_LIST: 1194 1292 return start<CandidateListPivotRule>(); 1195 case ALTERING_LIST _PIVOT:1293 case ALTERING_LIST: 1196 1294 return start<AlteringListPivotRule>(); 1197 1295 } … … 1199 1297 } 1200 1298 1201 template <class PivotRuleImplementation>1299 template <typename PivotRuleImpl> 1202 1300 bool start() { 1203 PivotRuleImpl ementationpivot(*this);1204 1205 // Execute the network simplex algorithm1301 PivotRuleImpl pivot(*this); 1302 1303 // Execute the Network Simplex algorithm 1206 1304 while (pivot.findEnteringArc()) { 1207 1305 findJoinNode(); … … 1220 1318 1221 1319 // Copy flow values to _flow_map 1222 if (_ orig_lower) {1320 if (_plower) { 1223 1321 for (int i = 0; i != _arc_num; ++i) { 1224 1322 Arc e = _arc_ref[i]; 1225 _flow_map->set(e, (*_ orig_lower)[e] + _flow[i]);1323 _flow_map->set(e, (*_plower)[e] + _flow[i]); 1226 1324 } 1227 1325 } else { -
test/min_cost_flow_test.cc
r648 r652 21 21 22 22 #include <lemon/list_graph.h> 23 #include <lemon/smart_graph.h>24 23 #include <lemon/lgf_reader.h> 25 24 26 //#include <lemon/cycle_canceling.h>27 //#include <lemon/capacity_scaling.h>28 //#include <lemon/cost_scaling.h>29 25 #include <lemon/network_simplex.h> 30 //#include <lemon/min_cost_flow.h>31 //#include <lemon/min_cost_max_flow.h>32 26 33 27 #include <lemon/concepts/digraph.h> … … 94 88 checkConcept<concepts::Digraph, GR>(); 95 89 96 MCF mcf _test1(g, lower, upper, cost, sup);97 MCF mcf_test2(g, upper, cost, sup); 98 MCF mcf_test3(g, lower, upper, cost, n, n, k);99 MCF mcf_test4(g, upper, cost, n, n, k);100 101 // TODO: This part should be enabled and the next part102 // should be removed if map copying is supported103 /* 104 flow = mcf_test1.flowMap();105 mcf_test1.flowMap(flow);106 107 pot = mcf_test1.potentialMap();108 mcf_test1.potentialMap(pot);109 */ 110 /**/ 111 const typename MCF::FlowMap &fm =112 mcf_test1.flowMap();113 mcf_test1.flowMap(flow);114 const typename MCF::PotentialMap &pm =115 mcf_test1.potentialMap();116 mcf_test1.potentialMap(pot); 90 MCF mcf(g); 91 92 b = mcf.lowerMap(lower) 93 .upperMap(upper) 94 .capacityMap(upper) 95 .boundMaps(lower, upper) 96 .costMap(cost) 97 .supplyMap(sup) 98 .stSupply(n, n, k) 99 .run(); 100 101 const typename MCF::FlowMap &fm = mcf.flowMap(); 102 const typename MCF::PotentialMap &pm = mcf.potentialMap(); 103 104 v = mcf.totalCost(); 105 double x = mcf.template totalCost<double>(); 106 v = mcf.flow(a); 107 v = mcf.potential(n); 108 mcf.flowMap(flow); 109 mcf.potentialMap(pot); 110 117 111 ignore_unused_variable_warning(fm); 118 112 ignore_unused_variable_warning(pm); 119 /**/ 120 121 mcf_test1.run(); 122 123 v = mcf_test1.totalCost(); 124 v = mcf_test1.flow(a); 125 v = mcf_test1.potential(n); 113 ignore_unused_variable_warning(x); 126 114 } 127 115 … … 140 128 const Value &k; 141 129 Value v; 130 bool b; 142 131 143 132 typename MCF::FlowMap &flow; … … 173 162 174 163 // Check the feasibility of the given potentials (dual soluiton) 175 // using the Complementary Slacknessoptimality condition164 // using the "Complementary Slackness" optimality condition 176 165 template < typename GR, typename LM, typename UM, 177 166 typename CM, typename FM, typename PM > … … 218 207 { 219 208 typedef int Value; 220 // This typedef should be enabled if the standard maps are 221 // reference maps in the graph concepts 209 // TODO: This typedef should be enabled if the standard maps are 210 // reference maps in the graph concepts (See #190). 211 /**/ 222 212 //typedef concepts::Digraph GR; 223 213 typedef ListDigraph GR; 224 typedef concepts::ReadMap<GR::Node, Value> NM; 225 typedef concepts::ReadMap<GR::Arc, Value> AM; 226 227 //checkConcept< McfClassConcept<GR, Value>, 228 // CycleCanceling<GR, AM, AM, AM, NM> >(); 229 //checkConcept< McfClassConcept<GR, Value>, 230 // CapacityScaling<GR, AM, AM, AM, NM> >(); 231 //checkConcept< McfClassConcept<GR, Value>, 232 // CostScaling<GR, AM, AM, AM, NM> >(); 214 /**/ 233 215 checkConcept< McfClassConcept<GR, Value>, 234 NetworkSimplex<GR, AM, AM, AM, NM> >(); 235 //checkConcept< MinCostFlow<GR, Value>, 236 // NetworkSimplex<GR, AM, AM, AM, NM> >(); 216 NetworkSimplex<GR, Value> >(); 237 217 } 238 218 … … 245 225 Digraph::ArcMap<int> c(gr), l1(gr), l2(gr), u(gr); 246 226 Digraph::NodeMap<int> s1(gr), s2(gr), s3(gr); 227 ConstMap<Arc, int> cc(1), cu(std::numeric_limits<int>::max()); 247 228 Node v, w; 248 229 … … 260 241 .run(); 261 242 262 /* 263 // A. Test CapacityScaling with scaling 243 // A. Test NetworkSimplex with the default pivot rule 264 244 { 265 CapacityScaling<Digraph> mcf1(gr, u, c, s1); 266 CapacityScaling<Digraph> mcf2(gr, u, c, v, w, 27); 267 CapacityScaling<Digraph> mcf3(gr, u, c, s3); 268 CapacityScaling<Digraph> mcf4(gr, l2, u, c, s1); 269 CapacityScaling<Digraph> mcf5(gr, l2, u, c, v, w, 27); 270 CapacityScaling<Digraph> mcf6(gr, l2, u, c, s3); 271 272 checkMcf(mcf1, mcf1.run(), gr, l1, u, c, s1, true, 5240, "#A1"); 273 checkMcf(mcf2, mcf2.run(), gr, l1, u, c, s2, true, 7620, "#A2"); 274 checkMcf(mcf3, mcf3.run(), gr, l1, u, c, s3, true, 0, "#A3"); 275 checkMcf(mcf4, mcf4.run(), gr, l2, u, c, s1, true, 5970, "#A4"); 276 checkMcf(mcf5, mcf5.run(), gr, l2, u, c, s2, true, 8010, "#A5"); 277 checkMcf(mcf6, mcf6.run(), gr, l2, u, c, s3, false, 0, "#A6"); 278 } 279 280 // B. Test CapacityScaling without scaling 245 NetworkSimplex<Digraph> mcf1(gr), mcf2(gr), mcf3(gr), mcf4(gr), 246 mcf5(gr), mcf6(gr), mcf7(gr), mcf8(gr); 247 248 checkMcf(mcf1, mcf1.upperMap(u).costMap(c).supplyMap(s1).run(), 249 gr, l1, u, c, s1, true, 5240, "#A1"); 250 checkMcf(mcf2, mcf2.upperMap(u).costMap(c).stSupply(v, w, 27).run(), 251 gr, l1, u, c, s2, true, 7620, "#A2"); 252 checkMcf(mcf3, mcf3.boundMaps(l2, u).costMap(c).supplyMap(s1).run(), 253 gr, l2, u, c, s1, true, 5970, "#A3"); 254 checkMcf(mcf4, mcf4.boundMaps(l2, u).costMap(c).stSupply(v, w, 27).run(), 255 gr, l2, u, c, s2, true, 8010, "#A4"); 256 checkMcf(mcf5, mcf5.supplyMap(s1).run(), 257 gr, l1, cu, cc, s1, true, 74, "#A5"); 258 checkMcf(mcf6, mcf6.stSupply(v, w, 27).lowerMap(l2).run(), 259 gr, l2, cu, cc, s2, true, 94, "#A6"); 260 checkMcf(mcf7, mcf7.run(), 261 gr, l1, cu, cc, s3, true, 0, "#A7"); 262 checkMcf(mcf8, mcf8.boundMaps(l2, u).run(), 263 gr, l2, u, cc, s3, false, 0, "#A8"); 264 } 265 266 // B. Test NetworkSimplex with each pivot rule 281 267 { 282 CapacityScaling<Digraph> mcf1(gr, u, c, s1); 283 CapacityScaling<Digraph> mcf2(gr, u, c, v, w, 27); 284 CapacityScaling<Digraph> mcf3(gr, u, c, s3); 285 CapacityScaling<Digraph> mcf4(gr, l2, u, c, s1); 286 CapacityScaling<Digraph> mcf5(gr, l2, u, c, v, w, 27); 287 CapacityScaling<Digraph> mcf6(gr, l2, u, c, s3); 288 289 checkMcf(mcf1, mcf1.run(false), gr, l1, u, c, s1, true, 5240, "#B1"); 290 checkMcf(mcf2, mcf2.run(false), gr, l1, u, c, s2, true, 7620, "#B2"); 291 checkMcf(mcf3, mcf3.run(false), gr, l1, u, c, s3, true, 0, "#B3"); 292 checkMcf(mcf4, mcf4.run(false), gr, l2, u, c, s1, true, 5970, "#B4"); 293 checkMcf(mcf5, mcf5.run(false), gr, l2, u, c, s2, true, 8010, "#B5"); 294 checkMcf(mcf6, mcf6.run(false), gr, l2, u, c, s3, false, 0, "#B6"); 295 } 296 297 // C. Test CostScaling using partial augment-relabel method 298 { 299 CostScaling<Digraph> mcf1(gr, u, c, s1); 300 CostScaling<Digraph> mcf2(gr, u, c, v, w, 27); 301 CostScaling<Digraph> mcf3(gr, u, c, s3); 302 CostScaling<Digraph> mcf4(gr, l2, u, c, s1); 303 CostScaling<Digraph> mcf5(gr, l2, u, c, v, w, 27); 304 CostScaling<Digraph> mcf6(gr, l2, u, c, s3); 305 306 checkMcf(mcf1, mcf1.run(), gr, l1, u, c, s1, true, 5240, "#C1"); 307 checkMcf(mcf2, mcf2.run(), gr, l1, u, c, s2, true, 7620, "#C2"); 308 checkMcf(mcf3, mcf3.run(), gr, l1, u, c, s3, true, 0, "#C3"); 309 checkMcf(mcf4, mcf4.run(), gr, l2, u, c, s1, true, 5970, "#C4"); 310 checkMcf(mcf5, mcf5.run(), gr, l2, u, c, s2, true, 8010, "#C5"); 311 checkMcf(mcf6, mcf6.run(), gr, l2, u, c, s3, false, 0, "#C6"); 312 } 313 314 // D. Test CostScaling using push-relabel method 315 { 316 CostScaling<Digraph> mcf1(gr, u, c, s1); 317 CostScaling<Digraph> mcf2(gr, u, c, v, w, 27); 318 CostScaling<Digraph> mcf3(gr, u, c, s3); 319 CostScaling<Digraph> mcf4(gr, l2, u, c, s1); 320 CostScaling<Digraph> mcf5(gr, l2, u, c, v, w, 27); 321 CostScaling<Digraph> mcf6(gr, l2, u, c, s3); 322 323 checkMcf(mcf1, mcf1.run(false), gr, l1, u, c, s1, true, 5240, "#D1"); 324 checkMcf(mcf2, mcf2.run(false), gr, l1, u, c, s2, true, 7620, "#D2"); 325 checkMcf(mcf3, mcf3.run(false), gr, l1, u, c, s3, true, 0, "#D3"); 326 checkMcf(mcf4, mcf4.run(false), gr, l2, u, c, s1, true, 5970, "#D4"); 327 checkMcf(mcf5, mcf5.run(false), gr, l2, u, c, s2, true, 8010, "#D5"); 328 checkMcf(mcf6, mcf6.run(false), gr, l2, u, c, s3, false, 0, "#D6"); 329 } 330 */ 331 332 // E. Test NetworkSimplex with FIRST_ELIGIBLE_PIVOT 333 { 334 NetworkSimplex<Digraph>::PivotRuleEnum pr = 335 NetworkSimplex<Digraph>::FIRST_ELIGIBLE_PIVOT; 336 NetworkSimplex<Digraph> mcf1(gr, u, c, s1); 337 NetworkSimplex<Digraph> mcf2(gr, u, c, v, w, 27); 338 NetworkSimplex<Digraph> mcf3(gr, u, c, s3); 339 NetworkSimplex<Digraph> mcf4(gr, l2, u, c, s1); 340 NetworkSimplex<Digraph> mcf5(gr, l2, u, c, v, w, 27); 341 NetworkSimplex<Digraph> mcf6(gr, l2, u, c, s3); 342 343 checkMcf(mcf1, mcf1.run(pr), gr, l1, u, c, s1, true, 5240, "#E1"); 344 checkMcf(mcf2, mcf2.run(pr), gr, l1, u, c, s2, true, 7620, "#E2"); 345 checkMcf(mcf3, mcf3.run(pr), gr, l1, u, c, s3, true, 0, "#E3"); 346 checkMcf(mcf4, mcf4.run(pr), gr, l2, u, c, s1, true, 5970, "#E4"); 347 checkMcf(mcf5, mcf5.run(pr), gr, l2, u, c, s2, true, 8010, "#E5"); 348 checkMcf(mcf6, mcf6.run(pr), gr, l2, u, c, s3, false, 0, "#E6"); 349 } 350 351 // F. Test NetworkSimplex with BEST_ELIGIBLE_PIVOT 352 { 353 NetworkSimplex<Digraph>::PivotRuleEnum pr = 354 NetworkSimplex<Digraph>::BEST_ELIGIBLE_PIVOT; 355 NetworkSimplex<Digraph> mcf1(gr, u, c, s1); 356 NetworkSimplex<Digraph> mcf2(gr, u, c, v, w, 27); 357 NetworkSimplex<Digraph> mcf3(gr, u, c, s3); 358 NetworkSimplex<Digraph> mcf4(gr, l2, u, c, s1); 359 NetworkSimplex<Digraph> mcf5(gr, l2, u, c, v, w, 27); 360 NetworkSimplex<Digraph> mcf6(gr, l2, u, c, s3); 361 362 checkMcf(mcf1, mcf1.run(pr), gr, l1, u, c, s1, true, 5240, "#F1"); 363 checkMcf(mcf2, mcf2.run(pr), gr, l1, u, c, s2, true, 7620, "#F2"); 364 checkMcf(mcf3, mcf3.run(pr), gr, l1, u, c, s3, true, 0, "#F3"); 365 checkMcf(mcf4, mcf4.run(pr), gr, l2, u, c, s1, true, 5970, "#F4"); 366 checkMcf(mcf5, mcf5.run(pr), gr, l2, u, c, s2, true, 8010, "#F5"); 367 checkMcf(mcf6, mcf6.run(pr), gr, l2, u, c, s3, false, 0, "#F6"); 368 } 369 370 // G. Test NetworkSimplex with BLOCK_SEARCH_PIVOT 371 { 372 NetworkSimplex<Digraph>::PivotRuleEnum pr = 373 NetworkSimplex<Digraph>::BLOCK_SEARCH_PIVOT; 374 NetworkSimplex<Digraph> mcf1(gr, u, c, s1); 375 NetworkSimplex<Digraph> mcf2(gr, u, c, v, w, 27); 376 NetworkSimplex<Digraph> mcf3(gr, u, c, s3); 377 NetworkSimplex<Digraph> mcf4(gr, l2, u, c, s1); 378 NetworkSimplex<Digraph> mcf5(gr, l2, u, c, v, w, 27); 379 NetworkSimplex<Digraph> mcf6(gr, l2, u, c, s3); 380 381 checkMcf(mcf1, mcf1.run(pr), gr, l1, u, c, s1, true, 5240, "#G1"); 382 checkMcf(mcf2, mcf2.run(pr), gr, l1, u, c, s2, true, 7620, "#G2"); 383 checkMcf(mcf3, mcf3.run(pr), gr, l1, u, c, s3, true, 0, "#G3"); 384 checkMcf(mcf4, mcf4.run(pr), gr, l2, u, c, s1, true, 5970, "#G4"); 385 checkMcf(mcf5, mcf5.run(pr), gr, l2, u, c, s2, true, 8010, "#G5"); 386 checkMcf(mcf6, mcf6.run(pr), gr, l2, u, c, s3, false, 0, "#G6"); 387 } 388 389 // H. Test NetworkSimplex with CANDIDATE_LIST_PIVOT 390 { 391 NetworkSimplex<Digraph>::PivotRuleEnum pr = 392 NetworkSimplex<Digraph>::CANDIDATE_LIST_PIVOT; 393 NetworkSimplex<Digraph> mcf1(gr, u, c, s1); 394 NetworkSimplex<Digraph> mcf2(gr, u, c, v, w, 27); 395 NetworkSimplex<Digraph> mcf3(gr, u, c, s3); 396 NetworkSimplex<Digraph> mcf4(gr, l2, u, c, s1); 397 NetworkSimplex<Digraph> mcf5(gr, l2, u, c, v, w, 27); 398 NetworkSimplex<Digraph> mcf6(gr, l2, u, c, s3); 399 400 checkMcf(mcf1, mcf1.run(pr), gr, l1, u, c, s1, true, 5240, "#H1"); 401 checkMcf(mcf2, mcf2.run(pr), gr, l1, u, c, s2, true, 7620, "#H2"); 402 checkMcf(mcf3, mcf3.run(pr), gr, l1, u, c, s3, true, 0, "#H3"); 403 checkMcf(mcf4, mcf4.run(pr), gr, l2, u, c, s1, true, 5970, "#H4"); 404 checkMcf(mcf5, mcf5.run(pr), gr, l2, u, c, s2, true, 8010, "#H5"); 405 checkMcf(mcf6, mcf6.run(pr), gr, l2, u, c, s3, false, 0, "#H6"); 406 } 407 408 // I. Test NetworkSimplex with ALTERING_LIST_PIVOT 409 { 410 NetworkSimplex<Digraph>::PivotRuleEnum pr = 411 NetworkSimplex<Digraph>::ALTERING_LIST_PIVOT; 412 NetworkSimplex<Digraph> mcf1(gr, u, c, s1); 413 NetworkSimplex<Digraph> mcf2(gr, u, c, v, w, 27); 414 NetworkSimplex<Digraph> mcf3(gr, u, c, s3); 415 NetworkSimplex<Digraph> mcf4(gr, l2, u, c, s1); 416 NetworkSimplex<Digraph> mcf5(gr, l2, u, c, v, w, 27); 417 NetworkSimplex<Digraph> mcf6(gr, l2, u, c, s3); 418 419 checkMcf(mcf1, mcf1.run(pr), gr, l1, u, c, s1, true, 5240, "#I1"); 420 checkMcf(mcf2, mcf2.run(pr), gr, l1, u, c, s2, true, 7620, "#I2"); 421 checkMcf(mcf3, mcf3.run(pr), gr, l1, u, c, s3, true, 0, "#I3"); 422 checkMcf(mcf4, mcf4.run(pr), gr, l2, u, c, s1, true, 5970, "#I4"); 423 checkMcf(mcf5, mcf5.run(pr), gr, l2, u, c, s2, true, 8010, "#I5"); 424 checkMcf(mcf6, mcf6.run(pr), gr, l2, u, c, s3, false, 0, "#I6"); 425 } 426 427 /* 428 // J. Test MinCostFlow 429 { 430 MinCostFlow<Digraph> mcf1(gr, u, c, s1); 431 MinCostFlow<Digraph> mcf2(gr, u, c, v, w, 27); 432 MinCostFlow<Digraph> mcf3(gr, u, c, s3); 433 MinCostFlow<Digraph> mcf4(gr, l2, u, c, s1); 434 MinCostFlow<Digraph> mcf5(gr, l2, u, c, v, w, 27); 435 MinCostFlow<Digraph> mcf6(gr, l2, u, c, s3); 436 437 checkMcf(mcf1, mcf1.run(), gr, l1, u, c, s1, true, 5240, "#J1"); 438 checkMcf(mcf2, mcf2.run(), gr, l1, u, c, s2, true, 7620, "#J2"); 439 checkMcf(mcf3, mcf3.run(), gr, l1, u, c, s3, true, 0, "#J3"); 440 checkMcf(mcf4, mcf4.run(), gr, l2, u, c, s1, true, 5970, "#J4"); 441 checkMcf(mcf5, mcf5.run(), gr, l2, u, c, s2, true, 8010, "#J5"); 442 checkMcf(mcf6, mcf6.run(), gr, l2, u, c, s3, false, 0, "#J6"); 443 } 444 */ 445 /* 446 // K. Test MinCostMaxFlow 447 { 448 MinCostMaxFlow<Digraph> mcmf(gr, u, c, v, w); 449 mcmf.run(); 450 checkMcf(mcmf, true, gr, l1, u, c, s3, true, 7620, "#K1"); 451 } 452 */ 268 NetworkSimplex<Digraph> mcf1(gr), mcf2(gr), mcf3(gr), mcf4(gr), mcf5(gr); 269 NetworkSimplex<Digraph>::PivotRule pr; 270 271 pr = NetworkSimplex<Digraph>::FIRST_ELIGIBLE; 272 checkMcf(mcf1, mcf1.boundMaps(l2, u).costMap(c).supplyMap(s1).run(pr), 273 gr, l2, u, c, s1, true, 5970, "#B1"); 274 pr = NetworkSimplex<Digraph>::BEST_ELIGIBLE; 275 checkMcf(mcf2, mcf2.boundMaps(l2, u).costMap(c).supplyMap(s1).run(pr), 276 gr, l2, u, c, s1, true, 5970, "#B2"); 277 pr = NetworkSimplex<Digraph>::BLOCK_SEARCH; 278 checkMcf(mcf3, mcf3.boundMaps(l2, u).costMap(c).supplyMap(s1).run(pr), 279 gr, l2, u, c, s1, true, 5970, "#B3"); 280 pr = NetworkSimplex<Digraph>::CANDIDATE_LIST; 281 checkMcf(mcf4, mcf4.boundMaps(l2, u).costMap(c).supplyMap(s1).run(pr), 282 gr, l2, u, c, s1, true, 5970, "#B4"); 283 pr = NetworkSimplex<Digraph>::ALTERING_LIST; 284 checkMcf(mcf5, mcf5.boundMaps(l2, u).costMap(c).supplyMap(s1).run(pr), 285 gr, l2, u, c, s1, true, 5970, "#B5"); 286 } 453 287 454 288 return 0; -
tools/dimacs-solver.cc
r649 r652 106 106 if (report) std::cerr << "Read the file: " << ti << '\n'; 107 107 ti.restart(); 108 NetworkSimplex< Digraph, Digraph::ArcMap<Value>, Digraph::ArcMap<Value>, 109 Digraph::ArcMap<Value>, Digraph::NodeMap<Value> > 110 ns(g, lower, cap, cost, sup); 108 NetworkSimplex<Digraph, Value> ns(g); 109 ns.lowerMap(lower).capacityMap(cap).costMap(cost).supplyMap(sup); 111 110 if (report) std::cerr << "Setup NetworkSimplex class: " << ti << '\n'; 112 111 ti.restart();
Note: See TracChangeset
for help on using the changeset viewer.