/* -*- C++ -*-

  *

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

  *

  * Copyright (C) 2003-2007

  * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport

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

  *

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

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

  * precise terms see the accompanying LICENSE file.

  *

  * This software is provided "AS IS" with no warranty of any kind,

  * express or implied, and with no claim as to its suitability for any

  * purpose.

  *

  */

 #ifndef LEMON_CAPACITY_SCALING_H

 #define LEMON_CAPACITY_SCALING_H

 /// \ingroup min_cost_flow

 ///

 /// \file

 /// \brief The capacity scaling algorithm for finding a minimum cost

 /// flow.

 #include <vector>

 #include <lemon/dijkstra.h>

 #include <lemon/graph_adaptor.h>

 #define WITH_SCALING

 namespace lemon {

   /// \addtogroup min_cost_flow

   /// @{

   /// \brief Implementation of the capacity scaling version of the

   /// succesive shortest path algorithm for finding a minimum cost flow.

   ///

   /// \ref lemon::CapacityScaling "CapacityScaling" implements a

   /// capacity scaling algorithm for finding a minimum cost flow.

   ///

   /// \param Graph The directed graph type the algorithm runs on.

   /// \param LowerMap The type of the lower bound map.

   /// \param CapacityMap The type of the capacity (upper bound) map.

   /// \param CostMap The type of the cost (length) map.

   /// \param SupplyMap The type of the supply map.

   ///

   /// \warning

   /// - Edge capacities and costs should be nonnegative integers.

   ///	However \c CostMap::Value should be signed type.

   /// - Supply values should be integers.

   /// - \c LowerMap::Value must be convertible to

   ///	\c CapacityMap::Value and \c CapacityMap::Value must be

   ///	convertible to \c SupplyMap::Value.

   ///

   /// \author Peter Kovacs

 template < typename Graph,

 	   typename LowerMap = typename Graph::template EdgeMap<int>,

 	   typename CapacityMap = LowerMap,

 	   typename CostMap = typename Graph::template EdgeMap<int>,

 	   typename SupplyMap = typename Graph::template NodeMap

 				<typename CapacityMap::Value> >

   class CapacityScaling

   {

     typedef typename Graph::Node Node;

     typedef typename Graph::NodeIt NodeIt;

     typedef typename Graph::Edge Edge;

     typedef typename Graph::EdgeIt EdgeIt;

     typedef typename Graph::InEdgeIt InEdgeIt;

     typedef typename Graph::OutEdgeIt OutEdgeIt;

     typedef typename LowerMap::Value Lower;

     typedef typename CapacityMap::Value Capacity;

     typedef typename CostMap::Value Cost;

     typedef typename SupplyMap::Value Supply;

     typedef typename Graph::template EdgeMap<Capacity> CapacityRefMap;

     typedef typename Graph::template NodeMap<Supply> SupplyRefMap;

     typedef ResGraphAdaptor< const Graph, Capacity,

 			     CapacityRefMap, CapacityRefMap > ResGraph;

     typedef typename ResGraph::Node ResNode;

     typedef typename ResGraph::NodeIt ResNodeIt;

     typedef typename ResGraph::Edge ResEdge;

     typedef typename ResGraph::EdgeIt ResEdgeIt;

   public:

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

     typedef CapacityRefMap FlowMap;

     /// \brief The type of the potential map.

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

   protected:

     /// \brief Map adaptor class for handling reduced edge costs.

     class ReducedCostMap : public MapBase<ResEdge, Cost>

     {

     private:

       const ResGraph &gr;

       const CostMap &cost_map;

       const PotentialMap &pot_map;

     public:

       typedef typename MapBase<ResEdge, Cost>::Value Value;

       typedef typename MapBase<ResEdge, Cost>::Key Key;

       ReducedCostMap( const ResGraph &_gr,

 		      const CostMap &_cost,

 		      const PotentialMap &_pot ) :

 	gr(_gr), cost_map(_cost), pot_map(_pot) {}

       Value operator[](const Key &e) const {

 	return ResGraph::forward(e) ?

 	   cost_map[e] - pot_map[gr.source(e)] + pot_map[gr.target(e)] :

 	  -cost_map[e] - pot_map[gr.source(e)] + pot_map[gr.target(e)];

       }

     }; //class ReducedCostMap

     /// \brief Map adaptor for \ref lemon::Dijkstra "Dijkstra" class to

     /// update node potentials.

     class PotentialUpdateMap : public MapBase<ResNode, Cost>

     {

     private:

       PotentialMap *pot;

       typedef std::pair<ResNode, Cost> Pair;

       std::vector<Pair> data;

     public:

       typedef typename MapBase<ResNode, Cost>::Value Value;

       typedef typename MapBase<ResNode, Cost>::Key Key;

       void potentialMap(PotentialMap &_pot) {

 	pot = &_pot;

       }

       void init() {

 	data.clear();

       }

       void set(const Key &n, const Value &v) {

 	data.push_back(Pair(n, v));

       }

       void update() {

 	Cost val = data[data.size()-1].second;

 	for (int i = 0; i < data.size()-1; ++i)

 	  (*pot)[data[i].first] += val - data[i].second;

       }

     }; //class PotentialUpdateMap

 #ifdef WITH_SCALING

     /// \brief Map adaptor class for identifing deficit nodes.

     class DeficitBoolMap : public MapBase<ResNode, bool>

     {

     private:

       const SupplyRefMap &imb;

       const Capacity δ

     public:

       DeficitBoolMap(const SupplyRefMap &_imb, const Capacity &_delta) :

 	imb(_imb), delta(_delta) {}

       bool operator[](const ResNode &n) const {

 	return imb[n] <= -delta;

       }

     }; //class DeficitBoolMap

     /// \brief Map adaptor class for filtering edges with at least

     /// \c delta residual capacity

     class DeltaFilterMap : public MapBase<ResEdge, bool>

     {

     private:

       const ResGraph &gr;

       const Capacity δ

     public:

       typedef typename MapBase<ResEdge, Cost>::Value Value;

       typedef typename MapBase<ResEdge, Cost>::Key Key;

       DeltaFilterMap(const ResGraph &_gr, const Capacity &_delta) :

 	gr(_gr), delta(_delta) {}

       Value operator[](const Key &e) const {

 	return gr.rescap(e) >= delta;

       }

     }; //class DeltaFilterMap

     typedef EdgeSubGraphAdaptor<const ResGraph, const DeltaFilterMap>

       DeltaResGraph;

     /// \brief Traits class for \ref lemon::Dijkstra "Dijkstra" class.

     class ResDijkstraTraits :

       public DijkstraDefaultTraits<DeltaResGraph, ReducedCostMap>

     {

     public:

       typedef PotentialUpdateMap DistMap;

       static DistMap *createDistMap(const DeltaResGraph&) {

 	return new DistMap();

       }

     }; //class ResDijkstraTraits

 #else //WITHOUT_CAPACITY_SCALING

     /// \brief Map adaptor class for identifing deficit nodes.

     class DeficitBoolMap : public MapBase<ResNode, bool>

     {

     private:

       const SupplyRefMap &imb;

     public:

       DeficitBoolMap(const SupplyRefMap &_imb) : imb(_imb) {}

       bool operator[](const ResNode &n) const {

 	return imb[n] < 0;

       }

     }; //class DeficitBoolMap

     /// \brief Traits class for \ref lemon::Dijkstra "Dijkstra" class.

     class ResDijkstraTraits :

       public DijkstraDefaultTraits<ResGraph, ReducedCostMap>

     {

     public:

       typedef PotentialUpdateMap DistMap;

       static DistMap *createDistMap(const ResGraph&) {

 	return new DistMap();

       }

     }; //class ResDijkstraTraits

 #endif

   protected:

     /// \brief The directed graph the algorithm runs on.

     const Graph &graph;

     /// \brief The original lower bound map.

     const LowerMap *lower;

     /// \brief The modified capacity map.

     CapacityRefMap capacity;

     /// \brief The cost map.

     const CostMap &cost;

     /// \brief The modified supply map.

     SupplyRefMap supply;

     /// \brief The sum of supply values equals zero.

     bool valid_supply;

     /// \brief The edge map of the current flow.

     FlowMap flow;

     /// \brief The potential node map.

     PotentialMap potential;

     /// \brief The residual graph.

     ResGraph res_graph;

     /// \brief The reduced cost map.

     ReducedCostMap red_cost;

     /// \brief The imbalance map.

     SupplyRefMap imbalance;

     /// \brief The excess nodes.

     std::vector<ResNode> excess_nodes;

     /// \brief The index of the next excess node.

     int next_node;

 #ifdef WITH_SCALING

     typedef Dijkstra<DeltaResGraph, ReducedCostMap, ResDijkstraTraits>

       ResDijkstra;

     /// \brief \ref lemon::Dijkstra "Dijkstra" class for finding

     /// shortest paths in the residual graph with respect to the

     /// reduced edge costs.

     ResDijkstra dijkstra;

     /// \brief The delta parameter used for capacity scaling.

     Capacity delta;

     /// \brief Edge filter map.

     DeltaFilterMap delta_filter;

     /// \brief The delta residual graph.

     DeltaResGraph dres_graph;

     /// \brief Map for identifing deficit nodes.

     DeficitBoolMap delta_deficit;

 #else //WITHOUT_CAPACITY_SCALING

     typedef Dijkstra<ResGraph, ReducedCostMap, ResDijkstraTraits>

       ResDijkstra;

     /// \brief \ref lemon::Dijkstra "Dijkstra" class for finding

     /// shortest paths in the residual graph with respect to the

     /// reduced edge costs.

     ResDijkstra dijkstra;

     /// \brief Map for identifing deficit nodes.

     DeficitBoolMap has_deficit;

 #endif

     /// \brief Pred map for the \ref lemon::Dijkstra "Dijkstra" class.

     typename ResDijkstra::PredMap pred;

     /// \brief Dist map for the \ref lemon::Dijkstra "Dijkstra" class to

     /// update node potentials.

     PotentialUpdateMap updater;

   public :

     /// \brief General constructor of the class (with lower bounds).

     ///

     /// General constructor of the class (with lower bounds).

     ///

     /// \param _graph The directed graph the algorithm runs on.

     /// \param _lower The lower bounds of the edges.

     /// \param _capacity The capacities (upper bounds) of the edges.

     /// \param _cost The cost (length) values of the edges.

     /// \param _supply The supply values of the nodes (signed).

     CapacityScaling( const Graph &_graph,

 		     const LowerMap &_lower,

 		     const CapacityMap &_capacity,

 		     const CostMap &_cost,

 		     const SupplyMap &_supply ) :

       graph(_graph), lower(&_lower), capacity(_graph), cost(_cost),

       supply(_graph), flow(_graph, 0), potential(_graph, 0),

       res_graph(_graph, capacity, flow),

       red_cost(res_graph, cost, potential), imbalance(_graph),

 #ifdef WITH_SCALING

       delta(0), delta_filter(res_graph, delta),

       dres_graph(res_graph, delta_filter),

       dijkstra(dres_graph, red_cost), pred(dres_graph),

       delta_deficit(imbalance, delta)

 #else //WITHOUT_CAPACITY_SCALING

       dijkstra(res_graph, red_cost), pred(res_graph),

       has_deficit(imbalance)

 #endif

     {

       // Removing nonzero lower bounds

       capacity = subMap(_capacity, _lower);

       Supply sum = 0;

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

 	Supply s = _supply[n];

 	for (InEdgeIt e(graph, n); e != INVALID; ++e)

 	  s += _lower[e];

 	for (OutEdgeIt e(graph, n); e != INVALID; ++e)

 	  s -= _lower[e];

 	supply[n] = imbalance[n] = s;

 	sum += s;

       }

       valid_supply = sum == 0;

     }

     /// \brief General constructor of the class (without lower bounds).

     ///

     /// General constructor of the class (without lower bounds).

     ///

     /// \param _graph The directed graph the algorithm runs on.

     /// \param _capacity The capacities (upper bounds) of the edges.

     /// \param _cost The cost (length) values of the edges.

     /// \param _supply The supply values of the nodes (signed).

     CapacityScaling( const Graph &_graph,

 		     const CapacityMap &_capacity,

 		     const CostMap &_cost,

 		     const SupplyMap &_supply ) :

       graph(_graph), lower(NULL), capacity(_capacity), cost(_cost),

       supply(_supply), flow(_graph, 0), potential(_graph, 0),

       res_graph(_graph, capacity, flow),

       red_cost(res_graph, cost, potential), imbalance(_graph),

 #ifdef WITH_SCALING

       delta(0), delta_filter(res_graph, delta),

       dres_graph(res_graph, delta_filter),

       dijkstra(dres_graph, red_cost), pred(dres_graph),

       delta_deficit(imbalance, delta)

 #else //WITHOUT_CAPACITY_SCALING

       dijkstra(res_graph, red_cost), pred(res_graph),

       has_deficit(imbalance)

 #endif

     {

       // Checking the sum of supply values

       Supply sum = 0;

       for (NodeIt n(graph); n != INVALID; ++n) sum += supply[n];

       valid_supply = sum == 0;

     }

     /// \brief Simple constructor of the class (with lower bounds).

     ///

     /// Simple constructor of the class (with lower bounds).

     ///

     /// \param _graph The directed graph the algorithm runs on.

     /// \param _lower The lower bounds of the edges.

     /// \param _capacity The capacities (upper bounds) of the edges.

     /// \param _cost The cost (length) values of the edges.

     /// \param _s The source node.

     /// \param _t The target node.

     /// \param _flow_value The required amount of flow from node \c _s

     /// to node \c _t (i.e. the supply of \c _s and the demand of

     /// \c _t).

     CapacityScaling( const Graph &_graph,

 		     const LowerMap &_lower,

 		     const CapacityMap &_capacity,

 		     const CostMap &_cost,

 		     Node _s, Node _t,

 		     Supply _flow_value ) :

       graph(_graph), lower(&_lower), capacity(_graph), cost(_cost),

       supply(_graph), flow(_graph, 0), potential(_graph, 0),

       res_graph(_graph, capacity, flow),

       red_cost(res_graph, cost, potential), imbalance(_graph),

 #ifdef WITH_SCALING

       delta(0), delta_filter(res_graph, delta),

       dres_graph(res_graph, delta_filter),

       dijkstra(dres_graph, red_cost), pred(dres_graph),

       delta_deficit(imbalance, delta)

 #else //WITHOUT_CAPACITY_SCALING

       dijkstra(res_graph, red_cost), pred(res_graph),

       has_deficit(imbalance)

 #endif

     {

       // Removing nonzero lower bounds

       capacity = subMap(_capacity, _lower);

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

 	Supply s = 0;

 	if (n == _s) s =  _flow_value;

 	if (n == _t) s = -_flow_value;

 	for (InEdgeIt e(graph, n); e != INVALID; ++e)

 	  s += _lower[e];

 	for (OutEdgeIt e(graph, n); e != INVALID; ++e)

 	  s -= _lower[e];

 	supply[n] = imbalance[n] = s;

       }

       valid_supply = true;

     }

     /// \brief Simple constructor of the class (without lower bounds).

     ///

     /// Simple constructor of the class (without lower bounds).

     ///

     /// \param _graph The directed graph the algorithm runs on.

     /// \param _capacity The capacities (upper bounds) of the edges.

     /// \param _cost The cost (length) values of the edges.

     /// \param _s The source node.

     /// \param _t The target node.

     /// \param _flow_value The required amount of flow from node \c _s

     /// to node \c _t (i.e. the supply of \c _s and the demand of

     /// \c _t).

     CapacityScaling( const Graph &_graph,

 		     const CapacityMap &_capacity,

 		     const CostMap &_cost,

 		     Node _s, Node _t,

 		     Supply _flow_value ) :

       graph(_graph), lower(NULL), capacity(_capacity), cost(_cost),

       supply(_graph, 0), flow(_graph, 0), potential(_graph, 0),

       res_graph(_graph, capacity, flow),

       red_cost(res_graph, cost, potential), imbalance(_graph),

 #ifdef WITH_SCALING

       delta(0), delta_filter(res_graph, delta),

       dres_graph(res_graph, delta_filter),

       dijkstra(dres_graph, red_cost), pred(dres_graph),

       delta_deficit(imbalance, delta)

 #else //WITHOUT_CAPACITY_SCALING

       dijkstra(res_graph, red_cost), pred(res_graph),

       has_deficit(imbalance)

 #endif

     {

       supply[_s] =  _flow_value;

       supply[_t] = -_flow_value;

       valid_supply = true;

     }

     /// \brief Returns a const reference to the flow map.

     ///

     /// Returns a const reference to the flow map.

     ///

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

     const FlowMap& flowMap() const {

       return flow;

     }

     /// \brief Returns a const reference to the potential map (the dual

     /// solution).

     ///

     /// Returns a const reference to the potential map (the dual

     /// solution).

     ///

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

     const PotentialMap& potentialMap() const {

       return potential;

     }

     /// \brief Returns the total cost of the found flow.

     ///

     /// Returns the total cost of the found flow. The complexity of the

     /// function is \f$ O(e) \f$.

     ///

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

     Cost totalCost() const {

       Cost c = 0;

       for (EdgeIt e(graph); e != INVALID; ++e)

 	c += flow[e] * cost[e];

       return c;

     }

     /// \brief Runs the successive shortest path algorithm.

     ///

     /// Runs the successive shortest path algorithm.

     ///

     /// \return \c true if a feasible flow can be found.

     bool run() {

       return init() && start();

     }

   protected:

     /// \brief Initializes the algorithm.

     bool init() {

       if (!valid_supply) return false;

       // Initalizing Dijkstra class

       updater.potentialMap(potential);

       dijkstra.distMap(updater).predMap(pred);

 #ifdef WITH_SCALING

       // Initilaizing delta value

       Capacity max_cap = 0;

       for (EdgeIt e(graph); e != INVALID; ++e) {

 	if (capacity[e] > max_cap) max_cap = capacity[e];

       }

       for (delta = 1; 2 * delta < max_cap; delta *= 2) ;

 #endif

       return true;

     }

 #ifdef WITH_SCALING

     /// \brief Executes the capacity scaling version of the successive

     /// shortest path algorithm.

     bool start() {

       typedef typename DeltaResGraph::EdgeIt DeltaResEdgeIt;

       typedef typename DeltaResGraph::Edge DeltaResEdge;

       // Processing capacity scaling phases

       ResNode s, t;

       for ( ; delta >= 1; delta = delta < 4 && delta > 1 ?

 				  1 : delta / 4 )

       {

 	// Saturating edges not satisfying the optimality condition

 	Capacity r;

 	for (DeltaResEdgeIt e(dres_graph); e != INVALID; ++e) {

 	  if (red_cost[e] < 0) {

 	    res_graph.augment(e, r = res_graph.rescap(e));

 	    imbalance[dres_graph.target(e)] += r;

 	    imbalance[dres_graph.source(e)] -= r;

 	  }

 	}

 	// Finding excess nodes

 	excess_nodes.clear();

 	for (ResNodeIt n(res_graph); n != INVALID; ++n) {

 	  if (imbalance[n] >= delta) excess_nodes.push_back(n);

 	}

 	next_node = 0;

 	// Finding successive shortest paths

 	while (next_node < excess_nodes.size()) {

 	  // Running Dijkstra

 	  s = excess_nodes[next_node];

 	  updater.init();

 	  dijkstra.init();

 	  dijkstra.addSource(s);

 	  if ((t = dijkstra.start(delta_deficit)) == INVALID) {

 	    if (delta > 1) {

 	      ++next_node;

 	      continue;

 	    }

 	    return false;

 	  }

 	  // Updating node potentials

 	  updater.update();

 	  // Augment along a shortest path from s to t

 	  Capacity d = imbalance[s] < -imbalance[t] ?

 	    imbalance[s] : -imbalance[t];

 	  ResNode u = t;

 	  ResEdge e;

 	  if (d > delta) {

 	    while ((e = pred[u]) != INVALID) {

 	      if (res_graph.rescap(e) < d) d = res_graph.rescap(e);

 	      u = dres_graph.source(e);

 	    }

 	  }

 	  u = t;

 	  while ((e = pred[u]) != INVALID) {

 	    res_graph.augment(e, d);

 	    u = dres_graph.source(e);

 	  }

 	  imbalance[s] -= d;

 	  imbalance[t] += d;

 	  if (imbalance[s] < delta) ++next_node;

 	}

       }

       // Handling nonzero lower bounds

       if (lower) {

 	for (EdgeIt e(graph); e != INVALID; ++e)

 	  flow[e] += (*lower)[e];

       }

       return true;

     }

 #else //WITHOUT_CAPACITY_SCALING

     /// \brief Executes the successive shortest path algorithm without

     /// capacity scaling.

     bool start() {

       // Finding excess nodes

       for (ResNodeIt n(res_graph); n != INVALID; ++n) {

 	if (imbalance[n] > 0) excess_nodes.push_back(n);

       }

       if (excess_nodes.size() == 0) return true;

       next_node = 0;

       // Finding successive shortest paths

       ResNode s, t;

       while ( imbalance[excess_nodes[next_node]] > 0 ||

 	      ++next_node < excess_nodes.size() )

       {

 	// Running Dijkstra

 	s = excess_nodes[next_node];

 	updater.init();

 	dijkstra.init();

 	dijkstra.addSource(s);

 	if ((t = dijkstra.start(has_deficit)) == INVALID)

 	  return false;

 	// Updating node potentials

 	updater.update();

 	// Augmenting along a shortest path from s to t

 	Capacity delta = imbalance[s] < -imbalance[t] ?

 	  imbalance[s] : -imbalance[t];

 	ResNode u = t;

 	ResEdge e;

 	while ((e = pred[u]) != INVALID) {

 	  if (res_graph.rescap(e) < delta) delta = res_graph.rescap(e);

 	  u = res_graph.source(e);

 	}

 	u = t;

 	while ((e = pred[u]) != INVALID) {

 	  res_graph.augment(e, delta);

 	  u = res_graph.source(e);

 	}

 	imbalance[s] -= delta;

 	imbalance[t] += delta;

       }

       // Handling nonzero lower bounds

       if (lower) {

 	for (EdgeIt e(graph); e != INVALID; ++e)

 	  flow[e] += (*lower)[e];

       }

       return true;

     }

 #endif

   }; //class CapacityScaling

   ///@}

 } //namespace lemon

 #endif //LEMON_CAPACITY_SCALING_H