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