# HG changeset patch
# User Peter Kovacs <kpeter@inf.elte.hu>
# 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<ListDigraph> 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 <tt>(*this)</tt>
+ 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<Digraph> mcf1(gr), mcf2(gr), mcf3(gr), mcf4(gr),
- mcf5(gr), mcf6(gr), mcf7(gr), mcf8(gr);
+ NetworkSimplex<Digraph> 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<Digraph> mcf1(gr), mcf2(gr), mcf3(gr), mcf4(gr), mcf5(gr);
- NetworkSimplex<Digraph>::PivotRule pr;
+ NetworkSimplex<Digraph> mcf(gr);
+ mcf.supplyMap(s1).costMap(c).capacityMap(u).lowerMap(l2);
- pr = NetworkSimplex<Digraph>::FIRST_ELIGIBLE;
- checkMcf(mcf1, mcf1.boundMaps(l2, u).costMap(c).supplyMap(s1).run(pr),
+ checkMcf(mcf, mcf.run(NetworkSimplex<Digraph>::FIRST_ELIGIBLE),
gr, l2, u, c, s1, true, 5970, "#B1");
- pr = NetworkSimplex<Digraph>::BEST_ELIGIBLE;
- checkMcf(mcf2, mcf2.boundMaps(l2, u).costMap(c).supplyMap(s1).run(pr),
+ checkMcf(mcf, mcf.run(NetworkSimplex<Digraph>::BEST_ELIGIBLE),
gr, l2, u, c, s1, true, 5970, "#B2");
- pr = NetworkSimplex<Digraph>::BLOCK_SEARCH;
- checkMcf(mcf3, mcf3.boundMaps(l2, u).costMap(c).supplyMap(s1).run(pr),
+ checkMcf(mcf, mcf.run(NetworkSimplex<Digraph>::BLOCK_SEARCH),
gr, l2, u, c, s1, true, 5970, "#B3");
- pr = NetworkSimplex<Digraph>::CANDIDATE_LIST;
- checkMcf(mcf4, mcf4.boundMaps(l2, u).costMap(c).supplyMap(s1).run(pr),
+ checkMcf(mcf, mcf.run(NetworkSimplex<Digraph>::CANDIDATE_LIST),
gr, l2, u, c, s1, true, 5970, "#B4");
- pr = NetworkSimplex<Digraph>::ALTERING_LIST;
- checkMcf(mcf5, mcf5.boundMaps(l2, u).costMap(c).supplyMap(s1).run(pr),
+ checkMcf(mcf, mcf.run(NetworkSimplex<Digraph>::ALTERING_LIST),
gr, l2, u, c, s1, true, 5970, "#B5");
}