1.1 --- a/lemon/network_simplex.h Wed Mar 25 15:58:44 2009 +0100
1.2 +++ b/lemon/network_simplex.h Wed Mar 25 21:37:50 2009 +0100
1.3 @@ -41,12 +41,18 @@
1.4 ///
1.5 /// \ref NetworkSimplex implements the primal Network Simplex algorithm
1.6 /// for finding a \ref min_cost_flow "minimum cost flow".
1.7 + /// This algorithm is a specialized version of the linear programming
1.8 + /// simplex method directly for the minimum cost flow problem.
1.9 + /// It is one of the most efficient solution methods.
1.10 + ///
1.11 + /// In general this class is the fastest implementation available
1.12 + /// in LEMON for the minimum cost flow problem.
1.13 ///
1.14 /// \tparam GR The digraph type the algorithm runs on.
1.15 /// \tparam V The value type used in the algorithm.
1.16 /// By default it is \c int.
1.17 ///
1.18 - /// \warning \c V must be a signed integer type.
1.19 + /// \warning The value type must be a signed integer type.
1.20 ///
1.21 /// \note %NetworkSimplex provides five different pivot rule
1.22 /// implementations. For more information see \ref PivotRule.
1.23 @@ -789,7 +795,7 @@
1.24 ///
1.25 /// This function runs the algorithm.
1.26 /// The paramters can be specified using \ref lowerMap(),
1.27 - /// \ref upperMap(), \ref capacityMap(), \ref boundMaps(),
1.28 + /// \ref upperMap(), \ref capacityMap(), \ref boundMaps(),
1.29 /// \ref costMap(), \ref supplyMap() and \ref stSupply()
1.30 /// functions. For example,
1.31 /// \code
1.32 @@ -798,6 +804,11 @@
1.33 /// .supplyMap(sup).run();
1.34 /// \endcode
1.35 ///
1.36 + /// This function can be called more than once. All the parameters
1.37 + /// that have been given are kept for the next call, unless
1.38 + /// \ref reset() is called, thus only the modified parameters
1.39 + /// have to be set again. See \ref reset() for examples.
1.40 + ///
1.41 /// \param pivot_rule The pivot rule that will be used during the
1.42 /// algorithm. For more information see \ref PivotRule.
1.43 ///
1.44 @@ -806,6 +817,51 @@
1.45 return init() && start(pivot_rule);
1.46 }
1.47
1.48 + /// \brief Reset all the parameters that have been given before.
1.49 + ///
1.50 + /// This function resets all the paramaters that have been given
1.51 + /// using \ref lowerMap(), \ref upperMap(), \ref capacityMap(),
1.52 + /// \ref boundMaps(), \ref costMap(), \ref supplyMap() and
1.53 + /// \ref stSupply() functions before.
1.54 + ///
1.55 + /// It is useful for multiple run() calls. If this function is not
1.56 + /// used, all the parameters given before are kept for the next
1.57 + /// \ref run() call.
1.58 + ///
1.59 + /// For example,
1.60 + /// \code
1.61 + /// NetworkSimplex<ListDigraph> ns(graph);
1.62 + ///
1.63 + /// // First run
1.64 + /// ns.lowerMap(lower).capacityMap(cap).costMap(cost)
1.65 + /// .supplyMap(sup).run();
1.66 + ///
1.67 + /// // Run again with modified cost map (reset() is not called,
1.68 + /// // so only the cost map have to be set again)
1.69 + /// cost[e] += 100;
1.70 + /// ns.costMap(cost).run();
1.71 + ///
1.72 + /// // Run again from scratch using reset()
1.73 + /// // (the lower bounds will be set to zero on all arcs)
1.74 + /// ns.reset();
1.75 + /// ns.capacityMap(cap).costMap(cost)
1.76 + /// .supplyMap(sup).run();
1.77 + /// \endcode
1.78 + ///
1.79 + /// \return <tt>(*this)</tt>
1.80 + NetworkSimplex& reset() {
1.81 + delete _plower;
1.82 + delete _pupper;
1.83 + delete _pcost;
1.84 + delete _psupply;
1.85 + _plower = NULL;
1.86 + _pupper = NULL;
1.87 + _pcost = NULL;
1.88 + _psupply = NULL;
1.89 + _pstsup = false;
1.90 + return *this;
1.91 + }
1.92 +
1.93 /// @}
1.94
1.95 /// \name Query Functions
1.96 @@ -920,8 +976,8 @@
1.97 _cap.resize(all_arc_num);
1.98 _cost.resize(all_arc_num);
1.99 _supply.resize(all_node_num);
1.100 - _flow.resize(all_arc_num, 0);
1.101 - _pi.resize(all_node_num, 0);
1.102 + _flow.resize(all_arc_num);
1.103 + _pi.resize(all_node_num);
1.104
1.105 _parent.resize(all_node_num);
1.106 _pred.resize(all_node_num);
1.107 @@ -930,7 +986,7 @@
1.108 _rev_thread.resize(all_node_num);
1.109 _succ_num.resize(all_node_num);
1.110 _last_succ.resize(all_node_num);
1.111 - _state.resize(all_arc_num, STATE_LOWER);
1.112 + _state.resize(all_arc_num);
1.113
1.114 // Initialize node related data
1.115 bool valid_supply = true;
1.116 @@ -986,12 +1042,16 @@
1.117 _target[i] = _node_id[_graph.target(e)];
1.118 _cap[i] = (*_pupper)[e];
1.119 _cost[i] = (*_pcost)[e];
1.120 + _flow[i] = 0;
1.121 + _state[i] = STATE_LOWER;
1.122 }
1.123 } else {
1.124 for (int i = 0; i != _arc_num; ++i) {
1.125 Arc e = _arc_ref[i];
1.126 _source[i] = _node_id[_graph.source(e)];
1.127 _target[i] = _node_id[_graph.target(e)];
1.128 + _flow[i] = 0;
1.129 + _state[i] = STATE_LOWER;
1.130 }
1.131 if (_pupper) {
1.132 for (int i = 0; i != _arc_num; ++i)
1.133 @@ -1032,6 +1092,9 @@
1.134 _last_succ[u] = u;
1.135 _parent[u] = _root;
1.136 _pred[u] = e;
1.137 + _cost[e] = max_cost;
1.138 + _cap[e] = max_cap;
1.139 + _state[e] = STATE_TREE;
1.140 if (_supply[u] >= 0) {
1.141 _flow[e] = _supply[u];
1.142 _forward[u] = true;
1.143 @@ -1041,9 +1104,6 @@
1.144 _forward[u] = false;
1.145 _pi[u] = max_cost;
1.146 }
1.147 - _cost[e] = max_cost;
1.148 - _cap[e] = max_cap;
1.149 - _state[e] = STATE_TREE;
1.150 }
1.151
1.152 return true;
2.1 --- a/test/min_cost_flow_test.cc Wed Mar 25 15:58:44 2009 +0100
2.2 +++ b/test/min_cost_flow_test.cc Wed Mar 25 21:37:50 2009 +0100
2.3 @@ -89,7 +89,8 @@
2.4
2.5 MCF mcf(g);
2.6
2.7 - b = mcf.lowerMap(lower)
2.8 + b = mcf.reset()
2.9 + .lowerMap(lower)
2.10 .upperMap(upper)
2.11 .capacityMap(upper)
2.12 .boundMaps(lower, upper)
2.13 @@ -242,46 +243,44 @@
2.14
2.15 // A. Test NetworkSimplex with the default pivot rule
2.16 {
2.17 - NetworkSimplex<Digraph> mcf1(gr), mcf2(gr), mcf3(gr), mcf4(gr),
2.18 - mcf5(gr), mcf6(gr), mcf7(gr), mcf8(gr);
2.19 + NetworkSimplex<Digraph> mcf(gr);
2.20
2.21 - checkMcf(mcf1, mcf1.upperMap(u).costMap(c).supplyMap(s1).run(),
2.22 + mcf.upperMap(u).costMap(c);
2.23 + checkMcf(mcf, mcf.supplyMap(s1).run(),
2.24 gr, l1, u, c, s1, true, 5240, "#A1");
2.25 - checkMcf(mcf2, mcf2.upperMap(u).costMap(c).stSupply(v, w, 27).run(),
2.26 + checkMcf(mcf, mcf.stSupply(v, w, 27).run(),
2.27 gr, l1, u, c, s2, true, 7620, "#A2");
2.28 - checkMcf(mcf3, mcf3.boundMaps(l2, u).costMap(c).supplyMap(s1).run(),
2.29 + mcf.lowerMap(l2);
2.30 + checkMcf(mcf, mcf.supplyMap(s1).run(),
2.31 gr, l2, u, c, s1, true, 5970, "#A3");
2.32 - checkMcf(mcf4, mcf4.boundMaps(l2, u).costMap(c).stSupply(v, w, 27).run(),
2.33 + checkMcf(mcf, mcf.stSupply(v, w, 27).run(),
2.34 gr, l2, u, c, s2, true, 8010, "#A4");
2.35 - checkMcf(mcf5, mcf5.supplyMap(s1).run(),
2.36 + mcf.reset();
2.37 + checkMcf(mcf, mcf.supplyMap(s1).run(),
2.38 gr, l1, cu, cc, s1, true, 74, "#A5");
2.39 - checkMcf(mcf6, mcf6.stSupply(v, w, 27).lowerMap(l2).run(),
2.40 + checkMcf(mcf, mcf.lowerMap(l2).stSupply(v, w, 27).run(),
2.41 gr, l2, cu, cc, s2, true, 94, "#A6");
2.42 - checkMcf(mcf7, mcf7.run(),
2.43 + mcf.reset();
2.44 + checkMcf(mcf, mcf.run(),
2.45 gr, l1, cu, cc, s3, true, 0, "#A7");
2.46 - checkMcf(mcf8, mcf8.boundMaps(l2, u).run(),
2.47 + checkMcf(mcf, mcf.boundMaps(l2, u).run(),
2.48 gr, l2, u, cc, s3, false, 0, "#A8");
2.49 }
2.50
2.51 // B. Test NetworkSimplex with each pivot rule
2.52 {
2.53 - NetworkSimplex<Digraph> mcf1(gr), mcf2(gr), mcf3(gr), mcf4(gr), mcf5(gr);
2.54 - NetworkSimplex<Digraph>::PivotRule pr;
2.55 + NetworkSimplex<Digraph> mcf(gr);
2.56 + mcf.supplyMap(s1).costMap(c).capacityMap(u).lowerMap(l2);
2.57
2.58 - pr = NetworkSimplex<Digraph>::FIRST_ELIGIBLE;
2.59 - checkMcf(mcf1, mcf1.boundMaps(l2, u).costMap(c).supplyMap(s1).run(pr),
2.60 + checkMcf(mcf, mcf.run(NetworkSimplex<Digraph>::FIRST_ELIGIBLE),
2.61 gr, l2, u, c, s1, true, 5970, "#B1");
2.62 - pr = NetworkSimplex<Digraph>::BEST_ELIGIBLE;
2.63 - checkMcf(mcf2, mcf2.boundMaps(l2, u).costMap(c).supplyMap(s1).run(pr),
2.64 + checkMcf(mcf, mcf.run(NetworkSimplex<Digraph>::BEST_ELIGIBLE),
2.65 gr, l2, u, c, s1, true, 5970, "#B2");
2.66 - pr = NetworkSimplex<Digraph>::BLOCK_SEARCH;
2.67 - checkMcf(mcf3, mcf3.boundMaps(l2, u).costMap(c).supplyMap(s1).run(pr),
2.68 + checkMcf(mcf, mcf.run(NetworkSimplex<Digraph>::BLOCK_SEARCH),
2.69 gr, l2, u, c, s1, true, 5970, "#B3");
2.70 - pr = NetworkSimplex<Digraph>::CANDIDATE_LIST;
2.71 - checkMcf(mcf4, mcf4.boundMaps(l2, u).costMap(c).supplyMap(s1).run(pr),
2.72 + checkMcf(mcf, mcf.run(NetworkSimplex<Digraph>::CANDIDATE_LIST),
2.73 gr, l2, u, c, s1, true, 5970, "#B4");
2.74 - pr = NetworkSimplex<Digraph>::ALTERING_LIST;
2.75 - checkMcf(mcf5, mcf5.boundMaps(l2, u).costMap(c).supplyMap(s1).run(pr),
2.76 + checkMcf(mcf, mcf.run(NetworkSimplex<Digraph>::ALTERING_LIST),
2.77 gr, l2, u, c, s1, true, 5970, "#B5");
2.78 }
2.79