/* -*- 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_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 MinCostFlow provides an efficient algorithm for finding

   /// a minimum cost flow.

   ///

   /// \note \ref MinCostFlow is just an alias for \ref NetworkSimplex,

   /// which 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 exactly the same way.

   /// - \ref CapacityScaling

   /// - \ref CycleCanceling

   /// - \ref NetworkSimplex

   ///

   /// \note For the detailed documentation of this class see

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

     /// 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) {}

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

     MinCostFlow( const Graph &graph,

                  const CapacityMap &capacity,

                  const CostMap &_ost,

                  const SupplyMap &supply ) :

       MinCostFlowImpl(graph, capacity, cost, supply) {}

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

     MinCostFlow( const Graph &graph,

                  const LowerMap &lower,

                  const CapacityMap &capacity,

                  const CostMap &_ost,

                  Node s, Node t,

                  Supply flow_value ) :

       MinCostFlowImpl( graph, lower, capacity, cost,

                        s, t, flow_value ) {}

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