20 #define LEMON_MIN_COST_MAX_FLOW_H |
20 #define LEMON_MIN_COST_MAX_FLOW_H |
21 |
21 |
22 /// \ingroup min_cost_flow |
22 /// \ingroup min_cost_flow |
23 /// |
23 /// |
24 /// \file |
24 /// \file |
25 /// \brief An efficient algorithm for finding a minimum cost maximum |
25 /// \brief An efficient algorithm for finding a minimum cost maximum flow. |
26 /// flow. |
|
27 |
26 |
28 #include <lemon/preflow.h> |
27 #include <lemon/preflow.h> |
29 #include <lemon/network_simplex.h> |
28 #include <lemon/network_simplex.h> |
30 #include <lemon/maps.h> |
29 #include <lemon/maps.h> |
31 |
30 |
32 namespace lemon { |
31 namespace lemon { |
33 |
32 |
34 /// \addtogroup min_cost_flow |
33 /// \addtogroup min_cost_flow |
35 /// @{ |
34 /// @{ |
36 |
35 |
37 /// \brief An efficient algorithm for finding a minimum cost maximum |
36 /// \brief An efficient algorithm for finding a minimum cost |
38 /// flow. |
37 /// maximum flow. |
39 /// |
38 /// |
40 /// \ref lemon::MinCostFlow "MinCostMaxFlow" implements an efficient |
39 /// \ref MinCostMaxFlow implements an efficient algorithm for |
41 /// algorithm for finding a maximum flow having minimal total cost |
40 /// finding a maximum flow having minimal total cost from a given |
42 /// from a given source node to a given target node in a directed |
41 /// source node to a given target node in a directed graph. |
43 /// graph. |
|
44 /// |
42 /// |
45 /// \note \ref lemon::MinCostMaxFlow "MinCostMaxFlow" uses |
43 /// \note \ref MinCostMaxFlow uses \ref Preflow algorithm for finding |
46 /// \ref lemon::Preflow "Preflow" algorithm for finding the maximum |
44 /// the maximum flow value and \ref NetworkSimplex algorithm for |
47 /// flow value and \ref lemon::NetworkSimplex "NetworkSimplex" |
45 /// finding a minimum cost flow of that value. |
48 /// algorithm for finding a minimum cost flow of that value. |
|
49 /// |
46 /// |
50 /// \param Graph The directed graph type the algorithm runs on. |
47 /// \param Graph The directed graph type the algorithm runs on. |
51 /// \param CapacityMap The type of the capacity (upper bound) map. |
48 /// \param CapacityMap The type of the capacity (upper bound) map. |
52 /// \param CostMap The type of the cost (length) map. |
49 /// \param CostMap The type of the cost (length) map. |
53 /// |
50 /// |
54 /// \warning |
51 /// \warning |
55 /// - Edge capacities and costs should be nonnegative integers. |
52 /// - Edge capacities and costs should be non-negative integers. |
56 /// However \c CostMap::Value should be signed type. |
53 /// However \c CostMap::Value should be signed type. |
57 /// |
54 /// |
58 /// \author Peter Kovacs |
55 /// \author Peter Kovacs |
59 |
56 |
60 template < typename Graph, |
57 template < typename Graph, |
61 typename CapacityMap = typename Graph::template EdgeMap<int>, |
58 typename CapacityMap = typename Graph::template EdgeMap<int>, |
62 typename CostMap = typename Graph::template EdgeMap<int> > |
59 typename CostMap = typename Graph::template EdgeMap<int> > |
63 class MinCostMaxFlow |
60 class MinCostMaxFlow |
64 { |
61 { |
65 typedef typename Graph::Node Node; |
62 typedef typename Graph::Node Node; |
66 typedef typename Graph::Edge Edge; |
63 typedef typename Graph::Edge Edge; |
67 |
64 |
68 typedef typename CapacityMap::Value Capacity; |
65 typedef typename CapacityMap::Value Capacity; |
|
66 typedef typename CostMap::Value Cost; |
69 typedef typename Graph::template NodeMap<Capacity> SupplyMap; |
67 typedef typename Graph::template NodeMap<Capacity> SupplyMap; |
70 typedef NetworkSimplex< Graph, CapacityMap, CapacityMap, |
68 typedef NetworkSimplex< Graph, CapacityMap, CapacityMap, |
71 CostMap, SupplyMap > |
69 CostMap, SupplyMap > |
72 MinCostFlowImpl; |
70 MinCostFlowImpl; |
73 |
71 |
74 public: |
72 public: |
75 |
73 |
76 /// \brief The type of the flow map. |
74 /// The type of the flow map. |
77 typedef typename Graph::template EdgeMap<Capacity> FlowMap; |
75 typedef typename Graph::template EdgeMap<Capacity> FlowMap; |
78 typedef typename CostMap::Value Cost; |
|
79 |
76 |
80 private: |
77 private: |
81 |
78 |
82 /// \brief The directed graph the algorithm runs on. |
79 /// The directed graph the algorithm runs on. |
83 const Graph &graph; |
80 const Graph &graph; |
84 /// \brief The modified capacity map. |
81 /// The modified capacity map. |
85 const CapacityMap &capacity; |
82 const CapacityMap &capacity; |
86 /// \brief The cost map. |
83 /// The cost map. |
87 const CostMap &cost; |
84 const CostMap &cost; |
88 /// \brief The source node. |
85 /// The edge map of the found flow. |
|
86 FlowMap flow; |
|
87 /// The source node. |
89 Node source; |
88 Node source; |
90 /// \brief The target node. |
89 /// The target node. |
91 Node target; |
90 Node target; |
92 /// \brief The edge map of the found flow. |
|
93 FlowMap flow; |
|
94 |
91 |
95 typedef Preflow<Graph, CapacityMap> PreflowImpl; |
92 typedef Preflow<Graph, CapacityMap> MaxFlowImpl; |
96 /// \brief \ref lemon::Preflow "Preflow" class for finding the |
93 /// \brief \ref Preflow class for finding the maximum flow value. |
97 /// maximum flow value. |
94 MaxFlowImpl preflow; |
98 PreflowImpl preflow; |
|
99 |
95 |
100 public: |
96 public: |
101 |
97 |
102 /// \brief The constructor of the class. |
98 /// \brief The constructor of the class. |
103 /// |
99 /// |
107 /// \param _capacity The capacities (upper bounds) of the edges. |
103 /// \param _capacity The capacities (upper bounds) of the edges. |
108 /// \param _cost The cost (length) values of the edges. |
104 /// \param _cost The cost (length) values of the edges. |
109 /// \param _s The source node. |
105 /// \param _s The source node. |
110 /// \param _t The target node. |
106 /// \param _t The target node. |
111 MinCostMaxFlow( const Graph &_graph, |
107 MinCostMaxFlow( const Graph &_graph, |
112 const CapacityMap &_capacity, |
108 const CapacityMap &_capacity, |
113 const CostMap &_cost, |
109 const CostMap &_cost, |
114 Node _s, Node _t ) : |
110 Node _s, Node _t ) : |
115 graph(_graph), capacity(_capacity), cost(_cost), |
111 graph(_graph), capacity(_capacity), cost(_cost), |
116 source(_s), target(_t), flow(_graph), |
112 source(_s), target(_t), flow(_graph), |
117 preflow(_graph, _capacity, _s, _t) |
113 preflow(_graph, _capacity, _s, _t) |
118 {} |
114 {} |
119 |
115 |
133 /// |
129 /// |
134 /// \pre \ref run() must be called before using this function. |
130 /// \pre \ref run() must be called before using this function. |
135 Cost totalCost() const { |
131 Cost totalCost() const { |
136 Cost c = 0; |
132 Cost c = 0; |
137 for (typename Graph::EdgeIt e(graph); e != INVALID; ++e) |
133 for (typename Graph::EdgeIt e(graph); e != INVALID; ++e) |
138 c += flow[e] * cost[e]; |
134 c += flow[e] * cost[e]; |
139 return c; |
135 return c; |
140 } |
136 } |
141 |
137 |
142 /// \brief Runs the algorithm. |
138 /// \brief Runs the algorithm. |
143 void run() { |
139 void run() { |
144 preflow.flowMap(flow); |
140 preflow.flowMap(flow); |
145 preflow.runMinCut(); |
141 preflow.runMinCut(); |
146 MinCostFlowImpl mcf_impl( graph, capacity, cost, |
142 MinCostFlowImpl mcf_impl( graph, capacity, cost, |
147 source, target, preflow.flowValue() ); |
143 source, target, preflow.flowValue() ); |
148 mcf_impl.run(); |
144 mcf_impl.run(); |
149 flow = mcf_impl.flowMap(); |
145 flow = mcf_impl.flowMap(); |
150 } |
146 } |
151 |
147 |
152 }; //class MinCostMaxFlow |
148 }; //class MinCostMaxFlow |