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