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