# HG changeset patch # User Peter Kovacs # 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::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 (*this) - 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 (*this) + /// + /// \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::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 (*this) - 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 (*this) + 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::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 (*this) - 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 (*this) + /// + /// \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::max()), INF(std::numeric_limits::has_infinity ? std::numeric_limits::infinity() : MAX) @@ -643,58 +645,7 @@ LEMON_ASSERT(std::numeric_limits::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 (*this) - 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 (*this) + /// + /// \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");