179 bool _local_flow; |
179 bool _local_flow; |
180 // Node map of the current potentials |
180 // Node map of the current potentials |
181 PotentialMap *_potential; |
181 PotentialMap *_potential; |
182 bool _local_potential; |
182 bool _local_potential; |
183 |
183 |
|
184 // The residual cost map |
|
185 ResidualCostMap<LargeCostMap> _res_cost; |
184 // The residual graph |
186 // The residual graph |
185 ResGraph *_res_graph; |
187 ResGraph *_res_graph; |
186 // The residual cost map |
|
187 ResidualCostMap<LargeCostMap> _res_cost; |
|
188 // The reduced cost map |
188 // The reduced cost map |
189 ReducedCostMap *_red_cost; |
189 ReducedCostMap *_red_cost; |
190 // The excess map |
190 // The excess map |
191 SupplyNodeMap _excess; |
191 SupplyNodeMap _excess; |
192 // The epsilon parameter used for cost scaling |
192 // The epsilon parameter used for cost scaling |
207 const LowerMap &lower, |
207 const LowerMap &lower, |
208 const CapacityMap &capacity, |
208 const CapacityMap &capacity, |
209 const CostMap &cost, |
209 const CostMap &cost, |
210 const SupplyMap &supply ) : |
210 const SupplyMap &supply ) : |
211 _graph(graph), _lower(&lower), _capacity(graph), _orig_cost(cost), |
211 _graph(graph), _lower(&lower), _capacity(graph), _orig_cost(cost), |
212 _cost(graph), _supply(graph), _flow(0), _local_flow(false), |
212 _cost(graph), _supply(graph), _flow(NULL), _local_flow(false), |
213 _potential(0), _local_potential(false), _res_cost(_cost), |
213 _potential(NULL), _local_potential(false), _res_cost(_cost), |
214 _excess(graph, 0) |
214 _res_graph(NULL), _red_cost(NULL), _excess(graph, 0) |
215 { |
215 { |
216 // Removing non-zero lower bounds |
216 // Removing non-zero lower bounds |
217 _capacity = subMap(capacity, lower); |
217 _capacity = subMap(capacity, lower); |
218 Supply sum = 0; |
218 Supply sum = 0; |
219 for (NodeIt n(_graph); n != INVALID; ++n) { |
219 for (NodeIt n(_graph); n != INVALID; ++n) { |
239 CostScaling( const Graph &graph, |
239 CostScaling( const Graph &graph, |
240 const CapacityMap &capacity, |
240 const CapacityMap &capacity, |
241 const CostMap &cost, |
241 const CostMap &cost, |
242 const SupplyMap &supply ) : |
242 const SupplyMap &supply ) : |
243 _graph(graph), _lower(NULL), _capacity(capacity), _orig_cost(cost), |
243 _graph(graph), _lower(NULL), _capacity(capacity), _orig_cost(cost), |
244 _cost(graph), _supply(supply), _flow(0), _local_flow(false), |
244 _cost(graph), _supply(supply), _flow(NULL), _local_flow(false), |
245 _potential(0), _local_potential(false), _res_cost(_cost), |
245 _potential(NULL), _local_potential(false), _res_cost(_cost), |
246 _excess(graph, 0) |
246 _res_graph(NULL), _red_cost(NULL), _excess(graph, 0) |
247 { |
247 { |
248 // Checking the sum of supply values |
248 // Checking the sum of supply values |
249 Supply sum = 0; |
249 Supply sum = 0; |
250 for (NodeIt n(_graph); n != INVALID; ++n) sum += _supply[n]; |
250 for (NodeIt n(_graph); n != INVALID; ++n) sum += _supply[n]; |
251 _valid_supply = sum == 0; |
251 _valid_supply = sum == 0; |
268 const CapacityMap &capacity, |
268 const CapacityMap &capacity, |
269 const CostMap &cost, |
269 const CostMap &cost, |
270 Node s, Node t, |
270 Node s, Node t, |
271 Supply flow_value ) : |
271 Supply flow_value ) : |
272 _graph(graph), _lower(&lower), _capacity(graph), _orig_cost(cost), |
272 _graph(graph), _lower(&lower), _capacity(graph), _orig_cost(cost), |
273 _cost(graph), _supply(graph), _flow(0), _local_flow(false), |
273 _cost(graph), _supply(graph), _flow(NULL), _local_flow(false), |
274 _potential(0), _local_potential(false), _res_cost(_cost), |
274 _potential(NULL), _local_potential(false), _res_cost(_cost), |
275 _excess(graph, 0) |
275 _res_graph(NULL), _red_cost(NULL), _excess(graph, 0) |
276 { |
276 { |
277 // Removing nonzero lower bounds |
277 // Removing nonzero lower bounds |
278 _capacity = subMap(capacity, lower); |
278 _capacity = subMap(capacity, lower); |
279 for (NodeIt n(_graph); n != INVALID; ++n) { |
279 for (NodeIt n(_graph); n != INVALID; ++n) { |
280 Supply sum = 0; |
280 Supply sum = 0; |
304 const CapacityMap &capacity, |
304 const CapacityMap &capacity, |
305 const CostMap &cost, |
305 const CostMap &cost, |
306 Node s, Node t, |
306 Node s, Node t, |
307 Supply flow_value ) : |
307 Supply flow_value ) : |
308 _graph(graph), _lower(NULL), _capacity(capacity), _orig_cost(cost), |
308 _graph(graph), _lower(NULL), _capacity(capacity), _orig_cost(cost), |
309 _cost(graph), _supply(graph, 0), _flow(0), _local_flow(false), |
309 _cost(graph), _supply(graph, 0), _flow(NULL), _local_flow(false), |
310 _potential(0), _local_potential(false), _res_cost(_cost), |
310 _potential(NULL), _local_potential(false), _res_cost(_cost), |
311 _excess(graph, 0) |
311 _res_graph(NULL), _red_cost(NULL), _excess(graph, 0) |
312 { |
312 { |
313 _supply[s] = flow_value; |
313 _supply[s] = flow_value; |
314 _supply[t] = -flow_value; |
314 _supply[t] = -flow_value; |
315 _valid_supply = true; |
315 _valid_supply = true; |
316 } |
316 } |