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

#define LEMON_MIN_COST_MAX_FLOW_H

/// \ingroup min_cost_flow

///

/// \file

/// \brief An efficient algorithm for finding a minimum cost maximum

/// flow.

#include <lemon/preflow.h>

#include <lemon/network_simplex.h>

#include <lemon/maps.h>

namespace lemon {

  /// \addtogroup min_cost_flow

  /// @{

  /// \brief An efficient algorithm for finding a minimum cost maximum

  /// flow.

  ///

  /// \ref lemon::MinCostFlow "MinCostMaxFlow" implements an efficient

  /// algorithm for finding a maximum flow having minimal total cost

  /// from a given source node to a given target node in a directed

  /// graph.

  ///

  /// \note \ref lemon::MinCostMaxFlow "MinCostMaxFlow" uses

  /// \ref lemon::Preflow "Preflow" algorithm for finding the maximum

  /// flow value and \ref lemon::NetworkSimplex "NetworkSimplex" 

  /// algorithm for finding a minimum cost flow of that value.

  ///

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

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

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

  ///

  /// \warning

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

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

  ///

  /// \author Peter Kovacs

template < typename Graph,

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

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

  class MinCostMaxFlow

  {

    typedef typename Graph::Node Node;

    typedef typename Graph::Edge Edge;

    typedef typename CapacityMap::Value Capacity;

    typedef typename Graph::template NodeMap<Capacity> SupplyMap;

    typedef NetworkSimplex< Graph, CapacityMap, CapacityMap,

			    CostMap, SupplyMap >

      MinCostFlowImpl;

  public:

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

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

    typedef typename CostMap::Value Cost;

  private:

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

    const Graph &graph;

    /// \brief The modified capacity map.

    const CapacityMap &capacity;

    /// \brief The cost map.

    const CostMap &cost;

    /// \brief The source node.

    Node source;

    /// \brief The target node.

    Node target;

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

    FlowMap flow;

    typedef Preflow<Graph, CapacityMap> PreflowImpl;

    /// \brief \ref lemon::Preflow "Preflow" class for finding the

    /// maximum flow value.

    PreflowImpl preflow;

  public:

    /// \brief The constructor of the class.

    ///

    /// The constructor of the class.

    ///

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

    MinCostMaxFlow( const Graph &_graph,

		    const CapacityMap &_capacity,

		    const CostMap &_cost,

		    Node _s, Node _t ) :

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

      source(_s), target(_t), flow(_graph),

      preflow(_graph, _capacity, _s, _t)

    {}

    /// \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 (typename Graph::EdgeIt e(graph); e != INVALID; ++e)

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

      return c;

    }

    /// \brief Runs the algorithm.

    void run() {

      preflow.flowMap(flow);

      preflow.runMinCut();

      MinCostFlowImpl mcf_impl( graph, capacity, cost,

				source, target, preflow.flowValue() );

      mcf_impl.run();

      flow = mcf_impl.flowMap();

    }

  }; //class MinCostMaxFlow

  ///@}

} //namespace lemon

#endif //LEMON_MIN_COST_MAX_FLOW_H