562 } |
430 } |
563 |
431 |
564 return _augment; |
432 return _augment; |
565 } |
433 } |
566 |
434 |
567 template<typename MutableGraph> bool augmentOnBlockingFlow1() { |
435 // template<typename MutableGraph> bool augmentOnBlockingFlow1() { |
568 bool _augment=false; |
|
569 |
|
570 AugGraph res_graph(*G, *flow, *capacity); |
|
571 |
|
572 //bfs for distances on the residual graph |
|
573 typedef typename AugGraph::NodeMap<bool> ReachedMap; |
|
574 BfsIterator5< AugGraph, ReachedMap > bfs(res_graph); |
|
575 bfs.pushAndSetReached(s); |
|
576 typename AugGraph::NodeMap<int> dist(res_graph); //filled up with 0's |
|
577 |
|
578 //F will contain the physical copy of the residual graph |
|
579 //with the set of edges which areon shortest paths |
|
580 MutableGraph F; |
|
581 typename AugGraph::NodeMap<typename MutableGraph::Node> |
|
582 res_graph_to_F(res_graph); |
|
583 for(typename AugGraph::NodeIt n=res_graph.template first<typename AugGraph::NodeIt>(); res_graph.valid(n); res_graph.next(n)) { |
|
584 res_graph_to_F.set(n, F.addNode()); |
|
585 } |
|
586 typename MutableGraph::Node sF=res_graph_to_F.get(s); |
|
587 typename MutableGraph::Node tF=res_graph_to_F.get(t); |
|
588 typename MutableGraph::EdgeMap<AugEdge> original_edge(F); |
|
589 typename MutableGraph::EdgeMap<Number> residual_capacity(F); |
|
590 |
|
591 while ( !bfs.finished() ) { |
|
592 AugOutEdgeIt e=bfs; |
|
593 if (res_graph.valid(e)) { |
|
594 if (bfs.isBNodeNewlyReached()) { |
|
595 dist.set(res_graph.head(e), dist.get(res_graph.tail(e))+1); |
|
596 typename MutableGraph::Edge f=F.addEdge(res_graph_to_F.get(res_graph.tail(e)), res_graph_to_F.get(res_graph.head(e))); |
|
597 original_edge.update(); |
|
598 original_edge.set(f, e); |
|
599 residual_capacity.update(); |
|
600 residual_capacity.set(f, res_graph.free(e)); |
|
601 } else { |
|
602 if (dist.get(res_graph.head(e))==(dist.get(res_graph.tail(e))+1)) { |
|
603 typename MutableGraph::Edge f=F.addEdge(res_graph_to_F.get(res_graph.tail(e)), res_graph_to_F.get(res_graph.head(e))); |
|
604 original_edge.update(); |
|
605 original_edge.set(f, e); |
|
606 residual_capacity.update(); |
|
607 residual_capacity.set(f, res_graph.free(e)); |
|
608 } |
|
609 } |
|
610 } |
|
611 ++bfs; |
|
612 } //computing distances from s in the residual graph |
|
613 |
|
614 bool __augment=true; |
|
615 |
|
616 while (__augment) { |
|
617 __augment=false; |
|
618 //computing blocking flow with dfs |
|
619 typedef typename TrivGraphWrapper<MutableGraph>::NodeMap<bool> BlockingReachedMap; |
|
620 DfsIterator5< TrivGraphWrapper<MutableGraph>/*, typename MutableGraph::OutEdgeIt*/, BlockingReachedMap > dfs(F); |
|
621 typename MutableGraph::NodeMap<typename MutableGraph::Edge> pred(F); |
|
622 pred.set(sF, typename MutableGraph::Edge(INVALID)); |
|
623 //invalid iterators for sources |
|
624 |
|
625 typename MutableGraph::NodeMap<Number> free(F); |
|
626 |
|
627 dfs.pushAndSetReached(sF); |
|
628 while (!dfs.finished()) { |
|
629 ++dfs; |
|
630 if (F.valid(typename MutableGraph::OutEdgeIt(dfs))) { |
|
631 if (dfs.isBNodeNewlyReached()) { |
|
632 typename MutableGraph::Node v=F.aNode(dfs); |
|
633 typename MutableGraph::Node w=F.bNode(dfs); |
|
634 pred.set(w, dfs); |
|
635 if (F.valid(pred.get(v))) { |
|
636 free.set(w, std::min(free.get(v), residual_capacity.get(dfs))); |
|
637 } else { |
|
638 free.set(w, residual_capacity.get(dfs)); |
|
639 } |
|
640 if (w==tF) { |
|
641 __augment=true; |
|
642 _augment=true; |
|
643 break; |
|
644 } |
|
645 |
|
646 } else { |
|
647 F.erase(typename MutableGraph::OutEdgeIt(dfs)); |
|
648 } |
|
649 } |
|
650 } |
|
651 |
|
652 if (__augment) { |
|
653 typename MutableGraph::Node n=tF; |
|
654 Number augment_value=free.get(tF); |
|
655 while (F.valid(pred.get(n))) { |
|
656 typename MutableGraph::Edge e=pred.get(n); |
|
657 res_graph.augment(original_edge.get(e), augment_value); |
|
658 n=F.tail(e); |
|
659 if (residual_capacity.get(e)==augment_value) |
|
660 F.erase(e); |
|
661 else |
|
662 residual_capacity.set(e, residual_capacity.get(e)-augment_value); |
|
663 } |
|
664 } |
|
665 |
|
666 } |
|
667 |
|
668 return _augment; |
|
669 } |
|
670 bool augmentOnBlockingFlow2() { |
|
671 bool _augment=false; |
|
672 |
|
673 //typedef ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap> EAugGraph; |
|
674 typedef FilterGraphWrapper< ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap> > EAugGraph; |
|
675 typedef typename EAugGraph::OutEdgeIt EAugOutEdgeIt; |
|
676 typedef typename EAugGraph::Edge EAugEdge; |
|
677 |
|
678 EAugGraph res_graph(*G, *flow, *capacity); |
|
679 |
|
680 //typedef typename EAugGraph::NodeMap<bool> ReachedMap; |
|
681 BfsIterator5< |
|
682 ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>, |
|
683 /*typename ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::OutEdgeIt,*/ |
|
684 ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::NodeMap<bool> > bfs(res_graph); |
|
685 |
|
686 bfs.pushAndSetReached(s); |
|
687 |
|
688 typename ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>:: |
|
689 NodeMap<int>& dist=res_graph.dist; |
|
690 |
|
691 while ( !bfs.finished() ) { |
|
692 typename ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::OutEdgeIt e=bfs; |
|
693 if (res_graph.valid(e) && bfs.isBNodeNewlyReached()) { |
|
694 dist.set(res_graph.head(e), dist.get(res_graph.tail(e))+1); |
|
695 } |
|
696 ++bfs; |
|
697 } //computing distances from s in the residual graph |
|
698 |
|
699 bool __augment=true; |
|
700 |
|
701 while (__augment) { |
|
702 |
|
703 __augment=false; |
|
704 //computing blocking flow with dfs |
|
705 typedef typename EAugGraph::NodeMap<bool> BlockingReachedMap; |
|
706 DfsIterator5< EAugGraph/*, EAugOutEdgeIt*/, BlockingReachedMap > |
|
707 dfs(res_graph); |
|
708 typename EAugGraph::NodeMap<EAugEdge> pred(res_graph); |
|
709 pred.set(s, EAugEdge(INVALID)); |
|
710 //invalid iterators for sources |
|
711 |
|
712 typename EAugGraph::NodeMap<Number> free(res_graph); |
|
713 |
|
714 dfs.pushAndSetReached(s); |
|
715 while (!dfs.finished()) { |
|
716 ++dfs; |
|
717 if (res_graph.valid(EAugOutEdgeIt(dfs))) { |
|
718 if (dfs.isBNodeNewlyReached()) { |
|
719 |
|
720 typename EAugGraph::Node v=res_graph.aNode(dfs); |
|
721 typename EAugGraph::Node w=res_graph.bNode(dfs); |
|
722 |
|
723 pred.set(w, EAugOutEdgeIt(dfs)); |
|
724 if (res_graph.valid(pred.get(v))) { |
|
725 free.set(w, std::min(free.get(v), res_graph.free(dfs))); |
|
726 } else { |
|
727 free.set(w, res_graph.free(dfs)); |
|
728 } |
|
729 |
|
730 if (w==t) { |
|
731 __augment=true; |
|
732 _augment=true; |
|
733 break; |
|
734 } |
|
735 } else { |
|
736 res_graph.erase(dfs); |
|
737 } |
|
738 } |
|
739 |
|
740 } |
|
741 |
|
742 if (__augment) { |
|
743 typename EAugGraph::Node n=t; |
|
744 Number augment_value=free.get(t); |
|
745 while (res_graph.valid(pred.get(n))) { |
|
746 EAugEdge e=pred.get(n); |
|
747 res_graph.augment(e, augment_value); |
|
748 n=res_graph.tail(e); |
|
749 if (res_graph.free(e)==0) |
|
750 res_graph.erase(e); |
|
751 } |
|
752 } |
|
753 |
|
754 } |
|
755 |
|
756 return _augment; |
|
757 } |
|
758 void run() { |
|
759 //int num_of_augmentations=0; |
|
760 while (augmentOnShortestPath()) { |
|
761 //while (augmentOnBlockingFlow<MutableGraph>()) { |
|
762 //std::cout << ++num_of_augmentations << " "; |
|
763 //std::cout<<std::endl; |
|
764 } |
|
765 } |
|
766 template<typename MutableGraph> void run() { |
|
767 //int num_of_augmentations=0; |
|
768 //while (augmentOnShortestPath()) { |
|
769 while (augmentOnBlockingFlow<MutableGraph>()) { |
|
770 //std::cout << ++num_of_augmentations << " "; |
|
771 //std::cout<<std::endl; |
|
772 } |
|
773 } |
|
774 Number flowValue() { |
|
775 Number a=0; |
|
776 OutEdgeIt e; |
|
777 for(G->/*getF*/first(e, s); G->valid(e); G->next(e)) { |
|
778 a+=flow->get(e); |
|
779 } |
|
780 return a; |
|
781 } |
|
782 }; |
|
783 |
|
784 |
|
785 template <typename Graph, typename Number, typename FlowMap, typename CapacityMap> |
|
786 class MaxMatching { |
|
787 public: |
|
788 typedef typename Graph::Node Node; |
|
789 typedef typename Graph::NodeIt NodeIt; |
|
790 typedef typename Graph::Edge Edge; |
|
791 typedef typename Graph::EdgeIt EdgeIt; |
|
792 typedef typename Graph::OutEdgeIt OutEdgeIt; |
|
793 typedef typename Graph::InEdgeIt InEdgeIt; |
|
794 |
|
795 typedef typename Graph::NodeMap<bool> SMap; |
|
796 typedef typename Graph::NodeMap<bool> TMap; |
|
797 private: |
|
798 const Graph* G; |
|
799 SMap* S; |
|
800 TMap* T; |
|
801 //Node s; |
|
802 //Node t; |
|
803 FlowMap* flow; |
|
804 const CapacityMap* capacity; |
|
805 typedef ResGraphWrapper<Graph, Number, FlowMap, CapacityMap > AugGraph; |
|
806 typedef typename AugGraph::OutEdgeIt AugOutEdgeIt; |
|
807 typedef typename AugGraph::Edge AugEdge; |
|
808 typename Graph::NodeMap<int> used; //0 |
|
809 |
|
810 public: |
|
811 MaxMatching(const Graph& _G, SMap& _S, TMap& _T, FlowMap& _flow, const CapacityMap& _capacity) : |
|
812 G(&_G), S(&_S), T(&_T), flow(&_flow), capacity(&_capacity), used(_G) { } |
|
813 bool augmentOnShortestPath() { |
|
814 AugGraph res_graph(*G, *flow, *capacity); |
|
815 bool _augment=false; |
|
816 |
|
817 typedef typename AugGraph::NodeMap<bool> ReachedMap; |
|
818 BfsIterator5< AugGraph, /*AugOutEdgeIt,*/ ReachedMap > res_bfs(res_graph); |
|
819 typename AugGraph::NodeMap<AugEdge> pred(res_graph); |
|
820 for(NodeIt s=G->template first<NodeIt>(); G->valid(s); G->next(s)) { |
|
821 if ((S->get(s)) && (used.get(s)<1) ) { |
|
822 //Number u=0; |
|
823 //for(OutEdgeIt e=G->template first<OutEdgeIt>(s); G->valid(e); G->next(e)) |
|
824 //u+=flow->get(e); |
|
825 //if (u<1) { |
|
826 res_bfs.pushAndSetReached(s); |
|
827 pred.set(s, AugEdge(INVALID)); |
|
828 //} |
|
829 } |
|
830 } |
|
831 |
|
832 typename AugGraph::NodeMap<Number> free(res_graph); |
|
833 |
|
834 Node n; |
|
835 //searching for augmenting path |
|
836 while ( !res_bfs.finished() ) { |
|
837 AugOutEdgeIt e=res_bfs; |
|
838 if (res_graph.valid(e) && res_bfs.isBNodeNewlyReached()) { |
|
839 Node v=res_graph.tail(e); |
|
840 Node w=res_graph.head(e); |
|
841 pred.set(w, e); |
|
842 if (res_graph.valid(pred.get(v))) { |
|
843 free.set(w, std::min(free.get(v), res_graph.free(e))); |
|
844 } else { |
|
845 free.set(w, res_graph.free(e)); |
|
846 } |
|
847 n=res_graph.head(e); |
|
848 if (T->get(n) && (used.get(n)<1) ) { |
|
849 //Number u=0; |
|
850 //for(InEdgeIt f=G->template first<InEdgeIt>(n); G->valid(f); G->next(f)) |
|
851 //u+=flow->get(f); |
|
852 //if (u<1) { |
|
853 _augment=true; |
|
854 break; |
|
855 //} |
|
856 } |
|
857 } |
|
858 |
|
859 ++res_bfs; |
|
860 } //end of searching augmenting path |
|
861 |
|
862 if (_augment) { |
|
863 //Node n=t; |
|
864 used.set(n, 1); //mind2 vegen jav |
|
865 Number augment_value=free.get(n); |
|
866 while (res_graph.valid(pred.get(n))) { |
|
867 AugEdge e=pred.get(n); |
|
868 res_graph.augment(e, augment_value); |
|
869 n=res_graph.tail(e); |
|
870 } |
|
871 used.set(n, 1); //mind2 vegen jav |
|
872 } |
|
873 |
|
874 return _augment; |
|
875 } |
|
876 |
|
877 // template<typename MutableGraph> bool augmentOnBlockingFlow() { |
|
878 // bool _augment=false; |
436 // bool _augment=false; |
879 |
437 |
880 // AugGraph res_graph(*G, *flow, *capacity); |
438 // AugGraph res_graph(*G, *flow, *capacity); |
881 |
439 |
|
440 // //bfs for distances on the residual graph |
882 // typedef typename AugGraph::NodeMap<bool> ReachedMap; |
441 // typedef typename AugGraph::NodeMap<bool> ReachedMap; |
883 // BfsIterator4< AugGraph, AugOutEdgeIt, ReachedMap > bfs(res_graph); |
442 // BfsIterator5< AugGraph, ReachedMap > bfs(res_graph); |
884 |
443 // bfs.pushAndSetReached(s); |
885 |
|
886 |
|
887 |
|
888 |
|
889 // //typename AugGraph::NodeMap<AugEdge> pred(res_graph); |
|
890 // for(NodeIt s=G->template first<NodeIt>(); G->valid(s); G->next(s)) { |
|
891 // if (S->get(s)) { |
|
892 // Number u=0; |
|
893 // for(OutEdgeIt e=G->template first<OutEdgeIt>(s); G->valid(e); G->next(e)) |
|
894 // u+=flow->get(e); |
|
895 // if (u<1) { |
|
896 // res_bfs.pushAndSetReached(s); |
|
897 // //pred.set(s, AugEdge(INVALID)); |
|
898 // } |
|
899 // } |
|
900 // } |
|
901 |
|
902 |
|
903 |
|
904 |
|
905 // //bfs.pushAndSetReached(s); |
|
906 // typename AugGraph::NodeMap<int> dist(res_graph); //filled up with 0's |
444 // typename AugGraph::NodeMap<int> dist(res_graph); //filled up with 0's |
907 // while ( !bfs.finished() ) { |
445 |
908 // AugOutEdgeIt e=bfs; |
446 // //F will contain the physical copy of the residual graph |
909 // if (res_graph.valid(e) && bfs.isBNodeNewlyReached()) { |
447 // //with the set of edges which areon shortest paths |
910 // dist.set(res_graph.head(e), dist.get(res_graph.tail(e))+1); |
|
911 // } |
|
912 |
|
913 // ++bfs; |
|
914 // } //computing distances from s in the residual graph |
|
915 |
|
916 // MutableGraph F; |
448 // MutableGraph F; |
917 // typename AugGraph::NodeMap<typename MutableGraph::Node> |
449 // typename AugGraph::NodeMap<typename MutableGraph::Node> |
918 // res_graph_to_F(res_graph); |
450 // res_graph_to_F(res_graph); |
919 // for(typename AugGraph::NodeIt n=res_graph.template first<typename AugGraph::NodeIt>(); res_graph.valid(n); res_graph.next(n)) { |
451 // for(typename AugGraph::NodeIt n=res_graph.template first<typename AugGraph::NodeIt>(); res_graph.valid(n); res_graph.next(n)) { |
920 // res_graph_to_F.set(n, F.addNode()); |
452 // res_graph_to_F.set(n, F.addNode()); |
921 // } |
453 // } |
922 |
|
923 // typename MutableGraph::Node sF=res_graph_to_F.get(s); |
454 // typename MutableGraph::Node sF=res_graph_to_F.get(s); |
924 // typename MutableGraph::Node tF=res_graph_to_F.get(t); |
455 // typename MutableGraph::Node tF=res_graph_to_F.get(t); |
925 |
|
926 // typename MutableGraph::EdgeMap<AugEdge> original_edge(F); |
456 // typename MutableGraph::EdgeMap<AugEdge> original_edge(F); |
927 // typename MutableGraph::EdgeMap<Number> residual_capacity(F); |
457 // typename MutableGraph::EdgeMap<Number> residual_capacity(F); |
928 |
458 |
929 // //Making F to the graph containing the edges of the residual graph |
459 // while ( !bfs.finished() ) { |
930 // //which are in some shortest paths |
460 // AugOutEdgeIt e=bfs; |
931 // for(typename AugGraph::EdgeIt e=res_graph.template first<typename AugGraph::EdgeIt>(); res_graph.valid(e); res_graph.next(e)) { |
461 // if (res_graph.valid(e)) { |
932 // if (dist.get(res_graph.head(e))==dist.get(res_graph.tail(e))+1) { |
462 // if (bfs.isBNodeNewlyReached()) { |
933 // typename MutableGraph::Edge f=F.addEdge(res_graph_to_F.get(res_graph.tail(e)), res_graph_to_F.get(res_graph.head(e))); |
463 // dist.set(res_graph.head(e), dist.get(res_graph.tail(e))+1); |
934 // original_edge.update(); |
464 // typename MutableGraph::Edge f=F.addEdge(res_graph_to_F.get(res_graph.tail(e)), res_graph_to_F.get(res_graph.head(e))); |
935 // original_edge.set(f, e); |
465 // original_edge.update(); |
936 // residual_capacity.update(); |
466 // original_edge.set(f, e); |
937 // residual_capacity.set(f, res_graph.free(e)); |
467 // residual_capacity.update(); |
938 // } |
468 // residual_capacity.set(f, res_graph.free(e)); |
939 // } |
469 // } else { |
|
470 // if (dist.get(res_graph.head(e))==(dist.get(res_graph.tail(e))+1)) { |
|
471 // typename MutableGraph::Edge f=F.addEdge(res_graph_to_F.get(res_graph.tail(e)), res_graph_to_F.get(res_graph.head(e))); |
|
472 // original_edge.update(); |
|
473 // original_edge.set(f, e); |
|
474 // residual_capacity.update(); |
|
475 // residual_capacity.set(f, res_graph.free(e)); |
|
476 // } |
|
477 // } |
|
478 // } |
|
479 // ++bfs; |
|
480 // } //computing distances from s in the residual graph |
940 |
481 |
941 // bool __augment=true; |
482 // bool __augment=true; |
942 |
483 |
943 // while (__augment) { |
484 // while (__augment) { |
944 // __augment=false; |
485 // __augment=false; |
945 // //computing blocking flow with dfs |
486 // //computing blocking flow with dfs |
946 // typedef typename MutableGraph::NodeMap<bool> BlockingReachedMap; |
487 // typedef typename TrivGraphWrapper<MutableGraph>::NodeMap<bool> BlockingReachedMap; |
947 // DfsIterator4< MutableGraph, typename MutableGraph::OutEdgeIt, BlockingReachedMap > dfs(F); |
488 // DfsIterator5< TrivGraphWrapper<MutableGraph>/*, typename MutableGraph::OutEdgeIt*/, BlockingReachedMap > dfs(F); |
948 // typename MutableGraph::NodeMap<typename MutableGraph::Edge> pred(F); |
489 // typename MutableGraph::NodeMap<typename MutableGraph::Edge> pred(F); |
949 // pred.set(sF, typename MutableGraph::Edge(INVALID)); |
490 // pred.set(sF, typename MutableGraph::Edge(INVALID)); |
950 // //invalid iterators for sources |
491 // //invalid iterators for sources |
951 |
492 |
952 // typename MutableGraph::NodeMap<Number> free(F); |
493 // typename MutableGraph::NodeMap<Number> free(F); |
992 |
533 |
993 // } |
534 // } |
994 |
535 |
995 // return _augment; |
536 // return _augment; |
996 // } |
537 // } |
997 bool augmentOnBlockingFlow2() { |
538 // bool augmentOnBlockingFlow2() { |
998 bool _augment=false; |
539 // bool _augment=false; |
999 |
540 |
1000 //typedef ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap> EAugGraph; |
541 // //typedef ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap> EAugGraph; |
1001 typedef FilterGraphWrapper< ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap> > EAugGraph; |
542 // typedef FilterGraphWrapper< ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap> > EAugGraph; |
1002 typedef typename EAugGraph::OutEdgeIt EAugOutEdgeIt; |
543 // typedef typename EAugGraph::OutEdgeIt EAugOutEdgeIt; |
1003 typedef typename EAugGraph::Edge EAugEdge; |
544 // typedef typename EAugGraph::Edge EAugEdge; |
1004 |
545 |
1005 EAugGraph res_graph(*G, *flow, *capacity); |
546 // EAugGraph res_graph(*G, *flow, *capacity); |
1006 |
547 |
1007 //typedef typename EAugGraph::NodeMap<bool> ReachedMap; |
548 // //typedef typename EAugGraph::NodeMap<bool> ReachedMap; |
1008 BfsIterator5< |
549 // BfsIterator5< |
1009 ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>, |
550 // ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>, |
1010 /*typename ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::OutEdgeIt,*/ |
551 // /*typename ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::OutEdgeIt,*/ |
1011 ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::NodeMap<bool> > bfs(res_graph); |
552 // ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::NodeMap<bool> > bfs(res_graph); |
1012 |
|
1013 |
|
1014 //typename AugGraph::NodeMap<AugEdge> pred(res_graph); |
|
1015 for(NodeIt s=G->template first<NodeIt>(); G->valid(s); G->next(s)) { |
|
1016 if (S->get(s)) { |
|
1017 Number u=0; |
|
1018 for(OutEdgeIt e=G->template first<OutEdgeIt>(s); G->valid(e); G->next(e)) |
|
1019 u+=flow->get(e); |
|
1020 if (u<1) { |
|
1021 bfs.pushAndSetReached(s); |
|
1022 //pred.set(s, AugEdge(INVALID)); |
|
1023 } |
|
1024 } |
|
1025 } |
|
1026 |
|
1027 |
553 |
1028 //bfs.pushAndSetReached(s); |
554 // bfs.pushAndSetReached(s); |
1029 |
555 |
1030 typename ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>:: |
556 // typename ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>:: |
1031 NodeMap<int>& dist=res_graph.dist; |
557 // NodeMap<int>& dist=res_graph.dist; |
1032 |
558 |
1033 while ( !bfs.finished() ) { |
559 // while ( !bfs.finished() ) { |
1034 typename ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::OutEdgeIt e=bfs; |
560 // typename ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::OutEdgeIt e=bfs; |
1035 if (res_graph.valid(e) && bfs.isBNodeNewlyReached()) { |
561 // if (res_graph.valid(e) && bfs.isBNodeNewlyReached()) { |
1036 dist.set(res_graph.head(e), dist.get(res_graph.tail(e))+1); |
562 // dist.set(res_graph.head(e), dist.get(res_graph.tail(e))+1); |
1037 } |
563 // } |
1038 ++bfs; |
564 // ++bfs; |
1039 } //computing distances from s in the residual graph |
565 // } //computing distances from s in the residual graph |
1040 |
566 |
1041 bool __augment=true; |
567 // bool __augment=true; |
1042 |
568 |
1043 while (__augment) { |
569 // while (__augment) { |
1044 |
570 |
1045 __augment=false; |
571 // __augment=false; |
1046 //computing blocking flow with dfs |
572 // //computing blocking flow with dfs |
1047 typedef typename EAugGraph::NodeMap<bool> BlockingReachedMap; |
573 // typedef typename EAugGraph::NodeMap<bool> BlockingReachedMap; |
1048 DfsIterator5< EAugGraph/*, EAugOutEdgeIt*/, BlockingReachedMap > |
574 // DfsIterator5< EAugGraph/*, EAugOutEdgeIt*/, BlockingReachedMap > |
1049 dfs(res_graph); |
575 // dfs(res_graph); |
1050 typename EAugGraph::NodeMap<EAugEdge> pred(res_graph, INVALID); |
576 // typename EAugGraph::NodeMap<EAugEdge> pred(res_graph); |
1051 //pred.set(s, EAugEdge(INVALID)); |
577 // pred.set(s, EAugEdge(INVALID)); |
1052 //invalid iterators for sources |
578 // //invalid iterators for sources |
1053 |
579 |
1054 typename EAugGraph::NodeMap<Number> free(res_graph); |
580 // typename EAugGraph::NodeMap<Number> free(res_graph); |
1055 |
581 |
1056 |
582 // dfs.pushAndSetReached(s); |
1057 //typename AugGraph::NodeMap<AugEdge> pred(res_graph); |
583 // while (!dfs.finished()) { |
1058 for(NodeIt s=G->template first<NodeIt>(); G->valid(s); G->next(s)) { |
584 // ++dfs; |
1059 if (S->get(s)) { |
585 // if (res_graph.valid(EAugOutEdgeIt(dfs))) { |
1060 Number u=0; |
586 // if (dfs.isBNodeNewlyReached()) { |
1061 for(OutEdgeIt e=G->template first<OutEdgeIt>(s); G->valid(e); G->next(e)) |
|
1062 u+=flow->get(e); |
|
1063 if (u<1) { |
|
1064 dfs.pushAndSetReached(s); |
|
1065 //pred.set(s, AugEdge(INVALID)); |
|
1066 } |
|
1067 } |
|
1068 } |
|
1069 |
|
1070 |
|
1071 |
|
1072 //dfs.pushAndSetReached(s); |
|
1073 typename EAugGraph::Node n; |
|
1074 while (!dfs.finished()) { |
|
1075 ++dfs; |
|
1076 if (res_graph.valid(EAugOutEdgeIt(dfs))) { |
|
1077 if (dfs.isBNodeNewlyReached()) { |
|
1078 |
587 |
1079 typename EAugGraph::Node v=res_graph.aNode(dfs); |
588 // typename EAugGraph::Node v=res_graph.aNode(dfs); |
1080 typename EAugGraph::Node w=res_graph.bNode(dfs); |
589 // typename EAugGraph::Node w=res_graph.bNode(dfs); |
1081 |
590 |
1082 pred.set(w, EAugOutEdgeIt(dfs)); |
591 // pred.set(w, EAugOutEdgeIt(dfs)); |
1083 if (res_graph.valid(pred.get(v))) { |
592 // if (res_graph.valid(pred.get(v))) { |
1084 free.set(w, std::min(free.get(v), res_graph.free(dfs))); |
593 // free.set(w, std::min(free.get(v), res_graph.free(dfs))); |
1085 } else { |
594 // } else { |
1086 free.set(w, res_graph.free(dfs)); |
595 // free.set(w, res_graph.free(dfs)); |
1087 } |
596 // } |
1088 |
597 |
1089 n=w; |
598 // if (w==t) { |
1090 if (T->get(w)) { |
599 // __augment=true; |
1091 Number u=0; |
600 // _augment=true; |
1092 for(InEdgeIt f=G->template first<InEdgeIt>(n); G->valid(f); G->next(f)) |
601 // break; |
1093 u+=flow->get(f); |
602 // } |
1094 if (u<1) { |
603 // } else { |
1095 __augment=true; |
604 // res_graph.erase(dfs); |
1096 _augment=true; |
605 // } |
1097 break; |
606 // } |
1098 } |
607 |
1099 } |
608 // } |
1100 } else { |
609 |
1101 res_graph.erase(dfs); |
610 // if (__augment) { |
1102 } |
611 // typename EAugGraph::Node n=t; |
1103 } |
612 // Number augment_value=free.get(t); |
1104 |
613 // while (res_graph.valid(pred.get(n))) { |
1105 } |
614 // EAugEdge e=pred.get(n); |
1106 |
615 // res_graph.augment(e, augment_value); |
1107 if (__augment) { |
616 // n=res_graph.tail(e); |
1108 // typename EAugGraph::Node n=t; |
617 // if (res_graph.free(e)==0) |
1109 Number augment_value=free.get(n); |
618 // res_graph.erase(e); |
1110 while (res_graph.valid(pred.get(n))) { |
619 // } |
1111 EAugEdge e=pred.get(n); |
620 // } |
1112 res_graph.augment(e, augment_value); |
|
1113 n=res_graph.tail(e); |
|
1114 if (res_graph.free(e)==0) |
|
1115 res_graph.erase(e); |
|
1116 } |
|
1117 } |
|
1118 |
621 |
1119 } |
622 // } |
1120 |
623 |
1121 return _augment; |
624 // return _augment; |
1122 } |
625 // } |
1123 void run() { |
626 // void run() { |
1124 //int num_of_augmentations=0; |
627 // //int num_of_augmentations=0; |
1125 while (augmentOnShortestPath()) { |
628 // while (augmentOnShortestPath()) { |
1126 //while (augmentOnBlockingFlow<MutableGraph>()) { |
629 // //while (augmentOnBlockingFlow<MutableGraph>()) { |
1127 //std::cout << ++num_of_augmentations << " "; |
630 // //std::cout << ++num_of_augmentations << " "; |
1128 //std::cout<<std::endl; |
631 // //std::cout<<std::endl; |
1129 } |
632 // } |
1130 } |
633 // } |
1131 // template<typename MutableGraph> void run() { |
634 // template<typename MutableGraph> void run() { |
1132 // //int num_of_augmentations=0; |
635 // //int num_of_augmentations=0; |
1133 // //while (augmentOnShortestPath()) { |
636 // //while (augmentOnShortestPath()) { |
1134 // while (augmentOnBlockingFlow<MutableGraph>()) { |
637 // while (augmentOnBlockingFlow<MutableGraph>()) { |
1135 // //std::cout << ++num_of_augmentations << " "; |
638 // //std::cout << ++num_of_augmentations << " "; |
1136 // //std::cout<<std::endl; |
639 // //std::cout<<std::endl; |
1137 // } |
640 // } |
1138 // } |
641 // } |
1139 Number flowValue() { |
642 Number flowValue() { |
1140 Number a=0; |
643 Number a=0; |
1141 EdgeIt e; |
644 OutEdgeIt e; |
1142 for(G->/*getF*/first(e); G->valid(e); G->next(e)) { |
645 for(gw.first(e, s); gw.valid(e); gw.next(e)) { |
1143 a+=flow->get(e); |
646 a+=flow->get(e); |
1144 } |
647 } |
1145 return a; |
648 return a; |
1146 } |
649 } |
1147 }; |
650 }; |
1148 |
651 |
1149 |
652 |
1150 |
|
1151 |
|
1152 |
|
1153 |
|
1154 // template <typename Graph, typename Number, typename FlowMap, typename CapacityMap> |
653 // template <typename Graph, typename Number, typename FlowMap, typename CapacityMap> |
1155 // class MaxFlow2 { |
654 // class MaxMatching { |
1156 // public: |
655 // public: |
1157 // typedef typename Graph::Node Node; |
656 // typedef typename Graph::Node Node; |
|
657 // typedef typename Graph::NodeIt NodeIt; |
1158 // typedef typename Graph::Edge Edge; |
658 // typedef typename Graph::Edge Edge; |
1159 // typedef typename Graph::EdgeIt EdgeIt; |
659 // typedef typename Graph::EdgeIt EdgeIt; |
1160 // typedef typename Graph::OutEdgeIt OutEdgeIt; |
660 // typedef typename Graph::OutEdgeIt OutEdgeIt; |
1161 // typedef typename Graph::InEdgeIt InEdgeIt; |
661 // typedef typename Graph::InEdgeIt InEdgeIt; |
|
662 |
|
663 // typedef typename Graph::NodeMap<bool> SMap; |
|
664 // typedef typename Graph::NodeMap<bool> TMap; |
1162 // private: |
665 // private: |
1163 // const Graph& G; |
666 // const Graph* G; |
1164 // std::list<Node>& S; |
667 // SMap* S; |
1165 // std::list<Node>& T; |
668 // TMap* T; |
1166 // FlowMap& flow; |
669 // //Node s; |
1167 // const CapacityMap& capacity; |
670 // //Node t; |
|
671 // FlowMap* flow; |
|
672 // const CapacityMap* capacity; |
1168 // typedef ResGraphWrapper<Graph, Number, FlowMap, CapacityMap > AugGraph; |
673 // typedef ResGraphWrapper<Graph, Number, FlowMap, CapacityMap > AugGraph; |
1169 // typedef typename AugGraph::OutEdgeIt AugOutEdgeIt; |
674 // typedef typename AugGraph::OutEdgeIt AugOutEdgeIt; |
1170 // typedef typename AugGraph::Edge AugEdge; |
675 // typedef typename AugGraph::Edge AugEdge; |
1171 // typename Graph::NodeMap<bool> SMap; |
676 // typename Graph::NodeMap<int> used; //0 |
1172 // typename Graph::NodeMap<bool> TMap; |
677 |
1173 // public: |
678 // public: |
1174 // MaxFlow2(const Graph& _G, std::list<Node>& _S, std::list<Node>& _T, FlowMap& _flow, const CapacityMap& _capacity) : G(_G), S(_S), T(_T), flow(_flow), capacity(_capacity), SMap(_G), TMap(_G) { |
679 // MaxMatching(const Graph& _G, SMap& _S, TMap& _T, FlowMap& _flow, const CapacityMap& _capacity) : |
1175 // for(typename std::list<Node>::const_iterator i=S.begin(); |
680 // G(&_G), S(&_S), T(&_T), flow(&_flow), capacity(&_capacity), used(_G) { } |
1176 // i!=S.end(); ++i) { |
681 // bool augmentOnShortestPath() { |
1177 // SMap.set(*i, true); |
682 // AugGraph res_graph(*G, *flow, *capacity); |
1178 // } |
|
1179 // for (typename std::list<Node>::const_iterator i=T.begin(); |
|
1180 // i!=T.end(); ++i) { |
|
1181 // TMap.set(*i, true); |
|
1182 // } |
|
1183 // } |
|
1184 // bool augment() { |
|
1185 // AugGraph res_graph(G, flow, capacity); |
|
1186 // bool _augment=false; |
683 // bool _augment=false; |
1187 // Node reached_t_node; |
|
1188 |
684 |
1189 // typedef typename AugGraph::NodeMap<bool> ReachedMap; |
685 // typedef typename AugGraph::NodeMap<bool> ReachedMap; |
1190 // BfsIterator4< AugGraph, AugOutEdgeIt, ReachedMap > res_bfs(res_graph); |
686 // BfsIterator5< AugGraph, /*AugOutEdgeIt,*/ ReachedMap > res_bfs(res_graph); |
1191 // for(typename std::list<Node>::const_iterator i=S.begin(); |
687 // typename AugGraph::NodeMap<AugEdge> pred(res_graph); |
1192 // i!=S.end(); ++i) { |
688 // for(NodeIt s=G->template first<NodeIt>(); G->valid(s); G->next(s)) { |
1193 // res_bfs.pushAndSetReached(*i); |
689 // if ((S->get(s)) && (used.get(s)<1) ) { |
|
690 // //Number u=0; |
|
691 // //for(OutEdgeIt e=G->template first<OutEdgeIt>(s); G->valid(e); G->next(e)) |
|
692 // //u+=flow->get(e); |
|
693 // //if (u<1) { |
|
694 // res_bfs.pushAndSetReached(s); |
|
695 // pred.set(s, AugEdge(INVALID)); |
|
696 // //} |
|
697 // } |
1194 // } |
698 // } |
1195 // //res_bfs.pushAndSetReached(s); |
|
1196 |
|
1197 // typename AugGraph::NodeMap<AugEdge> pred(res_graph); |
|
1198 // //filled up with invalid iterators |
|
1199 |
699 |
1200 // typename AugGraph::NodeMap<Number> free(res_graph); |
700 // typename AugGraph::NodeMap<Number> free(res_graph); |
1201 |
701 |
|
702 // Node n; |
1202 // //searching for augmenting path |
703 // //searching for augmenting path |
1203 // while ( !res_bfs.finished() ) { |
704 // while ( !res_bfs.finished() ) { |
1204 // AugOutEdgeIt e=/*AugOutEdgeIt*/(res_bfs); |
705 // AugOutEdgeIt e=res_bfs; |
1205 // if (e.valid() && res_bfs.isBNodeNewlyReached()) { |
706 // if (res_graph.valid(e) && res_bfs.isBNodeNewlyReached()) { |
1206 // Node v=res_graph.tail(e); |
707 // Node v=res_graph.tail(e); |
1207 // Node w=res_graph.head(e); |
708 // Node w=res_graph.head(e); |
1208 // pred.set(w, e); |
709 // pred.set(w, e); |
1209 // if (pred.get(v).valid()) { |
710 // if (res_graph.valid(pred.get(v))) { |
1210 // free.set(w, std::min(free.get(v), e.free())); |
711 // free.set(w, std::min(free.get(v), res_graph.free(e))); |
1211 // } else { |
712 // } else { |
1212 // free.set(w, e.free()); |
713 // free.set(w, res_graph.free(e)); |
1213 // } |
714 // } |
1214 // if (TMap.get(res_graph.head(e))) { |
715 // n=res_graph.head(e); |
1215 // _augment=true; |
716 // if (T->get(n) && (used.get(n)<1) ) { |
1216 // reached_t_node=res_graph.head(e); |
717 // //Number u=0; |
1217 // break; |
718 // //for(InEdgeIt f=G->template first<InEdgeIt>(n); G->valid(f); G->next(f)) |
|
719 // //u+=flow->get(f); |
|
720 // //if (u<1) { |
|
721 // _augment=true; |
|
722 // break; |
|
723 // //} |
1218 // } |
724 // } |
1219 // } |
725 // } |
1220 |
726 |
1221 // ++res_bfs; |
727 // ++res_bfs; |
1222 // } //end of searching augmenting path |
728 // } //end of searching augmenting path |
1223 |
729 |
1224 // if (_augment) { |
730 // if (_augment) { |
1225 // Node n=reached_t_node; |
731 // //Node n=t; |
1226 // Number augment_value=free.get(reached_t_node); |
732 // used.set(n, 1); //mind2 vegen jav |
1227 // while (pred.get(n).valid()) { |
733 // Number augment_value=free.get(n); |
|
734 // while (res_graph.valid(pred.get(n))) { |
1228 // AugEdge e=pred.get(n); |
735 // AugEdge e=pred.get(n); |
1229 // e.augment(augment_value); |
736 // res_graph.augment(e, augment_value); |
1230 // n=res_graph.tail(e); |
737 // n=res_graph.tail(e); |
1231 // } |
738 // } |
|
739 // used.set(n, 1); //mind2 vegen jav |
1232 // } |
740 // } |
1233 |
741 |
|
742 // return _augment; |
|
743 // } |
|
744 |
|
745 // // template<typename MutableGraph> bool augmentOnBlockingFlow() { |
|
746 // // bool _augment=false; |
|
747 |
|
748 // // AugGraph res_graph(*G, *flow, *capacity); |
|
749 |
|
750 // // typedef typename AugGraph::NodeMap<bool> ReachedMap; |
|
751 // // BfsIterator4< AugGraph, AugOutEdgeIt, ReachedMap > bfs(res_graph); |
|
752 |
|
753 |
|
754 |
|
755 |
|
756 |
|
757 // // //typename AugGraph::NodeMap<AugEdge> pred(res_graph); |
|
758 // // for(NodeIt s=G->template first<NodeIt>(); G->valid(s); G->next(s)) { |
|
759 // // if (S->get(s)) { |
|
760 // // Number u=0; |
|
761 // // for(OutEdgeIt e=G->template first<OutEdgeIt>(s); G->valid(e); G->next(e)) |
|
762 // // u+=flow->get(e); |
|
763 // // if (u<1) { |
|
764 // // res_bfs.pushAndSetReached(s); |
|
765 // // //pred.set(s, AugEdge(INVALID)); |
|
766 // // } |
|
767 // // } |
|
768 // // } |
|
769 |
|
770 |
|
771 |
|
772 |
|
773 // // //bfs.pushAndSetReached(s); |
|
774 // // typename AugGraph::NodeMap<int> dist(res_graph); //filled up with 0's |
|
775 // // while ( !bfs.finished() ) { |
|
776 // // AugOutEdgeIt e=bfs; |
|
777 // // if (res_graph.valid(e) && bfs.isBNodeNewlyReached()) { |
|
778 // // dist.set(res_graph.head(e), dist.get(res_graph.tail(e))+1); |
|
779 // // } |
|
780 |
|
781 // // ++bfs; |
|
782 // // } //computing distances from s in the residual graph |
|
783 |
|
784 // // MutableGraph F; |
|
785 // // typename AugGraph::NodeMap<typename MutableGraph::Node> |
|
786 // // res_graph_to_F(res_graph); |
|
787 // // for(typename AugGraph::NodeIt n=res_graph.template first<typename AugGraph::NodeIt>(); res_graph.valid(n); res_graph.next(n)) { |
|
788 // // res_graph_to_F.set(n, F.addNode()); |
|
789 // // } |
|
790 |
|
791 // // typename MutableGraph::Node sF=res_graph_to_F.get(s); |
|
792 // // typename MutableGraph::Node tF=res_graph_to_F.get(t); |
|
793 |
|
794 // // typename MutableGraph::EdgeMap<AugEdge> original_edge(F); |
|
795 // // typename MutableGraph::EdgeMap<Number> residual_capacity(F); |
|
796 |
|
797 // // //Making F to the graph containing the edges of the residual graph |
|
798 // // //which are in some shortest paths |
|
799 // // for(typename AugGraph::EdgeIt e=res_graph.template first<typename AugGraph::EdgeIt>(); res_graph.valid(e); res_graph.next(e)) { |
|
800 // // if (dist.get(res_graph.head(e))==dist.get(res_graph.tail(e))+1) { |
|
801 // // typename MutableGraph::Edge f=F.addEdge(res_graph_to_F.get(res_graph.tail(e)), res_graph_to_F.get(res_graph.head(e))); |
|
802 // // original_edge.update(); |
|
803 // // original_edge.set(f, e); |
|
804 // // residual_capacity.update(); |
|
805 // // residual_capacity.set(f, res_graph.free(e)); |
|
806 // // } |
|
807 // // } |
|
808 |
|
809 // // bool __augment=true; |
|
810 |
|
811 // // while (__augment) { |
|
812 // // __augment=false; |
|
813 // // //computing blocking flow with dfs |
|
814 // // typedef typename MutableGraph::NodeMap<bool> BlockingReachedMap; |
|
815 // // DfsIterator4< MutableGraph, typename MutableGraph::OutEdgeIt, BlockingReachedMap > dfs(F); |
|
816 // // typename MutableGraph::NodeMap<typename MutableGraph::Edge> pred(F); |
|
817 // // pred.set(sF, typename MutableGraph::Edge(INVALID)); |
|
818 // // //invalid iterators for sources |
|
819 |
|
820 // // typename MutableGraph::NodeMap<Number> free(F); |
|
821 |
|
822 // // dfs.pushAndSetReached(sF); |
|
823 // // while (!dfs.finished()) { |
|
824 // // ++dfs; |
|
825 // // if (F.valid(typename MutableGraph::OutEdgeIt(dfs))) { |
|
826 // // if (dfs.isBNodeNewlyReached()) { |
|
827 // // typename MutableGraph::Node v=F.aNode(dfs); |
|
828 // // typename MutableGraph::Node w=F.bNode(dfs); |
|
829 // // pred.set(w, dfs); |
|
830 // // if (F.valid(pred.get(v))) { |
|
831 // // free.set(w, std::min(free.get(v), residual_capacity.get(dfs))); |
|
832 // // } else { |
|
833 // // free.set(w, residual_capacity.get(dfs)); |
|
834 // // } |
|
835 // // if (w==tF) { |
|
836 // // __augment=true; |
|
837 // // _augment=true; |
|
838 // // break; |
|
839 // // } |
|
840 |
|
841 // // } else { |
|
842 // // F.erase(typename MutableGraph::OutEdgeIt(dfs)); |
|
843 // // } |
|
844 // // } |
|
845 // // } |
|
846 |
|
847 // // if (__augment) { |
|
848 // // typename MutableGraph::Node n=tF; |
|
849 // // Number augment_value=free.get(tF); |
|
850 // // while (F.valid(pred.get(n))) { |
|
851 // // typename MutableGraph::Edge e=pred.get(n); |
|
852 // // res_graph.augment(original_edge.get(e), augment_value); |
|
853 // // n=F.tail(e); |
|
854 // // if (residual_capacity.get(e)==augment_value) |
|
855 // // F.erase(e); |
|
856 // // else |
|
857 // // residual_capacity.set(e, residual_capacity.get(e)-augment_value); |
|
858 // // } |
|
859 // // } |
|
860 |
|
861 // // } |
|
862 |
|
863 // // return _augment; |
|
864 // // } |
|
865 // bool augmentOnBlockingFlow2() { |
|
866 // bool _augment=false; |
|
867 |
|
868 // //typedef ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap> EAugGraph; |
|
869 // typedef FilterGraphWrapper< ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap> > EAugGraph; |
|
870 // typedef typename EAugGraph::OutEdgeIt EAugOutEdgeIt; |
|
871 // typedef typename EAugGraph::Edge EAugEdge; |
|
872 |
|
873 // EAugGraph res_graph(*G, *flow, *capacity); |
|
874 |
|
875 // //typedef typename EAugGraph::NodeMap<bool> ReachedMap; |
|
876 // BfsIterator5< |
|
877 // ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>, |
|
878 // /*typename ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::OutEdgeIt,*/ |
|
879 // ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::NodeMap<bool> > bfs(res_graph); |
|
880 |
|
881 |
|
882 // //typename AugGraph::NodeMap<AugEdge> pred(res_graph); |
|
883 // for(NodeIt s=G->template first<NodeIt>(); G->valid(s); G->next(s)) { |
|
884 // if (S->get(s)) { |
|
885 // Number u=0; |
|
886 // for(OutEdgeIt e=G->template first<OutEdgeIt>(s); G->valid(e); G->next(e)) |
|
887 // u+=flow->get(e); |
|
888 // if (u<1) { |
|
889 // bfs.pushAndSetReached(s); |
|
890 // //pred.set(s, AugEdge(INVALID)); |
|
891 // } |
|
892 // } |
|
893 // } |
|
894 |
|
895 |
|
896 // //bfs.pushAndSetReached(s); |
|
897 |
|
898 // typename ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>:: |
|
899 // NodeMap<int>& dist=res_graph.dist; |
|
900 |
|
901 // while ( !bfs.finished() ) { |
|
902 // typename ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::OutEdgeIt e=bfs; |
|
903 // if (res_graph.valid(e) && bfs.isBNodeNewlyReached()) { |
|
904 // dist.set(res_graph.head(e), dist.get(res_graph.tail(e))+1); |
|
905 // } |
|
906 // ++bfs; |
|
907 // } //computing distances from s in the residual graph |
|
908 |
|
909 // bool __augment=true; |
|
910 |
|
911 // while (__augment) { |
|
912 |
|
913 // __augment=false; |
|
914 // //computing blocking flow with dfs |
|
915 // typedef typename EAugGraph::NodeMap<bool> BlockingReachedMap; |
|
916 // DfsIterator5< EAugGraph/*, EAugOutEdgeIt*/, BlockingReachedMap > |
|
917 // dfs(res_graph); |
|
918 // typename EAugGraph::NodeMap<EAugEdge> pred(res_graph, INVALID); |
|
919 // //pred.set(s, EAugEdge(INVALID)); |
|
920 // //invalid iterators for sources |
|
921 |
|
922 // typename EAugGraph::NodeMap<Number> free(res_graph); |
|
923 |
|
924 |
|
925 // //typename AugGraph::NodeMap<AugEdge> pred(res_graph); |
|
926 // for(NodeIt s=G->template first<NodeIt>(); G->valid(s); G->next(s)) { |
|
927 // if (S->get(s)) { |
|
928 // Number u=0; |
|
929 // for(OutEdgeIt e=G->template first<OutEdgeIt>(s); G->valid(e); G->next(e)) |
|
930 // u+=flow->get(e); |
|
931 // if (u<1) { |
|
932 // dfs.pushAndSetReached(s); |
|
933 // //pred.set(s, AugEdge(INVALID)); |
|
934 // } |
|
935 // } |
|
936 // } |
|
937 |
|
938 |
|
939 |
|
940 // //dfs.pushAndSetReached(s); |
|
941 // typename EAugGraph::Node n; |
|
942 // while (!dfs.finished()) { |
|
943 // ++dfs; |
|
944 // if (res_graph.valid(EAugOutEdgeIt(dfs))) { |
|
945 // if (dfs.isBNodeNewlyReached()) { |
|
946 |
|
947 // typename EAugGraph::Node v=res_graph.aNode(dfs); |
|
948 // typename EAugGraph::Node w=res_graph.bNode(dfs); |
|
949 |
|
950 // pred.set(w, EAugOutEdgeIt(dfs)); |
|
951 // if (res_graph.valid(pred.get(v))) { |
|
952 // free.set(w, std::min(free.get(v), res_graph.free(dfs))); |
|
953 // } else { |
|
954 // free.set(w, res_graph.free(dfs)); |
|
955 // } |
|
956 |
|
957 // n=w; |
|
958 // if (T->get(w)) { |
|
959 // Number u=0; |
|
960 // for(InEdgeIt f=G->template first<InEdgeIt>(n); G->valid(f); G->next(f)) |
|
961 // u+=flow->get(f); |
|
962 // if (u<1) { |
|
963 // __augment=true; |
|
964 // _augment=true; |
|
965 // break; |
|
966 // } |
|
967 // } |
|
968 // } else { |
|
969 // res_graph.erase(dfs); |
|
970 // } |
|
971 // } |
|
972 |
|
973 // } |
|
974 |
|
975 // if (__augment) { |
|
976 // // typename EAugGraph::Node n=t; |
|
977 // Number augment_value=free.get(n); |
|
978 // while (res_graph.valid(pred.get(n))) { |
|
979 // EAugEdge e=pred.get(n); |
|
980 // res_graph.augment(e, augment_value); |
|
981 // n=res_graph.tail(e); |
|
982 // if (res_graph.free(e)==0) |
|
983 // res_graph.erase(e); |
|
984 // } |
|
985 // } |
|
986 |
|
987 // } |
|
988 |
1234 // return _augment; |
989 // return _augment; |
1235 // } |
990 // } |
1236 // void run() { |
991 // void run() { |
1237 // while (augment()) { } |
992 // //int num_of_augmentations=0; |
|
993 // while (augmentOnShortestPath()) { |
|
994 // //while (augmentOnBlockingFlow<MutableGraph>()) { |
|
995 // //std::cout << ++num_of_augmentations << " "; |
|
996 // //std::cout<<std::endl; |
|
997 // } |
1238 // } |
998 // } |
|
999 // // template<typename MutableGraph> void run() { |
|
1000 // // //int num_of_augmentations=0; |
|
1001 // // //while (augmentOnShortestPath()) { |
|
1002 // // while (augmentOnBlockingFlow<MutableGraph>()) { |
|
1003 // // //std::cout << ++num_of_augmentations << " "; |
|
1004 // // //std::cout<<std::endl; |
|
1005 // // } |
|
1006 // // } |
1239 // Number flowValue() { |
1007 // Number flowValue() { |
1240 // Number a=0; |
1008 // Number a=0; |
1241 // for(typename std::list<Node>::const_iterator i=S.begin(); |
1009 // EdgeIt e; |
1242 // i!=S.end(); ++i) { |
1010 // for(G->/*getF*/first(e); G->valid(e); G->next(e)) { |
1243 // for(OutEdgeIt e=G.template first<OutEdgeIt>(*i); e.valid(); ++e) { |
1011 // a+=flow->get(e); |
1244 // a+=flow.get(e); |
|
1245 // } |
|
1246 // for(InEdgeIt e=G.template first<InEdgeIt>(*i); e.valid(); ++e) { |
|
1247 // a-=flow.get(e); |
|
1248 // } |
|
1249 // } |
1012 // } |
1250 // return a; |
1013 // return a; |
1251 // } |
1014 // } |
1252 // }; |
1015 // }; |
1253 |
1016 |
1254 |
1017 |
1255 |
1018 |
|
1019 |
|
1020 |
|
1021 |
|
1022 // // template <typename Graph, typename Number, typename FlowMap, typename CapacityMap> |
|
1023 // // class MaxFlow2 { |
|
1024 // // public: |
|
1025 // // typedef typename Graph::Node Node; |
|
1026 // // typedef typename Graph::Edge Edge; |
|
1027 // // typedef typename Graph::EdgeIt EdgeIt; |
|
1028 // // typedef typename Graph::OutEdgeIt OutEdgeIt; |
|
1029 // // typedef typename Graph::InEdgeIt InEdgeIt; |
|
1030 // // private: |
|
1031 // // const Graph& G; |
|
1032 // // std::list<Node>& S; |
|
1033 // // std::list<Node>& T; |
|
1034 // // FlowMap& flow; |
|
1035 // // const CapacityMap& capacity; |
|
1036 // // typedef ResGraphWrapper<Graph, Number, FlowMap, CapacityMap > AugGraph; |
|
1037 // // typedef typename AugGraph::OutEdgeIt AugOutEdgeIt; |
|
1038 // // typedef typename AugGraph::Edge AugEdge; |
|
1039 // // typename Graph::NodeMap<bool> SMap; |
|
1040 // // typename Graph::NodeMap<bool> TMap; |
|
1041 // // public: |
|
1042 // // MaxFlow2(const Graph& _G, std::list<Node>& _S, std::list<Node>& _T, FlowMap& _flow, const CapacityMap& _capacity) : G(_G), S(_S), T(_T), flow(_flow), capacity(_capacity), SMap(_G), TMap(_G) { |
|
1043 // // for(typename std::list<Node>::const_iterator i=S.begin(); |
|
1044 // // i!=S.end(); ++i) { |
|
1045 // // SMap.set(*i, true); |
|
1046 // // } |
|
1047 // // for (typename std::list<Node>::const_iterator i=T.begin(); |
|
1048 // // i!=T.end(); ++i) { |
|
1049 // // TMap.set(*i, true); |
|
1050 // // } |
|
1051 // // } |
|
1052 // // bool augment() { |
|
1053 // // AugGraph res_graph(G, flow, capacity); |
|
1054 // // bool _augment=false; |
|
1055 // // Node reached_t_node; |
|
1056 |
|
1057 // // typedef typename AugGraph::NodeMap<bool> ReachedMap; |
|
1058 // // BfsIterator4< AugGraph, AugOutEdgeIt, ReachedMap > res_bfs(res_graph); |
|
1059 // // for(typename std::list<Node>::const_iterator i=S.begin(); |
|
1060 // // i!=S.end(); ++i) { |
|
1061 // // res_bfs.pushAndSetReached(*i); |
|
1062 // // } |
|
1063 // // //res_bfs.pushAndSetReached(s); |
|
1064 |
|
1065 // // typename AugGraph::NodeMap<AugEdge> pred(res_graph); |
|
1066 // // //filled up with invalid iterators |
|
1067 |
|
1068 // // typename AugGraph::NodeMap<Number> free(res_graph); |
|
1069 |
|
1070 // // //searching for augmenting path |
|
1071 // // while ( !res_bfs.finished() ) { |
|
1072 // // AugOutEdgeIt e=/*AugOutEdgeIt*/(res_bfs); |
|
1073 // // if (e.valid() && res_bfs.isBNodeNewlyReached()) { |
|
1074 // // Node v=res_graph.tail(e); |
|
1075 // // Node w=res_graph.head(e); |
|
1076 // // pred.set(w, e); |
|
1077 // // if (pred.get(v).valid()) { |
|
1078 // // free.set(w, std::min(free.get(v), e.free())); |
|
1079 // // } else { |
|
1080 // // free.set(w, e.free()); |
|
1081 // // } |
|
1082 // // if (TMap.get(res_graph.head(e))) { |
|
1083 // // _augment=true; |
|
1084 // // reached_t_node=res_graph.head(e); |
|
1085 // // break; |
|
1086 // // } |
|
1087 // // } |
|
1088 |
|
1089 // // ++res_bfs; |
|
1090 // // } //end of searching augmenting path |
|
1091 |
|
1092 // // if (_augment) { |
|
1093 // // Node n=reached_t_node; |
|
1094 // // Number augment_value=free.get(reached_t_node); |
|
1095 // // while (pred.get(n).valid()) { |
|
1096 // // AugEdge e=pred.get(n); |
|
1097 // // e.augment(augment_value); |
|
1098 // // n=res_graph.tail(e); |
|
1099 // // } |
|
1100 // // } |
|
1101 |
|
1102 // // return _augment; |
|
1103 // // } |
|
1104 // // void run() { |
|
1105 // // while (augment()) { } |
|
1106 // // } |
|
1107 // // Number flowValue() { |
|
1108 // // Number a=0; |
|
1109 // // for(typename std::list<Node>::const_iterator i=S.begin(); |
|
1110 // // i!=S.end(); ++i) { |
|
1111 // // for(OutEdgeIt e=G.template first<OutEdgeIt>(*i); e.valid(); ++e) { |
|
1112 // // a+=flow.get(e); |
|
1113 // // } |
|
1114 // // for(InEdgeIt e=G.template first<InEdgeIt>(*i); e.valid(); ++e) { |
|
1115 // // a-=flow.get(e); |
|
1116 // // } |
|
1117 // // } |
|
1118 // // return a; |
|
1119 // // } |
|
1120 // // }; |
|
1121 |
|
1122 |
1256 } // namespace hugo |
1123 } // namespace hugo |
1257 |
1124 |
1258 #endif //HUGO_EDMONDS_KARP_H |
1125 #endif //HUGO_EDMONDS_KARP_H |