165 CycleCanceling( const Graph &graph, |
165 CycleCanceling( const Graph &graph, |
166 const LowerMap &lower, |
166 const LowerMap &lower, |
167 const CapacityMap &capacity, |
167 const CapacityMap &capacity, |
168 const CostMap &cost, |
168 const CostMap &cost, |
169 const SupplyMap &supply ) : |
169 const SupplyMap &supply ) : |
170 _graph(graph), _lower(&lower), _capacity(graph), _cost(cost), |
170 _graph(graph), _lower(&lower), _capacity(capacity), _cost(cost), |
171 _supply(graph), _flow(NULL), _local_flow(false), |
171 _supply(supply), _flow(NULL), _local_flow(false), |
172 _potential(NULL), _local_potential(false), _res_graph(NULL), |
172 _potential(NULL), _local_potential(false), _res_graph(NULL), |
173 _res_cost(_cost) |
173 _res_cost(_cost) |
174 { |
174 { |
175 // Removing non-zero lower bounds |
175 // Check the sum of supply values |
176 _capacity = subMap(capacity, lower); |
|
177 Supply sum = 0; |
176 Supply sum = 0; |
178 for (NodeIt n(_graph); n != INVALID; ++n) { |
177 for (NodeIt n(_graph); n != INVALID; ++n) sum += _supply[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 } |
|
186 _valid_supply = sum == 0; |
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 |
189 /// \brief General constructor (without lower bounds). |
190 /// \brief General constructor (without lower bounds). |
190 /// |
191 /// |
191 /// General constructor (without lower bounds). |
192 /// General constructor (without lower bounds). |
201 _graph(graph), _lower(NULL), _capacity(capacity), _cost(cost), |
202 _graph(graph), _lower(NULL), _capacity(capacity), _cost(cost), |
202 _supply(supply), _flow(NULL), _local_flow(false), |
203 _supply(supply), _flow(NULL), _local_flow(false), |
203 _potential(NULL), _local_potential(false), _res_graph(NULL), |
204 _potential(NULL), _local_potential(false), _res_graph(NULL), |
204 _res_cost(_cost) |
205 _res_cost(_cost) |
205 { |
206 { |
206 // Checking the sum of supply values |
207 // Check the sum of supply values |
207 Supply sum = 0; |
208 Supply sum = 0; |
208 for (NodeIt n(_graph); n != INVALID; ++n) sum += _supply[n]; |
209 for (NodeIt n(_graph); n != INVALID; ++n) sum += _supply[n]; |
209 _valid_supply = sum == 0; |
210 _valid_supply = sum == 0; |
210 } |
211 } |
211 |
212 |
225 const LowerMap &lower, |
226 const LowerMap &lower, |
226 const CapacityMap &capacity, |
227 const CapacityMap &capacity, |
227 const CostMap &cost, |
228 const CostMap &cost, |
228 Node s, Node t, |
229 Node s, Node t, |
229 Supply flow_value ) : |
230 Supply flow_value ) : |
230 _graph(graph), _lower(&lower), _capacity(graph), _cost(cost), |
231 _graph(graph), _lower(&lower), _capacity(capacity), _cost(cost), |
231 _supply(graph), _flow(NULL), _local_flow(false), |
232 _supply(graph, 0), _flow(NULL), _local_flow(false), |
232 _potential(NULL), _local_potential(false), _res_graph(NULL), |
233 _potential(NULL), _local_potential(false), _res_graph(NULL), |
233 _res_cost(_cost) |
234 _res_cost(_cost) |
234 { |
235 { |
235 // Removing non-zero lower bounds |
236 // Remove non-zero lower bounds |
236 _capacity = subMap(capacity, lower); |
237 _supply[s] = flow_value; |
237 for (NodeIt n(_graph); n != INVALID; ++n) { |
238 _supply[t] = -flow_value; |
238 Supply sum = 0; |
239 for (EdgeIt e(_graph); e != INVALID; ++e) { |
239 if (n == s) sum = flow_value; |
240 if (lower[e] != 0) { |
240 if (n == t) sum = -flow_value; |
241 _capacity[e] -= lower[e]; |
241 for (InEdgeIt e(_graph, n); e != INVALID; ++e) |
242 _supply[_graph.source(e)] -= lower[e]; |
242 sum += lower[e]; |
243 _supply[_graph.target(e)] += lower[e]; |
243 for (OutEdgeIt e(_graph, n); e != INVALID; ++e) |
244 } |
244 sum -= lower[e]; |
|
245 _supply[n] = sum; |
|
246 } |
245 } |
247 _valid_supply = true; |
246 _valid_supply = true; |
248 } |
247 } |
249 |
248 |
250 /// \brief Simple constructor (without lower bounds). |
249 /// \brief Simple constructor (without lower bounds). |