273 |
273 |
274 bool augmentOnShortestPath() { |
274 bool augmentOnShortestPath() { |
275 ResGW res_graph(*g, *capacity, *flow); |
275 ResGW res_graph(*g, *capacity, *flow); |
276 bool _augment=false; |
276 bool _augment=false; |
277 |
277 |
278 BfsIterator< ResGW, typename ResGW::NodeMap<bool> > bfs(res_graph); |
278 BfsIterator< ResGW, typename ResGW::template NodeMap<bool> > |
|
279 bfs(res_graph); |
279 bfs.pushAndSetReached(s); |
280 bfs.pushAndSetReached(s); |
280 |
281 |
281 typename ResGW::NodeMap<ResGWEdge> pred(res_graph); |
282 typename ResGW::template NodeMap<ResGWEdge> pred(res_graph); |
282 pred.set(s, INVALID); |
283 pred.set(s, INVALID); |
283 |
284 |
284 typename ResGW::NodeMap<Number> free(res_graph); |
285 typename ResGW::template NodeMap<Number> free(res_graph); |
285 |
286 |
286 //searching for augmenting path |
287 //searching for augmenting path |
287 while ( !bfs.finished() ) { |
288 while ( !bfs.finished() ) { |
288 ResGWOutEdgeIt e=bfs; |
289 ResGWOutEdgeIt e=bfs; |
289 if (res_graph.valid(e) && bfs.isBNodeNewlyReached()) { |
290 if (res_graph.valid(e) && bfs.isBNodeNewlyReached()) { |
316 |
317 |
317 template<typename MapGraphWrapper> |
318 template<typename MapGraphWrapper> |
318 class DistanceMap { |
319 class DistanceMap { |
319 protected: |
320 protected: |
320 const MapGraphWrapper* g; |
321 const MapGraphWrapper* g; |
321 typename MapGraphWrapper::NodeMap<int> dist; |
322 typename MapGraphWrapper::template NodeMap<int> dist; |
322 public: |
323 public: |
323 DistanceMap(MapGraphWrapper& _g) : g(&_g), dist(*g, g->nodeNum()) { } |
324 DistanceMap(MapGraphWrapper& _g) : g(&_g), dist(*g, g->nodeNum()) { } |
324 void set(const typename MapGraphWrapper::Node& n, int a) { dist[n]=a; } |
325 void set(const typename MapGraphWrapper::Node& n, int a) { dist[n]=a; } |
325 int operator[](const typename MapGraphWrapper::Node& n) |
326 int operator[](const typename MapGraphWrapper::Node& n) |
326 { return dist[n]; } |
327 { return dist[n]; } |
337 typedef MutableGraph MG; |
338 typedef MutableGraph MG; |
338 bool _augment=false; |
339 bool _augment=false; |
339 |
340 |
340 ResGW res_graph(*g, *capacity, *flow); |
341 ResGW res_graph(*g, *capacity, *flow); |
341 |
342 |
342 BfsIterator< ResGW, typename ResGW::NodeMap<bool> > bfs(res_graph); |
343 BfsIterator< ResGW, typename ResGW::template NodeMap<bool> > |
|
344 bfs(res_graph); |
343 |
345 |
344 bfs.pushAndSetReached(s); |
346 bfs.pushAndSetReached(s); |
345 //typename ResGW::NodeMap<int> dist(res_graph); //filled up with 0's |
347 //typename ResGW::NodeMap<int> dist(res_graph); //filled up with 0's |
346 DistanceMap<ResGW> dist(res_graph); |
348 DistanceMap<ResGW> dist(res_graph); |
347 while ( !bfs.finished() ) { |
349 while ( !bfs.finished() ) { |
355 MG F; |
357 MG F; |
356 ConstMap<typename ResGW::Node, bool> true_map(true); |
358 ConstMap<typename ResGW::Node, bool> true_map(true); |
357 typedef SubGraphWrapper<ResGW, ConstMap<typename ResGW::Node, bool>, |
359 typedef SubGraphWrapper<ResGW, ConstMap<typename ResGW::Node, bool>, |
358 DistanceMap<ResGW> > FilterResGW; |
360 DistanceMap<ResGW> > FilterResGW; |
359 FilterResGW filter_res_graph(res_graph, true_map, dist); |
361 FilterResGW filter_res_graph(res_graph, true_map, dist); |
360 typename ResGW::NodeMap<typename MG::Node> res_graph_to_F(res_graph); |
362 typename ResGW::template NodeMap<typename MG::Node> |
|
363 res_graph_to_F(res_graph); |
361 { |
364 { |
362 typename ResGW::NodeIt n; |
365 typename ResGW::NodeIt n; |
363 for(res_graph.first(n); res_graph.valid(n); res_graph.next(n)) { |
366 for(res_graph.first(n); res_graph.valid(n); res_graph.next(n)) { |
364 res_graph_to_F.set(n, F.addNode()); |
367 res_graph_to_F.set(n, F.addNode()); |
365 } |
368 } |
366 } |
369 } |
367 |
370 |
368 typename MG::Node sF=res_graph_to_F[s]; |
371 typename MG::Node sF=res_graph_to_F[s]; |
369 typename MG::Node tF=res_graph_to_F[t]; |
372 typename MG::Node tF=res_graph_to_F[t]; |
370 typename MG::EdgeMap<ResGWEdge> original_edge(F); |
373 typename MG::template EdgeMap<ResGWEdge> original_edge(F); |
371 typename MG::EdgeMap<Number> residual_capacity(F); |
374 typename MG::template EdgeMap<Number> residual_capacity(F); |
372 |
375 |
373 //Making F to the graph containing the edges of the residual graph |
376 //Making F to the graph containing the edges of the residual graph |
374 //which are in some shortest paths |
377 //which are in some shortest paths |
375 { |
378 { |
376 typename FilterResGW::EdgeIt e; |
379 typename FilterResGW::EdgeIt e; |
389 |
392 |
390 while (__augment) { |
393 while (__augment) { |
391 __augment=false; |
394 __augment=false; |
392 //computing blocking flow with dfs |
395 //computing blocking flow with dfs |
393 |
396 |
394 DfsIterator< MG, typename MG::NodeMap<bool> > dfs(F); |
397 DfsIterator< MG, typename MG::template NodeMap<bool> > dfs(F); |
395 typename MG::NodeMap<typename MG::Edge> pred(F); |
398 typename MG::template NodeMap<typename MG::Edge> pred(F); |
396 pred.set(sF, INVALID); |
399 pred.set(sF, INVALID); |
397 //invalid iterators for sources |
400 //invalid iterators for sources |
398 |
401 |
399 typename MG::NodeMap<Number> free(F); |
402 typename MG::template NodeMap<Number> free(F); |
400 |
403 |
401 dfs.pushAndSetReached(sF); |
404 dfs.pushAndSetReached(sF); |
402 while (!dfs.finished()) { |
405 while (!dfs.finished()) { |
403 ++dfs; |
406 ++dfs; |
404 if (F.valid(/*typename MG::OutEdgeIt*/(dfs))) { |
407 if (F.valid(/*typename MG::OutEdgeIt*/(dfs))) { |
447 bool _augment=false; |
450 bool _augment=false; |
448 |
451 |
449 ResGW res_graph(*g, *capacity, *flow); |
452 ResGW res_graph(*g, *capacity, *flow); |
450 |
453 |
451 //bfs for distances on the residual graph |
454 //bfs for distances on the residual graph |
452 BfsIterator< ResGW, typename ResGW::NodeMap<bool> > bfs(res_graph); |
455 BfsIterator< ResGW, typename ResGW::template NodeMap<bool> > |
|
456 bfs(res_graph); |
453 bfs.pushAndSetReached(s); |
457 bfs.pushAndSetReached(s); |
454 typename ResGW::NodeMap<int> dist(res_graph); //filled up with 0's |
458 typename ResGW::template NodeMap<int> |
|
459 dist(res_graph); //filled up with 0's |
455 |
460 |
456 //F will contain the physical copy of the residual graph |
461 //F will contain the physical copy of the residual graph |
457 //with the set of edges which are on shortest paths |
462 //with the set of edges which are on shortest paths |
458 MG F; |
463 MG F; |
459 typename ResGW::NodeMap<typename MG::Node> res_graph_to_F(res_graph); |
464 typename ResGW::template NodeMap<typename MG::Node> |
|
465 res_graph_to_F(res_graph); |
460 { |
466 { |
461 typename ResGW::NodeIt n; |
467 typename ResGW::NodeIt n; |
462 for(res_graph.first(n); res_graph.valid(n); res_graph.next(n)) { |
468 for(res_graph.first(n); res_graph.valid(n); res_graph.next(n)) { |
463 res_graph_to_F.set(n, F.addNode()); |
469 res_graph_to_F.set(n, F.addNode()); |
464 } |
470 } |
465 } |
471 } |
466 |
472 |
467 typename MG::Node sF=res_graph_to_F[s]; |
473 typename MG::Node sF=res_graph_to_F[s]; |
468 typename MG::Node tF=res_graph_to_F[t]; |
474 typename MG::Node tF=res_graph_to_F[t]; |
469 typename MG::EdgeMap<ResGWEdge> original_edge(F); |
475 typename MG::template EdgeMap<ResGWEdge> original_edge(F); |
470 typename MG::EdgeMap<Number> residual_capacity(F); |
476 typename MG::template EdgeMap<Number> residual_capacity(F); |
471 |
477 |
472 while ( !bfs.finished() ) { |
478 while ( !bfs.finished() ) { |
473 ResGWOutEdgeIt e=bfs; |
479 ResGWOutEdgeIt e=bfs; |
474 if (res_graph.valid(e)) { |
480 if (res_graph.valid(e)) { |
475 if (bfs.isBNodeNewlyReached()) { |
481 if (bfs.isBNodeNewlyReached()) { |
495 bool __augment=true; |
501 bool __augment=true; |
496 |
502 |
497 while (__augment) { |
503 while (__augment) { |
498 __augment=false; |
504 __augment=false; |
499 //computing blocking flow with dfs |
505 //computing blocking flow with dfs |
500 DfsIterator< MG, typename MG::NodeMap<bool> > dfs(F); |
506 DfsIterator< MG, typename MG::template NodeMap<bool> > dfs(F); |
501 typename MG::NodeMap<typename MG::Edge> pred(F); |
507 typename MG::template NodeMap<typename MG::Edge> pred(F); |
502 pred.set(sF, INVALID); |
508 pred.set(sF, INVALID); |
503 //invalid iterators for sources |
509 //invalid iterators for sources |
504 |
510 |
505 typename MG::NodeMap<Number> free(F); |
511 typename MG::template NodeMap<Number> free(F); |
506 |
512 |
507 dfs.pushAndSetReached(sF); |
513 dfs.pushAndSetReached(sF); |
508 while (!dfs.finished()) { |
514 while (!dfs.finished()) { |
509 ++dfs; |
515 ++dfs; |
510 if (F.valid(/*typename MG::OutEdgeIt*/(dfs))) { |
516 if (F.valid(/*typename MG::OutEdgeIt*/(dfs))) { |
551 bool augmentOnBlockingFlow2() { |
557 bool augmentOnBlockingFlow2() { |
552 bool _augment=false; |
558 bool _augment=false; |
553 |
559 |
554 ResGW res_graph(*g, *capacity, *flow); |
560 ResGW res_graph(*g, *capacity, *flow); |
555 |
561 |
556 BfsIterator< ResGW, typename ResGW::NodeMap<bool> > bfs(res_graph); |
562 BfsIterator< ResGW, typename ResGW::template NodeMap<bool> > |
|
563 bfs(res_graph); |
557 |
564 |
558 bfs.pushAndSetReached(s); |
565 bfs.pushAndSetReached(s); |
559 DistanceMap<ResGW> dist(res_graph); |
566 DistanceMap<ResGW> dist(res_graph); |
560 while ( !bfs.finished() ) { |
567 while ( !bfs.finished() ) { |
561 ResGWOutEdgeIt e=bfs; |
568 ResGWOutEdgeIt e=bfs; |
571 DistanceMap<ResGW> > FilterResGW; |
578 DistanceMap<ResGW> > FilterResGW; |
572 FilterResGW filter_res_graph(res_graph, true_map, dist); |
579 FilterResGW filter_res_graph(res_graph, true_map, dist); |
573 |
580 |
574 //Subgraph, which is able to delete edges which are already |
581 //Subgraph, which is able to delete edges which are already |
575 //met by the dfs |
582 //met by the dfs |
576 typename FilterResGW::NodeMap<typename FilterResGW::OutEdgeIt> |
583 typename FilterResGW::template NodeMap<typename FilterResGW::OutEdgeIt> |
577 first_out_edges(filter_res_graph); |
584 first_out_edges(filter_res_graph); |
578 typename FilterResGW::NodeIt v; |
585 typename FilterResGW::NodeIt v; |
579 for(filter_res_graph.first(v); filter_res_graph.valid(v); |
586 for(filter_res_graph.first(v); filter_res_graph.valid(v); |
580 filter_res_graph.next(v)) |
587 filter_res_graph.next(v)) |
581 { |
588 { |
582 typename FilterResGW::OutEdgeIt e; |
589 typename FilterResGW::OutEdgeIt e; |
583 filter_res_graph.first(e, v); |
590 filter_res_graph.first(e, v); |
584 first_out_edges.set(v, e); |
591 first_out_edges.set(v, e); |
585 } |
592 } |
586 typedef ErasingFirstGraphWrapper<FilterResGW, typename FilterResGW:: |
593 typedef ErasingFirstGraphWrapper<FilterResGW, typename FilterResGW:: |
587 NodeMap<typename FilterResGW::OutEdgeIt> > ErasingResGW; |
594 template NodeMap<typename FilterResGW::OutEdgeIt> > ErasingResGW; |
588 ErasingResGW erasing_res_graph(filter_res_graph, first_out_edges); |
595 ErasingResGW erasing_res_graph(filter_res_graph, first_out_edges); |
589 |
596 |
590 bool __augment=true; |
597 bool __augment=true; |
591 |
598 |
592 while (__augment) { |
599 while (__augment) { |
593 |
600 |
594 __augment=false; |
601 __augment=false; |
595 //computing blocking flow with dfs |
602 //computing blocking flow with dfs |
596 DfsIterator< ErasingResGW, typename ErasingResGW::NodeMap<bool> > |
603 DfsIterator< ErasingResGW, |
|
604 typename ErasingResGW::template NodeMap<bool> > |
597 dfs(erasing_res_graph); |
605 dfs(erasing_res_graph); |
598 typename ErasingResGW::NodeMap<typename ErasingResGW::OutEdgeIt> |
606 typename ErasingResGW:: |
599 pred(erasing_res_graph); |
607 template NodeMap<typename ErasingResGW::OutEdgeIt> |
|
608 pred(erasing_res_graph); |
600 pred.set(s, INVALID); |
609 pred.set(s, INVALID); |
601 //invalid iterators for sources |
610 //invalid iterators for sources |
602 |
611 |
603 typename ErasingResGW::NodeMap<Number> free1(erasing_res_graph); |
612 typename ErasingResGW::template NodeMap<Number> |
|
613 free1(erasing_res_graph); |
604 |
614 |
605 dfs.pushAndSetReached( |
615 dfs.pushAndSetReached( |
606 typename ErasingResGW::Node( |
616 typename ErasingResGW::Node( |
607 typename FilterResGW::Node( |
617 typename FilterResGW::Node( |
608 typename ResGW::Node(s) |
618 typename ResGW::Node(s) |