524 a+=flow->get(e); |
524 a+=flow->get(e); |
525 } |
525 } |
526 return a; |
526 return a; |
527 } |
527 } |
528 }; |
528 }; |
|
529 |
|
530 |
|
531 template <typename Graph, typename Number, typename FlowMap, typename CapacityMap> |
|
532 class MaxMatching { |
|
533 public: |
|
534 typedef typename Graph::Node Node; |
|
535 typedef typename Graph::Edge Edge; |
|
536 typedef typename Graph::EdgeIt EdgeIt; |
|
537 typedef typename Graph::OutEdgeIt OutEdgeIt; |
|
538 typedef typename Graph::InEdgeIt InEdgeIt; |
|
539 |
|
540 typedef typename Graph::NodeMap<bool> SMap; |
|
541 typedef typename Graph::NodeMap<bool> TMap; |
|
542 private: |
|
543 const Graph* G; |
|
544 SMap* S; |
|
545 TMap* T; |
|
546 //Node s; |
|
547 //Node t; |
|
548 FlowMap* flow; |
|
549 const CapacityMap* capacity; |
|
550 typedef ResGraphWrapper<Graph, Number, FlowMap, CapacityMap > AugGraph; |
|
551 typedef typename AugGraph::OutEdgeIt AugOutEdgeIt; |
|
552 typedef typename AugGraph::Edge AugEdge; |
|
553 |
|
554 public: |
|
555 MaxMatching(const Graph& _G, SMap& _S, TMap& _T, FlowMap& _flow, const CapacityMap& _capacity) : |
|
556 G(&_G), S(&_S), T(&_T), flow(&_flow), capacity(&_capacity) { } |
|
557 bool augmentOnShortestPath() { |
|
558 AugGraph res_graph(*G, *flow, *capacity); |
|
559 bool _augment=false; |
|
560 |
|
561 typedef typename AugGraph::NodeMap<bool> ReachedMap; |
|
562 BfsIterator5< AugGraph, /*AugOutEdgeIt,*/ ReachedMap > res_bfs(res_graph); |
|
563 typename AugGraph::NodeMap<AugEdge> pred(res_graph); |
|
564 for(NodeIt s=G->template first<NodeIt>(); G->valid(s); G->next(s)) { |
|
565 Number f=0; |
|
566 for(OutEdgeIt e=G->template first<OutEdgeIt>(); G->valid(e); G->next(e)) |
|
567 f+=flow->get(e); |
|
568 if (f<1) { |
|
569 res_bfs.pushAndSetReached(s); |
|
570 pred.set(s, AugEdge(INVALID)); |
|
571 } |
|
572 } |
|
573 |
|
574 typename AugGraph::NodeMap<Number> free(res_graph); |
|
575 |
|
576 Node n; |
|
577 //searching for augmenting path |
|
578 while ( !res_bfs.finished() ) { |
|
579 AugOutEdgeIt e=res_bfs; |
|
580 if (res_graph.valid(e) && res_bfs.isBNodeNewlyReached()) { |
|
581 Node v=res_graph.tail(e); |
|
582 Node w=res_graph.head(e); |
|
583 pred.set(w, e); |
|
584 if (res_graph.valid(pred.get(v))) { |
|
585 free.set(w, std::min(free.get(v), res_graph.free(e))); |
|
586 } else { |
|
587 free.set(w, res_graph.free(e)); |
|
588 } |
|
589 if (TMap(res_graph.head(e))) { |
|
590 n=res_graph.head(e); |
|
591 _augment=true; |
|
592 break; |
|
593 } |
|
594 } |
|
595 |
|
596 ++res_bfs; |
|
597 } //end of searching augmenting path |
|
598 |
|
599 if (_augment) { |
|
600 //Node n=t; |
|
601 Number augment_value=free.get(t); |
|
602 while (res_graph.valid(pred.get(n))) { |
|
603 AugEdge e=pred.get(n); |
|
604 res_graph.augment(e, augment_value); |
|
605 n=res_graph.tail(e); |
|
606 } |
|
607 } |
|
608 |
|
609 return _augment; |
|
610 } |
|
611 |
|
612 // template<typename MutableGraph> bool augmentOnBlockingFlow() { |
|
613 // bool _augment=false; |
|
614 |
|
615 // AugGraph res_graph(*G, *flow, *capacity); |
|
616 |
|
617 // typedef typename AugGraph::NodeMap<bool> ReachedMap; |
|
618 // BfsIterator4< AugGraph, AugOutEdgeIt, ReachedMap > bfs(res_graph); |
|
619 |
|
620 // bfs.pushAndSetReached(s); |
|
621 // typename AugGraph::NodeMap<int> dist(res_graph); //filled up with 0's |
|
622 // while ( !bfs.finished() ) { |
|
623 // AugOutEdgeIt e=bfs; |
|
624 // if (res_graph.valid(e) && bfs.isBNodeNewlyReached()) { |
|
625 // dist.set(res_graph.head(e), dist.get(res_graph.tail(e))+1); |
|
626 // } |
|
627 |
|
628 // ++bfs; |
|
629 // } //computing distances from s in the residual graph |
|
630 |
|
631 // MutableGraph F; |
|
632 // typename AugGraph::NodeMap<typename MutableGraph::Node> |
|
633 // res_graph_to_F(res_graph); |
|
634 // for(typename AugGraph::NodeIt n=res_graph.template first<typename AugGraph::NodeIt>(); res_graph.valid(n); res_graph.next(n)) { |
|
635 // res_graph_to_F.set(n, F.addNode()); |
|
636 // } |
|
637 |
|
638 // typename MutableGraph::Node sF=res_graph_to_F.get(s); |
|
639 // typename MutableGraph::Node tF=res_graph_to_F.get(t); |
|
640 |
|
641 // typename MutableGraph::EdgeMap<AugEdge> original_edge(F); |
|
642 // typename MutableGraph::EdgeMap<Number> residual_capacity(F); |
|
643 |
|
644 // //Making F to the graph containing the edges of the residual graph |
|
645 // //which are in some shortest paths |
|
646 // for(typename AugGraph::EdgeIt e=res_graph.template first<typename AugGraph::EdgeIt>(); res_graph.valid(e); res_graph.next(e)) { |
|
647 // if (dist.get(res_graph.head(e))==dist.get(res_graph.tail(e))+1) { |
|
648 // typename MutableGraph::Edge f=F.addEdge(res_graph_to_F.get(res_graph.tail(e)), res_graph_to_F.get(res_graph.head(e))); |
|
649 // original_edge.update(); |
|
650 // original_edge.set(f, e); |
|
651 // residual_capacity.update(); |
|
652 // residual_capacity.set(f, res_graph.free(e)); |
|
653 // } |
|
654 // } |
|
655 |
|
656 // bool __augment=true; |
|
657 |
|
658 // while (__augment) { |
|
659 // __augment=false; |
|
660 // //computing blocking flow with dfs |
|
661 // typedef typename MutableGraph::NodeMap<bool> BlockingReachedMap; |
|
662 // DfsIterator4< MutableGraph, typename MutableGraph::OutEdgeIt, BlockingReachedMap > dfs(F); |
|
663 // typename MutableGraph::NodeMap<typename MutableGraph::Edge> pred(F); |
|
664 // pred.set(sF, typename MutableGraph::Edge(INVALID)); |
|
665 // //invalid iterators for sources |
|
666 |
|
667 // typename MutableGraph::NodeMap<Number> free(F); |
|
668 |
|
669 // dfs.pushAndSetReached(sF); |
|
670 // while (!dfs.finished()) { |
|
671 // ++dfs; |
|
672 // if (F.valid(typename MutableGraph::OutEdgeIt(dfs))) { |
|
673 // if (dfs.isBNodeNewlyReached()) { |
|
674 // typename MutableGraph::Node v=F.aNode(dfs); |
|
675 // typename MutableGraph::Node w=F.bNode(dfs); |
|
676 // pred.set(w, dfs); |
|
677 // if (F.valid(pred.get(v))) { |
|
678 // free.set(w, std::min(free.get(v), residual_capacity.get(dfs))); |
|
679 // } else { |
|
680 // free.set(w, residual_capacity.get(dfs)); |
|
681 // } |
|
682 // if (w==tF) { |
|
683 // __augment=true; |
|
684 // _augment=true; |
|
685 // break; |
|
686 // } |
|
687 |
|
688 // } else { |
|
689 // F.erase(typename MutableGraph::OutEdgeIt(dfs)); |
|
690 // } |
|
691 // } |
|
692 // } |
|
693 |
|
694 // if (__augment) { |
|
695 // typename MutableGraph::Node n=tF; |
|
696 // Number augment_value=free.get(tF); |
|
697 // while (F.valid(pred.get(n))) { |
|
698 // typename MutableGraph::Edge e=pred.get(n); |
|
699 // res_graph.augment(original_edge.get(e), augment_value); |
|
700 // n=F.tail(e); |
|
701 // if (residual_capacity.get(e)==augment_value) |
|
702 // F.erase(e); |
|
703 // else |
|
704 // residual_capacity.set(e, residual_capacity.get(e)-augment_value); |
|
705 // } |
|
706 // } |
|
707 |
|
708 // } |
|
709 |
|
710 // return _augment; |
|
711 // } |
|
712 // bool augmentOnBlockingFlow2() { |
|
713 // bool _augment=false; |
|
714 |
|
715 // //typedef ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap> EAugGraph; |
|
716 // typedef FilterGraphWrapper< ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap> > EAugGraph; |
|
717 // typedef typename EAugGraph::OutEdgeIt EAugOutEdgeIt; |
|
718 // typedef typename EAugGraph::Edge EAugEdge; |
|
719 |
|
720 // EAugGraph res_graph(*G, *flow, *capacity); |
|
721 |
|
722 // //typedef typename EAugGraph::NodeMap<bool> ReachedMap; |
|
723 // BfsIterator4< |
|
724 // ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>, |
|
725 // typename ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::OutEdgeIt, |
|
726 // ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::NodeMap<bool> > bfs(res_graph); |
|
727 |
|
728 // bfs.pushAndSetReached(s); |
|
729 |
|
730 // typename ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>:: |
|
731 // NodeMap<int>& dist=res_graph.dist; |
|
732 |
|
733 // while ( !bfs.finished() ) { |
|
734 // typename ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::OutEdgeIt e=bfs; |
|
735 // if (res_graph.valid(e) && bfs.isBNodeNewlyReached()) { |
|
736 // dist.set(res_graph.head(e), dist.get(res_graph.tail(e))+1); |
|
737 // } |
|
738 // ++bfs; |
|
739 // } //computing distances from s in the residual graph |
|
740 |
|
741 // bool __augment=true; |
|
742 |
|
743 // while (__augment) { |
|
744 |
|
745 // __augment=false; |
|
746 // //computing blocking flow with dfs |
|
747 // typedef typename EAugGraph::NodeMap<bool> BlockingReachedMap; |
|
748 // DfsIterator4< EAugGraph, EAugOutEdgeIt, BlockingReachedMap > |
|
749 // dfs(res_graph); |
|
750 // typename EAugGraph::NodeMap<EAugEdge> pred(res_graph); |
|
751 // pred.set(s, EAugEdge(INVALID)); |
|
752 // //invalid iterators for sources |
|
753 |
|
754 // typename EAugGraph::NodeMap<Number> free(res_graph); |
|
755 |
|
756 // dfs.pushAndSetReached(s); |
|
757 // while (!dfs.finished()) { |
|
758 // ++dfs; |
|
759 // if (res_graph.valid(EAugOutEdgeIt(dfs))) { |
|
760 // if (dfs.isBNodeNewlyReached()) { |
|
761 |
|
762 // typename EAugGraph::Node v=res_graph.aNode(dfs); |
|
763 // typename EAugGraph::Node w=res_graph.bNode(dfs); |
|
764 |
|
765 // pred.set(w, EAugOutEdgeIt(dfs)); |
|
766 // if (res_graph.valid(pred.get(v))) { |
|
767 // free.set(w, std::min(free.get(v), res_graph.free(dfs))); |
|
768 // } else { |
|
769 // free.set(w, res_graph.free(dfs)); |
|
770 // } |
|
771 |
|
772 // if (w==t) { |
|
773 // __augment=true; |
|
774 // _augment=true; |
|
775 // break; |
|
776 // } |
|
777 // } else { |
|
778 // res_graph.erase(dfs); |
|
779 // } |
|
780 // } |
|
781 |
|
782 // } |
|
783 |
|
784 // if (__augment) { |
|
785 // typename EAugGraph::Node n=t; |
|
786 // Number augment_value=free.get(t); |
|
787 // while (res_graph.valid(pred.get(n))) { |
|
788 // EAugEdge e=pred.get(n); |
|
789 // res_graph.augment(e, augment_value); |
|
790 // n=res_graph.tail(e); |
|
791 // if (res_graph.free(e)==0) |
|
792 // res_graph.erase(e); |
|
793 // } |
|
794 // } |
|
795 |
|
796 // } |
|
797 |
|
798 // return _augment; |
|
799 // } |
|
800 void run() { |
|
801 //int num_of_augmentations=0; |
|
802 while (augmentOnShortestPath()) { |
|
803 //while (augmentOnBlockingFlow<MutableGraph>()) { |
|
804 //std::cout << ++num_of_augmentations << " "; |
|
805 //std::cout<<std::endl; |
|
806 } |
|
807 } |
|
808 template<typename MutableGraph> void run() { |
|
809 //int num_of_augmentations=0; |
|
810 //while (augmentOnShortestPath()) { |
|
811 while (augmentOnBlockingFlow<MutableGraph>()) { |
|
812 //std::cout << ++num_of_augmentations << " "; |
|
813 //std::cout<<std::endl; |
|
814 } |
|
815 } |
|
816 Number flowValue() { |
|
817 Number a=0; |
|
818 OutEdgeIt e; |
|
819 for(G->/*getF*/first(e, s); G->valid(e); G->next(e)) { |
|
820 a+=flow->get(e); |
|
821 } |
|
822 return a; |
|
823 } |
|
824 }; |
|
825 |
|
826 |
|
827 |
|
828 |
529 |
829 |
530 |
830 |
531 // template <typename Graph, typename Number, typename FlowMap, typename CapacityMap> |
831 // template <typename Graph, typename Number, typename FlowMap, typename CapacityMap> |
532 // class MaxFlow2 { |
832 // class MaxFlow2 { |
533 // public: |
833 // public: |