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