198 CostScaling( const Graph &graph, |
198 CostScaling( const Graph &graph, |
199 const LowerMap &lower, |
199 const LowerMap &lower, |
200 const CapacityMap &capacity, |
200 const CapacityMap &capacity, |
201 const CostMap &cost, |
201 const CostMap &cost, |
202 const SupplyMap &supply ) : |
202 const SupplyMap &supply ) : |
203 _graph(graph), _lower(&lower), _capacity(graph), _orig_cost(cost), |
203 _graph(graph), _lower(&lower), _capacity(capacity), _orig_cost(cost), |
204 _cost(graph), _supply(graph), _flow(NULL), _local_flow(false), |
204 _cost(graph), _supply(supply), _flow(NULL), _local_flow(false), |
205 _potential(NULL), _local_potential(false), _res_cost(_cost), |
205 _potential(NULL), _local_potential(false), _res_cost(_cost), |
206 _res_graph(NULL), _red_cost(NULL), _excess(graph, 0) |
206 _res_graph(NULL), _red_cost(NULL), _excess(graph, 0) |
207 { |
207 { |
|
208 // Check the sum of supply values |
|
209 Supply sum = 0; |
|
210 for (NodeIt n(_graph); n != INVALID; ++n) sum += _supply[n]; |
|
211 _valid_supply = sum == 0; |
|
212 |
208 // Remove non-zero lower bounds |
213 // Remove non-zero lower bounds |
209 _capacity = subMap(capacity, lower); |
214 for (EdgeIt e(_graph); e != INVALID; ++e) { |
210 Supply sum = 0; |
215 if (lower[e] != 0) { |
211 for (NodeIt n(_graph); n != INVALID; ++n) { |
216 _capacity[e] -= lower[e]; |
212 Supply s = supply[n]; |
217 _supply[_graph.source(e)] -= lower[e]; |
213 for (InEdgeIt e(_graph, n); e != INVALID; ++e) |
218 _supply[_graph.target(e)] += lower[e]; |
214 s += lower[e]; |
219 } |
215 for (OutEdgeIt e(_graph, n); e != INVALID; ++e) |
220 } |
216 s -= lower[e]; |
|
217 _supply[n] = s; |
|
218 sum += s; |
|
219 } |
|
220 _valid_supply = sum == 0; |
|
221 } |
221 } |
222 |
222 |
223 /// \brief General constructor (without lower bounds). |
223 /// \brief General constructor (without lower bounds). |
224 /// |
224 /// |
225 /// General constructor (without lower bounds). |
225 /// General constructor (without lower bounds). |
259 const LowerMap &lower, |
259 const LowerMap &lower, |
260 const CapacityMap &capacity, |
260 const CapacityMap &capacity, |
261 const CostMap &cost, |
261 const CostMap &cost, |
262 Node s, Node t, |
262 Node s, Node t, |
263 Supply flow_value ) : |
263 Supply flow_value ) : |
264 _graph(graph), _lower(&lower), _capacity(graph), _orig_cost(cost), |
264 _graph(graph), _lower(&lower), _capacity(capacity), _orig_cost(cost), |
265 _cost(graph), _supply(graph), _flow(NULL), _local_flow(false), |
265 _cost(graph), _supply(graph, 0), _flow(NULL), _local_flow(false), |
266 _potential(NULL), _local_potential(false), _res_cost(_cost), |
266 _potential(NULL), _local_potential(false), _res_cost(_cost), |
267 _res_graph(NULL), _red_cost(NULL), _excess(graph, 0) |
267 _res_graph(NULL), _red_cost(NULL), _excess(graph, 0) |
268 { |
268 { |
269 // Remove nonzero lower bounds |
269 // Remove non-zero lower bounds |
270 _capacity = subMap(capacity, lower); |
270 _supply[s] = flow_value; |
271 for (NodeIt n(_graph); n != INVALID; ++n) { |
271 _supply[t] = -flow_value; |
272 Supply sum = 0; |
272 for (EdgeIt e(_graph); e != INVALID; ++e) { |
273 if (n == s) sum = flow_value; |
273 if (lower[e] != 0) { |
274 if (n == t) sum = -flow_value; |
274 _capacity[e] -= lower[e]; |
275 for (InEdgeIt e(_graph, n); e != INVALID; ++e) |
275 _supply[_graph.source(e)] -= lower[e]; |
276 sum += lower[e]; |
276 _supply[_graph.target(e)] += lower[e]; |
277 for (OutEdgeIt e(_graph, n); e != INVALID; ++e) |
277 } |
278 sum -= lower[e]; |
|
279 _supply[n] = sum; |
|
280 } |
278 } |
281 _valid_supply = true; |
279 _valid_supply = true; |
282 } |
280 } |
283 |
281 |
284 /// \brief Simple constructor (without lower bounds). |
282 /// \brief Simple constructor (without lower bounds). |