Changeset 2629:84354c78b068 in lemon-0.x for lemon/cycle_canceling.h
- Timestamp:
- 11/13/08 16:29:04 (16 years ago)
- Branch:
- default
- Phase:
- public
- Convert:
- svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@3514
- File:
-
- 1 edited
Legend:
- Unmodified
- Added
- Removed
-
lemon/cycle_canceling.h
r2623 r2629 168 168 const CostMap &cost, 169 169 const SupplyMap &supply ) : 170 _graph(graph), _lower(&lower), _capacity( graph), _cost(cost),171 _supply( graph), _flow(NULL), _local_flow(false),170 _graph(graph), _lower(&lower), _capacity(capacity), _cost(cost), 171 _supply(supply), _flow(NULL), _local_flow(false), 172 172 _potential(NULL), _local_potential(false), _res_graph(NULL), 173 173 _res_cost(_cost) 174 174 { 175 // Removing non-zero lower bounds 176 _capacity = subMap(capacity, lower); 175 // Check the sum of supply values 177 176 Supply sum = 0; 178 for (NodeIt n(_graph); n != INVALID; ++n) { 179 Supply s = supply[n]; 180 for (InEdgeIt e(_graph, n); e != INVALID; ++e) 181 s += lower[e]; 182 for (OutEdgeIt e(_graph, n); e != INVALID; ++e) 183 s -= lower[e]; 184 sum += (_supply[n] = s); 185 } 177 for (NodeIt n(_graph); n != INVALID; ++n) sum += _supply[n]; 186 178 _valid_supply = sum == 0; 179 180 // Remove non-zero lower bounds 181 for (EdgeIt e(_graph); e != INVALID; ++e) { 182 if (lower[e] != 0) { 183 _capacity[e] -= lower[e]; 184 _supply[_graph.source(e)] -= lower[e]; 185 _supply[_graph.target(e)] += lower[e]; 186 } 187 } 187 188 } 188 189 … … 204 205 _res_cost(_cost) 205 206 { 206 // Check ingthe sum of supply values207 // Check the sum of supply values 207 208 Supply sum = 0; 208 209 for (NodeIt n(_graph); n != INVALID; ++n) sum += _supply[n]; … … 228 229 Node s, Node t, 229 230 Supply flow_value ) : 230 _graph(graph), _lower(&lower), _capacity( graph), _cost(cost),231 _supply(graph ), _flow(NULL), _local_flow(false),231 _graph(graph), _lower(&lower), _capacity(capacity), _cost(cost), 232 _supply(graph, 0), _flow(NULL), _local_flow(false), 232 233 _potential(NULL), _local_potential(false), _res_graph(NULL), 233 234 _res_cost(_cost) 234 235 { 235 // Removing non-zero lower bounds 236 _capacity = subMap(capacity, lower); 237 for (NodeIt n(_graph); n != INVALID; ++n) { 238 Supply sum = 0; 239 if (n == s) sum = flow_value; 240 if (n == t) sum = -flow_value; 241 for (InEdgeIt e(_graph, n); e != INVALID; ++e) 242 sum += lower[e]; 243 for (OutEdgeIt e(_graph, n); e != INVALID; ++e) 244 sum -= lower[e]; 245 _supply[n] = sum; 236 // Remove non-zero lower bounds 237 _supply[s] = flow_value; 238 _supply[t] = -flow_value; 239 for (EdgeIt e(_graph); e != INVALID; ++e) { 240 if (lower[e] != 0) { 241 _capacity[e] -= lower[e]; 242 _supply[_graph.source(e)] -= lower[e]; 243 _supply[_graph.target(e)] += lower[e]; 244 } 246 245 } 247 246 _valid_supply = true;
Note: See TracChangeset
for help on using the changeset viewer.