equal
deleted
inserted
replaced
530 |
530 |
531 template <typename Graph, typename Number, typename FlowMap, typename CapacityMap> |
531 template <typename Graph, typename Number, typename FlowMap, typename CapacityMap> |
532 class MaxMatching { |
532 class MaxMatching { |
533 public: |
533 public: |
534 typedef typename Graph::Node Node; |
534 typedef typename Graph::Node Node; |
|
535 typedef typename Graph::NodeIt NodeIt; |
535 typedef typename Graph::Edge Edge; |
536 typedef typename Graph::Edge Edge; |
536 typedef typename Graph::EdgeIt EdgeIt; |
537 typedef typename Graph::EdgeIt EdgeIt; |
537 typedef typename Graph::OutEdgeIt OutEdgeIt; |
538 typedef typename Graph::OutEdgeIt OutEdgeIt; |
538 typedef typename Graph::InEdgeIt InEdgeIt; |
539 typedef typename Graph::InEdgeIt InEdgeIt; |
539 |
540 |
561 typedef typename AugGraph::NodeMap<bool> ReachedMap; |
562 typedef typename AugGraph::NodeMap<bool> ReachedMap; |
562 BfsIterator5< AugGraph, /*AugOutEdgeIt,*/ ReachedMap > res_bfs(res_graph); |
563 BfsIterator5< AugGraph, /*AugOutEdgeIt,*/ ReachedMap > res_bfs(res_graph); |
563 typename AugGraph::NodeMap<AugEdge> pred(res_graph); |
564 typename AugGraph::NodeMap<AugEdge> pred(res_graph); |
564 for(NodeIt s=G->template first<NodeIt>(); G->valid(s); G->next(s)) { |
565 for(NodeIt s=G->template first<NodeIt>(); G->valid(s); G->next(s)) { |
565 Number f=0; |
566 Number f=0; |
566 for(OutEdgeIt e=G->template first<OutEdgeIt>(); G->valid(e); G->next(e)) |
567 for(OutEdgeIt e=G->template first<OutEdgeIt>(s); G->valid(e); G->next(e)) |
567 f+=flow->get(e); |
568 f+=flow->get(e); |
568 if (f<1) { |
569 if (f<1) { |
569 res_bfs.pushAndSetReached(s); |
570 res_bfs.pushAndSetReached(s); |
570 pred.set(s, AugEdge(INVALID)); |
571 pred.set(s, AugEdge(INVALID)); |
571 } |
572 } |
584 if (res_graph.valid(pred.get(v))) { |
585 if (res_graph.valid(pred.get(v))) { |
585 free.set(w, std::min(free.get(v), res_graph.free(e))); |
586 free.set(w, std::min(free.get(v), res_graph.free(e))); |
586 } else { |
587 } else { |
587 free.set(w, res_graph.free(e)); |
588 free.set(w, res_graph.free(e)); |
588 } |
589 } |
589 if (TMap(res_graph.head(e))) { |
590 if (T->get(res_graph.head(e))) { |
590 n=res_graph.head(e); |
591 n=res_graph.head(e); |
591 _augment=true; |
592 _augment=true; |
592 break; |
593 break; |
593 } |
594 } |
594 } |
595 } |
596 ++res_bfs; |
597 ++res_bfs; |
597 } //end of searching augmenting path |
598 } //end of searching augmenting path |
598 |
599 |
599 if (_augment) { |
600 if (_augment) { |
600 //Node n=t; |
601 //Node n=t; |
601 Number augment_value=free.get(t); |
602 Number augment_value=free.get(n); |
602 while (res_graph.valid(pred.get(n))) { |
603 while (res_graph.valid(pred.get(n))) { |
603 AugEdge e=pred.get(n); |
604 AugEdge e=pred.get(n); |
604 res_graph.augment(e, augment_value); |
605 res_graph.augment(e, augment_value); |
605 n=res_graph.tail(e); |
606 n=res_graph.tail(e); |
606 } |
607 } |
803 //while (augmentOnBlockingFlow<MutableGraph>()) { |
804 //while (augmentOnBlockingFlow<MutableGraph>()) { |
804 //std::cout << ++num_of_augmentations << " "; |
805 //std::cout << ++num_of_augmentations << " "; |
805 //std::cout<<std::endl; |
806 //std::cout<<std::endl; |
806 } |
807 } |
807 } |
808 } |
808 template<typename MutableGraph> void run() { |
809 // template<typename MutableGraph> void run() { |
809 //int num_of_augmentations=0; |
810 // //int num_of_augmentations=0; |
810 //while (augmentOnShortestPath()) { |
811 // //while (augmentOnShortestPath()) { |
811 while (augmentOnBlockingFlow<MutableGraph>()) { |
812 // while (augmentOnBlockingFlow<MutableGraph>()) { |
812 //std::cout << ++num_of_augmentations << " "; |
813 // //std::cout << ++num_of_augmentations << " "; |
813 //std::cout<<std::endl; |
814 // //std::cout<<std::endl; |
814 } |
815 // } |
815 } |
816 // } |
816 Number flowValue() { |
817 Number flowValue() { |
817 Number a=0; |
818 Number a=0; |
818 OutEdgeIt e; |
819 EdgeIt e; |
819 for(G->/*getF*/first(e, s); G->valid(e); G->next(e)) { |
820 for(G->/*getF*/first(e); G->valid(e); G->next(e)) { |
820 a+=flow->get(e); |
821 a+=flow->get(e); |
821 } |
822 } |
822 return a; |
823 return a; |
823 } |
824 } |
824 }; |
825 }; |