// 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 <tt>(*this)</tt>

     template <typename LowerMap>

     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 <tt>(*this)</tt>

     template<typename UpperMap>

     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 <tt>(*this)</tt>

     template<typename CostMap>

     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 <tt>(*this)</tt>

     template<typename SupplyMap>

     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 <tt>(*this)</tt>

     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<ListDigraph> 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<ListDigraph> 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 <tt>(*this)</tt>

     ///

     /// \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 <tt>(*this)</tt>

     CostScaling& reset() {

       reset();

       resetParams();

     }

     /// \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 <tt>(*this)</tt>

     template <typename LowerMap>

     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 <tt>(*this)</tt>

     template<typename UpperMap>

     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 <tt>(*this)</tt>

     template<typename CostMap>

     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 <tt>(*this)</tt>

     template<typename SupplyMap>

     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 <tt>(*this)</tt>

     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<ListDigraph> 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<ListDigraph> 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 <tt>(*this)</tt>

     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;