/* -*- C++ -*-

 *

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

 *

 * Copyright (C) 2003-2008

 * 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/graph_adaptor.h>

#include <lemon/circulation.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>

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

  // Bellman-Ford algorithm. It should be at least 2.

  #define STARTING_LIMIT        2

  // The iteration limit for the Bellman-Ford algorithm is multiplied by

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

  // <tt>ALPHA_MUL / ALPHA_DIV</tt> must be greater than 1.

  #define ALPHA_MUL             3

  #define ALPHA_DIV             2

//#define _ONLY_ONE_CYCLE_

//#define _NO_BACK_STEP_

#endif

#ifdef MIN_MEAN_CYCLE_CANCELING

  #include <lemon/min_mean_cycle.h>

  #include <lemon/path.h>

#endif

//#define _DEBUG_ITER_

namespace lemon {

  /// \addtogroup min_cost_flow

  /// @{

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

  /// finding a minimum cost flow.

  ///

  /// \ref 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 non-negative integers.

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

  /// - Supply values should be signed 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

  {

    GRAPH_TYPEDEFS(typename Graph);

    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> CapacityEdgeMap;

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

    typedef ResGraphAdaptor< const Graph, Capacity,

                             CapacityEdgeMap, CapacityEdgeMap > ResGraph;

    typedef typename ResGraph::Node ResNode;

    typedef typename ResGraph::NodeIt ResNodeIt;

    typedef typename ResGraph::Edge ResEdge;

    typedef typename ResGraph::EdgeIt ResEdgeIt;

  public:

    /// The type of the flow map.

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

  protected:

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

    class ResCostMap : public MapBase<ResEdge, Cost>

    {

    private:

      const CostMap &cost_map;

    public:

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

      Cost operator[](const ResEdge &e) const {

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

      }

    }; //class ResCostMap

  protected:

    /// The directed graph the algorithm runs on.

    const Graph &graph;

    /// The original lower bound map.

    const LowerMap *lower;

    /// The modified capacity map.

    CapacityEdgeMap capacity;

    /// The cost map.

    const CostMap &cost;

    /// The modified supply map.

    SupplyNodeMap supply;

    bool valid_supply;

    /// The current flow.

    FlowMap flow;

    /// The residual graph.

    ResGraph res_graph;

    /// 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), flow(_graph, 0),

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

    {

      // Removing non-zero 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), 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), flow(_graph, 0),

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

    {

      // Removing non-zero 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), flow(_graph, 0),

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

    {

      supply[_s] =  _flow_value;

      supply[_t] = -_flow_value;

      valid_supply = true;

    }

    /// \brief Runs the algorithm.

    ///

    /// Runs the algorithm.

    ///

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

    bool run() {

      return init() && start();

    }

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

    }

  protected:

    /// 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, ConstMap<Edge, Capacity>, CapacityEdgeMap,

                   SupplyMap >

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

                     supply );

      circulation.flowMap(flow);

      return circulation.run();

    }

#ifdef LIMITED_CYCLE_CANCELING

    /// \brief Executes a cycle-canceling algorithm using

    /// \ref 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) {

#ifdef _NO_BACK_STEP_

          int curr_iter_num = length_bound <= node_num ?

                              length_bound - iter_num : node_num - iter_num;

#else

          int curr_iter_num = iter_num + length_bound <= node_num ?

                              length_bound : node_num - iter_num;

#endif

          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 non-zero 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 MinMeanCycle.

    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_

          ++cycle_num;

#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 non-zero 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