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

 #define LEMON_MIN_COST_FLOW_H

 /// \ingroup min_cost_flow

 ///

 /// \file

 /// \brief An efficient algorithm for finding a minimum cost flow.

 #include <lemon/network_simplex.h>

 namespace lemon {

   /// \addtogroup min_cost_flow

   /// @{

   /// \brief An efficient algorithm for finding a minimum cost flow.

   ///

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

   /// algorithm for finding a minimum cost flow.

   ///

   /// \note \ref lemon::MinCostFlow "MinCostFlow" is just an alias for

   /// \ref lemon::NetworkSimplex "NetworkSimplex", wich is the most

   /// efficient implementation for the minimum cost flow problem in the

   /// LEMON library according to our benchmark tests.

   ///

   /// \note There are three implementations for the minimum cost flow

   /// problem, that can be used in the same way.

   /// - \ref lemon::CapacityScaling "CapacityScaling"

   /// - \ref lemon::CycleCanceling "CycleCanceling"

   /// - \ref lemon::NetworkSimplex "NetworkSimplex"

   ///

   /// \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 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 MinCostFlow :

     public NetworkSimplex< Graph,

 			   LowerMap,

 			   CapacityMap,

 			   CostMap,

 			   SupplyMap >

   {

     typedef NetworkSimplex< Graph, LowerMap, CapacityMap,

 			    CostMap, SupplyMap >

       MinCostFlowImpl;

     typedef typename Graph::Node Node;

     typedef typename SupplyMap::Value Supply;

   public:

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

     MinCostFlow( const Graph &_graph,

 		 const LowerMap &_lower,

 		 const CapacityMap &_capacity,

 		 const CostMap &_cost,

 		 const SupplyMap &_supply ) :

       MinCostFlowImpl(_graph, _lower, _capacity, _cost, _supply) {}

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

     MinCostFlow( const Graph &_graph,

 		 const CapacityMap &_capacity,

 		 const CostMap &_cost,

 		 const SupplyMap &_supply ) :

       MinCostFlowImpl(_graph, _capacity, _cost, _supply) {}

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

     MinCostFlow( const Graph &_graph,

 		 const LowerMap &_lower,

 		 const CapacityMap &_capacity,

 		 const CostMap &_cost,

 		 Node _s, Node _t,

 		 Supply _flow_value ) :

       MinCostFlowImpl( _graph, _lower, _capacity, _cost,

 		       _s, _t, _flow_value ) {}

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

     MinCostFlow( const Graph &_graph,

 		 const CapacityMap &_capacity,

 		 const CostMap &_cost,

 		 Node _s, Node _t,

 		 Supply _flow_value ) :

       MinCostFlowImpl( _graph, _capacity, _cost,

 		       _s, _t, _flow_value ) {}

   }; //class MinCostFlow

   ///@}

 } //namespace lemon

 #endif //LEMON_MIN_COST_FLOW_H