deba@2440: /* -*- C++ -*-
deba@2440:  *
deba@2440:  * This file is a part of LEMON, a generic C++ optimization library
deba@2440:  *
deba@2440:  * Copyright (C) 2003-2007
deba@2440:  * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
deba@2440:  * (Egervary Research Group on Combinatorial Optimization, EGRES).
deba@2440:  *
deba@2440:  * Permission to use, modify and distribute this software is granted
deba@2440:  * provided that this copyright notice appears in all copies. For
deba@2440:  * precise terms see the accompanying LICENSE file.
deba@2440:  *
deba@2440:  * This software is provided "AS IS" with no warranty of any kind,
deba@2440:  * express or implied, and with no claim as to its suitability for any
deba@2440:  * purpose.
deba@2440:  *
deba@2440:  */
deba@2440: 
deba@2440: #ifndef LEMON_MIN_COST_FLOW_H
deba@2440: #define LEMON_MIN_COST_FLOW_H
deba@2440: 
deba@2440: /// \ingroup min_cost_flow
deba@2440: ///
deba@2440: /// \file
deba@2440: /// \brief An efficient algorithm for finding a minimum cost flow.
deba@2440: 
deba@2440: #include <lemon/network_simplex.h>
deba@2440: 
deba@2440: namespace lemon {
deba@2440: 
deba@2440:   /// \addtogroup min_cost_flow
deba@2440:   /// @{
deba@2440: 
deba@2440:   /// \brief An efficient algorithm for finding a minimum cost flow.
deba@2440:   ///
deba@2440:   /// \ref lemon::MinCostFlow "MinCostFlow" implements an efficient
deba@2440:   /// algorithm for finding a minimum cost flow.
deba@2440:   ///
deba@2440:   /// \note \ref lemon::MinCostFlow "MinCostFlow" is just an alias for
deba@2440:   /// \ref lemon::NetworkSimplex "NetworkSimplex", wich is the most
deba@2440:   /// efficient implementation for the minimum cost flow problem in the
kpeter@2474:   /// LEMON library according to our benchmark tests.
deba@2440:   ///
deba@2440:   /// \note There are three implementations for the minimum cost flow
deba@2440:   /// problem, that can be used in the same way.
deba@2440:   /// - \ref lemon::CapacityScaling "CapacityScaling"
deba@2440:   /// - \ref lemon::CycleCanceling "CycleCanceling"
deba@2440:   /// - \ref lemon::NetworkSimplex "NetworkSimplex"
deba@2440:   ///
deba@2440:   /// \param Graph The directed graph type the algorithm runs on.
deba@2440:   /// \param LowerMap The type of the lower bound map.
deba@2440:   /// \param CapacityMap The type of the capacity (upper bound) map.
deba@2440:   /// \param CostMap The type of the cost (length) map.
deba@2440:   /// \param SupplyMap The type of the supply map.
deba@2440:   ///
deba@2440:   /// \warning
deba@2440:   /// - Edge capacities and costs should be nonnegative integers.
deba@2440:   ///	However \c CostMap::Value should be signed type.
kpeter@2509:   /// - Supply values should be signed integers.
deba@2440:   /// - \c LowerMap::Value must be convertible to
deba@2440:   ///	\c CapacityMap::Value and \c CapacityMap::Value must be
deba@2440:   ///	convertible to \c SupplyMap::Value.
deba@2440:   ///
deba@2440:   /// \author Peter Kovacs
deba@2440: 
kpeter@2533:   template < typename Graph,
kpeter@2533:              typename LowerMap = typename Graph::template EdgeMap<int>,
kpeter@2533:              typename CapacityMap = LowerMap,
kpeter@2533:              typename CostMap = typename Graph::template EdgeMap<int>,
kpeter@2533:              typename SupplyMap = typename Graph::template NodeMap
kpeter@2533:                                   <typename CapacityMap::Value> >
deba@2440:   class MinCostFlow :
deba@2440:     public NetworkSimplex< Graph,
deba@2440: 			   LowerMap,
deba@2440: 			   CapacityMap,
deba@2440: 			   CostMap,
deba@2440: 			   SupplyMap >
deba@2440:   {
deba@2440:     typedef NetworkSimplex< Graph, LowerMap, CapacityMap,
deba@2440: 			    CostMap, SupplyMap >
deba@2440:       MinCostFlowImpl;
deba@2440:     typedef typename Graph::Node Node;
deba@2440:     typedef typename SupplyMap::Value Supply;
deba@2440: 
deba@2440:   public:
deba@2440: 
deba@2440:     /// \brief General constructor of the class (with lower bounds).
deba@2440:     MinCostFlow( const Graph &_graph,
deba@2440: 		 const LowerMap &_lower,
deba@2440: 		 const CapacityMap &_capacity,
deba@2440: 		 const CostMap &_cost,
deba@2440: 		 const SupplyMap &_supply ) :
deba@2440:       MinCostFlowImpl(_graph, _lower, _capacity, _cost, _supply) {}
deba@2440: 
deba@2440:     /// \brief General constructor of the class (without lower bounds).
deba@2440:     MinCostFlow( const Graph &_graph,
deba@2440: 		 const CapacityMap &_capacity,
deba@2440: 		 const CostMap &_cost,
deba@2440: 		 const SupplyMap &_supply ) :
deba@2440:       MinCostFlowImpl(_graph, _capacity, _cost, _supply) {}
deba@2440: 
deba@2440:     /// \brief Simple constructor of the class (with lower bounds).
deba@2440:     MinCostFlow( const Graph &_graph,
deba@2440: 		 const LowerMap &_lower,
deba@2440: 		 const CapacityMap &_capacity,
deba@2440: 		 const CostMap &_cost,
deba@2440: 		 Node _s, Node _t,
deba@2440: 		 Supply _flow_value ) :
deba@2440:       MinCostFlowImpl( _graph, _lower, _capacity, _cost,
deba@2440: 		       _s, _t, _flow_value ) {}
deba@2440: 
deba@2440:     /// \brief Simple constructor of the class (without lower bounds).
deba@2440:     MinCostFlow( const Graph &_graph,
deba@2440: 		 const CapacityMap &_capacity,
deba@2440: 		 const CostMap &_cost,
deba@2440: 		 Node _s, Node _t,
deba@2440: 		 Supply _flow_value ) :
deba@2440:       MinCostFlowImpl( _graph, _capacity, _cost,
deba@2440: 		       _s, _t, _flow_value ) {}
deba@2440: 
deba@2440:   }; //class MinCostFlow
deba@2440: 
deba@2440:   ///@}
deba@2440: 
deba@2440: } //namespace lemon
deba@2440: 
deba@2440: #endif //LEMON_MIN_COST_FLOW_H