Changeset 653:c7d160f73d52 in lemon
 Timestamp:
 03/25/09 21:37:50 (10 years ago)
 Branch:
 default
 Phase:
 public
 Files:

 2 edited
Legend:
 Unmodified
 Added
 Removed

lemon/network_simplex.h
r652 r653 42 42 /// \ref NetworkSimplex implements the primal Network Simplex algorithm 43 43 /// for finding a \ref min_cost_flow "minimum cost flow". 44 /// This algorithm is a specialized version of the linear programming 45 /// simplex method directly for the minimum cost flow problem. 46 /// It is one of the most efficient solution methods. 47 /// 48 /// In general this class is the fastest implementation available 49 /// in LEMON for the minimum cost flow problem. 44 50 /// 45 51 /// \tparam GR The digraph type the algorithm runs on. … … 47 53 /// By default it is \c int. 48 54 /// 49 /// \warning \c Vmust be a signed integer type.55 /// \warning The value type must be a signed integer type. 50 56 /// 51 57 /// \note %NetworkSimplex provides five different pivot rule … … 790 796 /// This function runs the algorithm. 791 797 /// The paramters can be specified using \ref lowerMap(), 792 /// \ref upperMap(), \ref capacityMap(), \ref boundMaps(), 798 /// \ref upperMap(), \ref capacityMap(), \ref boundMaps(), 793 799 /// \ref costMap(), \ref supplyMap() and \ref stSupply() 794 800 /// functions. For example, … … 799 805 /// \endcode 800 806 /// 807 /// This function can be called more than once. All the parameters 808 /// that have been given are kept for the next call, unless 809 /// \ref reset() is called, thus only the modified parameters 810 /// have to be set again. See \ref reset() for examples. 811 /// 801 812 /// \param pivot_rule The pivot rule that will be used during the 802 813 /// algorithm. For more information see \ref PivotRule. … … 805 816 bool run(PivotRule pivot_rule = BLOCK_SEARCH) { 806 817 return init() && start(pivot_rule); 818 } 819 820 /// \brief Reset all the parameters that have been given before. 821 /// 822 /// This function resets all the paramaters that have been given 823 /// using \ref lowerMap(), \ref upperMap(), \ref capacityMap(), 824 /// \ref boundMaps(), \ref costMap(), \ref supplyMap() and 825 /// \ref stSupply() functions before. 826 /// 827 /// It is useful for multiple run() calls. If this function is not 828 /// used, all the parameters given before are kept for the next 829 /// \ref run() call. 830 /// 831 /// For example, 832 /// \code 833 /// NetworkSimplex<ListDigraph> ns(graph); 834 /// 835 /// // First run 836 /// ns.lowerMap(lower).capacityMap(cap).costMap(cost) 837 /// .supplyMap(sup).run(); 838 /// 839 /// // Run again with modified cost map (reset() is not called, 840 /// // so only the cost map have to be set again) 841 /// cost[e] += 100; 842 /// ns.costMap(cost).run(); 843 /// 844 /// // Run again from scratch using reset() 845 /// // (the lower bounds will be set to zero on all arcs) 846 /// ns.reset(); 847 /// ns.capacityMap(cap).costMap(cost) 848 /// .supplyMap(sup).run(); 849 /// \endcode 850 /// 851 /// \return <tt>(*this)</tt> 852 NetworkSimplex& reset() { 853 delete _plower; 854 delete _pupper; 855 delete _pcost; 856 delete _psupply; 857 _plower = NULL; 858 _pupper = NULL; 859 _pcost = NULL; 860 _psupply = NULL; 861 _pstsup = false; 862 return *this; 807 863 } 808 864 … … 921 977 _cost.resize(all_arc_num); 922 978 _supply.resize(all_node_num); 923 _flow.resize(all_arc_num , 0);924 _pi.resize(all_node_num , 0);979 _flow.resize(all_arc_num); 980 _pi.resize(all_node_num); 925 981 926 982 _parent.resize(all_node_num); … … 931 987 _succ_num.resize(all_node_num); 932 988 _last_succ.resize(all_node_num); 933 _state.resize(all_arc_num , STATE_LOWER);989 _state.resize(all_arc_num); 934 990 935 991 // Initialize node related data … … 987 1043 _cap[i] = (*_pupper)[e]; 988 1044 _cost[i] = (*_pcost)[e]; 1045 _flow[i] = 0; 1046 _state[i] = STATE_LOWER; 989 1047 } 990 1048 } else { … … 993 1051 _source[i] = _node_id[_graph.source(e)]; 994 1052 _target[i] = _node_id[_graph.target(e)]; 1053 _flow[i] = 0; 1054 _state[i] = STATE_LOWER; 995 1055 } 996 1056 if (_pupper) { … … 1033 1093 _parent[u] = _root; 1034 1094 _pred[u] = e; 1095 _cost[e] = max_cost; 1096 _cap[e] = max_cap; 1097 _state[e] = STATE_TREE; 1035 1098 if (_supply[u] >= 0) { 1036 1099 _flow[e] = _supply[u]; … … 1042 1105 _pi[u] = max_cost; 1043 1106 } 1044 _cost[e] = max_cost;1045 _cap[e] = max_cap;1046 _state[e] = STATE_TREE;1047 1107 } 1048 1108 
test/min_cost_flow_test.cc
r652 r653 90 90 MCF mcf(g); 91 91 92 b = mcf.lowerMap(lower) 92 b = mcf.reset() 93 .lowerMap(lower) 93 94 .upperMap(upper) 94 95 .capacityMap(upper) … … 243 244 // A. Test NetworkSimplex with the default pivot rule 244 245 { 245 NetworkSimplex<Digraph> mcf 1(gr), mcf2(gr), mcf3(gr), mcf4(gr),246 mcf5(gr), mcf6(gr), mcf7(gr), mcf8(gr); 247 248 checkMcf(mcf 1, mcf1.upperMap(u).costMap(c).supplyMap(s1).run(),246 NetworkSimplex<Digraph> mcf(gr); 247 248 mcf.upperMap(u).costMap(c); 249 checkMcf(mcf, mcf.supplyMap(s1).run(), 249 250 gr, l1, u, c, s1, true, 5240, "#A1"); 250 checkMcf(mcf 2, mcf2.upperMap(u).costMap(c).stSupply(v, w, 27).run(),251 checkMcf(mcf, mcf.stSupply(v, w, 27).run(), 251 252 gr, l1, u, c, s2, true, 7620, "#A2"); 252 checkMcf(mcf3, mcf3.boundMaps(l2, u).costMap(c).supplyMap(s1).run(), 253 mcf.lowerMap(l2); 254 checkMcf(mcf, mcf.supplyMap(s1).run(), 253 255 gr, l2, u, c, s1, true, 5970, "#A3"); 254 checkMcf(mcf 4, mcf4.boundMaps(l2, u).costMap(c).stSupply(v, w, 27).run(),256 checkMcf(mcf, mcf.stSupply(v, w, 27).run(), 255 257 gr, l2, u, c, s2, true, 8010, "#A4"); 256 checkMcf(mcf5, mcf5.supplyMap(s1).run(), 258 mcf.reset(); 259 checkMcf(mcf, mcf.supplyMap(s1).run(), 257 260 gr, l1, cu, cc, s1, true, 74, "#A5"); 258 checkMcf(mcf 6, mcf6.stSupply(v, w, 27).lowerMap(l2).run(),261 checkMcf(mcf, mcf.lowerMap(l2).stSupply(v, w, 27).run(), 259 262 gr, l2, cu, cc, s2, true, 94, "#A6"); 260 checkMcf(mcf7, mcf7.run(), 263 mcf.reset(); 264 checkMcf(mcf, mcf.run(), 261 265 gr, l1, cu, cc, s3, true, 0, "#A7"); 262 checkMcf(mcf 8, mcf8.boundMaps(l2, u).run(),266 checkMcf(mcf, mcf.boundMaps(l2, u).run(), 263 267 gr, l2, u, cc, s3, false, 0, "#A8"); 264 268 } … … 266 270 // B. Test NetworkSimplex with each pivot rule 267 271 { 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), 272 NetworkSimplex<Digraph> mcf(gr); 273 mcf.supplyMap(s1).costMap(c).capacityMap(u).lowerMap(l2); 274 275 checkMcf(mcf, mcf.run(NetworkSimplex<Digraph>::FIRST_ELIGIBLE), 273 276 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), 277 checkMcf(mcf, mcf.run(NetworkSimplex<Digraph>::BEST_ELIGIBLE), 276 278 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 checkMcf(mcf, mcf.run(NetworkSimplex<Digraph>::BLOCK_SEARCH), 279 280 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), 281 checkMcf(mcf, mcf.run(NetworkSimplex<Digraph>::CANDIDATE_LIST), 282 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), 283 checkMcf(mcf, mcf.run(NetworkSimplex<Digraph>::ALTERING_LIST), 285 284 gr, l2, u, c, s1, true, 5970, "#B5"); 286 285 }
Note: See TracChangeset
for help on using the changeset viewer.