Changeset 2629:84354c78b068 in lemon-0.x for lemon/cost_scaling.h
- Timestamp:
- 11/13/08 16:29:04 (17 years ago)
- Branch:
- default
- Phase:
- public
- Convert:
- svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@3514
- File:
-
- 1 edited
Legend:
- Unmodified
- Added
- Removed
-
lemon/cost_scaling.h
r2625 r2629 201 201 const CostMap &cost, 202 202 const SupplyMap &supply ) : 203 _graph(graph), _lower(&lower), _capacity( graph), _orig_cost(cost),204 _cost(graph), _supply( graph), _flow(NULL), _local_flow(false),203 _graph(graph), _lower(&lower), _capacity(capacity), _orig_cost(cost), 204 _cost(graph), _supply(supply), _flow(NULL), _local_flow(false), 205 205 _potential(NULL), _local_potential(false), _res_cost(_cost), 206 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 213 // Remove non-zero lower bounds 209 _capacity = subMap(capacity, lower); 210 Supply sum = 0; 211 for (NodeIt n(_graph); n != INVALID; ++n) { 212 Supply s = supply[n]; 213 for (InEdgeIt e(_graph, n); e != INVALID; ++e) 214 s += lower[e]; 215 for (OutEdgeIt e(_graph, n); e != INVALID; ++e) 216 s -= lower[e]; 217 _supply[n] = s; 218 sum += s; 219 } 220 _valid_supply = sum == 0; 214 for (EdgeIt e(_graph); e != INVALID; ++e) { 215 if (lower[e] != 0) { 216 _capacity[e] -= lower[e]; 217 _supply[_graph.source(e)] -= lower[e]; 218 _supply[_graph.target(e)] += lower[e]; 219 } 220 } 221 221 } 222 222 … … 262 262 Node s, Node t, 263 263 Supply flow_value ) : 264 _graph(graph), _lower(&lower), _capacity( graph), _orig_cost(cost),265 _cost(graph), _supply(graph ), _flow(NULL), _local_flow(false),264 _graph(graph), _lower(&lower), _capacity(capacity), _orig_cost(cost), 265 _cost(graph), _supply(graph, 0), _flow(NULL), _local_flow(false), 266 266 _potential(NULL), _local_potential(false), _res_cost(_cost), 267 267 _res_graph(NULL), _red_cost(NULL), _excess(graph, 0) 268 268 { 269 // Remove nonzero lower bounds 270 _capacity = subMap(capacity, lower); 271 for (NodeIt n(_graph); n != INVALID; ++n) { 272 Supply sum = 0; 273 if (n == s) sum = flow_value; 274 if (n == t) sum = -flow_value; 275 for (InEdgeIt e(_graph, n); e != INVALID; ++e) 276 sum += lower[e]; 277 for (OutEdgeIt e(_graph, n); e != INVALID; ++e) 278 sum -= lower[e]; 279 _supply[n] = sum; 269 // Remove non-zero lower bounds 270 _supply[s] = flow_value; 271 _supply[t] = -flow_value; 272 for (EdgeIt e(_graph); e != INVALID; ++e) { 273 if (lower[e] != 0) { 274 _capacity[e] -= lower[e]; 275 _supply[_graph.source(e)] -= lower[e]; 276 _supply[_graph.target(e)] += lower[e]; 277 } 280 278 } 281 279 _valid_supply = true;
Note: See TracChangeset
for help on using the changeset viewer.