deba@2440: /* -*- C++ -*-
deba@2440:  *
deba@2440:  * This file is a part of LEMON, a generic C++ optimization library
deba@2440:  *
alpar@2553:  * Copyright (C) 2003-2008
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:   ///
kpeter@2556:   /// \ref MinCostFlow provides an efficient algorithm for finding
kpeter@2556:   /// a minimum cost flow.
deba@2440:   ///
kpeter@2576:   /// This class is just an alias for \ref NetworkSimplex,
kpeter@2576:   /// which is the most efficient algorithm for the minimum cost
kpeter@2576:   /// flow problem in LEMON according to our benchmark tests.
kpeter@2576:   /// For the detailed documentation of this class see
kpeter@2556:   /// \ref NetworkSimplex.
deba@2440:   ///
kpeter@2576:   /// There are four implementations for the minimum cost flow problem,
kpeter@2581:   /// which can be used exactly the same way.
kpeter@2588:   /// - \ref CapacityScaling
kpeter@2588:   /// - \ref CostScaling
kpeter@2588:   /// - \ref CycleCanceling
kpeter@2588:   /// - \ref NetworkSimplex
kpeter@2576:   ///
kpeter@2576:   /// \tparam Graph The directed graph type the algorithm runs on.
kpeter@2576:   /// \tparam LowerMap The type of the lower bound map.
kpeter@2576:   /// \tparam CapacityMap The type of the capacity (upper bound) map.
kpeter@2576:   /// \tparam CostMap The type of the cost (length) map.
kpeter@2576:   /// \tparam SupplyMap The type of the supply map.
deba@2440:   ///
deba@2440:   /// \warning
kpeter@2576:   /// - Edge capacities and costs should be \e non-negative \e integers.
kpeter@2576:   /// - Supply values should be \e signed \e integers.
kpeter@2581:   /// - The value types of the maps should be convertible to each other.
kpeter@2581:   /// - \c CostMap::Value must be signed type.
deba@2440:   ///
deba@2440:   /// \author Peter Kovacs
deba@2440: 
kpeter@2533:   template < typename Graph,
kpeter@2533:              typename LowerMap = typename Graph::template EdgeMap<int>,
kpeter@2581:              typename CapacityMap = typename Graph::template EdgeMap<int>,
kpeter@2533:              typename CostMap = typename Graph::template EdgeMap<int>,
kpeter@2581:              typename SupplyMap = typename Graph::template NodeMap<int> >
deba@2440:   class MinCostFlow :
kpeter@2556:     public NetworkSimplex< Graph, LowerMap, CapacityMap,
kpeter@2556:                            CostMap, SupplyMap >
deba@2440:   {
deba@2440:     typedef NetworkSimplex< Graph, LowerMap, CapacityMap,
kpeter@2556:                             CostMap, SupplyMap > MinCostFlowImpl;
deba@2440:     typedef typename Graph::Node Node;
deba@2440:     typedef typename SupplyMap::Value Supply;
deba@2440: 
deba@2440:   public:
deba@2440: 
kpeter@2581:     /// General constructor (with lower bounds).
kpeter@2556:     MinCostFlow( const Graph &graph,
kpeter@2556:                  const LowerMap &lower,
kpeter@2556:                  const CapacityMap &capacity,
kpeter@2556:                  const CostMap &cost,
kpeter@2556:                  const SupplyMap &supply ) :
kpeter@2556:       MinCostFlowImpl(graph, lower, capacity, cost, supply) {}
deba@2440: 
kpeter@2556:     /// General constructor of the class (without lower bounds).
kpeter@2556:     MinCostFlow( const Graph &graph,
kpeter@2556:                  const CapacityMap &capacity,
kpeter@2579:                  const CostMap &cost,
kpeter@2556:                  const SupplyMap &supply ) :
kpeter@2556:       MinCostFlowImpl(graph, capacity, cost, supply) {}
deba@2440: 
kpeter@2581:     /// Simple constructor (with lower bounds).
kpeter@2556:     MinCostFlow( const Graph &graph,
kpeter@2556:                  const LowerMap &lower,
kpeter@2556:                  const CapacityMap &capacity,
kpeter@2579:                  const CostMap &cost,
kpeter@2556:                  Node s, Node t,
kpeter@2556:                  Supply flow_value ) :
kpeter@2556:       MinCostFlowImpl( graph, lower, capacity, cost,
kpeter@2556:                        s, t, flow_value ) {}
deba@2440: 
kpeter@2581:     /// Simple constructor (without lower bounds).
kpeter@2556:     MinCostFlow( const Graph &graph,
kpeter@2556:                  const CapacityMap &capacity,
kpeter@2556:                  const CostMap &cost,
kpeter@2556:                  Node s, Node t,
kpeter@2556:                  Supply flow_value ) :
kpeter@2556:       MinCostFlowImpl( graph, capacity, cost,
kpeter@2556:                        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