*

  *

  *

  *

  * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport

  * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport

  * (Egervary Research Group on Combinatorial Optimization, EGRES).

  * (Egervary Research Group on Combinatorial Optimization, EGRES).

  *

  *

  * Permission to use, modify and distribute this software is granted

  * Permission to use, modify and distribute this software is granted

  * provided that this copyright notice appears in all copies. For

  * provided that this copyright notice appears in all copies. For

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

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

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

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

       /// these cases.

       /// these cases.

       UNBOUNDED

       UNBOUNDED

     };

     };

   private:

   private:

     TEMPLATE_DIGRAPH_TYPEDEFS(GR);

     TEMPLATE_DIGRAPH_TYPEDEFS(GR);

     typedef std::vector<int> IntVector;

     typedef std::vector<int> IntVector;

     Value _delta;

     Value _delta;

     int _factor;

     int _factor;

     IntVector _pred;

     IntVector _pred;

   public:

   public:

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

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

     ///

     ///

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

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

     /// It is \c std::numeric_limits<Value>::infinity() if available,

     /// It is \c std::numeric_limits<Value>::infinity() if available,

     /// \c std::numeric_limits<Value>::max() otherwise.

     /// \c std::numeric_limits<Value>::max() otherwise.

       const CostVector &_cost;

       const CostVector &_cost;

       const ValueVector &_res_cap;

       const ValueVector &_res_cap;

       const ValueVector &_excess;

       const ValueVector &_excess;

       CostVector &_pi;

       CostVector &_pi;

       IntVector &_pred;

       IntVector &_pred;

       IntVector _proc_nodes;

       IntVector _proc_nodes;

       CostVector _dist;

       CostVector _dist;

     public:

     public:

       ResidualDijkstra(CapacityScaling& cs) :

       ResidualDijkstra(CapacityScaling& cs) :

         _node_num(cs._node_num), _geq(cs._sum_supply < 0),

         _node_num(cs._node_num), _geq(cs._sum_supply < 0),

         _first_out(cs._first_out), _target(cs._target), _cost(cs._cost),

         _first_out(cs._first_out), _target(cs._target), _cost(cs._cost),

       }

       }

       _supply[_node_id[s]] =  k;

       _supply[_node_id[s]] =  k;

       _supply[_node_id[t]] = -k;

       _supply[_node_id[t]] = -k;

       return *this;

       return *this;

     }

     }

     /// @}

     /// @}

     /// \name Execution control

     /// \name Execution control

     /// The algorithm can be executed using \ref run().

     /// The algorithm can be executed using \ref run().

       _lower.resize(_res_arc_num);

       _lower.resize(_res_arc_num);

       _upper.resize(_res_arc_num);

       _upper.resize(_res_arc_num);

       _cost.resize(_res_arc_num);

       _cost.resize(_res_arc_num);

       _supply.resize(_node_num);

       _supply.resize(_node_num);

       _res_cap.resize(_res_arc_num);

       _res_cap.resize(_res_arc_num);

       _pi.resize(_node_num);

       _pi.resize(_node_num);

       _excess.resize(_node_num);

       _excess.resize(_node_num);

       _pred.resize(_node_num);

       _pred.resize(_node_num);

         int fi = _arc_idf[a];

         int fi = _arc_idf[a];

         int bi = _arc_idb[a];

         int bi = _arc_idb[a];

         _reverse[fi] = bi;

         _reverse[fi] = bi;

         _reverse[bi] = fi;

         _reverse[bi] = fi;

       }

       }

       // Reset parameters

       // Reset parameters

       resetParams();

       resetParams();

       return *this;

       return *this;

     }

     }

       _sum_supply = 0;

       _sum_supply = 0;

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

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

         _sum_supply += _supply[i];

         _sum_supply += _supply[i];

       }

       }

       if (_sum_supply > 0) return INFEASIBLE;

       if (_sum_supply > 0) return INFEASIBLE;

       // Initialize vectors

       // Initialize vectors

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

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

         _pi[i] = 0;

         _pi[i] = 0;

         _excess[i] = _supply[i];

         _excess[i] = _supply[i];

       }

       }

             _res_cap[j] = 0;

             _res_cap[j] = 0;

             _res_cap[_reverse[j]] += rc;

             _res_cap[_reverse[j]] += rc;

           }

           }

         }

         }

       }

       }

       // Handle GEQ supply type

       // Handle GEQ supply type

       if (_sum_supply < 0) {

       if (_sum_supply < 0) {

         _pi[_root] = 0;

         _pi[_root] = 0;

         _excess[_root] = -_sum_supply;

         _excess[_root] = -_sum_supply;

         for (int a = _first_out[_root]; a != _res_arc_num; ++a) {

         for (int a = _first_out[_root]; a != _res_arc_num; ++a) {

       // Shift potentials if necessary

       // Shift potentials if necessary

       Cost pr = _pi[_root];

       Cost pr = _pi[_root];

       if (_sum_supply < 0 || pr > 0) {

       if (_sum_supply < 0 || pr > 0) {

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

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

           _pi[i] -= pr;

           _pi[i] -= pr;

       return pt;

       return pt;

     }

     }

     // Execute the capacity scaling algorithm

     // Execute the capacity scaling algorithm

     ProblemType startWithScaling() {

     ProblemType startWithScaling() {