# HG changeset patch
# User Peter Kovacs <kpeter@inf.elte.hu>
# Date 1265825120 -3600
# Node ID 75c97c3786d67ff19a6421c06ed497166ed310bd
# Parent a7e93de12cbda2267756b130476b8e84572002bf
Handle graph changes in the MCF algorithms (#327)
The reset() functions are renamed to resetParams() and the new reset()
functions handle the graph chnages, as well.
diff -r a7e93de12cbd -r 75c97c3786d6 lemon/capacity_scaling.h
--- a/lemon/capacity_scaling.h Tue Feb 09 23:29:51 2010 +0100
+++ b/lemon/capacity_scaling.h Wed Feb 10 19:05:20 2010 +0100
@@ -314,69 +314,7 @@
LEMON_ASSERT(std::numeric_limits<Cost>::is_signed,
"The cost type of CapacityScaling must be signed");
- // Resize vectors
- _node_num = countNodes(_graph);
- _arc_num = countArcs(_graph);
- _res_arc_num = 2 * (_arc_num + _node_num);
- _root = _node_num;
- ++_node_num;
-
- _first_out.resize(_node_num + 1);
- _forward.resize(_res_arc_num);
- _source.resize(_res_arc_num);
- _target.resize(_res_arc_num);
- _reverse.resize(_res_arc_num);
-
- _lower.resize(_res_arc_num);
- _upper.resize(_res_arc_num);
- _cost.resize(_res_arc_num);
- _supply.resize(_node_num);
-
- _res_cap.resize(_res_arc_num);
- _pi.resize(_node_num);
- _excess.resize(_node_num);
- _pred.resize(_node_num);
-
- // Copy the graph
- int i = 0, j = 0, k = 2 * _arc_num + _node_num - 1;
- for (NodeIt n(_graph); n != INVALID; ++n, ++i) {
- _node_id[n] = i;
- }
- i = 0;
- for (NodeIt n(_graph); n != INVALID; ++n, ++i) {
- _first_out[i] = j;
- for (OutArcIt a(_graph, n); a != INVALID; ++a, ++j) {
- _arc_idf[a] = j;
- _forward[j] = true;
- _source[j] = i;
- _target[j] = _node_id[_graph.runningNode(a)];
- }
- for (InArcIt a(_graph, n); a != INVALID; ++a, ++j) {
- _arc_idb[a] = j;
- _forward[j] = false;
- _source[j] = i;
- _target[j] = _node_id[_graph.runningNode(a)];
- }
- _forward[j] = false;
- _source[j] = i;
- _target[j] = _root;
- _reverse[j] = k;
- _forward[k] = true;
- _source[k] = _root;
- _target[k] = i;
- _reverse[k] = j;
- ++j; ++k;
- }
- _first_out[i] = j;
- _first_out[_node_num] = k;
- for (ArcIt a(_graph); a != INVALID; ++a) {
- int fi = _arc_idf[a];
- int bi = _arc_idb[a];
- _reverse[fi] = bi;
- _reverse[bi] = fi;
- }
-
- // Reset parameters
+ // Reset data structures
reset();
}
@@ -511,12 +449,12 @@
/// .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.
- /// However, the underlying digraph must not be modified after this
- /// class have been constructed, since it copies and extends the graph.
+ /// This function can be called more than once. All the given parameters
+ /// are kept for the next call, unless \ref resetParams() or \ref reset()
+ /// is used, thus only the modified parameters have to be set again.
+ /// If the underlying digraph was also modified after the construction
+ /// of the class (or the last \ref reset() call), then the \ref reset()
+ /// function must be called.
///
/// \param factor The capacity scaling factor. It must be larger than
/// one to use scaling. If it is less or equal to one, then scaling
@@ -533,6 +471,7 @@
/// these cases.
///
/// \see ProblemType
+ /// \see resetParams(), reset()
ProblemType run(int factor = 4) {
_factor = factor;
ProblemType pt = init();
@@ -546,11 +485,12 @@
/// before using functions \ref lowerMap(), \ref upperMap(),
/// \ref costMap(), \ref supplyMap(), \ref stSupply().
///
- /// 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.
- /// However, the underlying digraph must not be modified after this
- /// class have been constructed, since it copies and extends the graph.
+ /// It is useful for multiple \ref run() calls. Basically, all the given
+ /// parameters are kept for the next \ref run() call, unless
+ /// \ref resetParams() or \ref reset() is used.
+ /// If the underlying digraph was also modified after the construction
+ /// of the class or the last \ref reset() call, then the \ref reset()
+ /// function must be used, otherwise \ref resetParams() is sufficient.
///
/// For example,
/// \code
@@ -560,20 +500,22 @@
/// cs.lowerMap(lower).upperMap(upper).costMap(cost)
/// .supplyMap(sup).run();
///
- /// // Run again with modified cost map (reset() is not called,
+ /// // Run again with modified cost map (resetParams() is not called,
/// // so only the cost map have to be set again)
/// cost[e] += 100;
/// cs.costMap(cost).run();
///
- /// // Run again from scratch using reset()
+ /// // Run again from scratch using resetParams()
/// // (the lower bounds will be set to zero on all arcs)
- /// cs.reset();
+ /// cs.resetParams();
/// cs.upperMap(capacity).costMap(cost)
/// .supplyMap(sup).run();
/// \endcode
///
/// \return <tt>(*this)</tt>
- CapacityScaling& reset() {
+ ///
+ /// \see reset(), run()
+ CapacityScaling& resetParams() {
for (int i = 0; i != _node_num; ++i) {
_supply[i] = 0;
}
@@ -586,6 +528,93 @@
return *this;
}
+ /// \brief Reset the internal data structures and all the parameters
+ /// that have been given before.
+ ///
+ /// This function resets the internal data structures and all the
+ /// paramaters that have been given before using functions \ref lowerMap(),
+ /// \ref upperMap(), \ref costMap(), \ref supplyMap(), \ref stSupply().
+ ///
+ /// It is useful for multiple \ref run() calls. Basically, all the given
+ /// parameters are kept for the next \ref run() call, unless
+ /// \ref resetParams() or \ref reset() is used.
+ /// If the underlying digraph was also modified after the construction
+ /// of the class or the last \ref reset() call, then the \ref reset()
+ /// function must be used, otherwise \ref resetParams() is sufficient.
+ ///
+ /// See \ref resetParams() for examples.
+ ///
+ /// \return <tt>(*this)</tt>
+ ///
+ /// \see resetParams(), run()
+ CapacityScaling& reset() {
+ // Resize vectors
+ _node_num = countNodes(_graph);
+ _arc_num = countArcs(_graph);
+ _res_arc_num = 2 * (_arc_num + _node_num);
+ _root = _node_num;
+ ++_node_num;
+
+ _first_out.resize(_node_num + 1);
+ _forward.resize(_res_arc_num);
+ _source.resize(_res_arc_num);
+ _target.resize(_res_arc_num);
+ _reverse.resize(_res_arc_num);
+
+ _lower.resize(_res_arc_num);
+ _upper.resize(_res_arc_num);
+ _cost.resize(_res_arc_num);
+ _supply.resize(_node_num);
+
+ _res_cap.resize(_res_arc_num);
+ _pi.resize(_node_num);
+ _excess.resize(_node_num);
+ _pred.resize(_node_num);
+
+ // Copy the graph
+ int i = 0, j = 0, k = 2 * _arc_num + _node_num - 1;
+ for (NodeIt n(_graph); n != INVALID; ++n, ++i) {
+ _node_id[n] = i;
+ }
+ i = 0;
+ for (NodeIt n(_graph); n != INVALID; ++n, ++i) {
+ _first_out[i] = j;
+ for (OutArcIt a(_graph, n); a != INVALID; ++a, ++j) {
+ _arc_idf[a] = j;
+ _forward[j] = true;
+ _source[j] = i;
+ _target[j] = _node_id[_graph.runningNode(a)];
+ }
+ for (InArcIt a(_graph, n); a != INVALID; ++a, ++j) {
+ _arc_idb[a] = j;
+ _forward[j] = false;
+ _source[j] = i;
+ _target[j] = _node_id[_graph.runningNode(a)];
+ }
+ _forward[j] = false;
+ _source[j] = i;
+ _target[j] = _root;
+ _reverse[j] = k;
+ _forward[k] = true;
+ _source[k] = _root;
+ _target[k] = i;
+ _reverse[k] = j;
+ ++j; ++k;
+ }
+ _first_out[i] = j;
+ _first_out[_node_num] = k;
+ for (ArcIt a(_graph); a != INVALID; ++a) {
+ int fi = _arc_idf[a];
+ int bi = _arc_idb[a];
+ _reverse[fi] = bi;
+ _reverse[bi] = fi;
+ }
+
+ // Reset parameters
+ resetParams();
+ return *this;
+ }
+
/// @}
/// \name Query Functions
diff -r a7e93de12cbd -r 75c97c3786d6 lemon/cost_scaling.h
--- a/lemon/cost_scaling.h Tue Feb 09 23:29:51 2010 +0100
+++ b/lemon/cost_scaling.h Wed Feb 10 19:05:20 2010 +0100
@@ -332,74 +332,8 @@
"The flow type of CostScaling must be signed");
LEMON_ASSERT(std::numeric_limits<Cost>::is_signed,
"The cost type of CostScaling must be signed");
-
- // Resize vectors
- _node_num = countNodes(_graph);
- _arc_num = countArcs(_graph);
- _res_node_num = _node_num + 1;
- _res_arc_num = 2 * (_arc_num + _node_num);
- _root = _node_num;
-
- _first_out.resize(_res_node_num + 1);
- _forward.resize(_res_arc_num);
- _source.resize(_res_arc_num);
- _target.resize(_res_arc_num);
- _reverse.resize(_res_arc_num);
-
- _lower.resize(_res_arc_num);
- _upper.resize(_res_arc_num);
- _scost.resize(_res_arc_num);
- _supply.resize(_res_node_num);
- _res_cap.resize(_res_arc_num);
- _cost.resize(_res_arc_num);
- _pi.resize(_res_node_num);
- _excess.resize(_res_node_num);
- _next_out.resize(_res_node_num);
-
- _arc_vec.reserve(_res_arc_num);
- _cost_vec.reserve(_res_arc_num);
-
- // Copy the graph
- int i = 0, j = 0, k = 2 * _arc_num + _node_num;
- for (NodeIt n(_graph); n != INVALID; ++n, ++i) {
- _node_id[n] = i;
- }
- i = 0;
- for (NodeIt n(_graph); n != INVALID; ++n, ++i) {
- _first_out[i] = j;
- for (OutArcIt a(_graph, n); a != INVALID; ++a, ++j) {
- _arc_idf[a] = j;
- _forward[j] = true;
- _source[j] = i;
- _target[j] = _node_id[_graph.runningNode(a)];
- }
- for (InArcIt a(_graph, n); a != INVALID; ++a, ++j) {
- _arc_idb[a] = j;
- _forward[j] = false;
- _source[j] = i;
- _target[j] = _node_id[_graph.runningNode(a)];
- }
- _forward[j] = false;
- _source[j] = i;
- _target[j] = _root;
- _reverse[j] = k;
- _forward[k] = true;
- _source[k] = _root;
- _target[k] = i;
- _reverse[k] = j;
- ++j; ++k;
- }
- _first_out[i] = j;
- _first_out[_res_node_num] = k;
- for (ArcIt a(_graph); a != INVALID; ++a) {
- int fi = _arc_idf[a];
- int bi = _arc_idb[a];
- _reverse[fi] = bi;
- _reverse[bi] = fi;
- }
-
- // Reset parameters
+ // Reset data structures
reset();
}
@@ -534,12 +468,12 @@
/// .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.
- /// However, the underlying digraph must not be modified after this
- /// class have been constructed, since it copies and extends the graph.
+ /// This function can be called more than once. All the given parameters
+ /// are kept for the next call, unless \ref resetParams() or \ref reset()
+ /// is used, thus only the modified parameters have to be set again.
+ /// If the underlying digraph was also modified after the construction
+ /// of the class (or the last \ref reset() call), then the \ref reset()
+ /// function must be called.
///
/// \param method The internal method that will be used in the
/// algorithm. For more information, see \ref Method.
@@ -556,6 +490,7 @@
/// these cases.
///
/// \see ProblemType, Method
+ /// \see resetParams(), reset()
ProblemType run(Method method = PARTIAL_AUGMENT, int factor = 8) {
_alpha = factor;
ProblemType pt = init();
@@ -570,11 +505,12 @@
/// before using functions \ref lowerMap(), \ref upperMap(),
/// \ref costMap(), \ref supplyMap(), \ref stSupply().
///
- /// 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.
- /// However, the underlying digraph must not be modified after this
- /// class have been constructed, since it copies and extends the graph.
+ /// It is useful for multiple \ref run() calls. Basically, all the given
+ /// parameters are kept for the next \ref run() call, unless
+ /// \ref resetParams() or \ref reset() is used.
+ /// If the underlying digraph was also modified after the construction
+ /// of the class or the last \ref reset() call, then the \ref reset()
+ /// function must be used, otherwise \ref resetParams() is sufficient.
///
/// For example,
/// \code
@@ -584,20 +520,22 @@
/// cs.lowerMap(lower).upperMap(upper).costMap(cost)
/// .supplyMap(sup).run();
///
- /// // Run again with modified cost map (reset() is not called,
+ /// // Run again with modified cost map (resetParams() is not called,
/// // so only the cost map have to be set again)
/// cost[e] += 100;
/// cs.costMap(cost).run();
///
- /// // Run again from scratch using reset()
+ /// // Run again from scratch using resetParams()
/// // (the lower bounds will be set to zero on all arcs)
- /// cs.reset();
+ /// cs.resetParams();
/// cs.upperMap(capacity).costMap(cost)
/// .supplyMap(sup).run();
/// \endcode
///
/// \return <tt>(*this)</tt>
- CostScaling& reset() {
+ ///
+ /// \see reset(), run()
+ CostScaling& resetParams() {
for (int i = 0; i != _res_node_num; ++i) {
_supply[i] = 0;
}
@@ -617,6 +555,90 @@
return *this;
}
+ /// \brief Reset all the parameters that have been given before.
+ ///
+ /// This function resets all the paramaters that have been given
+ /// before using functions \ref lowerMap(), \ref upperMap(),
+ /// \ref costMap(), \ref supplyMap(), \ref stSupply().
+ ///
+ /// 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.
+ /// However, the underlying digraph must not be modified after this
+ /// class have been constructed, since it copies and extends the graph.
+ /// \return <tt>(*this)</tt>
+ CostScaling& reset() {
+ // Resize vectors
+ _node_num = countNodes(_graph);
+ _arc_num = countArcs(_graph);
+ _res_node_num = _node_num + 1;
+ _res_arc_num = 2 * (_arc_num + _node_num);
+ _root = _node_num;
+
+ _first_out.resize(_res_node_num + 1);
+ _forward.resize(_res_arc_num);
+ _source.resize(_res_arc_num);
+ _target.resize(_res_arc_num);
+ _reverse.resize(_res_arc_num);
+
+ _lower.resize(_res_arc_num);
+ _upper.resize(_res_arc_num);
+ _scost.resize(_res_arc_num);
+ _supply.resize(_res_node_num);
+
+ _res_cap.resize(_res_arc_num);
+ _cost.resize(_res_arc_num);
+ _pi.resize(_res_node_num);
+ _excess.resize(_res_node_num);
+ _next_out.resize(_res_node_num);
+
+ _arc_vec.reserve(_res_arc_num);
+ _cost_vec.reserve(_res_arc_num);
+
+ // Copy the graph
+ int i = 0, j = 0, k = 2 * _arc_num + _node_num;
+ for (NodeIt n(_graph); n != INVALID; ++n, ++i) {
+ _node_id[n] = i;
+ }
+ i = 0;
+ for (NodeIt n(_graph); n != INVALID; ++n, ++i) {
+ _first_out[i] = j;
+ for (OutArcIt a(_graph, n); a != INVALID; ++a, ++j) {
+ _arc_idf[a] = j;
+ _forward[j] = true;
+ _source[j] = i;
+ _target[j] = _node_id[_graph.runningNode(a)];
+ }
+ for (InArcIt a(_graph, n); a != INVALID; ++a, ++j) {
+ _arc_idb[a] = j;
+ _forward[j] = false;
+ _source[j] = i;
+ _target[j] = _node_id[_graph.runningNode(a)];
+ }
+ _forward[j] = false;
+ _source[j] = i;
+ _target[j] = _root;
+ _reverse[j] = k;
+ _forward[k] = true;
+ _source[k] = _root;
+ _target[k] = i;
+ _reverse[k] = j;
+ ++j; ++k;
+ }
+ _first_out[i] = j;
+ _first_out[_res_node_num] = k;
+ for (ArcIt a(_graph); a != INVALID; ++a) {
+ int fi = _arc_idf[a];
+ int bi = _arc_idb[a];
+ _reverse[fi] = bi;
+ _reverse[bi] = fi;
+ }
+
+ // Reset parameters
+ resetParams();
+ return *this;
+ }
+
/// @}
/// \name Query Functions
diff -r a7e93de12cbd -r 75c97c3786d6 lemon/cycle_canceling.h
--- a/lemon/cycle_canceling.h Tue Feb 09 23:29:51 2010 +0100
+++ b/lemon/cycle_canceling.h Wed Feb 10 19:05:20 2010 +0100
@@ -250,71 +250,7 @@
LEMON_ASSERT(std::numeric_limits<Cost>::is_signed,
"The cost type of CycleCanceling must be signed");
- // Resize vectors
- _node_num = countNodes(_graph);
- _arc_num = countArcs(_graph);
- _res_node_num = _node_num + 1;
- _res_arc_num = 2 * (_arc_num + _node_num);
- _root = _node_num;
-
- _first_out.resize(_res_node_num + 1);
- _forward.resize(_res_arc_num);
- _source.resize(_res_arc_num);
- _target.resize(_res_arc_num);
- _reverse.resize(_res_arc_num);
-
- _lower.resize(_res_arc_num);
- _upper.resize(_res_arc_num);
- _cost.resize(_res_arc_num);
- _supply.resize(_res_node_num);
-
- _res_cap.resize(_res_arc_num);
- _pi.resize(_res_node_num);
-
- _arc_vec.reserve(_res_arc_num);
- _cost_vec.reserve(_res_arc_num);
- _id_vec.reserve(_res_arc_num);
-
- // Copy the graph
- int i = 0, j = 0, k = 2 * _arc_num + _node_num;
- for (NodeIt n(_graph); n != INVALID; ++n, ++i) {
- _node_id[n] = i;
- }
- i = 0;
- for (NodeIt n(_graph); n != INVALID; ++n, ++i) {
- _first_out[i] = j;
- for (OutArcIt a(_graph, n); a != INVALID; ++a, ++j) {
- _arc_idf[a] = j;
- _forward[j] = true;
- _source[j] = i;
- _target[j] = _node_id[_graph.runningNode(a)];
- }
- for (InArcIt a(_graph, n); a != INVALID; ++a, ++j) {
- _arc_idb[a] = j;
- _forward[j] = false;
- _source[j] = i;
- _target[j] = _node_id[_graph.runningNode(a)];
- }
- _forward[j] = false;
- _source[j] = i;
- _target[j] = _root;
- _reverse[j] = k;
- _forward[k] = true;
- _source[k] = _root;
- _target[k] = i;
- _reverse[k] = j;
- ++j; ++k;
- }
- _first_out[i] = j;
- _first_out[_res_node_num] = k;
- for (ArcIt a(_graph); a != INVALID; ++a) {
- int fi = _arc_idf[a];
- int bi = _arc_idb[a];
- _reverse[fi] = bi;
- _reverse[bi] = fi;
- }
-
- // Reset parameters
+ // Reset data structures
reset();
}
@@ -449,12 +385,12 @@
/// .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.
- /// However, the underlying digraph must not be modified after this
- /// class have been constructed, since it copies and extends the graph.
+ /// This function can be called more than once. All the given parameters
+ /// are kept for the next call, unless \ref resetParams() or \ref reset()
+ /// is used, thus only the modified parameters have to be set again.
+ /// If the underlying digraph was also modified after the construction
+ /// of the class (or the last \ref reset() call), then the \ref reset()
+ /// function must be called.
///
/// \param method The cycle-canceling method that will be used.
/// For more information, see \ref Method.
@@ -470,6 +406,7 @@
/// these cases.
///
/// \see ProblemType, Method
+ /// \see resetParams(), reset()
ProblemType run(Method method = CANCEL_AND_TIGHTEN) {
ProblemType pt = init();
if (pt != OPTIMAL) return pt;
@@ -483,11 +420,12 @@
/// before using functions \ref lowerMap(), \ref upperMap(),
/// \ref costMap(), \ref supplyMap(), \ref stSupply().
///
- /// 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.
- /// However, the underlying digraph must not be modified after this
- /// class have been constructed, since it copies and extends the graph.
+ /// It is useful for multiple \ref run() calls. Basically, all the given
+ /// parameters are kept for the next \ref run() call, unless
+ /// \ref resetParams() or \ref reset() is used.
+ /// If the underlying digraph was also modified after the construction
+ /// of the class or the last \ref reset() call, then the \ref reset()
+ /// function must be used, otherwise \ref resetParams() is sufficient.
///
/// For example,
/// \code
@@ -497,20 +435,22 @@
/// cc.lowerMap(lower).upperMap(upper).costMap(cost)
/// .supplyMap(sup).run();
///
- /// // Run again with modified cost map (reset() is not called,
+ /// // Run again with modified cost map (resetParams() is not called,
/// // so only the cost map have to be set again)
/// cost[e] += 100;
/// cc.costMap(cost).run();
///
- /// // Run again from scratch using reset()
+ /// // Run again from scratch using resetParams()
/// // (the lower bounds will be set to zero on all arcs)
- /// cc.reset();
+ /// cc.resetParams();
/// cc.upperMap(capacity).costMap(cost)
/// .supplyMap(sup).run();
/// \endcode
///
/// \return <tt>(*this)</tt>
- CycleCanceling& reset() {
+ ///
+ /// \see reset(), run()
+ CycleCanceling& resetParams() {
for (int i = 0; i != _res_node_num; ++i) {
_supply[i] = 0;
}
@@ -530,6 +470,95 @@
return *this;
}
+ /// \brief Reset the internal data structures and all the parameters
+ /// that have been given before.
+ ///
+ /// This function resets the internal data structures and all the
+ /// paramaters that have been given before using functions \ref lowerMap(),
+ /// \ref upperMap(), \ref costMap(), \ref supplyMap(), \ref stSupply().
+ ///
+ /// It is useful for multiple \ref run() calls. Basically, all the given
+ /// parameters are kept for the next \ref run() call, unless
+ /// \ref resetParams() or \ref reset() is used.
+ /// If the underlying digraph was also modified after the construction
+ /// of the class or the last \ref reset() call, then the \ref reset()
+ /// function must be used, otherwise \ref resetParams() is sufficient.
+ ///
+ /// See \ref resetParams() for examples.
+ ///
+ /// \return <tt>(*this)</tt>
+ ///
+ /// \see resetParams(), run()
+ CycleCanceling& reset() {
+ // Resize vectors
+ _node_num = countNodes(_graph);
+ _arc_num = countArcs(_graph);
+ _res_node_num = _node_num + 1;
+ _res_arc_num = 2 * (_arc_num + _node_num);
+ _root = _node_num;
+
+ _first_out.resize(_res_node_num + 1);
+ _forward.resize(_res_arc_num);
+ _source.resize(_res_arc_num);
+ _target.resize(_res_arc_num);
+ _reverse.resize(_res_arc_num);
+
+ _lower.resize(_res_arc_num);
+ _upper.resize(_res_arc_num);
+ _cost.resize(_res_arc_num);
+ _supply.resize(_res_node_num);
+
+ _res_cap.resize(_res_arc_num);
+ _pi.resize(_res_node_num);
+
+ _arc_vec.reserve(_res_arc_num);
+ _cost_vec.reserve(_res_arc_num);
+ _id_vec.reserve(_res_arc_num);
+
+ // Copy the graph
+ int i = 0, j = 0, k = 2 * _arc_num + _node_num;
+ for (NodeIt n(_graph); n != INVALID; ++n, ++i) {
+ _node_id[n] = i;
+ }
+ i = 0;
+ for (NodeIt n(_graph); n != INVALID; ++n, ++i) {
+ _first_out[i] = j;
+ for (OutArcIt a(_graph, n); a != INVALID; ++a, ++j) {
+ _arc_idf[a] = j;
+ _forward[j] = true;
+ _source[j] = i;
+ _target[j] = _node_id[_graph.runningNode(a)];
+ }
+ for (InArcIt a(_graph, n); a != INVALID; ++a, ++j) {
+ _arc_idb[a] = j;
+ _forward[j] = false;
+ _source[j] = i;
+ _target[j] = _node_id[_graph.runningNode(a)];
+ }
+ _forward[j] = false;
+ _source[j] = i;
+ _target[j] = _root;
+ _reverse[j] = k;
+ _forward[k] = true;
+ _source[k] = _root;
+ _target[k] = i;
+ _reverse[k] = j;
+ ++j; ++k;
+ }
+ _first_out[i] = j;
+ _first_out[_res_node_num] = k;
+ for (ArcIt a(_graph); a != INVALID; ++a) {
+ int fi = _arc_idf[a];
+ int bi = _arc_idb[a];
+ _reverse[fi] = bi;
+ _reverse[bi] = fi;
+ }
+
+ // Reset parameters
+ resetParams();
+ return *this;
+ }
+
/// @}
/// \name Query Functions
diff -r a7e93de12cbd -r 75c97c3786d6 lemon/network_simplex.h
--- a/lemon/network_simplex.h Tue Feb 09 23:29:51 2010 +0100
+++ b/lemon/network_simplex.h Wed Feb 10 19:05:20 2010 +0100
@@ -194,6 +194,7 @@
IntArcMap _arc_id;
IntVector _source;
IntVector _target;
+ bool _arc_mixing;
// Node and arc data
ValueVector _lower;
@@ -633,6 +634,7 @@
/// but it is usually slower. Therefore it is disabled by default.
NetworkSimplex(const GR& graph, bool arc_mixing = false) :
_graph(graph), _node_id(graph), _arc_id(graph),
+ _arc_mixing(arc_mixing),
MAX(std::numeric_limits<Value>::max()),
INF(std::numeric_limits<Value>::has_infinity ?
std::numeric_limits<Value>::infinity() : MAX)
@@ -643,58 +645,7 @@
LEMON_ASSERT(std::numeric_limits<Cost>::is_signed,
"The cost type of NetworkSimplex must be signed");
- // Resize vectors
- _node_num = countNodes(_graph);
- _arc_num = countArcs(_graph);
- int all_node_num = _node_num + 1;
- int max_arc_num = _arc_num + 2 * _node_num;
-
- _source.resize(max_arc_num);
- _target.resize(max_arc_num);
-
- _lower.resize(_arc_num);
- _upper.resize(_arc_num);
- _cap.resize(max_arc_num);
- _cost.resize(max_arc_num);
- _supply.resize(all_node_num);
- _flow.resize(max_arc_num);
- _pi.resize(all_node_num);
-
- _parent.resize(all_node_num);
- _pred.resize(all_node_num);
- _forward.resize(all_node_num);
- _thread.resize(all_node_num);
- _rev_thread.resize(all_node_num);
- _succ_num.resize(all_node_num);
- _last_succ.resize(all_node_num);
- _state.resize(max_arc_num);
-
- // Copy the graph
- int i = 0;
- for (NodeIt n(_graph); n != INVALID; ++n, ++i) {
- _node_id[n] = i;
- }
- if (arc_mixing) {
- // Store the arcs in a mixed order
- int k = std::max(int(std::sqrt(double(_arc_num))), 10);
- int i = 0, j = 0;
- for (ArcIt a(_graph); a != INVALID; ++a) {
- _arc_id[a] = i;
- _source[i] = _node_id[_graph.source(a)];
- _target[i] = _node_id[_graph.target(a)];
- if ((i += k) >= _arc_num) i = ++j;
- }
- } else {
- // Store the arcs in the original order
- int i = 0;
- for (ArcIt a(_graph); a != INVALID; ++a, ++i) {
- _arc_id[a] = i;
- _source[i] = _node_id[_graph.source(a)];
- _target[i] = _node_id[_graph.target(a)];
- }
- }
-
- // Reset parameters
+ // Reset data structures
reset();
}
@@ -842,12 +793,12 @@
/// .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.
- /// However, the underlying digraph must not be modified after this
- /// class have been constructed, since it copies and extends the graph.
+ /// This function can be called more than once. All the given parameters
+ /// are kept for the next call, unless \ref resetParams() or \ref reset()
+ /// is used, thus only the modified parameters have to be set again.
+ /// If the underlying digraph was also modified after the construction
+ /// of the class (or the last \ref reset() call), then the \ref reset()
+ /// function must be called.
///
/// \param pivot_rule The pivot rule that will be used during the
/// algorithm. For more information, see \ref PivotRule.
@@ -861,6 +812,7 @@
/// cost and infinite upper bound.
///
/// \see ProblemType, PivotRule
+ /// \see resetParams(), reset()
ProblemType run(PivotRule pivot_rule = BLOCK_SEARCH) {
if (!init()) return INFEASIBLE;
return start(pivot_rule);
@@ -872,11 +824,12 @@
/// before using functions \ref lowerMap(), \ref upperMap(),
/// \ref costMap(), \ref supplyMap(), \ref stSupply(), \ref supplyType().
///
- /// 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.
- /// However, the underlying digraph must not be modified after this
- /// class have been constructed, since it copies and extends the graph.
+ /// It is useful for multiple \ref run() calls. Basically, all the given
+ /// parameters are kept for the next \ref run() call, unless
+ /// \ref resetParams() or \ref reset() is used.
+ /// If the underlying digraph was also modified after the construction
+ /// of the class or the last \ref reset() call, then the \ref reset()
+ /// function must be used, otherwise \ref resetParams() is sufficient.
///
/// For example,
/// \code
@@ -886,20 +839,22 @@
/// ns.lowerMap(lower).upperMap(upper).costMap(cost)
/// .supplyMap(sup).run();
///
- /// // Run again with modified cost map (reset() is not called,
+ /// // Run again with modified cost map (resetParams() 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()
+ /// // Run again from scratch using resetParams()
/// // (the lower bounds will be set to zero on all arcs)
- /// ns.reset();
+ /// ns.resetParams();
/// ns.upperMap(capacity).costMap(cost)
/// .supplyMap(sup).run();
/// \endcode
///
/// \return <tt>(*this)</tt>
- NetworkSimplex& reset() {
+ ///
+ /// \see reset(), run()
+ NetworkSimplex& resetParams() {
for (int i = 0; i != _node_num; ++i) {
_supply[i] = 0;
}
@@ -913,6 +868,83 @@
return *this;
}
+ /// \brief Reset the internal data structures and all the parameters
+ /// that have been given before.
+ ///
+ /// This function resets the internal data structures and all the
+ /// paramaters that have been given before using functions \ref lowerMap(),
+ /// \ref upperMap(), \ref costMap(), \ref supplyMap(), \ref stSupply(),
+ /// \ref supplyType().
+ ///
+ /// It is useful for multiple \ref run() calls. Basically, all the given
+ /// parameters are kept for the next \ref run() call, unless
+ /// \ref resetParams() or \ref reset() is used.
+ /// If the underlying digraph was also modified after the construction
+ /// of the class or the last \ref reset() call, then the \ref reset()
+ /// function must be used, otherwise \ref resetParams() is sufficient.
+ ///
+ /// See \ref resetParams() for examples.
+ ///
+ /// \return <tt>(*this)</tt>
+ ///
+ /// \see resetParams(), run()
+ NetworkSimplex& reset() {
+ // Resize vectors
+ _node_num = countNodes(_graph);
+ _arc_num = countArcs(_graph);
+ int all_node_num = _node_num + 1;
+ int max_arc_num = _arc_num + 2 * _node_num;
+
+ _source.resize(max_arc_num);
+ _target.resize(max_arc_num);
+
+ _lower.resize(_arc_num);
+ _upper.resize(_arc_num);
+ _cap.resize(max_arc_num);
+ _cost.resize(max_arc_num);
+ _supply.resize(all_node_num);
+ _flow.resize(max_arc_num);
+ _pi.resize(all_node_num);
+
+ _parent.resize(all_node_num);
+ _pred.resize(all_node_num);
+ _forward.resize(all_node_num);
+ _thread.resize(all_node_num);
+ _rev_thread.resize(all_node_num);
+ _succ_num.resize(all_node_num);
+ _last_succ.resize(all_node_num);
+ _state.resize(max_arc_num);
+
+ // Copy the graph
+ int i = 0;
+ for (NodeIt n(_graph); n != INVALID; ++n, ++i) {
+ _node_id[n] = i;
+ }
+ if (_arc_mixing) {
+ // Store the arcs in a mixed order
+ int k = std::max(int(std::sqrt(double(_arc_num))), 10);
+ int i = 0, j = 0;
+ for (ArcIt a(_graph); a != INVALID; ++a) {
+ _arc_id[a] = i;
+ _source[i] = _node_id[_graph.source(a)];
+ _target[i] = _node_id[_graph.target(a)];
+ if ((i += k) >= _arc_num) i = ++j;
+ }
+ } else {
+ // Store the arcs in the original order
+ int i = 0;
+ for (ArcIt a(_graph); a != INVALID; ++a, ++i) {
+ _arc_id[a] = i;
+ _source[i] = _node_id[_graph.source(a)];
+ _target[i] = _node_id[_graph.target(a)];
+ }
+ }
+
+ // Reset parameters
+ resetParams();
+ return *this;
+ }
+
/// @}
/// \name Query Functions
diff -r a7e93de12cbd -r 75c97c3786d6 test/min_cost_flow_test.cc
--- a/test/min_cost_flow_test.cc Tue Feb 09 23:29:51 2010 +0100
+++ b/test/min_cost_flow_test.cc Wed Feb 10 19:05:20 2010 +0100
@@ -157,7 +157,7 @@
MCF mcf(me.g);
const MCF& const_mcf = mcf;
- b = mcf.reset()
+ b = mcf.reset().resetParams()
.lowerMap(me.lower)
.upperMap(me.upper)
.costMap(me.cost)
@@ -346,7 +346,7 @@
mcf1.stSupply(v, w, 27);
checkMcf(mcf1, mcf1.run(param), gr, l2, u, c, s2,
mcf1.OPTIMAL, true, 8010, test_str + "-4");
- mcf1.reset().supplyMap(s1);
+ mcf1.resetParams().supplyMap(s1);
checkMcf(mcf1, mcf1.run(param), gr, l1, cu, cc, s1,
mcf1.OPTIMAL, true, 74, test_str + "-5");
mcf1.lowerMap(l2).stSupply(v, w, 27);
@@ -363,7 +363,7 @@
mcf1.OPTIMAL, true, 6360, test_str + "-9");
// Tests for the GEQ form
- mcf1.reset().upperMap(u).costMap(c).supplyMap(s5);
+ mcf1.resetParams().upperMap(u).costMap(c).supplyMap(s5);
checkMcf(mcf1, mcf1.run(param), gr, l1, u, c, s5,
mcf1.OPTIMAL, true, 3530, test_str + "-10", GEQ);
mcf1.lowerMap(l2);
@@ -380,7 +380,7 @@
mcf2.upperMap(neg1_u2);
checkMcf(mcf2, mcf2.run(param), neg1_gr, neg1_l1, neg1_u2, neg1_c, neg1_s,
mcf2.OPTIMAL, true, -40000, test_str + "-14");
- mcf2.reset().lowerMap(neg1_l2).costMap(neg1_c).supplyMap(neg1_s);
+ mcf2.resetParams().lowerMap(neg1_l2).costMap(neg1_c).supplyMap(neg1_s);
checkMcf(mcf2, mcf2.run(param), neg1_gr, neg1_l2, neg1_u1, neg1_c, neg1_s,
mcf2.UNBOUNDED, false, 0, test_str + "-15");