RhodeCode

  ///

  /// \tparam GR The digraph type the algorithm runs on.

  ///

  ///

  /// \note %NetworkSimplex provides five different pivot rule

  /// implementations. For more information see \ref PivotRule.

  class NetworkSimplex

  {

  public:

    /// The type of the flow map

    /// The type of the potential map

  public:

    TEMPLATE_DIGRAPH_TYPEDEFS(GR);

    typedef std::vector<Arc> ArcVector;

    typedef std::vector<int> IntVector;

    typedef std::vector<bool> BoolVector;

    // State constants for arcs

    // Parameters of the problem

    bool _pstsup;

    Node _psource, _ptarget;

    // Result maps

    // Node and arc data

    // Data for storing the spanning tree structure

    int first, second, right, last;

    int stem, par_stem, new_stem;

  private:

      const IntVector  &_source;

      const IntVector  &_target;

      const IntVector  &_state;

      int &_in_arc;

      int _arc_num;

      // Find next entering arc

      bool findEnteringArc() {

        for (int e = _next_arc; e < _arc_num; ++e) {

          c = _state[e] * (_cost[e] + _pi[_source[e]] - _pi[_target[e]]);

      const IntVector  &_source;

      const IntVector  &_target;

      const IntVector  &_state;

      int &_in_arc;

      int _arc_num;

      // Find next entering arc

      bool findEnteringArc() {

        for (int e = 0; e < _arc_num; ++e) {

          c = _state[e] * (_cost[e] + _pi[_source[e]] - _pi[_target[e]]);

      const IntVector  &_source;

      const IntVector  &_target;

      const IntVector  &_state;

      int &_in_arc;

      int _arc_num;

      // Find next entering arc

      bool findEnteringArc() {

        int cnt = _block_size;

        int e, min_arc = _next_arc;

      const IntVector  &_source;

      const IntVector  &_target;

      const IntVector  &_state;

      int &_in_arc;

      int _arc_num;

      /// Find next entering arc

      bool findEnteringArc() {

        int e, min_arc = _next_arc;

        if (_curr_length > 0 && _minor_count < _minor_limit) {

      const IntVector  &_source;

      const IntVector  &_target;

      const IntVector  &_state;

      int &_in_arc;

      int _arc_num;

      int _next_arc;

      IntVector _candidates;

      // Functor class to compare arcs during sort of the candidate list

      {

      private:

      public:

        bool operator()(int left, int right) {

          return _map[left] > _map[right];

      _node_id(graph)

    {

    }

    ///

    /// \param map An arc map storing the lower bounds.

    /// of the algorithm.

    ///

    NetworkSimplex& lowerMap(const LOWER& map) {

      delete _plower;

      for (ArcIt a(_graph); a != INVALID; ++a) {

        (*_plower)[a] = map[a];

    /// and \ref boundMaps() is used before calling \ref run(),

    /// the upper bounds (capacities) will be set to

    ///

    /// \param map An arc map storing the upper bounds.

    /// of the algorithm.

    ///

    NetworkSimplex& upperMap(const UPPER& map) {

      delete _pupper;

      for (ArcIt a(_graph); a != INVALID; ++a) {

        (*_pupper)[a] = map[a];

    /// and \ref boundMaps() is used before calling \ref run(),

    /// the upper bounds (capacities) will be set to

    ///

    /// \param lower An arc map storing the lower bounds.

    ///

    /// The \c Value type of the maps must be convertible to the

    ///

    /// \note This function is just a shortcut of calling \ref lowerMap()

    ///

    /// \param map An arc map storing the costs.

    /// of the algorithm.

    ///

    NetworkSimplex& costMap(const COST& map) {

      delete _pcost;

      for (ArcIt a(_graph); a != INVALID; ++a) {

        (*_pcost)[a] = map[a];

    ///

    /// \param map A node map storing the supply values.

    /// of the algorithm.

    ///

      delete _psupply;

      _pstsup = false;

      for (NodeIt n(_graph); n != INVALID; ++n) {

        (*_psupply)[n] = map[n];

    ///

    /// \return <tt>(*this)</tt>

      delete _psupply;

      _psupply = NULL;

    ///

    /// This function returns the total cost of the found flow.

    ///

    /// \note The return type of the function can be specified as a

    ///   ns.totalCost<double>();

    /// \endcode

    /// type of the algorithm, which is the default return type of the

    /// function.

#ifndef DOXYGEN

    }

#endif

    ///

    /// \pre \ref run() must be called before using this function.

      return (*_flow_map)[a];

    }

    ///

    /// \pre \ref run() must be called before using this function.

      return (*_potential_map)[n];

    }

      }

      if (_psupply) {

        int i = 0;

        for (NodeIt n(_graph); n != INVALID; ++n, ++i) {

      // Initialize arc maps

      if (_pupper && _pcost) {

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

            _cap[i] = (*_pupper)[_arc_ref[i]];

        } else {

          for (int i = 0; i != _arc_num; ++i)

        }

        if (_pcost) {

      if (_plower) {

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

          if (c != 0) {

            _cap[i] -= c;

      // Add artificial arcs and initialize the spanning tree data structure

      for (int u = 0, e = _arc_num; u != _node_num; ++u, ++e) {

        _thread[u] = u + 1;

      delta = _cap[in_arc];

      int result = 0;

      int e;

      // Augment along the cycle

      if (delta > 0) {

        _flow[in_arc] += val;

        for (int u = _source[in_arc]; u != join; u = _parent[u]) {

    // Update potentials

    void updatePotential() {

        _pi[v_in] - _pi[u_in] - _cost[_pred[u_in]] :

        _pi[v_in] - _pi[u_in] + _cost[_pred[u_in]];

// Check the interface of an MCF algorithm

class McfClassConcept

{

    typedef typename GR::Node Node;

    typedef typename GR::Arc Arc;

    const GR &g;

    const NM ⊃

    const Node &n;

    const Arc &a;

    bool b;

  // Check the interfaces

  {

    // TODO: This typedef should be enabled if the standard maps are

    // reference maps in the graph concepts (See #190).

    typedef ListDigraph GR;

/**/

  }