RhodeCode

    typedef SM SupplyMap;

    /// \brief The type of the map that stores the flow values.

    /// It must conform to the \ref concepts::ReadWriteMap "ReadWriteMap"

    /// concept.

    /// \brief Instantiates a FlowMap.

    ///

    /// The tolerance used by the algorithm to handle inexact computation.

  };

    ///The type of the digraph the algorithm runs on.

    typedef typename Traits::Digraph Digraph;

    ///The type of the lower bound map.

    bool _local_level;

    ExcessMap* _excess;

          (*_excess)[_g.source(e)] -= (*_lo)[e];

        } else {

          _flow->set(e, fc);

          (*_excess)[_g.target(e)] = 0;

        int actlevel=(*_level)[act];

        int mlevel=_node_num;

        for(OutArcIt e(_g,act);e!=INVALID; ++e) {

          Node v = _g.target(e);

          if(!_tol.positive(fc)) continue;

          if((*_level)[v]<actlevel) {

        for(InArcIt e(_g,act);e!=INVALID; ++e) {

          Node v = _g.source(e);

          if(!_tol.positive(fc)) continue;

          if((*_level)[v]<actlevel) {

    ///@{

    ///

    ///

    /// \pre Either \ref run() or \ref init() must be called before

    /// using this function.

      return (*_flow)[arc];

    }

      for(NodeIt n(_g);n!=INVALID;++n)

        {

          for(InArcIt e(_g,n);e!=INVALID;++e) dif-=(*_flow)[e];

          for(OutArcIt e(_g,n);e!=INVALID;++e) dif+=(*_flow)[e];

    bool checkBarrier() const

    {

      for(NodeIt n(_g);n!=INVALID;++n)

        if(barrier(n))

  ///

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

  /// and supply values in the algorithm. By default it is \c int.

  /// \tparam C The value type used for costs and potentials in the

  ///

  /// \warning Both value types must be signed and all input data must

  /// implementations, from which the most efficient one is used

  /// by default. For more information see \ref PivotRule.

  class NetworkSimplex

  {

    /// The flow type of the algorithm

    /// The cost type of the algorithm

    typedef C Cost;

#ifdef DOXYGEN

    /// The type of the flow map

    /// The type of the potential map

    typedef GR::NodeMap<Cost> PotentialMap;

#else

    /// The type of the flow map

    /// The type of the potential map

    typedef typename GR::template NodeMap<Cost> PotentialMap;

    TEMPLATE_DIGRAPH_TYPEDEFS(GR);

    typedef typename GR::template ArcMap<Cost> CostArcMap;

    typedef std::vector<Arc> ArcVector;

    typedef std::vector<int> IntVector;

    typedef std::vector<bool> BoolVector;

    typedef std::vector<Cost> CostVector;

    // Parameters of the problem

    CostArcMap *_pcost;

    bool _pstsup;

    Node _psource, _ptarget;

    SupplyType _stype;

    // Result maps

    int first, second, right, last;

    int stem, par_stem, new_stem;

  public:

    ///

    /// Constant for infinite upper bounds (capacities).

  private:

      _local_flow(false), _local_potential(false),

      _node_id(graph),

    {

      // Check the value types

        "The flow type of NetworkSimplex must be signed");

      LEMON_ASSERT(std::numeric_limits<Cost>::is_signed,

    ///

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

    /// of the algorithm.

    ///

    NetworkSimplex& lowerMap(const LowerMap& map) {

      delete _plower;

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

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

    ///

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

    /// of the algorithm.

    ///

    NetworkSimplex& upperMap(const UpperMap& map) {

      delete _pupper;

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

        (*_pupper)[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;

    ///

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

      return (*_flow_map)[a];

    }

      if (_plower) {

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

          if (c > 0) {

            if (_cap[i] < INF) _cap[i] -= c;

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

    /// \brief The type of the flow values.

    /// \brief The type of the map that stores the flow values.

    /// The type of the map that stores the flow values.

    /// It must meet the \ref concepts::ReadWriteMap "ReadWriteMap" concept.

    /// \brief Instantiates a FlowMap.

    ///

    /// The tolerance used by the algorithm to handle inexact computation.

  };

    typedef typename Traits::CapacityMap CapacityMap;

    ///The type of the flow values.

    ///The type of the flow map.

    bool _local_level;

    ExcessMap* _excess;

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

        for (InArcIt e(_graph, n); e != INVALID; ++e) {

          excess += (*_flow)[e];

      for (OutArcIt e(_graph, _source); e != INVALID; ++e) {

        if (_tolerance.positive(rem)) {

          Node u = _graph.target(e);

      }

      for (InArcIt e(_graph, _source); e != INVALID; ++e) {

        if (_tolerance.positive(rem)) {

          Node v = _graph.source(e);

        while (num > 0 && n != INVALID) {

          int new_level = _level->maxLevel();

          for (OutArcIt e(_graph, n); e != INVALID; ++e) {

            if (!_tolerance.positive(rem)) continue;

            Node v = _graph.target(e);

          for (InArcIt e(_graph, n); e != INVALID; ++e) {

            if (!_tolerance.positive(rem)) continue;

            Node v = _graph.source(e);

        num = _node_num * 20;

        while (num > 0 && n != INVALID) {

          int new_level = _level->maxLevel();

          for (OutArcIt e(_graph, n); e != INVALID; ++e) {

            if (!_tolerance.positive(rem)) continue;

            Node v = _graph.target(e);

          for (InArcIt e(_graph, n); e != INVALID; ++e) {

            if (!_tolerance.positive(rem)) continue;

            Node v = _graph.source(e);

      Node n;

      while ((n = _level->highestActive()) != INVALID) {

        int level = _level->highestActiveLevel();

        int new_level = _level->maxLevel();

        for (OutArcIt e(_graph, n); e != INVALID; ++e) {

          if (!_tolerance.positive(rem)) continue;

          Node v = _graph.target(e);

        for (InArcIt e(_graph, n); e != INVALID; ++e) {

          if (!_tolerance.positive(rem)) continue;

          Node v = _graph.source(e);

    /// \pre Either \ref run() or \ref init() must be called before

    /// using this function.

      return (*_excess)[_target];

    }

    ///

    /// be called after the second phase of the algorithm.

    ///

    /// \pre Either \ref run() or \ref init() must be called before

    /// using this function.

      return (*_flow)[arc];

    }