lemon-1.2: comparison lemon/capacity

equal deleted inserted replaced

-:5979e08ce50b
+:598654f6b73b
 ValueVector _excess;
 IntVector _excess_nodes;
 IntVector _deficit_nodes;
 Value _delta;
-int _phase_num;
+int _factor;
 IntVector _pred;
 public:
 /// \brief Constant for infinite upper bounds (capacities).
 /// 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 the digraph.
+/// class have been constructed, since it copies and extends the graph.
 ///
-/// \param scaling Enable or disable capacity scaling.
+/// \param factor The capacity scaling factor. It must be larger than
-/// If the maximum upper bound and/or the amount of total supply
+/// one to use scaling. If it is less or equal to one, then scaling
-/// is rather small, the algorithm could be slightly faster without
+/// will be disabled.
-/// scaling.
 ///
 /// \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),
 /// 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(bool scaling = true) {
+ProblemType run(int factor = 4) {
-ProblemType pt = init(scaling);
+_factor = factor;
+ProblemType pt = init();
 if (pt != OPTIMAL) return pt;
 return start();
 }
 /// \brief Reset all the parameters that have been given before.
 /// \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
+/// 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<ListDigraph> cs(graph);
 /// @}
 private:
 // Initialize the algorithm
-ProblemType init(bool scaling) {
+ProblemType init() {
 if (_node_num == 0) return INFEASIBLE;
 // Check the sum of supply values
 _sum_supply = 0;
 for (int i = 0; i != _root; ++i) {
 _cost[_reverse[a]] = 0;
 }
 }
 // Initialize delta value
-if (scaling) {
+if (_factor > 1) {
 // With scaling
 Value max_sup = 0, max_dem = 0;
 for (int i = 0; i != _node_num; ++i) {
 if ( _excess[i] > max_sup) max_sup =  _excess[i];
 if (-_excess[i] > max_dem) max_dem = -_excess[i];
 Value max_cap = 0;
 for (int j = 0; j != _res_arc_num; ++j) {
 if (_res_cap[j] > max_cap) max_cap = _res_cap[j];
 }
 max_sup = std::min(std::min(max_sup, max_dem), max_cap);
-_phase_num = 0;
+for (_delta = 1; 2 * _delta <= max_sup; _delta *= 2) ;
-for (_delta = 1; 2 * _delta <= max_sup; _delta *= 2)
-++_phase_num;
 } else {
 // Without scaling
 _delta = 1;
 }
 // Execute the capacity scaling algorithm
 ProblemType startWithScaling() {
 // Perform capacity scaling phases
 int s, t;
-int phase_cnt = 0;
-int factor = 4;
 ResidualDijkstra _dijkstra(*this);
 while (true) {
 // Saturate all arcs not satisfying the optimality condition
 for (int u = 0; u != _node_num; ++u) {
 for (int a = _first_out[u]; a != _first_out[u+1]; ++a) {
 if (_excess[s] < _delta) ++next_node;
 }
 if (_delta == 1) break;
-if (++phase_cnt == _phase_num / 4) factor = 2;
+_delta = _delta <= _factor ? 1 : _delta / _factor;
-_delta = _delta <= factor ? 1 : _delta / factor;
 }
 return OPTIMAL;
 }

changeset 810	3b53491bf643
parent 807	78071e00de00
child 811	fe80a8145653