350 |
350 |
351 MG F; |
351 MG F; |
352 typedef SubGraphWrapper<ResGW, DistanceMap<ResGW> > FilterResGW; |
352 typedef SubGraphWrapper<ResGW, DistanceMap<ResGW> > FilterResGW; |
353 FilterResGW filter_res_graph(res_graph, dist); |
353 FilterResGW filter_res_graph(res_graph, dist); |
354 typename ResGW::NodeMap<typename MG::Node> res_graph_to_F(res_graph); |
354 typename ResGW::NodeMap<typename MG::Node> res_graph_to_F(res_graph); |
355 for(typename ResGW::NodeIt n=res_graph.template first<typename ResGW::NodeIt>(); res_graph.valid(n); res_graph.next(n)) { |
355 { |
356 res_graph_to_F.set(n, F.addNode()); |
356 typename ResGW::NodeIt n; |
|
357 for(res_graph.first(n); res_graph.valid(n); res_graph.next(n)) { |
|
358 res_graph_to_F.set(n, F.addNode()); |
|
359 } |
357 } |
360 } |
358 |
361 |
359 typename MG::Node sF=res_graph_to_F.get(s); |
362 typename MG::Node sF=res_graph_to_F.get(s); |
360 typename MG::Node tF=res_graph_to_F.get(t); |
363 typename MG::Node tF=res_graph_to_F.get(t); |
361 typename MG::EdgeMap<ResGWEdge> original_edge(F); |
364 typename MG::EdgeMap<ResGWEdge> original_edge(F); |
362 typename MG::EdgeMap<Number> residual_capacity(F); |
365 typename MG::EdgeMap<Number> residual_capacity(F); |
363 |
366 |
364 //Making F to the graph containing the edges of the residual graph |
367 //Making F to the graph containing the edges of the residual graph |
365 //which are in some shortest paths |
368 //which are in some shortest paths |
366 for(typename FilterResGW::EdgeIt e=filter_res_graph.template first<typename FilterResGW::EdgeIt>(); filter_res_graph.valid(e); filter_res_graph.next(e)) { |
369 { |
367 //if (dist.get(res_graph.head(e))==dist.get(res_graph.tail(e))+1) { |
370 typename FilterResGW::EdgeIt e; |
|
371 for(filter_res_graph.first(e); filter_res_graph.valid(e); filter_res_graph.next(e)) { |
|
372 //if (dist.get(res_graph.head(e))==dist.get(res_graph.tail(e))+1) { |
368 typename MG::Edge f=F.addEdge(res_graph_to_F.get(res_graph.tail(e)), res_graph_to_F.get(res_graph.head(e))); |
373 typename MG::Edge f=F.addEdge(res_graph_to_F.get(res_graph.tail(e)), res_graph_to_F.get(res_graph.head(e))); |
369 original_edge.update(); |
374 original_edge.update(); |
370 original_edge.set(f, e); |
375 original_edge.set(f, e); |
371 residual_capacity.update(); |
376 residual_capacity.update(); |
372 residual_capacity.set(f, res_graph.resCap(e)); |
377 residual_capacity.set(f, res_graph.resCap(e)); |
373 //} |
378 //} |
|
379 } |
374 } |
380 } |
375 |
381 |
376 bool __augment=true; |
382 bool __augment=true; |
377 |
383 |
378 while (__augment) { |
384 while (__augment) { |
444 |
450 |
445 //F will contain the physical copy of the residual graph |
451 //F will contain the physical copy of the residual graph |
446 //with the set of edges which are on shortest paths |
452 //with the set of edges which are on shortest paths |
447 MG F; |
453 MG F; |
448 typename ResGW::NodeMap<typename MG::Node> res_graph_to_F(res_graph); |
454 typename ResGW::NodeMap<typename MG::Node> res_graph_to_F(res_graph); |
449 for(typename ResGW::NodeIt n=res_graph.template first<typename ResGW::NodeIt>(); res_graph.valid(n); res_graph.next(n)) { |
455 { |
450 res_graph_to_F.set(n, F.addNode()); |
456 typename ResGW::NodeIt n; |
|
457 for(res_graph.first(n); res_graph.valid(n); res_graph.next(n)) { |
|
458 res_graph_to_F.set(n, F.addNode()); |
|
459 } |
451 } |
460 } |
452 |
461 |
453 typename MG::Node sF=res_graph_to_F.get(s); |
462 typename MG::Node sF=res_graph_to_F.get(s); |
454 typename MG::Node tF=res_graph_to_F.get(t); |
463 typename MG::Node tF=res_graph_to_F.get(t); |
455 typename MG::EdgeMap<ResGWEdge> original_edge(F); |
464 typename MG::EdgeMap<ResGWEdge> original_edge(F); |