Changeset 607:9ad8d2122b50 in lemonmain
 Timestamp:
 04/03/09 13:46:16 (13 years ago)
 Branch:
 default
 Phase:
 public
 Files:

 2 edited
Legend:
 Unmodified
 Added
 Removed

lemon/network_simplex.h
r606 r607 50 50 /// 51 51 /// \tparam GR The digraph type the algorithm runs on. 52 /// \tparam V The value type used in the algorithm. 53 /// By default it is \c int. 52 /// \tparam F The value type used for flow amounts, capacity bounds 53 /// and supply values in the algorithm. By default it is \c int. 54 /// \tparam C The value type used for costs and potentials in the 55 /// algorithm. By default it is the same as \c F. 54 56 /// 55 /// \warning The value type must be a signed integer type.57 /// \warning Both value types must be signed integer types. 56 58 /// 57 59 /// \note %NetworkSimplex provides five different pivot rule 58 60 /// implementations. For more information see \ref PivotRule. 59 template <typename GR, typename V = int>61 template <typename GR, typename F = int, typename C = F> 60 62 class NetworkSimplex 61 63 { 62 64 public: 63 65 64 /// The value type of the algorithm 65 typedef V Value; 66 /// The flow type of the algorithm 67 typedef F Flow; 68 /// The cost type of the algorithm 69 typedef C Cost; 66 70 /// The type of the flow map 67 typedef typename GR::template ArcMap< Value> FlowMap;71 typedef typename GR::template ArcMap<Flow> FlowMap; 68 72 /// The type of the potential map 69 typedef typename GR::template NodeMap< Value> PotentialMap;73 typedef typename GR::template NodeMap<Cost> PotentialMap; 70 74 71 75 public: … … 118 122 TEMPLATE_DIGRAPH_TYPEDEFS(GR); 119 123 120 typedef typename GR::template ArcMap<Value> ValueArcMap; 121 typedef typename GR::template NodeMap<Value> ValueNodeMap; 124 typedef typename GR::template ArcMap<Flow> FlowArcMap; 125 typedef typename GR::template ArcMap<Cost> CostArcMap; 126 typedef typename GR::template NodeMap<Flow> FlowNodeMap; 122 127 123 128 typedef std::vector<Arc> ArcVector; … … 125 130 typedef std::vector<int> IntVector; 126 131 typedef std::vector<bool> BoolVector; 127 typedef std::vector<Value> ValueVector; 132 typedef std::vector<Flow> FlowVector; 133 typedef std::vector<Cost> CostVector; 128 134 129 135 // State constants for arcs … … 142 148 143 149 // Parameters of the problem 144 ValueArcMap *_plower;145 ValueArcMap *_pupper;146 ValueArcMap *_pcost;147 ValueNodeMap *_psupply;150 FlowArcMap *_plower; 151 FlowArcMap *_pupper; 152 CostArcMap *_pcost; 153 FlowNodeMap *_psupply; 148 154 bool _pstsup; 149 155 Node _psource, _ptarget; 150 Value_pstflow;156 Flow _pstflow; 151 157 152 158 // Result maps … … 163 169 164 170 // Node and arc data 165 ValueVector _cap;166 ValueVector _cost;167 ValueVector _supply;168 ValueVector _flow;169 ValueVector _pi;171 FlowVector _cap; 172 CostVector _cost; 173 FlowVector _supply; 174 FlowVector _flow; 175 CostVector _pi; 170 176 171 177 // Data for storing the spanning tree structure … … 185 191 int first, second, right, last; 186 192 int stem, par_stem, new_stem; 187 Valuedelta;193 Flow delta; 188 194 189 195 private: … … 197 203 const IntVector &_source; 198 204 const IntVector &_target; 199 const ValueVector &_cost;205 const CostVector &_cost; 200 206 const IntVector &_state; 201 const ValueVector &_pi;207 const CostVector &_pi; 202 208 int &_in_arc; 203 209 int _arc_num; … … 217 223 // Find next entering arc 218 224 bool findEnteringArc() { 219 Valuec;225 Cost c; 220 226 for (int e = _next_arc; e < _arc_num; ++e) { 221 227 c = _state[e] * (_cost[e] + _pi[_source[e]]  _pi[_target[e]]); … … 248 254 const IntVector &_source; 249 255 const IntVector &_target; 250 const ValueVector &_cost;256 const CostVector &_cost; 251 257 const IntVector &_state; 252 const ValueVector &_pi;258 const CostVector &_pi; 253 259 int &_in_arc; 254 260 int _arc_num; … … 265 271 // Find next entering arc 266 272 bool findEnteringArc() { 267 Valuec, min = 0;273 Cost c, min = 0; 268 274 for (int e = 0; e < _arc_num; ++e) { 269 275 c = _state[e] * (_cost[e] + _pi[_source[e]]  _pi[_target[e]]); … … 287 293 const IntVector &_source; 288 294 const IntVector &_target; 289 const ValueVector &_cost;295 const CostVector &_cost; 290 296 const IntVector &_state; 291 const ValueVector &_pi;297 const CostVector &_pi; 292 298 int &_in_arc; 293 299 int _arc_num; … … 315 321 // Find next entering arc 316 322 bool findEnteringArc() { 317 Valuec, min = 0;323 Cost c, min = 0; 318 324 int cnt = _block_size; 319 325 int e, min_arc = _next_arc; … … 359 365 const IntVector &_source; 360 366 const IntVector &_target; 361 const ValueVector &_cost;367 const CostVector &_cost; 362 368 const IntVector &_state; 363 const ValueVector &_pi;369 const CostVector &_pi; 364 370 int &_in_arc; 365 371 int _arc_num; … … 395 401 /// Find next entering arc 396 402 bool findEnteringArc() { 397 Valuemin, c;403 Cost min, c; 398 404 int e, min_arc = _next_arc; 399 405 if (_curr_length > 0 && _minor_count < _minor_limit) { … … 464 470 const IntVector &_source; 465 471 const IntVector &_target; 466 const ValueVector &_cost;472 const CostVector &_cost; 467 473 const IntVector &_state; 468 const ValueVector &_pi;474 const CostVector &_pi; 469 475 int &_in_arc; 470 476 int _arc_num; … … 474 480 int _next_arc; 475 481 IntVector _candidates; 476 ValueVector _cand_cost;482 CostVector _cand_cost; 477 483 478 484 // Functor class to compare arcs during sort of the candidate list … … 480 486 { 481 487 private: 482 const ValueVector &_map;488 const CostVector &_map; 483 489 public: 484 SortFunc(const ValueVector &map) : _map(map) {}490 SortFunc(const CostVector &map) : _map(map) {} 485 491 bool operator()(int left, int right) { 486 492 return _map[left] > _map[right]; … … 591 597 _node_id(graph) 592 598 { 593 LEMON_ASSERT(std::numeric_limits<Value>::is_integer && 594 std::numeric_limits<Value>::is_signed, 595 "The value type of NetworkSimplex must be a signed integer"); 599 LEMON_ASSERT(std::numeric_limits<Flow>::is_integer && 600 std::numeric_limits<Flow>::is_signed, 601 "The flow type of NetworkSimplex must be signed integer"); 602 LEMON_ASSERT(std::numeric_limits<Cost>::is_integer && 603 std::numeric_limits<Cost>::is_signed, 604 "The cost type of NetworkSimplex must be signed integer"); 596 605 } 597 606 … … 610 619 /// 611 620 /// \param map An arc map storing the lower bounds. 612 /// Its \c Value type must be convertible to the \c Valuetype621 /// Its \c Value type must be convertible to the \c Flow type 613 622 /// of the algorithm. 614 623 /// … … 617 626 NetworkSimplex& lowerMap(const LOWER& map) { 618 627 delete _plower; 619 _plower = new ValueArcMap(_graph);628 _plower = new FlowArcMap(_graph); 620 629 for (ArcIt a(_graph); a != INVALID; ++a) { 621 630 (*_plower)[a] = map[a]; … … 630 639 /// and \ref boundMaps() is used before calling \ref run(), 631 640 /// the upper bounds (capacities) will be set to 632 /// \c std::numeric_limits< Value>::max() on all arcs.641 /// \c std::numeric_limits<Flow>::max() on all arcs. 633 642 /// 634 643 /// \param map An arc map storing the upper bounds. 635 /// Its \c Value type must be convertible to the \c Valuetype644 /// Its \c Value type must be convertible to the \c Flow type 636 645 /// of the algorithm. 637 646 /// … … 640 649 NetworkSimplex& upperMap(const UPPER& map) { 641 650 delete _pupper; 642 _pupper = new ValueArcMap(_graph);651 _pupper = new FlowArcMap(_graph); 643 652 for (ArcIt a(_graph); a != INVALID; ++a) { 644 653 (*_pupper)[a] = map[a]; … … 667 676 /// and \ref boundMaps() is used before calling \ref run(), 668 677 /// the upper bounds (capacities) will be set to 669 /// \c std::numeric_limits< Value>::max() on all arcs.678 /// \c std::numeric_limits<Flow>::max() on all arcs. 670 679 /// 671 680 /// \param lower An arc map storing the lower bounds. … … 673 682 /// 674 683 /// The \c Value type of the maps must be convertible to the 675 /// \c Valuetype of the algorithm.684 /// \c Flow type of the algorithm. 676 685 /// 677 686 /// \note This function is just a shortcut of calling \ref lowerMap() … … 691 700 /// 692 701 /// \param map An arc map storing the costs. 693 /// Its \c Value type must be convertible to the \c Valuetype702 /// Its \c Value type must be convertible to the \c Cost type 694 703 /// of the algorithm. 695 704 /// … … 698 707 NetworkSimplex& costMap(const COST& map) { 699 708 delete _pcost; 700 _pcost = new ValueArcMap(_graph);709 _pcost = new CostArcMap(_graph); 701 710 for (ArcIt a(_graph); a != INVALID; ++a) { 702 711 (*_pcost)[a] = map[a]; … … 713 722 /// 714 723 /// \param map A node map storing the supply values. 715 /// Its \c Value type must be convertible to the \c Valuetype724 /// Its \c Value type must be convertible to the \c Flow type 716 725 /// of the algorithm. 717 726 /// … … 721 730 delete _psupply; 722 731 _pstsup = false; 723 _psupply = new ValueNodeMap(_graph);732 _psupply = new FlowNodeMap(_graph); 724 733 for (NodeIt n(_graph); n != INVALID; ++n) { 725 734 (*_psupply)[n] = map[n]; … … 742 751 /// 743 752 /// \return <tt>(*this)</tt> 744 NetworkSimplex& stSupply(const Node& s, const Node& t, Valuek) {753 NetworkSimplex& stSupply(const Node& s, const Node& t, Flow k) { 745 754 delete _psupply; 746 755 _psupply = NULL; … … 875 884 /// 876 885 /// This function returns the total cost of the found flow. 877 /// The complexity of the function is \f$ O(e) \f$.886 /// The complexity of the function is O(e). 878 887 /// 879 888 /// \note The return type of the function can be specified as a … … 882 891 /// ns.totalCost<double>(); 883 892 /// \endcode 884 /// It is useful if the total cost cannot be stored in the \c Value893 /// It is useful if the total cost cannot be stored in the \c Cost 885 894 /// type of the algorithm, which is the default return type of the 886 895 /// function. … … 901 910 902 911 #ifndef DOXYGEN 903 ValuetotalCost() const {904 return totalCost< Value>();912 Cost totalCost() const { 913 return totalCost<Cost>(); 905 914 } 906 915 #endif … … 911 920 /// 912 921 /// \pre \ref run() must be called before using this function. 913 Valueflow(const Arc& a) const {922 Flow flow(const Arc& a) const { 914 923 return (*_flow_map)[a]; 915 924 } … … 931 940 /// 932 941 /// \pre \ref run() must be called before using this function. 933 Valuepotential(const Node& n) const {942 Cost potential(const Node& n) const { 934 943 return (*_potential_map)[n]; 935 944 } … … 997 1006 } 998 1007 if (_psupply) { 999 Valuesum = 0;1008 Flow sum = 0; 1000 1009 int i = 0; 1001 1010 for (NodeIt n(_graph); n != INVALID; ++n, ++i) { … … 1036 1045 1037 1046 // Initialize arc maps 1047 Flow max_cap = std::numeric_limits<Flow>::max(); 1048 Cost max_cost = std::numeric_limits<Cost>::max() / 4; 1038 1049 if (_pupper && _pcost) { 1039 1050 for (int i = 0; i != _arc_num; ++i) { … … 1058 1069 _cap[i] = (*_pupper)[_arc_ref[i]]; 1059 1070 } else { 1060 Value val = std::numeric_limits<Value>::max();1061 1071 for (int i = 0; i != _arc_num; ++i) 1062 _cap[i] = val;1072 _cap[i] = max_cap; 1063 1073 } 1064 1074 if (_pcost) { … … 1074 1084 if (_plower) { 1075 1085 for (int i = 0; i != _arc_num; ++i) { 1076 Valuec = (*_plower)[_arc_ref[i]];1086 Flow c = (*_plower)[_arc_ref[i]]; 1077 1087 if (c != 0) { 1078 1088 _cap[i] = c; … … 1084 1094 1085 1095 // Add artificial arcs and initialize the spanning tree data structure 1086 Value max_cap = std::numeric_limits<Value>::max();1087 Value max_cost = std::numeric_limits<Value>::max() / 4;1088 1096 for (int u = 0, e = _arc_num; u != _node_num; ++u, ++e) { 1089 1097 _thread[u] = u + 1; … … 1138 1146 delta = _cap[in_arc]; 1139 1147 int result = 0; 1140 Valued;1148 Flow d; 1141 1149 int e; 1142 1150 … … 1176 1184 // Augment along the cycle 1177 1185 if (delta > 0) { 1178 Valueval = _state[in_arc] * delta;1186 Flow val = _state[in_arc] * delta; 1179 1187 _flow[in_arc] += val; 1180 1188 for (int u = _source[in_arc]; u != join; u = _parent[u]) { … … 1317 1325 // Update potentials 1318 1326 void updatePotential() { 1319 Valuesigma = _forward[u_in] ?1327 Cost sigma = _forward[u_in] ? 1320 1328 _pi[v_in]  _pi[u_in]  _cost[_pred[u_in]] : 1321 1329 _pi[v_in]  _pi[u_in] + _cost[_pred[u_in]]; 
test/min_cost_flow_test.cc
r606 r607 78 78 79 79 // Check the interface of an MCF algorithm 80 template <typename GR, typename Value>80 template <typename GR, typename Flow, typename Cost> 81 81 class McfClassConcept 82 82 { … … 117 117 typedef typename GR::Node Node; 118 118 typedef typename GR::Arc Arc; 119 typedef concepts::ReadMap<Node, Value> NM; 120 typedef concepts::ReadMap<Arc, Value> AM; 119 typedef concepts::ReadMap<Node, Flow> NM; 120 typedef concepts::ReadMap<Arc, Flow> FAM; 121 typedef concepts::ReadMap<Arc, Cost> CAM; 121 122 122 123 const GR &g; 123 const AM &lower;124 const AM &upper;125 const AM &cost;124 const FAM &lower; 125 const FAM &upper; 126 const CAM &cost; 126 127 const NM ⊃ 127 128 const Node &n; 128 129 const Arc &a; 129 const Value&k;130 Valuev;130 const Flow &k; 131 Flow v; 131 132 bool b; 132 133 … … 207 208 // Check the interfaces 208 209 { 209 typedef int Value; 210 typedef int Flow; 211 typedef int Cost; 210 212 // TODO: This typedef should be enabled if the standard maps are 211 213 // reference maps in the graph concepts (See #190). … … 214 216 typedef ListDigraph GR; 215 217 /**/ 216 checkConcept< McfClassConcept<GR, Value>,217 NetworkSimplex<GR, Value> >();218 checkConcept< McfClassConcept<GR, Flow, Cost>, 219 NetworkSimplex<GR, Flow, Cost> >(); 218 220 } 219 221
Note: See TracChangeset
for help on using the changeset viewer.