Changeset 2629:84354c78b068 in lemon-0.x for lemon/capacity_scaling.h
- Timestamp:
- 11/13/08 16:29:04 (15 years ago)
- Branch:
- default
- Phase:
- public
- Convert:
- svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@3514
- File:
-
- 1 edited
Legend:
- Unmodified
- Added
- Removed
-
lemon/capacity_scaling.h
r2623 r2629 255 255 const CostMap &cost, 256 256 const SupplyMap &supply ) : 257 _graph(graph), _lower(&lower), _capacity( graph), _cost(cost),258 _supply( graph), _flow(NULL), _local_flow(false),257 _graph(graph), _lower(&lower), _capacity(capacity), _cost(cost), 258 _supply(supply), _flow(NULL), _local_flow(false), 259 259 _potential(NULL), _local_potential(false), 260 _res_cap( graph), _excess(graph), _pred(graph), _dijkstra(NULL)260 _res_cap(capacity), _excess(supply), _pred(graph), _dijkstra(NULL) 261 261 { 262 // Removing non-zero lower bounds 263 _capacity = subMap(capacity, lower); 264 _res_cap = _capacity; 262 // Check the sum of supply values 265 263 Supply sum = 0; 266 for (NodeIt n(_graph); n != INVALID; ++n) { 267 Supply s = supply[n]; 268 for (InEdgeIt e(_graph, n); e != INVALID; ++e) 269 s += lower[e]; 270 for (OutEdgeIt e(_graph, n); e != INVALID; ++e) 271 s -= lower[e]; 272 _supply[n] = s; 273 sum += s; 274 } 264 for (NodeIt n(_graph); n != INVALID; ++n) sum += _supply[n]; 275 265 _valid_supply = sum == 0; 266 267 // Remove non-zero lower bounds 268 typename LowerMap::Value lcap; 269 for (EdgeIt e(_graph); e != INVALID; ++e) { 270 if ((lcap = lower[e]) != 0) { 271 _capacity[e] -= lcap; 272 _res_cap[e] -= lcap; 273 _supply[_graph.source(e)] -= lcap; 274 _supply[_graph.target(e)] += lcap; 275 _excess[_graph.source(e)] -= lcap; 276 _excess[_graph.target(e)] += lcap; 277 } 278 } 276 279 } 277 280 … … 291 294 _supply(supply), _flow(NULL), _local_flow(false), 292 295 _potential(NULL), _local_potential(false), 293 _res_cap(capacity), _excess( graph), _pred(graph), _dijkstra(NULL)296 _res_cap(capacity), _excess(supply), _pred(graph), _dijkstra(NULL) 294 297 { 295 // Check ingthe sum of supply values298 // Check the sum of supply values 296 299 Supply sum = 0; 297 300 for (NodeIt n(_graph); n != INVALID; ++n) sum += _supply[n]; … … 317 320 Node s, Node t, 318 321 Supply flow_value ) : 319 _graph(graph), _lower(&lower), _capacity( graph), _cost(cost),320 _supply(graph ), _flow(NULL), _local_flow(false),322 _graph(graph), _lower(&lower), _capacity(capacity), _cost(cost), 323 _supply(graph, 0), _flow(NULL), _local_flow(false), 321 324 _potential(NULL), _local_potential(false), 322 _res_cap( graph), _excess(graph), _pred(graph), _dijkstra(NULL)325 _res_cap(capacity), _excess(graph, 0), _pred(graph), _dijkstra(NULL) 323 326 { 324 // Removing non-zero lower bounds 325 _capacity = subMap(capacity, lower); 326 _res_cap = _capacity; 327 for (NodeIt n(_graph); n != INVALID; ++n) { 328 Supply sum = 0; 329 if (n == s) sum = flow_value; 330 if (n == t) sum = -flow_value; 331 for (InEdgeIt e(_graph, n); e != INVALID; ++e) 332 sum += lower[e]; 333 for (OutEdgeIt e(_graph, n); e != INVALID; ++e) 334 sum -= lower[e]; 335 _supply[n] = sum; 327 // Remove non-zero lower bounds 328 _supply[s] = _excess[s] = flow_value; 329 _supply[t] = _excess[t] = -flow_value; 330 typename LowerMap::Value lcap; 331 for (EdgeIt e(_graph); e != INVALID; ++e) { 332 if ((lcap = lower[e]) != 0) { 333 _capacity[e] -= lcap; 334 _res_cap[e] -= lcap; 335 _supply[_graph.source(e)] -= lcap; 336 _supply[_graph.target(e)] += lcap; 337 _excess[_graph.source(e)] -= lcap; 338 _excess[_graph.target(e)] += lcap; 339 } 336 340 } 337 341 _valid_supply = true; … … 357 361 _supply(graph, 0), _flow(NULL), _local_flow(false), 358 362 _potential(NULL), _local_potential(false), 359 _res_cap(capacity), _excess(graph ), _pred(graph), _dijkstra(NULL)363 _res_cap(capacity), _excess(graph, 0), _pred(graph), _dijkstra(NULL) 360 364 { 361 _supply[s] = flow_value;362 _supply[t] = -flow_value;365 _supply[s] = _excess[s] = flow_value; 366 _supply[t] = _excess[t] = -flow_value; 363 367 _valid_supply = true; 364 368 } … … 498 502 for (EdgeIt e(_graph); e != INVALID; ++e) (*_flow)[e] = 0; 499 503 for (NodeIt n(_graph); n != INVALID; ++n) (*_potential)[n] = 0; 500 _excess = _supply;501 504 502 505 _dijkstra = new ResidualDijkstra( _graph, *_flow, _res_cap, _cost,
Note: See TracChangeset
for help on using the changeset viewer.