# Changes in lemon/capacity_scaling.h[956:141f9c0db4a3:1270:dceba191c00d] in lemon

Ignore:
File:
1 edited

### Legend:

Unmodified
 r956 * This file is a part of LEMON, a generic C++ optimization library. * * Copyright (C) 2003-2010 * Copyright (C) 2003-2013 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport * (Egervary Research Group on Combinatorial Optimization, EGRES). /// \ref CapacityScaling implements the capacity scaling version /// of the successive shortest path algorithm for finding a /// \ref min_cost_flow "minimum cost flow" \ref amo93networkflows, /// \ref edmondskarp72theoretical. It is an efficient dual /// solution method. /// \ref min_cost_flow "minimum cost flow" \cite amo93networkflows, /// \cite edmondskarp72theoretical. It is an efficient dual /// solution method, which runs in polynomial time /// \f$O(m\log U (n+m)\log n)\f$, where U denotes the maximum /// of node supply and arc capacity values. /// /// This algorithm is typically slower than \ref CostScaling and /// \ref NetworkSimplex, but in special cases, it can be more /// efficient than them. /// (For more information, see \ref min_cost_flow_algs "the module page".) /// /// Most of the parameters of the problem (except for the digraph) /// consider to use the named template parameters instead. /// /// \warning Both number types must be signed and all input data must /// be integer. /// \warning This algorithm does not support negative costs for such /// arcs that have infinite upper bound. /// \warning Both \c V and \c C must be signed number types. /// \warning Capacity bounds and supply values must be integer, but /// arc costs can be arbitrary real numbers. /// \warning This algorithm does not support negative costs for /// arcs having infinite upper bound. #ifdef DOXYGEN template typedef typename TR::Heap Heap; /// The \ref CapacityScalingDefaultTraits "traits class" of the algorithm /// \brief The \ref lemon::CapacityScalingDefaultTraits "traits class" /// of the algorithm typedef TR Traits; /// /// 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 /// with 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. /// /// /// This function returns the total cost of the found flow. /// Its complexity is O(e). /// Its complexity is O(m). /// /// \note The return type of the function can be specified as a } /// \brief Return the flow map (the primal solution). /// \brief Copy the flow values (the primal solution) into the /// given map. /// /// This function copies the flow value on each arc into the given } /// \brief Return the potential map (the dual solution). /// \brief Copy the potential values (the dual solution) into the /// given map. /// /// This function copies the potential (dual value) of each node } if (_sum_supply > 0) return INFEASIBLE; // Check lower and upper bounds LEMON_DEBUG(checkBoundMaps(), "Upper bounds must be greater or equal to the lower bounds"); // Initialize vectors return OPTIMAL; } // Check if the upper bound is greater or equal to the lower bound // on each arc. bool checkBoundMaps() { for (int j = 0; j != _res_arc_num; ++j) { if (_upper[j] < _lower[j]) return false; } return true; }