RhodeCode

    CostVector _pi;

    ValueVector _excess;

    IntVector _excess_nodes;

    IntVector _deficit_nodes;

    Value _delta;

    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

    ///

    ///

    /// \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

      if (pt != OPTIMAL) return pt;

      return start();

    }

    /// \brief Reset all the parameters that have been given before.

    ///

    /// 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.

    /// class have been constructed, since it copies and extends the graph.

    ///

    /// For example,

    /// \code

    ///   CapacityScaling<ListDigraph> cs(graph);

    ///

    /// @}

  private:

    // Initialize the algorithm

      if (_node_num == 0) return INFEASIBLE;

      // Check the sum of supply values

      _sum_supply = 0;

      for (int i = 0; i != _root; ++i) {

        _sum_supply += _supply[i];

          _cost[a] = 0;

          _cost[_reverse[a]] = 0;

        }

      }

      // Initialize delta value

        // 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);

      } else {

        // Without scaling

        _delta = 1;

      }

      return OPTIMAL;

    }

    // Execute the capacity scaling algorithm

    ProblemType startWithScaling() {

      // Perform capacity scaling phases

      int s, t;

      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) {

            int v = _target[a];

          _excess[t] += d;

          if (_excess[s] < _delta) ++next_node;

        }

        if (_delta == 1) break;

      }

      return OPTIMAL;

    }

    // Execute the successive shortest path algorithm

  /// algorithm. By default it is the same as \c V.

  ///

  /// \warning Both value 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.

#ifdef DOXYGEN

  template <typename GR, typename V, typename C, typename TR>

#else

  template < typename GR, typename V = int, typename C = V,

             typename TR = CostScalingDefaultTraits<GR, V, C> >

#endif

      /// on that arc, however note that it could actually be bounded

      /// over the feasible flows, but this algroithm cannot handle

      /// these cases.

      UNBOUNDED

    };

  private:

    TEMPLATE_DIGRAPH_TYPEDEFS(GR);

    typedef std::vector<int> IntVector;

    typedef std::vector<char> BoolVector;

    /// \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.

    ///

    ///

    /// \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.

    ///

      ProblemType pt = init();

      if (pt != OPTIMAL) return pt;

      return OPTIMAL;

    }

    /// \brief Reset all the parameters that have been given before.

    ///

    /// This function resets all the paramaters that have been given

  private:

    // Initialize the algorithm

    ProblemType init() {

      if (_res_node_num == 0) return INFEASIBLE;

      // Check the sum of supply values

      _sum_supply = 0;

      for (int i = 0; i != _root; ++i) {

        _sum_supply += _supply[i];

      }

      if (_sum_supply > 0) return INFEASIBLE;

      }

      return OPTIMAL;

    }

    // Execute the algorithm and transform the results

      // Execute the algorithm

      }

      // Compute node potentials for the original costs

      _arc_vec.clear();

      _cost_vec.clear();

      for (int j = 0; j != _res_arc_num; ++j) {

        for (int j = 0; j != limit; ++j) {

          if (!_forward[j]) _res_cap[j] += _lower[j];

        }

      }

    }

      // Paramters for heuristics

      const int BF_HEURISTIC_EPSILON_BOUND = 1000;

      const int BF_HEURISTIC_BOUND_FACTOR  = 3;

      // Perform cost scaling phases

      IntVector pred_arc(_res_node_num);

      std::vector<int> path_nodes;

      for ( ; _epsilon >= 1; _epsilon = _epsilon < _alpha && _epsilon > 1 ?

                                        1 : _epsilon / _alpha )

          path_nodes.clear();

          path_nodes.push_back(start);

          // Find an augmenting path from the start node

          int tip = start;

          while (_excess[tip] >= 0 &&

            int u;

            LargeCost min_red_cost, rc;

            int last_out = _sum_supply < 0 ?

              _first_out[tip+1] : _first_out[tip+1] - 1;

            for (int a = _next_out[tip]; a != last_out; ++a) {

              if (_res_cap[a] > 0 &&

          }

        }

      }

    }

    /// Execute the algorithm performing push and relabel operations

      // Paramters for heuristics

      const int BF_HEURISTIC_EPSILON_BOUND = 1000;

      const int BF_HEURISTIC_BOUND_FACTOR  = 3;

      // Perform cost scaling phases

      BoolVector hyper(_res_node_num, false);