253 const LowerMap &lower, |
253 const LowerMap &lower, |
254 const CapacityMap &capacity, |
254 const CapacityMap &capacity, |
255 const CostMap &cost, |
255 const CostMap &cost, |
256 const SupplyMap &supply ) : |
256 const SupplyMap &supply ) : |
257 _graph(graph), _lower(&lower), _capacity(graph), _cost(cost), |
257 _graph(graph), _lower(&lower), _capacity(graph), _cost(cost), |
258 _supply(graph), _flow(0), _local_flow(false), |
258 _supply(graph), _flow(NULL), _local_flow(false), |
259 _potential(0), _local_potential(false), |
259 _potential(NULL), _local_potential(false), |
260 _res_cap(graph), _excess(graph), _pred(graph) |
260 _res_cap(graph), _excess(graph), _pred(graph), _dijkstra(NULL) |
261 { |
261 { |
262 // Removing non-zero lower bounds |
262 // Removing non-zero lower bounds |
263 _capacity = subMap(capacity, lower); |
263 _capacity = subMap(capacity, lower); |
264 _res_cap = _capacity; |
264 _res_cap = _capacity; |
265 Supply sum = 0; |
265 Supply sum = 0; |
286 CapacityScaling( const Graph &graph, |
286 CapacityScaling( const Graph &graph, |
287 const CapacityMap &capacity, |
287 const CapacityMap &capacity, |
288 const CostMap &cost, |
288 const CostMap &cost, |
289 const SupplyMap &supply ) : |
289 const SupplyMap &supply ) : |
290 _graph(graph), _lower(NULL), _capacity(capacity), _cost(cost), |
290 _graph(graph), _lower(NULL), _capacity(capacity), _cost(cost), |
291 _supply(supply), _flow(0), _local_flow(false), |
291 _supply(supply), _flow(NULL), _local_flow(false), |
292 _potential(0), _local_potential(false), |
292 _potential(NULL), _local_potential(false), |
293 _res_cap(capacity), _excess(graph), _pred(graph) |
293 _res_cap(capacity), _excess(graph), _pred(graph), _dijkstra(NULL) |
294 { |
294 { |
295 // Checking the sum of supply values |
295 // Checking the sum of supply values |
296 Supply sum = 0; |
296 Supply sum = 0; |
297 for (NodeIt n(_graph); n != INVALID; ++n) sum += _supply[n]; |
297 for (NodeIt n(_graph); n != INVALID; ++n) sum += _supply[n]; |
298 _valid_supply = sum == 0; |
298 _valid_supply = sum == 0; |
315 const CapacityMap &capacity, |
315 const CapacityMap &capacity, |
316 const CostMap &cost, |
316 const CostMap &cost, |
317 Node s, Node t, |
317 Node s, Node t, |
318 Supply flow_value ) : |
318 Supply flow_value ) : |
319 _graph(graph), _lower(&lower), _capacity(graph), _cost(cost), |
319 _graph(graph), _lower(&lower), _capacity(graph), _cost(cost), |
320 _supply(graph), _flow(0), _local_flow(false), |
320 _supply(graph), _flow(NULL), _local_flow(false), |
321 _potential(0), _local_potential(false), |
321 _potential(NULL), _local_potential(false), |
322 _res_cap(graph), _excess(graph), _pred(graph) |
322 _res_cap(graph), _excess(graph), _pred(graph), _dijkstra(NULL) |
323 { |
323 { |
324 // Removing non-zero lower bounds |
324 // Removing non-zero lower bounds |
325 _capacity = subMap(capacity, lower); |
325 _capacity = subMap(capacity, lower); |
326 _res_cap = _capacity; |
326 _res_cap = _capacity; |
327 for (NodeIt n(_graph); n != INVALID; ++n) { |
327 for (NodeIt n(_graph); n != INVALID; ++n) { |
352 const CapacityMap &capacity, |
352 const CapacityMap &capacity, |
353 const CostMap &cost, |
353 const CostMap &cost, |
354 Node s, Node t, |
354 Node s, Node t, |
355 Supply flow_value ) : |
355 Supply flow_value ) : |
356 _graph(graph), _lower(NULL), _capacity(capacity), _cost(cost), |
356 _graph(graph), _lower(NULL), _capacity(capacity), _cost(cost), |
357 _supply(graph, 0), _flow(0), _local_flow(false), |
357 _supply(graph, 0), _flow(NULL), _local_flow(false), |
358 _potential(0), _local_potential(false), |
358 _potential(NULL), _local_potential(false), |
359 _res_cap(capacity), _excess(graph), _pred(graph) |
359 _res_cap(capacity), _excess(graph), _pred(graph), _dijkstra(NULL) |
360 { |
360 { |
361 _supply[s] = flow_value; |
361 _supply[s] = flow_value; |
362 _supply[t] = -flow_value; |
362 _supply[t] = -flow_value; |
363 _valid_supply = true; |
363 _valid_supply = true; |
364 } |
364 } |