# Changeset 899:cc9e0c15d747 in lemon

Ignore:
Timestamp:
02/12/10 22:24:26 (8 years ago)
Branch:
default
Children:
902:d2bc45e8f6f2, 915:c2ff0a365245
Parents:
898:75c97c3786d6 (diff), 897:7762cab7f372 (diff)
Note: this is a merge changeset, the changes displayed below correspond to the merge itself.
Use the (diff) links above to see all the changes relative to each parent.
Message:

Merge

Location:
lemon
Files:
4 edited

Unmodified
Removed
• ## lemon/capacity_scaling.h

 r891 "The cost type of CapacityScaling must be signed"); // Reset data structures reset(); } /// \name Parameters /// The parameters of the algorithm can be specified using these /// functions. /// @{ /// \brief Set the lower bounds on the arcs. /// /// This function sets the lower bounds on the arcs. /// If it is not used before calling \ref run(), the lower bounds /// will be set to zero on all arcs. /// /// \param map An arc map storing the lower bounds. /// Its \c Value type must be convertible to the \c Value type /// of the algorithm. /// /// \return (*this) template CapacityScaling& lowerMap(const LowerMap& map) { _have_lower = true; for (ArcIt a(_graph); a != INVALID; ++a) { _lower[_arc_idf[a]] = map[a]; _lower[_arc_idb[a]] = map[a]; } return *this; } /// \brief Set the upper bounds (capacities) on the arcs. /// /// This function sets the upper bounds (capacities) on the arcs. /// If it is not used before calling \ref run(), the upper bounds /// will be set to \ref INF on all arcs (i.e. the flow value will be /// unbounded from above). /// /// \param map An arc map storing the upper bounds. /// Its \c Value type must be convertible to the \c Value type /// of the algorithm. /// /// \return (*this) template CapacityScaling& upperMap(const UpperMap& map) { for (ArcIt a(_graph); a != INVALID; ++a) { _upper[_arc_idf[a]] = map[a]; } return *this; } /// \brief Set the costs of the arcs. /// /// This function sets the costs of the arcs. /// If it is not used before calling \ref run(), the costs /// will be set to \c 1 on all arcs. /// /// \param map An arc map storing the costs. /// Its \c Value type must be convertible to the \c Cost type /// of the algorithm. /// /// \return (*this) template CapacityScaling& costMap(const CostMap& map) { for (ArcIt a(_graph); a != INVALID; ++a) { _cost[_arc_idf[a]] =  map[a]; _cost[_arc_idb[a]] = -map[a]; } return *this; } /// \brief Set the supply values of the nodes. /// /// This function sets the supply values of the nodes. /// If neither this function nor \ref stSupply() is used before /// calling \ref run(), the supply of each node will be set to zero. /// /// \param map A node map storing the supply values. /// Its \c Value type must be convertible to the \c Value type /// of the algorithm. /// /// \return (*this) template CapacityScaling& supplyMap(const SupplyMap& map) { for (NodeIt n(_graph); n != INVALID; ++n) { _supply[_node_id[n]] = map[n]; } return *this; } /// \brief Set single source and target nodes and a supply value. /// /// This function sets a single source node and a single target node /// and the required flow value. /// If neither this function nor \ref supplyMap() is used before /// calling \ref run(), the supply of each node will be set to zero. /// /// Using this function has the same effect as using \ref supplyMap() /// with such a map in which \c k is assigned to \c s, \c -k is /// assigned to \c t and all other nodes have zero supply value. /// /// \param s The source node. /// \param t The target node. /// \param k The required amount of flow from node \c s to node \c t /// (i.e. the supply of \c s and the demand of \c t). /// /// \return (*this) CapacityScaling& stSupply(const Node& s, const Node& t, Value k) { for (int i = 0; i != _node_num; ++i) { _supply[i] = 0; } _supply[_node_id[s]] =  k; _supply[_node_id[t]] = -k; return *this; } /// @} /// \name Execution control /// The algorithm can be executed using \ref run(). /// @{ /// \brief Run the algorithm. /// /// This function runs the algorithm. /// The paramters can be specified using functions \ref lowerMap(), /// \ref upperMap(), \ref costMap(), \ref supplyMap(), \ref stSupply(). /// For example, /// \code ///   CapacityScaling cs(graph); ///   cs.lowerMap(lower).upperMap(upper).costMap(cost) ///     .supplyMap(sup).run(); /// \endcode /// /// 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 /// will be disabled. /// /// \return \c INFEASIBLE if no feasible flow exists, /// \n \c OPTIMAL if the problem has optimal solution /// (i.e. it is feasible and bounded), and the algorithm has found /// optimal flow and node potentials (primal and dual solutions), /// \n \c UNBOUNDED if the digraph contains an arc of negative cost /// and infinite upper bound. It means that the objective function /// is unbounded on that arc, however, note that it could actually be /// bounded over the feasible flows, but this algroithm cannot handle /// these cases. /// /// \see ProblemType /// \see resetParams(), reset() ProblemType run(int factor = 4) { _factor = factor; ProblemType pt = init(); if (pt != OPTIMAL) return pt; return start(); } /// \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 \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 ///   CapacityScaling cs(graph); /// ///   // First run ///   cs.lowerMap(lower).upperMap(upper).costMap(cost) ///     .supplyMap(sup).run(); /// ///   // 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 resetParams() ///   // (the lower bounds will be set to zero on all arcs) ///   cs.resetParams(); ///   cs.upperMap(capacity).costMap(cost) ///     .supplyMap(sup).run(); /// \endcode /// /// \return (*this) /// /// \see reset(), run() CapacityScaling& resetParams() { for (int i = 0; i != _node_num; ++i) { _supply[i] = 0; } for (int j = 0; j != _res_arc_num; ++j) { _lower[j] = 0; _upper[j] = INF; _cost[j] = _forward[j] ? 1 : -1; } _have_lower = false; 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); // Reset parameters reset(); } /// \name Parameters /// The parameters of the algorithm can be specified using these /// functions. /// @{ /// \brief Set the lower bounds on the arcs. /// /// This function sets the lower bounds on the arcs. /// If it is not used before calling \ref run(), the lower bounds /// will be set to zero on all arcs. /// /// \param map An arc map storing the lower bounds. /// Its \c Value type must be convertible to the \c Value type /// of the algorithm. /// /// \return (*this) template CapacityScaling& lowerMap(const LowerMap& map) { _have_lower = true; for (ArcIt a(_graph); a != INVALID; ++a) { _lower[_arc_idf[a]] = map[a]; _lower[_arc_idb[a]] = map[a]; } return *this; } /// \brief Set the upper bounds (capacities) on the arcs. /// /// This function sets the upper bounds (capacities) on the arcs. /// If it is not used before calling \ref run(), the upper bounds /// will be set to \ref INF on all arcs (i.e. the flow value will be /// unbounded from above). /// /// \param map An arc map storing the upper bounds. /// Its \c Value type must be convertible to the \c Value type /// of the algorithm. /// /// \return (*this) template CapacityScaling& upperMap(const UpperMap& map) { for (ArcIt a(_graph); a != INVALID; ++a) { _upper[_arc_idf[a]] = map[a]; } return *this; } /// \brief Set the costs of the arcs. /// /// This function sets the costs of the arcs. /// If it is not used before calling \ref run(), the costs /// will be set to \c 1 on all arcs. /// /// \param map An arc map storing the costs. /// Its \c Value type must be convertible to the \c Cost type /// of the algorithm. /// /// \return (*this) template CapacityScaling& costMap(const CostMap& map) { for (ArcIt a(_graph); a != INVALID; ++a) { _cost[_arc_idf[a]] =  map[a]; _cost[_arc_idb[a]] = -map[a]; } return *this; } /// \brief Set the supply values of the nodes. /// /// This function sets the supply values of the nodes. /// If neither this function nor \ref stSupply() is used before /// calling \ref run(), the supply of each node will be set to zero. /// /// \param map A node map storing the supply values. /// Its \c Value type must be convertible to the \c Value type /// of the algorithm. /// /// \return (*this) template CapacityScaling& supplyMap(const SupplyMap& map) { for (NodeIt n(_graph); n != INVALID; ++n) { _supply[_node_id[n]] = map[n]; } return *this; } /// \brief Set single source and target nodes and a supply value. /// /// This function sets a single source node and a single target node /// and the required flow value. /// If neither this function nor \ref supplyMap() is used before /// calling \ref run(), the supply of each node will be set to zero. /// /// Using this function has the same effect as using \ref supplyMap() /// with such a map in which \c k is assigned to \c s, \c -k is /// assigned to \c t and all other nodes have zero supply value. /// /// \param s The source node. /// \param t The target node. /// \param k The required amount of flow from node \c s to node \c t /// (i.e. the supply of \c s and the demand of \c t). /// /// \return (*this) CapacityScaling& stSupply(const Node& s, const Node& t, Value k) { for (int i = 0; i != _node_num; ++i) { _supply[i] = 0; } _supply[_node_id[s]] =  k; _supply[_node_id[t]] = -k; return *this; } /// @} /// \name Execution control /// The algorithm can be executed using \ref run(). /// @{ /// \brief Run the algorithm. /// /// This function runs the algorithm. /// The paramters can be specified using functions \ref lowerMap(), /// \ref upperMap(), \ref costMap(), \ref supplyMap(), \ref stSupply(). /// For example, /// \code ///   CapacityScaling cs(graph); ///   cs.lowerMap(lower).upperMap(upper).costMap(cost) ///     .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. /// /// \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 /// will be disabled. /// /// \return \c INFEASIBLE if no feasible flow exists, /// \n \c OPTIMAL if the problem has optimal solution /// (i.e. it is feasible and bounded), and the algorithm has found /// optimal flow and node potentials (primal and dual solutions), /// \n \c UNBOUNDED if the digraph contains an arc of negative cost /// and infinite upper bound. It means that the objective function /// is unbounded on that arc, however, note that it could actually be /// bounded over the feasible flows, but this algroithm cannot handle /// these cases. /// /// \see ProblemType ProblemType run(int factor = 4) { _factor = factor; ProblemType pt = init(); if (pt != OPTIMAL) return pt; return start(); } /// \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. /// /// For example, /// \code ///   CapacityScaling cs(graph); /// ///   // First run ///   cs.lowerMap(lower).upperMap(upper).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; ///   cs.costMap(cost).run(); /// ///   // Run again from scratch using reset() ///   // (the lower bounds will be set to zero on all arcs) ///   cs.reset(); ///   cs.upperMap(capacity).costMap(cost) ///     .supplyMap(sup).run(); /// \endcode /// /// \return (*this) CapacityScaling& reset() { for (int i = 0; i != _node_num; ++i) { _supply[i] = 0; } for (int j = 0; j != _res_arc_num; ++j) { _lower[j] = 0; _upper[j] = INF; _cost[j] = _forward[j] ? 1 : -1; } _have_lower = false; resetParams(); return *this; }
• ## lemon/capacity_scaling.h

 r898 /// \tparam GR The digraph type the algorithm runs on. /// \tparam V The number type used for flow amounts, capacity bounds /// and supply values in the algorithm. By default it is \c int. /// and supply values in the algorithm. By default, it is \c int. /// \tparam C The number type used for costs and potentials in the /// algorithm. By default it is the same as \c V. /// algorithm. By default, it is the same as \c V. /// \tparam TR The traits class that defines various types used by the /// algorithm. By default, it is \ref CapacityScalingDefaultTraits /// "CapacityScalingDefaultTraits". /// In most cases, this parameter should not be set directly, /// consider to use the named template parameters instead. /// /// \warning Both number types must be signed and all input data must
• ## lemon/cost_scaling.h

 r891 LEMON_ASSERT(std::numeric_limits::is_signed, "The cost type of CostScaling must be signed"); // Reset data structures reset(); } /// \name Parameters /// The parameters of the algorithm can be specified using these /// functions. /// @{ /// \brief Set the lower bounds on the arcs. /// /// This function sets the lower bounds on the arcs. /// If it is not used before calling \ref run(), the lower bounds /// will be set to zero on all arcs. /// /// \param map An arc map storing the lower bounds. /// Its \c Value type must be convertible to the \c Value type /// of the algorithm. /// /// \return (*this) template CostScaling& lowerMap(const LowerMap& map) { _have_lower = true; for (ArcIt a(_graph); a != INVALID; ++a) { _lower[_arc_idf[a]] = map[a]; _lower[_arc_idb[a]] = map[a]; } return *this; } /// \brief Set the upper bounds (capacities) on the arcs. /// /// This function sets the upper bounds (capacities) on the arcs. /// If it is not used before calling \ref run(), the upper bounds /// will be set to \ref INF on all arcs (i.e. the flow value will be /// unbounded from above). /// /// \param map An arc map storing the upper bounds. /// Its \c Value type must be convertible to the \c Value type /// of the algorithm. /// /// \return (*this) template CostScaling& upperMap(const UpperMap& map) { for (ArcIt a(_graph); a != INVALID; ++a) { _upper[_arc_idf[a]] = map[a]; } return *this; } /// \brief Set the costs of the arcs. /// /// This function sets the costs of the arcs. /// If it is not used before calling \ref run(), the costs /// will be set to \c 1 on all arcs. /// /// \param map An arc map storing the costs. /// Its \c Value type must be convertible to the \c Cost type /// of the algorithm. /// /// \return (*this) template CostScaling& costMap(const CostMap& map) { for (ArcIt a(_graph); a != INVALID; ++a) { _scost[_arc_idf[a]] =  map[a]; _scost[_arc_idb[a]] = -map[a]; } return *this; } /// \brief Set the supply values of the nodes. /// /// This function sets the supply values of the nodes. /// If neither this function nor \ref stSupply() is used before /// calling \ref run(), the supply of each node will be set to zero. /// /// \param map A node map storing the supply values. /// Its \c Value type must be convertible to the \c Value type /// of the algorithm. /// /// \return (*this) template CostScaling& supplyMap(const SupplyMap& map) { for (NodeIt n(_graph); n != INVALID; ++n) { _supply[_node_id[n]] = map[n]; } return *this; } /// \brief Set single source and target nodes and a supply value. /// /// This function sets a single source node and a single target node /// and the required flow value. /// If neither this function nor \ref supplyMap() is used before /// calling \ref run(), the supply of each node will be set to zero. /// /// Using this function has the same effect as using \ref supplyMap() /// with such a map in which \c k is assigned to \c s, \c -k is /// assigned to \c t and all other nodes have zero supply value. /// /// \param s The source node. /// \param t The target node. /// \param k The required amount of flow from node \c s to node \c t /// (i.e. the supply of \c s and the demand of \c t). /// /// \return (*this) CostScaling& stSupply(const Node& s, const Node& t, Value k) { for (int i = 0; i != _res_node_num; ++i) { _supply[i] = 0; } _supply[_node_id[s]] =  k; _supply[_node_id[t]] = -k; return *this; } /// @} /// \name Execution control /// The algorithm can be executed using \ref run(). /// @{ /// \brief Run the algorithm. /// /// This function runs the algorithm. /// The paramters can be specified using functions \ref lowerMap(), /// \ref upperMap(), \ref costMap(), \ref supplyMap(), \ref stSupply(). /// For example, /// \code ///   CostScaling cs(graph); ///   cs.lowerMap(lower).upperMap(upper).costMap(cost) ///     .supplyMap(sup).run(); /// \endcode /// /// 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. /// \param factor The cost scaling factor. It must be larger than one. /// /// \return \c INFEASIBLE if no feasible flow exists, /// \n \c OPTIMAL if the problem has optimal solution /// (i.e. it is feasible and bounded), and the algorithm has found /// optimal flow and node potentials (primal and dual solutions), /// \n \c UNBOUNDED if the digraph contains an arc of negative cost /// and infinite upper bound. It means that the objective function /// is unbounded on that arc, however, note that it could actually be /// bounded over the feasible flows, but this algroithm cannot handle /// these cases. /// /// \see ProblemType, Method /// \see resetParams(), reset() ProblemType run(Method method = PARTIAL_AUGMENT, int factor = 8) { _alpha = factor; ProblemType pt = init(); if (pt != OPTIMAL) return pt; start(method); return OPTIMAL; } /// \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 \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 ///   CostScaling cs(graph); /// ///   // First run ///   cs.lowerMap(lower).upperMap(upper).costMap(cost) ///     .supplyMap(sup).run(); /// ///   // 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 resetParams() ///   // (the lower bounds will be set to zero on all arcs) ///   cs.resetParams(); ///   cs.upperMap(capacity).costMap(cost) ///     .supplyMap(sup).run(); /// \endcode /// /// \return (*this) /// /// \see reset(), run() CostScaling& resetParams() { for (int i = 0; i != _res_node_num; ++i) { _supply[i] = 0; } int limit = _first_out[_root]; for (int j = 0; j != limit; ++j) { _lower[j] = 0; _upper[j] = INF; _scost[j] = _forward[j] ? 1 : -1; } for (int j = limit; j != _res_arc_num; ++j) { _lower[j] = 0; _upper[j] = INF; _scost[j] = 0; _scost[_reverse[j]] = 0; } _have_lower = false; 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); // Reset parameters reset(); } /// \name Parameters /// The parameters of the algorithm can be specified using these /// functions. /// @{ /// \brief Set the lower bounds on the arcs. /// /// This function sets the lower bounds on the arcs. /// If it is not used before calling \ref run(), the lower bounds /// will be set to zero on all arcs. /// /// \param map An arc map storing the lower bounds. /// Its \c Value type must be convertible to the \c Value type /// of the algorithm. /// /// \return (*this) template CostScaling& lowerMap(const LowerMap& map) { _have_lower = true; for (ArcIt a(_graph); a != INVALID; ++a) { _lower[_arc_idf[a]] = map[a]; _lower[_arc_idb[a]] = map[a]; } return *this; } /// \brief Set the upper bounds (capacities) on the arcs. /// /// This function sets the upper bounds (capacities) on the arcs. /// If it is not used before calling \ref run(), the upper bounds /// will be set to \ref INF on all arcs (i.e. the flow value will be /// unbounded from above). /// /// \param map An arc map storing the upper bounds. /// Its \c Value type must be convertible to the \c Value type /// of the algorithm. /// /// \return (*this) template CostScaling& upperMap(const UpperMap& map) { for (ArcIt a(_graph); a != INVALID; ++a) { _upper[_arc_idf[a]] = map[a]; } return *this; } /// \brief Set the costs of the arcs. /// /// This function sets the costs of the arcs. /// If it is not used before calling \ref run(), the costs /// will be set to \c 1 on all arcs. /// /// \param map An arc map storing the costs. /// Its \c Value type must be convertible to the \c Cost type /// of the algorithm. /// /// \return (*this) template CostScaling& costMap(const CostMap& map) { for (ArcIt a(_graph); a != INVALID; ++a) { _scost[_arc_idf[a]] =  map[a]; _scost[_arc_idb[a]] = -map[a]; } return *this; } /// \brief Set the supply values of the nodes. /// /// This function sets the supply values of the nodes. /// If neither this function nor \ref stSupply() is used before /// calling \ref run(), the supply of each node will be set to zero. /// /// \param map A node map storing the supply values. /// Its \c Value type must be convertible to the \c Value type /// of the algorithm. /// /// \return (*this) template CostScaling& supplyMap(const SupplyMap& map) { for (NodeIt n(_graph); n != INVALID; ++n) { _supply[_node_id[n]] = map[n]; } return *this; } /// \brief Set single source and target nodes and a supply value. /// /// This function sets a single source node and a single target node /// and the required flow value. /// If neither this function nor \ref supplyMap() is used before /// calling \ref run(), the supply of each node will be set to zero. /// /// Using this function has the same effect as using \ref supplyMap() /// with such a map in which \c k is assigned to \c s, \c -k is /// assigned to \c t and all other nodes have zero supply value. /// /// \param s The source node. /// \param t The target node. /// \param k The required amount of flow from node \c s to node \c t /// (i.e. the supply of \c s and the demand of \c t). /// /// \return (*this) CostScaling& stSupply(const Node& s, const Node& t, Value k) { for (int i = 0; i != _res_node_num; ++i) { _supply[i] = 0; } _supply[_node_id[s]] =  k; _supply[_node_id[t]] = -k; return *this; } /// @} /// \name Execution control /// The algorithm can be executed using \ref run(). /// @{ /// \brief Run the algorithm. /// /// This function runs the algorithm. /// The paramters can be specified using functions \ref lowerMap(), /// \ref upperMap(), \ref costMap(), \ref supplyMap(), \ref stSupply(). /// For example, /// \code ///   CostScaling cs(graph); ///   cs.lowerMap(lower).upperMap(upper).costMap(cost) ///     .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. /// /// \param method The internal method that will be used in the /// algorithm. For more information, see \ref Method. /// \param factor The cost scaling factor. It must be larger than one. /// /// \return \c INFEASIBLE if no feasible flow exists, /// \n \c OPTIMAL if the problem has optimal solution /// (i.e. it is feasible and bounded), and the algorithm has found /// optimal flow and node potentials (primal and dual solutions), /// \n \c UNBOUNDED if the digraph contains an arc of negative cost /// and infinite upper bound. It means that the objective function /// is unbounded on that arc, however, note that it could actually be /// bounded over the feasible flows, but this algroithm cannot handle /// these cases. /// /// \see ProblemType, Method ProblemType run(Method method = PARTIAL_AUGMENT, int factor = 8) { _alpha = factor; ProblemType pt = init(); if (pt != OPTIMAL) return pt; start(method); return OPTIMAL; } /// \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. /// /// For example, /// \code ///   CostScaling cs(graph); /// ///   // First run ///   cs.lowerMap(lower).upperMap(upper).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; ///   cs.costMap(cost).run(); /// ///   // Run again from scratch using reset() ///   // (the lower bounds will be set to zero on all arcs) ///   cs.reset(); ///   cs.upperMap(capacity).costMap(cost) ///     .supplyMap(sup).run(); /// \endcode /// /// \return (*this) CostScaling& reset() { for (int i = 0; i != _res_node_num; ++i) { _supply[i] = 0; } int limit = _first_out[_root]; for (int j = 0; j != limit; ++j) { _lower[j] = 0; _upper[j] = INF; _scost[j] = _forward[j] ? 1 : -1; } for (int j = limit; j != _res_arc_num; ++j) { _lower[j] = 0; _upper[j] = INF; _scost[j] = 0; _scost[_reverse[j]] = 0; } _have_lower = false; resetParams(); return *this; }
• ## lemon/cost_scaling.h

 r898 /// \tparam GR The digraph type the algorithm runs on. /// \tparam V The number type used for flow amounts, capacity bounds /// and supply values in the algorithm. By default it is \c int. /// and supply values in the algorithm. By default, it is \c int. /// \tparam C The number type used for costs and potentials in the /// algorithm. By default it is the same as \c V. /// algorithm. By default, it is the same as \c V. /// \tparam TR The traits class that defines various types used by the /// algorithm. By default, it is \ref CostScalingDefaultTraits /// "CostScalingDefaultTraits". /// In most cases, this parameter should not be set directly, /// consider to use the named template parameters instead. /// /// \warning Both number types must be signed and all input data must /// /// The large cost type used for internal computations. /// Using the \ref CostScalingDefaultTraits "default traits class", /// it is \c long \c long if the \c Cost type is integer, /// By default, it is \c long \c long if the \c Cost type is integer, /// otherwise it is \c double. typedef typename TR::LargeCost LargeCost;
Note: See TracChangeset for help on using the changeset viewer.