diff --git a/lemon/cost_scaling.h b/lemon/cost_scaling.h --- a/lemon/cost_scaling.h +++ b/lemon/cost_scaling.h @@ -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