/* -*- 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_CYCLE_CANCELING_H

 #define LEMON_CYCLE_CANCELING_H

 /// \ingroup min_cost_flow

 ///

 /// \file

 /// \brief A cycle canceling algorithm for finding a minimum cost flow.

 #include <vector>

 #include <lemon/circulation.h>

 #include <lemon/graph_adaptor.h>

 /// \brief The used cycle canceling method.

 #define LIMITED_CYCLE_CANCELING

 //#define MIN_MEAN_CYCLE_CANCELING

 #ifdef LIMITED_CYCLE_CANCELING

   #include <lemon/bellman_ford.h>

   /// \brief The maximum number of iterations for the first execution

   /// of the \ref lemon::BellmanFord "Bellman-Ford" algorithm.

   #define STARTING_LIMIT	2

   /// \brief The iteration limit for the

   /// \ref lemon::BellmanFord "Bellman-Ford" algorithm is multiplied by

   /// <tt>ALPHA_MUL % ALPHA_DIV</tt> in every round.

   #define ALPHA_MUL		3

   /// \brief The iteration limit for the

   /// \ref lemon::BellmanFord "Bellman-Ford" algorithm is multiplied by

   /// <tt>ALPHA_MUL % ALPHA_DIV</tt> in every round.

   #define ALPHA_DIV		2

 //#define _ONLY_ONE_CYCLE_

 //#define _DEBUG_ITER_

 #endif

 #ifdef MIN_MEAN_CYCLE_CANCELING

   #include <lemon/min_mean_cycle.h>

   #include <lemon/path.h>

 #endif

 namespace lemon {

   /// \addtogroup min_cost_flow

   /// @{

   /// \brief Implementation of a cycle canceling algorithm for finding

   /// a minimum cost flow.

   ///

   /// \ref lemon::CycleCanceling "CycleCanceling" implements a cycle

   /// canceling 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 CycleCanceling

   {

     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;

   protected:

     /// \brief Map adaptor class for demand map.

     class DemandMap : public MapBase<Node, Supply>

     {

     private:

       const SupplyMap *map;

     public:

       typedef typename MapBase<Node, Supply>::Value Value;

       typedef typename MapBase<Node, Supply>::Key Key;

       DemandMap(const SupplyMap &_map) : map(&_map) {}

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

 	return -(*map)[e];

       }

     }; //class DemandMap

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

     class ResCostMap : public MapBase<ResEdge, Cost>

     {

     private:

       const CostMap &cost_map;

     public:

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

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

       ResCostMap(const CostMap &_cost) : cost_map(_cost) {}

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

 	return ResGraph::forward(e) ? cost_map[e] : -cost_map[e];

       }

     }; //class ResCostMap

   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 modified demand map.

     DemandMap demand;

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

     bool valid_supply;

     /// \brief The current flow.

     FlowMap flow;

     /// \brief The residual graph.

     ResGraph res_graph;

     /// \brief The residual cost map.

     ResCostMap res_cost;

   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).

     CycleCanceling( 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), demand(supply), flow(_graph, 0),

       res_graph(_graph, capacity, flow), res_cost(cost)

     {

       // 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];

 	sum += (supply[n] = 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).

     CycleCanceling( const Graph &_graph,

 		    const CapacityMap &_capacity,

 		    const CostMap &_cost,

 		    const SupplyMap &_supply ) :

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

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

       res_graph(_graph, capacity, flow), res_cost(cost)

     {

       // 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).

     CycleCanceling( 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), demand(supply), flow(_graph, 0),

       res_graph(_graph, capacity, flow), res_cost(cost)

     {

       // 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] = 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).

     CycleCanceling( 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), demand(supply), flow(_graph, 0),

       res_graph(_graph, capacity, flow), res_cost(cost)

     {

       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 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 algorithm.

     ///

     /// Runs the algorithm.

     ///

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

     bool run() {

       return init() && start();

     }

   protected:

     /// \brief Initializes the algorithm.

     bool init() {

       // Checking the sum of supply values

       Supply sum = 0;

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

       if (sum != 0) return false;

       // Finding a feasible flow

       Circulation< Graph, Capacity, FlowMap, ConstMap<Edge, Capacity>,

 		   CapacityRefMap, DemandMap >

 	circulation( graph, constMap<Edge>((Capacity)0),

 		     capacity, demand, flow );

       return circulation.run() == -1;

     }

 #ifdef LIMITED_CYCLE_CANCELING

     /// \brief Executes a cycle canceling algorithm using

     /// \ref lemon::BellmanFord "Bellman-Ford" algorithm with limited

     /// iteration count.

     bool start() {

       typename BellmanFord<ResGraph, ResCostMap>::PredMap pred(res_graph);

       typename ResGraph::template NodeMap<int> visited(res_graph);

       std::vector<ResEdge> cycle;

       int node_num = countNodes(graph);

 #ifdef _DEBUG_ITER_

       int cycle_num = 0;

 #endif

       int length_bound = STARTING_LIMIT;

       bool optimal = false;

       while (!optimal) {

 	BellmanFord<ResGraph, ResCostMap> bf(res_graph, res_cost);

 	bf.predMap(pred);

 	bf.init(0);

 	int iter_num = 0;

 	bool cycle_found = false;

 	while (!cycle_found) {

 	  int curr_iter_num = iter_num + length_bound <= node_num ?

 			      length_bound : node_num - iter_num;

 	  iter_num += curr_iter_num;

 	  int real_iter_num = curr_iter_num;

 	  for (int i = 0; i < curr_iter_num; ++i) {

 	    if (bf.processNextWeakRound()) {

 	      real_iter_num = i;

 	      break;

 	    }

 	  }

 	  if (real_iter_num < curr_iter_num) {

 	    optimal = true;

 	    break;

 	  } else {

 	    // Searching for node disjoint negative cycles

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

 	      visited[n] = 0;

 	    int id = 0;

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

 	      if (visited[n] > 0) continue;

 	      visited[n] = ++id;

 	      ResNode u = pred[n] == INVALID ?

 			  INVALID : res_graph.source(pred[n]);

 	      while (u != INVALID && visited[u] == 0) {

 		visited[u] = id;

 		u = pred[u] == INVALID ?

 		    INVALID : res_graph.source(pred[u]);

 	      }

 	      if (u != INVALID && visited[u] == id) {

 		// Finding the negative cycle

 		cycle_found = true;

 		cycle.clear();

 		ResEdge e = pred[u];

 		cycle.push_back(e);

 		Capacity d = res_graph.rescap(e);

 		while (res_graph.source(e) != u) {

 		  cycle.push_back(e = pred[res_graph.source(e)]);

 		  if (res_graph.rescap(e) < d)

 		    d = res_graph.rescap(e);

 		}

 #ifdef _DEBUG_ITER_

 		++cycle_num;

 #endif

 		// Augmenting along the cycle

 		for (int i = 0; i < cycle.size(); ++i)

 		  res_graph.augment(cycle[i], d);

 #ifdef _ONLY_ONE_CYCLE_

 		break;

 #endif

 	      }

 	    }

 	  }

 	  if (!cycle_found)

 	    length_bound = length_bound * ALPHA_MUL / ALPHA_DIV;

 	}

       }

 #ifdef _DEBUG_ITER_

       std::cout << "Limited cycle canceling algorithm finished. "

 		<< "Found " << cycle_num << " negative cycles."

 		<< std::endl;

 #endif

       // Handling nonzero lower bounds

       if (lower) {

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

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

       }

       return true;

     }

 #endif

 #ifdef MIN_MEAN_CYCLE_CANCELING

     /// \brief Executes the minimum mean cycle canceling algorithm

     /// using \ref lemon::MinMeanCycle "MinMeanCycle" class.

     bool start() {

       typedef Path<ResGraph> ResPath;

       MinMeanCycle<ResGraph, ResCostMap> mmc(res_graph, res_cost);

       ResPath cycle;

 #ifdef _DEBUG_ITER_

       int cycle_num = 0;

 #endif

       mmc.cyclePath(cycle).init();

       if (mmc.findMinMean()) {

 	while (mmc.cycleLength() < 0) {

 #ifdef _DEBUG_ITER_

 	  ++iter;

 #endif

 	  // Finding the cycle

 	  mmc.findCycle();

 	  // Finding the largest flow amount that can be augmented

 	  // along the cycle

 	  Capacity delta = 0;

 	  for (typename ResPath::EdgeIt e(cycle); e != INVALID; ++e) {

 	    if (delta == 0 || res_graph.rescap(e) < delta)

 	      delta = res_graph.rescap(e);

 	  }

 	  // Augmenting along the cycle

 	  for (typename ResPath::EdgeIt e(cycle); e != INVALID; ++e)

 	    res_graph.augment(e, delta);

 	  // Finding the minimum cycle mean for the modified residual

 	  // graph

 	  mmc.reset();

 	  if (!mmc.findMinMean()) break;

 	}

       }

 #ifdef _DEBUG_ITER_

       std::cout << "Minimum mean cycle canceling algorithm finished. "

 		<< "Found " << cycle_num << " negative cycles."

 		<< std::endl;

 #endif

       // Handling nonzero lower bounds

       if (lower) {

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

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

       }

       return true;

     }

 #endif

   }; //class CycleCanceling

   ///@}

 } //namespace lemon

 #endif //LEMON_CYCLE_CANCELING_H