211 //We need things for the bfs |
211 //We need things for the bfs |
212 typename ResAbGraph::template NodeMap<bool> bfs_reached(res_ab_graph); |
212 typename ResAbGraph::template NodeMap<bool> bfs_reached(res_ab_graph); |
213 typename ResAbGraph::template NodeMap<typename ResAbGraph::Edge> |
213 typename ResAbGraph::template NodeMap<typename ResAbGraph::Edge> |
214 bfs_pred(res_ab_graph); |
214 bfs_pred(res_ab_graph); |
215 NullMap<typename ResAbGraph::Node, int> bfs_dist_dummy; |
215 NullMap<typename ResAbGraph::Node, int> bfs_dist_dummy; |
|
216 //Teszt celbol: |
|
217 //BfsIterator<ResAbGraph, typename ResAbGraph::template NodeMap<bool> > |
|
218 //izebize(res_ab_graph, bfs_reached); |
216 //We want to run bfs-es (more) on this graph 'res_ab_graph' |
219 //We want to run bfs-es (more) on this graph 'res_ab_graph' |
217 Bfs < ResAbGraph , |
220 Bfs < const ResAbGraph , |
218 typename ResAbGraph::template NodeMap<bool>, |
221 typename ResAbGraph::template NodeMap<bool>, |
219 typename ResAbGraph::template NodeMap<typename ResAbGraph::Edge>, |
222 typename ResAbGraph::template NodeMap<typename ResAbGraph::Edge>, |
220 NullMap<typename ResAbGraph::Node, int> > |
223 NullMap<typename ResAbGraph::Node, int> > |
221 bfs(res_ab_graph, bfs_reached, bfs_pred, bfs_dist_dummy); |
224 bfs(res_ab_graph, bfs_reached, bfs_pred, bfs_dist_dummy); |
222 /*This is what Marci wants for a bfs |
225 /*This is what Marci wants for a bfs |
231 |
234 |
232 ModCostMap mod_cost(res_graph, cost, potential); |
235 ModCostMap mod_cost(res_graph, cost, potential); |
233 |
236 |
234 Dijkstra<ResGraph, ModCostMap> dijkstra(res_graph, mod_cost); |
237 Dijkstra<ResGraph, ModCostMap> dijkstra(res_graph, mod_cost); |
235 |
238 |
|
239 //We will use the number of the nodes of the graph often |
|
240 int number_of_nodes = graph.nodeNum(); |
236 |
241 |
237 while (max_excess > 0){ |
242 while (max_excess > 0){ |
238 |
243 |
239 //Reset delta if still too big |
244 //Reset delta if still too big |
240 if (8*number_of_nodes*max_excess <= delta){ |
245 if (8*number_of_nodes*max_excess <= delta){ |
248 //Merge and stuff |
253 //Merge and stuff |
249 { |
254 { |
250 SupplyDemand buf=8*number_of_nodes*delta; |
255 SupplyDemand buf=8*number_of_nodes*delta; |
251 typename std::list<Edge>::iterator i = nonabundant_arcs.begin(); |
256 typename std::list<Edge>::iterator i = nonabundant_arcs.begin(); |
252 while ( i != nonabundant_arcs.end() ){ |
257 while ( i != nonabundant_arcs.end() ){ |
253 if (flow[i]>=buf){ |
258 if (flow[*i]>=buf){ |
254 Node a = abundant_components.find(res_graph.head(i)); |
259 Node a = abundant_components.find(res_graph.head(*i)); |
255 Node b = abundant_components.find(res_graph.tail(i)); |
260 Node b = abundant_components.find(res_graph.tail(*i)); |
256 //Merge |
261 //Merge |
257 if (a != b){ |
262 if (a != b){ |
258 abundant_components.join(a,b); |
263 abundant_components.join(a,b); |
259 //We want to push the smaller |
264 //We want to push the smaller |
260 //Which has greater absolut value excess/deficit |
265 //Which has greater absolut value excess/deficit |
267 if (excess_deficit[non_root] < 0) |
272 if (excess_deficit[non_root] < 0) |
268 swap(root, non_root); |
273 swap(root, non_root); |
269 //If the non_root node has excess/deficit at all |
274 //If the non_root node has excess/deficit at all |
270 if (qty_to_augment>0){ |
275 if (qty_to_augment>0){ |
271 //Find path and augment |
276 //Find path and augment |
272 bfs.run(non_root); |
277 bfs.run(typename AbundantGraph::Node(non_root)); |
273 //root should be reached |
278 //root should be reached |
274 |
279 |
275 //Augmenting on the found path |
280 //Augmenting on the found path |
276 Node n=root; |
281 Node n=root; |
277 ResGraphEdge e; |
282 ResGraphEdge e; |
278 while (n!=non_root){ |
283 while (n!=non_root){ |
279 e = bfs_pred(n); |
284 e = bfs_pred[n]; |
280 n = res_graph.tail(e); |
285 n = res_graph.tail(e); |
281 res_graph.augment(e,qty_to_augment); |
286 res_graph.augment(e,qty_to_augment); |
282 } |
287 } |
283 |
288 |
284 //We know that non_root had positive excess |
289 //We know that non_root had positive excess |
285 excess_nodes[non_root] -= qty_to_augment; |
290 excess_nodes.set(non_root, |
|
291 excess_nodes[non_root] - qty_to_augment); |
286 //But what about root node |
292 //But what about root node |
287 //It might have been positive and so became larger |
293 //It might have been positive and so became larger |
288 if (excess_deficit[root]>0){ |
294 if (excess_deficit[root]>0){ |
289 excess_nodes[root] += qty_to_augment; |
295 excess_nodes.set(root, |
|
296 excess_nodes[root] + qty_to_augment); |
290 } |
297 } |
291 else{ |
298 else{ |
292 //Or negative but not turned into positive |
299 //Or negative but not turned into positive |
293 deficit_nodes[root] -= qty_to_augment; |
300 deficit_nodes.set(root, |
|
301 deficit_nodes[root] - qty_to_augment); |
294 } |
302 } |
295 |
303 |
296 //Update the excess_deficit map |
304 //Update the excess_deficit map |
297 excess_deficit[non_root] -= qty_to_augment; |
305 excess_deficit[non_root] -= qty_to_augment; |
298 excess_deficit[root] += qty_to_augment; |
306 excess_deficit[root] += qty_to_augment; |
367 deficit_nodes.push(s,delta - excess_nodes[s]); |
375 deficit_nodes.push(s,delta - excess_nodes[s]); |
368 excess_nodes.pop(); |
376 excess_nodes.pop(); |
369 |
377 |
370 } |
378 } |
371 else{ |
379 else{ |
372 excess_nodes[s] -= delta; |
380 excess_nodes.set(s, excess_nodes[s] - delta); |
373 } |
381 } |
374 //Update the deficit_nodes heap |
382 //Update the deficit_nodes heap |
375 if (delta >= deficit_nodes[t]){ |
383 if (delta >= deficit_nodes[t]){ |
376 if (delta > deficit_nodes[t]) |
384 if (delta > deficit_nodes[t]) |
377 excess_nodes.push(t,delta - deficit_nodes[t]); |
385 excess_nodes.push(t,delta - deficit_nodes[t]); |
378 deficit_nodes.pop(); |
386 deficit_nodes.pop(); |
379 |
387 |
380 } |
388 } |
381 else{ |
389 else{ |
382 deficit_nodes[t] -= delta; |
390 deficit_nodes.set(t, deficit_nodes[t] - delta); |
383 } |
391 } |
384 //Dijkstra part ends here |
392 //Dijkstra part ends here |
385 |
393 |
386 //Choose s and t again |
394 //Choose s and t again |
387 s = excess_nodes.top(); |
395 s = excess_nodes.top(); |