3 * This file is a part of LEMON, a generic C++ optimization library
5 * Copyright (C) 2003-2007
6 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
7 * (Egervary Research Group on Combinatorial Optimization, EGRES).
9 * Permission to use, modify and distribute this software is granted
10 * provided that this copyright notice appears in all copies. For
11 * precise terms see the accompanying LICENSE file.
13 * This software is provided "AS IS" with no warranty of any kind,
14 * express or implied, and with no claim as to its suitability for any
19 #ifndef LEMON_MIN_COST_FLOW_H
20 #define LEMON_MIN_COST_FLOW_H
22 /// \ingroup min_cost_flow
25 /// \brief An efficient algorithm for finding a minimum cost flow.
27 #include <lemon/network_simplex.h>
31 /// \addtogroup min_cost_flow
34 /// \brief An efficient algorithm for finding a minimum cost flow.
36 /// \ref lemon::MinCostFlow "MinCostFlow" implements an efficient
37 /// algorithm for finding a minimum cost flow.
39 /// \note \ref lemon::MinCostFlow "MinCostFlow" is just an alias for
40 /// \ref lemon::NetworkSimplex "NetworkSimplex", wich is the most
41 /// efficient implementation for the minimum cost flow problem in the
42 /// LEMON library according to our benchmark tests.
44 /// \note There are three implementations for the minimum cost flow
45 /// problem, that can be used in the same way.
46 /// - \ref lemon::CapacityScaling "CapacityScaling"
47 /// - \ref lemon::CycleCanceling "CycleCanceling"
48 /// - \ref lemon::NetworkSimplex "NetworkSimplex"
50 /// \param Graph The directed graph type the algorithm runs on.
51 /// \param LowerMap The type of the lower bound map.
52 /// \param CapacityMap The type of the capacity (upper bound) map.
53 /// \param CostMap The type of the cost (length) map.
54 /// \param SupplyMap The type of the supply map.
57 /// - Edge capacities and costs should be nonnegative integers.
58 /// However \c CostMap::Value should be signed type.
59 /// - Supply values should be signed integers.
60 /// - \c LowerMap::Value must be convertible to
61 /// \c CapacityMap::Value and \c CapacityMap::Value must be
62 /// convertible to \c SupplyMap::Value.
64 /// \author Peter Kovacs
66 template < typename Graph,
67 typename LowerMap = typename Graph::template EdgeMap<int>,
68 typename CapacityMap = LowerMap,
69 typename CostMap = typename Graph::template EdgeMap<int>,
70 typename SupplyMap = typename Graph::template NodeMap
71 <typename CapacityMap::Value> >
73 public NetworkSimplex< Graph,
79 typedef NetworkSimplex< Graph, LowerMap, CapacityMap,
82 typedef typename Graph::Node Node;
83 typedef typename SupplyMap::Value Supply;
87 /// \brief General constructor of the class (with lower bounds).
88 MinCostFlow( const Graph &_graph,
89 const LowerMap &_lower,
90 const CapacityMap &_capacity,
92 const SupplyMap &_supply ) :
93 MinCostFlowImpl(_graph, _lower, _capacity, _cost, _supply) {}
95 /// \brief General constructor of the class (without lower bounds).
96 MinCostFlow( const Graph &_graph,
97 const CapacityMap &_capacity,
99 const SupplyMap &_supply ) :
100 MinCostFlowImpl(_graph, _capacity, _cost, _supply) {}
102 /// \brief Simple constructor of the class (with lower bounds).
103 MinCostFlow( const Graph &_graph,
104 const LowerMap &_lower,
105 const CapacityMap &_capacity,
106 const CostMap &_cost,
108 Supply _flow_value ) :
109 MinCostFlowImpl( _graph, _lower, _capacity, _cost,
110 _s, _t, _flow_value ) {}
112 /// \brief Simple constructor of the class (without lower bounds).
113 MinCostFlow( const Graph &_graph,
114 const CapacityMap &_capacity,
115 const CostMap &_cost,
117 Supply _flow_value ) :
118 MinCostFlowImpl( _graph, _capacity, _cost,
119 _s, _t, _flow_value ) {}
121 }; //class MinCostFlow
127 #endif //LEMON_MIN_COST_FLOW_H