RhodeCode

    /// the \c Value type of the map.

    ///

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

    template <typename FlowMap>

    void flowMap(FlowMap &map) const {

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

        map.set(a, _flow[_arc_id[a]]);

      }

    }

    /// \brief Return the potential (dual value) of the given node.

    ///

    /// This function returns the potential (dual value) of the

    /// given node.

    ///

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

    Cost potential(const Node& n) const {

      return _pi[_node_id[n]];

    }

    /// \brief Return the potential map (the dual solution).

    ///

    /// This function copies the potential (dual value) of each node

    /// into the given map.

    /// The \c Cost type of the algorithm must be convertible to the

    /// \c Value type of the map.

    ///

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

    template <typename PotentialMap>

    void potentialMap(PotentialMap &map) const {

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

        map.set(n, _pi[_node_id[n]]);

      }

    }

    /// @}

  private:

    // Initialize internal data structures

    bool init() {

      if (_node_num == 0) return false;

      // Check the sum of supply values

      _sum_supply = 0;

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

        _sum_supply += _supply[i];

      }

      // Remove non-zero lower bounds

      if (_have_lower) {

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

          Value c = _lower[i];

          if (c >= 0) {

            _cap[i] = _upper[i] < INF ? _upper[i] - c : INF;

          } else {

            _cap[i] = _upper[i] < INF + c ? _upper[i] - c : INF;

          }

          _supply[_source[i]] -= c;

          _supply[_target[i]] += c;

        }

      } else {

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

          _cap[i] = _upper[i];

        }

      }

      // Initialize artifical cost

      Cost ART_COST;

      if (std::numeric_limits<Cost>::is_exact) {

        ART_COST = std::numeric_limits<Cost>::max() / 4 + 1;

      } else {

        ART_COST = std::numeric_limits<Cost>::min();

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

          if (_cost[i] > ART_COST) ART_COST = _cost[i];

        }

        ART_COST = (ART_COST + 1) * _node_num;

      }

      // Initialize arc maps

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

        _flow[i] = 0;

        _state[i] = STATE_LOWER;

      }

      // Set data for the artificial root node

      _root = _node_num;

      _parent[_root] = -1;

      _pred[_root] = -1;

      _thread[_root] = 0;

      _rev_thread[0] = _root;

      _succ_num[_root] = _node_num + 1;

      _last_succ[_root] = _root - 1;

      _supply[_root] = -_sum_supply;

      _pi[_root] = _sum_supply < 0 ? -ART_COST : ART_COST;