Changes in lemon/network_simplex.h [835:c92296660262:898:75c97c3786d6] in lemon
- File:
-
- 1 edited
Legend:
- Unmodified
- Added
- Removed
-
lemon/network_simplex.h
r835 r898 44 44 /// \ref amo93networkflows, \ref dantzig63linearprog, 45 45 /// \ref kellyoneill91netsimplex. 46 /// This algorithm is a specialized version of the linear programming47 /// simplex method directly for the minimum cost flow problem.48 /// It is one of the most efficient solution methods.46 /// This algorithm is a highly efficient specialized version of the 47 /// linear programming simplex method directly for the minimum cost 48 /// flow problem. 49 49 /// 50 /// In general this classis the fastest implementation available51 /// in LEMON for th e minimum cost flowproblem.52 /// Moreover it supports both directions of the supply/demand inequality50 /// In general, %NetworkSimplex is the fastest implementation available 51 /// in LEMON for this problem. 52 /// Moreover, it supports both directions of the supply/demand inequality 53 53 /// constraints. For more information, see \ref SupplyType. 54 54 /// … … 59 59 /// 60 60 /// \tparam GR The digraph type the algorithm runs on. 61 /// \tparam V The valuetype used for flow amounts, capacity bounds61 /// \tparam V The number type used for flow amounts, capacity bounds 62 62 /// and supply values in the algorithm. By default, it is \c int. 63 /// \tparam C The valuetype used for costs and potentials in the63 /// \tparam C The number type used for costs and potentials in the 64 64 /// algorithm. By default, it is the same as \c V. 65 65 /// 66 /// \warning Both valuetypes must be signed and all input data must66 /// \warning Both number types must be signed and all input data must 67 67 /// be integer. 68 68 /// … … 127 127 /// By default, \ref BLOCK_SEARCH "Block Search" is used, which 128 128 /// proved to be the most efficient and the most robust on various 129 /// test inputs according to our benchmark tests.129 /// test inputs. 130 130 /// However, another pivot rule can be selected using the \ref run() 131 131 /// function with the proper parameter. … … 165 165 166 166 typedef std::vector<int> IntVector; 167 typedef std::vector< bool> BoolVector;167 typedef std::vector<char> CharVector; 168 168 typedef std::vector<Value> ValueVector; 169 169 typedef std::vector<Cost> CostVector; … … 195 195 IntVector _source; 196 196 IntVector _target; 197 bool _arc_mixing; 197 198 198 199 // Node and arc data … … 213 214 IntVector _last_succ; 214 215 IntVector _dirty_revs; 215 BoolVector _forward;216 IntVector _state;216 CharVector _forward; 217 CharVector _state; 217 218 int _root; 218 219 … … 222 223 int stem, par_stem, new_stem; 223 224 Value delta; 225 226 const Value MAX; 224 227 225 228 public: … … 243 246 const IntVector &_target; 244 247 const CostVector &_cost; 245 const IntVector&_state;248 const CharVector &_state; 246 249 const CostVector &_pi; 247 250 int &_in_arc; … … 295 298 const IntVector &_target; 296 299 const CostVector &_cost; 297 const IntVector&_state;300 const CharVector &_state; 298 301 const CostVector &_pi; 299 302 int &_in_arc; … … 334 337 const IntVector &_target; 335 338 const CostVector &_cost; 336 const IntVector&_state;339 const CharVector &_state; 337 340 const CostVector &_pi; 338 341 int &_in_arc; … … 407 410 const IntVector &_target; 408 411 const CostVector &_cost; 409 const IntVector&_state;412 const CharVector &_state; 410 413 const CostVector &_pi; 411 414 int &_in_arc; … … 510 513 const IntVector &_target; 511 514 const CostVector &_cost; 512 const IntVector&_state;515 const CharVector &_state; 513 516 const CostVector &_pi; 514 517 int &_in_arc; … … 632 635 NetworkSimplex(const GR& graph, bool arc_mixing = false) : 633 636 _graph(graph), _node_id(graph), _arc_id(graph), 637 _arc_mixing(arc_mixing), 638 MAX(std::numeric_limits<Value>::max()), 634 639 INF(std::numeric_limits<Value>::has_infinity ? 635 std::numeric_limits<Value>::infinity() : 636 std::numeric_limits<Value>::max()) 640 std::numeric_limits<Value>::infinity() : MAX) 637 641 { 638 // Check the valuetypes642 // Check the number types 639 643 LEMON_ASSERT(std::numeric_limits<Value>::is_signed, 640 644 "The flow type of NetworkSimplex must be signed"); … … 642 646 "The cost type of NetworkSimplex must be signed"); 643 647 644 // Resize vectors 645 _node_num = countNodes(_graph); 646 _arc_num = countArcs(_graph); 647 int all_node_num = _node_num + 1; 648 int max_arc_num = _arc_num + 2 * _node_num; 649 650 _source.resize(max_arc_num); 651 _target.resize(max_arc_num); 652 653 _lower.resize(_arc_num); 654 _upper.resize(_arc_num); 655 _cap.resize(max_arc_num); 656 _cost.resize(max_arc_num); 657 _supply.resize(all_node_num); 658 _flow.resize(max_arc_num); 659 _pi.resize(all_node_num); 660 661 _parent.resize(all_node_num); 662 _pred.resize(all_node_num); 663 _forward.resize(all_node_num); 664 _thread.resize(all_node_num); 665 _rev_thread.resize(all_node_num); 666 _succ_num.resize(all_node_num); 667 _last_succ.resize(all_node_num); 668 _state.resize(max_arc_num); 669 670 // Copy the graph 671 int i = 0; 672 for (NodeIt n(_graph); n != INVALID; ++n, ++i) { 673 _node_id[n] = i; 674 } 675 if (arc_mixing) { 676 // Store the arcs in a mixed order 677 int k = std::max(int(std::sqrt(double(_arc_num))), 10); 678 int i = 0, j = 0; 679 for (ArcIt a(_graph); a != INVALID; ++a) { 680 _arc_id[a] = i; 681 _source[i] = _node_id[_graph.source(a)]; 682 _target[i] = _node_id[_graph.target(a)]; 683 if ((i += k) >= _arc_num) i = ++j; 684 } 685 } else { 686 // Store the arcs in the original order 687 int i = 0; 688 for (ArcIt a(_graph); a != INVALID; ++a, ++i) { 689 _arc_id[a] = i; 690 _source[i] = _node_id[_graph.source(a)]; 691 _target[i] = _node_id[_graph.target(a)]; 692 } 693 } 694 695 // Reset parameters 648 // Reset data structures 696 649 reset(); 697 650 } … … 728 681 /// If it is not used before calling \ref run(), the upper bounds 729 682 /// will be set to \ref INF on all arcs (i.e. the flow value will be 730 /// unbounded from above on each arc).683 /// unbounded from above). 731 684 /// 732 685 /// \param map An arc map storing the upper bounds. … … 841 794 /// \endcode 842 795 /// 843 /// This function can be called more than once. All the parameters844 /// that have been given are kept for the next call, unless845 /// \ref reset() is called, thus only the modified parameters846 /// have to be set again. See \ref reset() for examples.847 /// However, the underlying digraph must not be modified after this848 /// class have been constructed, since it copies and extends the graph.796 /// This function can be called more than once. All the given parameters 797 /// are kept for the next call, unless \ref resetParams() or \ref reset() 798 /// is used, thus only the modified parameters have to be set again. 799 /// If the underlying digraph was also modified after the construction 800 /// of the class (or the last \ref reset() call), then the \ref reset() 801 /// function must be called. 849 802 /// 850 803 /// \param pivot_rule The pivot rule that will be used during the … … 860 813 /// 861 814 /// \see ProblemType, PivotRule 815 /// \see resetParams(), reset() 862 816 ProblemType run(PivotRule pivot_rule = BLOCK_SEARCH) { 863 817 if (!init()) return INFEASIBLE; … … 871 825 /// \ref costMap(), \ref supplyMap(), \ref stSupply(), \ref supplyType(). 872 826 /// 873 /// It is useful for multiple run() calls. If this function is not 874 /// used, all the parameters given before are kept for the next 875 /// \ref run() call. 876 /// However, the underlying digraph must not be modified after this 877 /// class have been constructed, since it copies and extends the graph. 827 /// It is useful for multiple \ref run() calls. Basically, all the given 828 /// parameters are kept for the next \ref run() call, unless 829 /// \ref resetParams() or \ref reset() is used. 830 /// If the underlying digraph was also modified after the construction 831 /// of the class or the last \ref reset() call, then the \ref reset() 832 /// function must be used, otherwise \ref resetParams() is sufficient. 878 833 /// 879 834 /// For example, … … 885 840 /// .supplyMap(sup).run(); 886 841 /// 887 /// // Run again with modified cost map (reset () is not called,842 /// // Run again with modified cost map (resetParams() is not called, 888 843 /// // so only the cost map have to be set again) 889 844 /// cost[e] += 100; 890 845 /// ns.costMap(cost).run(); 891 846 /// 892 /// // Run again from scratch using reset ()847 /// // Run again from scratch using resetParams() 893 848 /// // (the lower bounds will be set to zero on all arcs) 894 /// ns.reset ();849 /// ns.resetParams(); 895 850 /// ns.upperMap(capacity).costMap(cost) 896 851 /// .supplyMap(sup).run(); … … 898 853 /// 899 854 /// \return <tt>(*this)</tt> 900 NetworkSimplex& reset() { 855 /// 856 /// \see reset(), run() 857 NetworkSimplex& resetParams() { 901 858 for (int i = 0; i != _node_num; ++i) { 902 859 _supply[i] = 0; … … 912 869 } 913 870 871 /// \brief Reset the internal data structures and all the parameters 872 /// that have been given before. 873 /// 874 /// This function resets the internal data structures and all the 875 /// paramaters that have been given before using functions \ref lowerMap(), 876 /// \ref upperMap(), \ref costMap(), \ref supplyMap(), \ref stSupply(), 877 /// \ref supplyType(). 878 /// 879 /// It is useful for multiple \ref run() calls. Basically, all the given 880 /// parameters are kept for the next \ref run() call, unless 881 /// \ref resetParams() or \ref reset() is used. 882 /// If the underlying digraph was also modified after the construction 883 /// of the class or the last \ref reset() call, then the \ref reset() 884 /// function must be used, otherwise \ref resetParams() is sufficient. 885 /// 886 /// See \ref resetParams() for examples. 887 /// 888 /// \return <tt>(*this)</tt> 889 /// 890 /// \see resetParams(), run() 891 NetworkSimplex& reset() { 892 // Resize vectors 893 _node_num = countNodes(_graph); 894 _arc_num = countArcs(_graph); 895 int all_node_num = _node_num + 1; 896 int max_arc_num = _arc_num + 2 * _node_num; 897 898 _source.resize(max_arc_num); 899 _target.resize(max_arc_num); 900 901 _lower.resize(_arc_num); 902 _upper.resize(_arc_num); 903 _cap.resize(max_arc_num); 904 _cost.resize(max_arc_num); 905 _supply.resize(all_node_num); 906 _flow.resize(max_arc_num); 907 _pi.resize(all_node_num); 908 909 _parent.resize(all_node_num); 910 _pred.resize(all_node_num); 911 _forward.resize(all_node_num); 912 _thread.resize(all_node_num); 913 _rev_thread.resize(all_node_num); 914 _succ_num.resize(all_node_num); 915 _last_succ.resize(all_node_num); 916 _state.resize(max_arc_num); 917 918 // Copy the graph 919 int i = 0; 920 for (NodeIt n(_graph); n != INVALID; ++n, ++i) { 921 _node_id[n] = i; 922 } 923 if (_arc_mixing) { 924 // Store the arcs in a mixed order 925 int k = std::max(int(std::sqrt(double(_arc_num))), 10); 926 int i = 0, j = 0; 927 for (ArcIt a(_graph); a != INVALID; ++a) { 928 _arc_id[a] = i; 929 _source[i] = _node_id[_graph.source(a)]; 930 _target[i] = _node_id[_graph.target(a)]; 931 if ((i += k) >= _arc_num) i = ++j; 932 } 933 } else { 934 // Store the arcs in the original order 935 int i = 0; 936 for (ArcIt a(_graph); a != INVALID; ++a, ++i) { 937 _arc_id[a] = i; 938 _source[i] = _node_id[_graph.source(a)]; 939 _target[i] = _node_id[_graph.target(a)]; 940 } 941 } 942 943 // Reset parameters 944 resetParams(); 945 return *this; 946 } 947 914 948 /// @} 915 949 … … 1021 1055 Value c = _lower[i]; 1022 1056 if (c >= 0) { 1023 _cap[i] = _upper[i] < INF? _upper[i] - c : INF;1057 _cap[i] = _upper[i] < MAX ? _upper[i] - c : INF; 1024 1058 } else { 1025 _cap[i] = _upper[i] < INF+ c ? _upper[i] - c : INF;1059 _cap[i] = _upper[i] < MAX + c ? _upper[i] - c : INF; 1026 1060 } 1027 1061 _supply[_source[i]] -= c; … … 1215 1249 e = _pred[u]; 1216 1250 d = _forward[u] ? 1217 _flow[e] : (_cap[e] == INF? INF : _cap[e] - _flow[e]);1251 _flow[e] : (_cap[e] >= MAX ? INF : _cap[e] - _flow[e]); 1218 1252 if (d < delta) { 1219 1253 delta = d; … … 1226 1260 e = _pred[u]; 1227 1261 d = _forward[u] ? 1228 (_cap[e] == INF? INF : _cap[e] - _flow[e]) : _flow[e];1262 (_cap[e] >= MAX ? INF : _cap[e] - _flow[e]) : _flow[e]; 1229 1263 if (d <= delta) { 1230 1264 delta = d; … … 1425 1459 findJoinNode(); 1426 1460 bool change = findLeavingArc(); 1427 if (delta >= INF) return UNBOUNDED;1461 if (delta >= MAX) return UNBOUNDED; 1428 1462 changeFlow(change); 1429 1463 if (change) {
Note: See TracChangeset
for help on using the changeset viewer.