/* -*- mode: C++; indent-tabs-mode: nil; -*-

 /* -*- mode: C++; indent-tabs-mode: nil; -*-

  *

  *

  * This file is a part of LEMON, a generic C++ optimization library.

  * This file is a part of LEMON, a generic C++ optimization library.

  *

  *

  * 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

       /// The objective function of the problem is unbounded, i.e.

       /// The objective function of the problem is unbounded, i.e.

       /// there is a directed cycle having negative total cost and

       /// there is a directed cycle having negative total cost and

       /// infinite upper bound.

       /// infinite upper bound.

       UNBOUNDED

       UNBOUNDED

     };

     };

     /// \brief Constants for selecting the type of the supply constraints.

     /// \brief Constants for selecting the type of the supply constraints.

     ///

     ///

     /// Enum type containing constants for selecting the supply type,

     /// Enum type containing constants for selecting the supply type,

     /// i.e. the direction of the inequalities in the supply/demand

     /// i.e. the direction of the inequalities in the supply/demand

     /// constraints of the \ref min_cost_flow "minimum cost flow problem".

     /// constraints of the \ref min_cost_flow "minimum cost flow problem".

       GEQ,

       GEQ,

       /// This option means that there are <em>"less or equal"</em>

       /// This option means that there are <em>"less or equal"</em>

       /// supply/demand constraints in the definition of the problem.

       /// supply/demand constraints in the definition of the problem.

       LEQ

       LEQ

     };

     };

     /// \brief Constants for selecting the pivot rule.

     /// \brief Constants for selecting the pivot rule.

     ///

     ///

     /// Enum type containing constants for selecting the pivot rule for

     /// Enum type containing constants for selecting the pivot rule for

     /// the \ref run() function.

     /// the \ref run() function.

     ///

     ///

       /// It is a modified version of the Candidate List method.

       /// It is a modified version of the Candidate List method.

       /// It keeps only the several best eligible arcs from the former

       /// It keeps only the several best eligible arcs from the former

       /// candidate list and extends this list in every iteration.

       /// candidate list and extends this list in every iteration.

       ALTERING_LIST

       ALTERING_LIST

     };

     };

   private:

   private:

     TEMPLATE_DIGRAPH_TYPEDEFS(GR);

     TEMPLATE_DIGRAPH_TYPEDEFS(GR);

     typedef std::vector<Arc> ArcVector;

     typedef std::vector<Arc> ArcVector;

     int first, second, right, last;

     int first, second, right, last;

     int stem, par_stem, new_stem;

     int stem, par_stem, new_stem;

     Value delta;

     Value delta;

   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.

       // Check the value types

       // Check the value types

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

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

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

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

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

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

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

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

       // Resize vectors

       // Resize vectors

       _node_num = countNodes(_graph);

       _node_num = countNodes(_graph);

       _arc_num = countArcs(_graph);

       _arc_num = countArcs(_graph);

       int all_node_num = _node_num + 1;

       int all_node_num = _node_num + 1;

       int max_arc_num = _arc_num + 2 * _node_num;

       int max_arc_num = _arc_num + 2 * _node_num;

         _arc_id[a] = i;

         _arc_id[a] = i;

         _source[i] = _node_id[_graph.source(a)];

         _source[i] = _node_id[_graph.source(a)];

         _target[i] = _node_id[_graph.target(a)];

         _target[i] = _node_id[_graph.target(a)];

         if ((i += k) >= _arc_num) i = (i % k) + 1;

         if ((i += k) >= _arc_num) i = (i % k) + 1;

       }

       }

       // Initialize maps

       // Initialize maps

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

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

         _supply[i] = 0;

         _supply[i] = 0;

       }

       }

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

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

       }

       }

       _supply[_node_id[s]] =  k;

       _supply[_node_id[s]] =  k;

       _supply[_node_id[t]] = -k;

       _supply[_node_id[t]] = -k;

       return *this;

       return *this;

     }

     }

     /// \brief Set the type of the supply constraints.

     /// \brief Set the type of the supply constraints.

     ///

     ///

     /// This function sets the type of the supply/demand constraints.

     /// This function sets the type of the supply/demand constraints.

     /// If it is not used before calling \ref run(), the \ref GEQ supply

     /// If it is not used before calling \ref run(), the \ref GEQ supply

     /// type will be used.

     /// type will be used.

     /// \brief Run the algorithm.

     /// \brief Run the algorithm.

     ///

     ///

     /// This function runs the algorithm.

     /// This function runs the algorithm.

     /// The paramters can be specified using functions \ref lowerMap(),

     /// The paramters can be specified using functions \ref lowerMap(),

     /// \ref supplyType().

     /// \ref supplyType().

     /// For example,

     /// For example,

     /// \code

     /// \code

     ///   NetworkSimplex<ListDigraph> ns(graph);

     ///   NetworkSimplex<ListDigraph> ns(graph);

     ///   ns.lowerMap(lower).upperMap(upper).costMap(cost)

     ///   ns.lowerMap(lower).upperMap(upper).costMap(cost)

       // Initialize arc maps

       // Initialize arc maps

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

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

         _flow[i] = 0;

         _flow[i] = 0;

         _state[i] = STATE_LOWER;

         _state[i] = STATE_LOWER;

       }

       }

       // Set data for the artificial root node

       // Set data for the artificial root node

       _root = _node_num;

       _root = _node_num;

       _parent[_root] = -1;

       _parent[_root] = -1;

       _pred[_root] = -1;

       _pred[_root] = -1;

       _thread[_root] = 0;

       _thread[_root] = 0;

         }

         }

       }

       }

       // Search the cycle along the path form the second node to the root

       // Search the cycle along the path form the second node to the root

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

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

         e = _pred[u];

         e = _pred[u];

           (_cap[e] == INF ? INF : _cap[e] - _flow[e]) : _flow[e];

           (_cap[e] == INF ? INF : _cap[e] - _flow[e]) : _flow[e];

         if (d <= delta) {

         if (d <= delta) {

           delta = d;

           delta = d;

           u_out = u;

           u_out = u;

           result = 2;

           result = 2;

         if (change) {

         if (change) {

           updateTreeStructure();

           updateTreeStructure();

           updatePotential();

           updatePotential();

         }

         }

       }

       }

       // Check feasibility

       // Check feasibility

       for (int e = _search_arc_num; e != _all_arc_num; ++e) {

       for (int e = _search_arc_num; e != _all_arc_num; ++e) {

         if (_flow[e] != 0) return INFEASIBLE;

         if (_flow[e] != 0) return INFEASIBLE;

       }

       }

             _supply[_source[i]] += c;

             _supply[_source[i]] += c;

             _supply[_target[i]] -= c;

             _supply[_target[i]] -= c;

           }

           }

         }

         }

       }

       }

       // Shift potentials to meet the requirements of the GEQ/LEQ type

       // Shift potentials to meet the requirements of the GEQ/LEQ type

       // optimality conditions

       // optimality conditions

       if (_sum_supply == 0) {

       if (_sum_supply == 0) {

         if (_stype == GEQ) {

         if (_stype == GEQ) {

           Cost max_pot = -std::numeric_limits<Cost>::max();

           Cost max_pot = -std::numeric_limits<Cost>::max();