# HG changeset patch # User Peter Kovacs # Date 1238013470 -3600 # Node ID c7d160f73d52e2d3f1ab1236cb0b440daf5f7a85 # Parent 5232721b3f1430a5035eed7913c9024a4c24ed8c Support multiple run() calls in NetworkSimplex (#234) diff -r 5232721b3f14 -r c7d160f73d52 lemon/network_simplex.h --- a/lemon/network_simplex.h Wed Mar 25 15:58:44 2009 +0100 +++ b/lemon/network_simplex.h Wed Mar 25 21:37:50 2009 +0100 @@ -41,12 +41,18 @@ /// /// \ref NetworkSimplex implements the primal Network Simplex algorithm /// for finding a \ref min_cost_flow "minimum cost flow". + /// This algorithm is a specialized version of the linear programming + /// simplex method directly for the minimum cost flow problem. + /// It is one of the most efficient solution methods. + /// + /// In general this class is the fastest implementation available + /// in LEMON for the minimum cost flow problem. /// /// \tparam GR The digraph type the algorithm runs on. /// \tparam V The value type used in the algorithm. /// By default it is \c int. /// - /// \warning \c V must be a signed integer type. + /// \warning The value type must be a signed integer type. /// /// \note %NetworkSimplex provides five different pivot rule /// implementations. For more information see \ref PivotRule. @@ -789,7 +795,7 @@ /// /// This function runs the algorithm. /// The paramters can be specified using \ref lowerMap(), - /// \ref upperMap(), \ref capacityMap(), \ref boundMaps(), + /// \ref upperMap(), \ref capacityMap(), \ref boundMaps(), /// \ref costMap(), \ref supplyMap() and \ref stSupply() /// functions. For example, /// \code @@ -798,6 +804,11 @@ /// .supplyMap(sup).run(); /// \endcode /// + /// This function can be called more than once. All the parameters + /// that have been given are kept for the next call, unless + /// \ref reset() is called, thus only the modified parameters + /// have to be set again. See \ref reset() for examples. + /// /// \param pivot_rule The pivot rule that will be used during the /// algorithm. For more information see \ref PivotRule. /// @@ -806,6 +817,51 @@ return init() && start(pivot_rule); } + /// \brief Reset all the parameters that have been given before. + /// + /// This function resets all the paramaters that have been given + /// using \ref lowerMap(), \ref upperMap(), \ref capacityMap(), + /// \ref boundMaps(), \ref costMap(), \ref supplyMap() and + /// \ref stSupply() functions before. + /// + /// It is useful for multiple run() calls. If this function is not + /// used, all the parameters given before are kept for the next + /// \ref run() call. + /// + /// For example, + /// \code + /// NetworkSimplex ns(graph); + /// + /// // First run + /// ns.lowerMap(lower).capacityMap(cap).costMap(cost) + /// .supplyMap(sup).run(); + /// + /// // Run again with modified cost map (reset() is not called, + /// // so only the cost map have to be set again) + /// cost[e] += 100; + /// ns.costMap(cost).run(); + /// + /// // Run again from scratch using reset() + /// // (the lower bounds will be set to zero on all arcs) + /// ns.reset(); + /// ns.capacityMap(cap).costMap(cost) + /// .supplyMap(sup).run(); + /// \endcode + /// + /// \return (*this) + NetworkSimplex& reset() { + delete _plower; + delete _pupper; + delete _pcost; + delete _psupply; + _plower = NULL; + _pupper = NULL; + _pcost = NULL; + _psupply = NULL; + _pstsup = false; + return *this; + } + /// @} /// \name Query Functions @@ -920,8 +976,8 @@ _cap.resize(all_arc_num); _cost.resize(all_arc_num); _supply.resize(all_node_num); - _flow.resize(all_arc_num, 0); - _pi.resize(all_node_num, 0); + _flow.resize(all_arc_num); + _pi.resize(all_node_num); _parent.resize(all_node_num); _pred.resize(all_node_num); @@ -930,7 +986,7 @@ _rev_thread.resize(all_node_num); _succ_num.resize(all_node_num); _last_succ.resize(all_node_num); - _state.resize(all_arc_num, STATE_LOWER); + _state.resize(all_arc_num); // Initialize node related data bool valid_supply = true; @@ -986,12 +1042,16 @@ _target[i] = _node_id[_graph.target(e)]; _cap[i] = (*_pupper)[e]; _cost[i] = (*_pcost)[e]; + _flow[i] = 0; + _state[i] = STATE_LOWER; } } else { for (int i = 0; i != _arc_num; ++i) { Arc e = _arc_ref[i]; _source[i] = _node_id[_graph.source(e)]; _target[i] = _node_id[_graph.target(e)]; + _flow[i] = 0; + _state[i] = STATE_LOWER; } if (_pupper) { for (int i = 0; i != _arc_num; ++i) @@ -1032,6 +1092,9 @@ _last_succ[u] = u; _parent[u] = _root; _pred[u] = e; + _cost[e] = max_cost; + _cap[e] = max_cap; + _state[e] = STATE_TREE; if (_supply[u] >= 0) { _flow[e] = _supply[u]; _forward[u] = true; @@ -1041,9 +1104,6 @@ _forward[u] = false; _pi[u] = max_cost; } - _cost[e] = max_cost; - _cap[e] = max_cap; - _state[e] = STATE_TREE; } return true; diff -r 5232721b3f14 -r c7d160f73d52 test/min_cost_flow_test.cc --- a/test/min_cost_flow_test.cc Wed Mar 25 15:58:44 2009 +0100 +++ b/test/min_cost_flow_test.cc Wed Mar 25 21:37:50 2009 +0100 @@ -89,7 +89,8 @@ MCF mcf(g); - b = mcf.lowerMap(lower) + b = mcf.reset() + .lowerMap(lower) .upperMap(upper) .capacityMap(upper) .boundMaps(lower, upper) @@ -242,46 +243,44 @@ // A. Test NetworkSimplex with the default pivot rule { - NetworkSimplex mcf1(gr), mcf2(gr), mcf3(gr), mcf4(gr), - mcf5(gr), mcf6(gr), mcf7(gr), mcf8(gr); + NetworkSimplex mcf(gr); - checkMcf(mcf1, mcf1.upperMap(u).costMap(c).supplyMap(s1).run(), + mcf.upperMap(u).costMap(c); + checkMcf(mcf, mcf.supplyMap(s1).run(), gr, l1, u, c, s1, true, 5240, "#A1"); - checkMcf(mcf2, mcf2.upperMap(u).costMap(c).stSupply(v, w, 27).run(), + checkMcf(mcf, mcf.stSupply(v, w, 27).run(), gr, l1, u, c, s2, true, 7620, "#A2"); - checkMcf(mcf3, mcf3.boundMaps(l2, u).costMap(c).supplyMap(s1).run(), + mcf.lowerMap(l2); + checkMcf(mcf, mcf.supplyMap(s1).run(), gr, l2, u, c, s1, true, 5970, "#A3"); - checkMcf(mcf4, mcf4.boundMaps(l2, u).costMap(c).stSupply(v, w, 27).run(), + checkMcf(mcf, mcf.stSupply(v, w, 27).run(), gr, l2, u, c, s2, true, 8010, "#A4"); - checkMcf(mcf5, mcf5.supplyMap(s1).run(), + mcf.reset(); + checkMcf(mcf, mcf.supplyMap(s1).run(), gr, l1, cu, cc, s1, true, 74, "#A5"); - checkMcf(mcf6, mcf6.stSupply(v, w, 27).lowerMap(l2).run(), + checkMcf(mcf, mcf.lowerMap(l2).stSupply(v, w, 27).run(), gr, l2, cu, cc, s2, true, 94, "#A6"); - checkMcf(mcf7, mcf7.run(), + mcf.reset(); + checkMcf(mcf, mcf.run(), gr, l1, cu, cc, s3, true, 0, "#A7"); - checkMcf(mcf8, mcf8.boundMaps(l2, u).run(), + checkMcf(mcf, mcf.boundMaps(l2, u).run(), gr, l2, u, cc, s3, false, 0, "#A8"); } // B. Test NetworkSimplex with each pivot rule { - NetworkSimplex mcf1(gr), mcf2(gr), mcf3(gr), mcf4(gr), mcf5(gr); - NetworkSimplex::PivotRule pr; + NetworkSimplex mcf(gr); + mcf.supplyMap(s1).costMap(c).capacityMap(u).lowerMap(l2); - pr = NetworkSimplex::FIRST_ELIGIBLE; - checkMcf(mcf1, mcf1.boundMaps(l2, u).costMap(c).supplyMap(s1).run(pr), + checkMcf(mcf, mcf.run(NetworkSimplex::FIRST_ELIGIBLE), gr, l2, u, c, s1, true, 5970, "#B1"); - pr = NetworkSimplex::BEST_ELIGIBLE; - checkMcf(mcf2, mcf2.boundMaps(l2, u).costMap(c).supplyMap(s1).run(pr), + checkMcf(mcf, mcf.run(NetworkSimplex::BEST_ELIGIBLE), gr, l2, u, c, s1, true, 5970, "#B2"); - pr = NetworkSimplex::BLOCK_SEARCH; - checkMcf(mcf3, mcf3.boundMaps(l2, u).costMap(c).supplyMap(s1).run(pr), + checkMcf(mcf, mcf.run(NetworkSimplex::BLOCK_SEARCH), gr, l2, u, c, s1, true, 5970, "#B3"); - pr = NetworkSimplex::CANDIDATE_LIST; - checkMcf(mcf4, mcf4.boundMaps(l2, u).costMap(c).supplyMap(s1).run(pr), + checkMcf(mcf, mcf.run(NetworkSimplex::CANDIDATE_LIST), gr, l2, u, c, s1, true, 5970, "#B4"); - pr = NetworkSimplex::ALTERING_LIST; - checkMcf(mcf5, mcf5.boundMaps(l2, u).costMap(c).supplyMap(s1).run(pr), + checkMcf(mcf, mcf.run(NetworkSimplex::ALTERING_LIST), gr, l2, u, c, s1, true, 5970, "#B5"); }