Changeset 197:fff43d9c7110 in lemon0.x
 Timestamp:
 03/17/04 18:04:41 (17 years ago)
 Branch:
 default
 Phase:
 public
 Convert:
 svn:c9d7d8f590d60310b91f818b3a526b0e/lemon/trunk@274
 Location:
 src/work
 Files:

 2 edited
Legend:
 Unmodified
 Added
 Removed

src/work/edmonds_karp.h
r196 r197 565 565 for(NodeIt s=G>template first<NodeIt>(); G>valid(s); G>next(s)) { 566 566 if (S>get(s)) { 567 Number f=0;567 Number u=0; 568 568 for(OutEdgeIt e=G>template first<OutEdgeIt>(s); G>valid(e); G>next(e)) 569 f+=flow>get(e);570 if ( f<1) {569 u+=flow>get(e); 570 if (u<1) { 571 571 res_bfs.pushAndSetReached(s); 572 572 pred.set(s, AugEdge(INVALID)); … … 590 590 free.set(w, res_graph.free(e)); 591 591 } 592 if (T>get(res_graph.head(e))) { 593 n=res_graph.head(e); 594 _augment=true; 595 break; 592 n=res_graph.head(e); 593 if (T>get(n)) { 594 Number u=0; 595 for(InEdgeIt f=G>template first<InEdgeIt>(n); G>valid(f); G>next(f)) 596 u+=flow>get(f); 597 if (u<1) { 598 _augment=true; 599 break; 600 } 596 601 } 597 602 } … … 621 626 // BfsIterator4< AugGraph, AugOutEdgeIt, ReachedMap > bfs(res_graph); 622 627 623 // bfs.pushAndSetReached(s); 628 629 630 631 632 // //typename AugGraph::NodeMap<AugEdge> pred(res_graph); 633 // for(NodeIt s=G>template first<NodeIt>(); G>valid(s); G>next(s)) { 634 // if (S>get(s)) { 635 // Number u=0; 636 // for(OutEdgeIt e=G>template first<OutEdgeIt>(s); G>valid(e); G>next(e)) 637 // u+=flow>get(e); 638 // if (u<1) { 639 // res_bfs.pushAndSetReached(s); 640 // //pred.set(s, AugEdge(INVALID)); 641 // } 642 // } 643 // } 644 645 646 647 648 // //bfs.pushAndSetReached(s); 624 649 // typename AugGraph::NodeMap<int> dist(res_graph); //filled up with 0's 625 650 // while ( !bfs.finished() ) { … … 713 738 // return _augment; 714 739 // } 715 // bool augmentOnBlockingFlow2() { 716 // bool _augment=false; 717 718 // //typedef ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap> EAugGraph; 719 // typedef FilterGraphWrapper< ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap> > EAugGraph; 720 // typedef typename EAugGraph::OutEdgeIt EAugOutEdgeIt; 721 // typedef typename EAugGraph::Edge EAugEdge; 722 723 // EAugGraph res_graph(*G, *flow, *capacity); 724 725 // //typedef typename EAugGraph::NodeMap<bool> ReachedMap; 726 // BfsIterator4< 727 // ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>, 728 // typename ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::OutEdgeIt, 729 // ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::NodeMap<bool> > bfs(res_graph); 730 731 // bfs.pushAndSetReached(s); 732 733 // typename ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>:: 734 // NodeMap<int>& dist=res_graph.dist; 735 736 // while ( !bfs.finished() ) { 737 // typename ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::OutEdgeIt e=bfs; 738 // if (res_graph.valid(e) && bfs.isBNodeNewlyReached()) { 739 // dist.set(res_graph.head(e), dist.get(res_graph.tail(e))+1); 740 // } 741 // ++bfs; 742 // } //computing distances from s in the residual graph 743 744 // bool __augment=true; 745 746 // while (__augment) { 747 748 // __augment=false; 749 // //computing blocking flow with dfs 750 // typedef typename EAugGraph::NodeMap<bool> BlockingReachedMap; 751 // DfsIterator4< EAugGraph, EAugOutEdgeIt, BlockingReachedMap > 752 // dfs(res_graph); 753 // typename EAugGraph::NodeMap<EAugEdge> pred(res_graph); 754 // pred.set(s, EAugEdge(INVALID)); 755 // //invalid iterators for sources 756 757 // typename EAugGraph::NodeMap<Number> free(res_graph); 758 759 // dfs.pushAndSetReached(s); 760 // while (!dfs.finished()) { 761 // ++dfs; 762 // if (res_graph.valid(EAugOutEdgeIt(dfs))) { 763 // if (dfs.isBNodeNewlyReached()) { 740 bool augmentOnBlockingFlow2() { 741 bool _augment=false; 742 743 //typedef ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap> EAugGraph; 744 typedef FilterGraphWrapper< ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap> > EAugGraph; 745 typedef typename EAugGraph::OutEdgeIt EAugOutEdgeIt; 746 typedef typename EAugGraph::Edge EAugEdge; 747 748 EAugGraph res_graph(*G, *flow, *capacity); 749 750 //typedef typename EAugGraph::NodeMap<bool> ReachedMap; 751 BfsIterator4< 752 ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>, 753 typename ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::OutEdgeIt, 754 ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::NodeMap<bool> > bfs(res_graph); 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 bfs.pushAndSetReached(s); 765 //pred.set(s, AugEdge(INVALID)); 766 } 767 } 768 } 769 770 771 //bfs.pushAndSetReached(s); 772 773 typename ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>:: 774 NodeMap<int>& dist=res_graph.dist; 775 776 while ( !bfs.finished() ) { 777 typename ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::OutEdgeIt e=bfs; 778 if (res_graph.valid(e) && bfs.isBNodeNewlyReached()) { 779 dist.set(res_graph.head(e), dist.get(res_graph.tail(e))+1); 780 } 781 ++bfs; 782 } //computing distances from s in the residual graph 783 784 bool __augment=true; 785 786 while (__augment) { 787 788 __augment=false; 789 //computing blocking flow with dfs 790 typedef typename EAugGraph::NodeMap<bool> BlockingReachedMap; 791 DfsIterator4< EAugGraph, EAugOutEdgeIt, BlockingReachedMap > 792 dfs(res_graph); 793 typename EAugGraph::NodeMap<EAugEdge> pred(res_graph, INVALID); 794 //pred.set(s, EAugEdge(INVALID)); 795 //invalid iterators for sources 796 797 typename EAugGraph::NodeMap<Number> free(res_graph); 798 799 800 //typename AugGraph::NodeMap<AugEdge> pred(res_graph); 801 for(NodeIt s=G>template first<NodeIt>(); G>valid(s); G>next(s)) { 802 if (S>get(s)) { 803 Number u=0; 804 for(OutEdgeIt e=G>template first<OutEdgeIt>(s); G>valid(e); G>next(e)) 805 u+=flow>get(e); 806 if (u<1) { 807 dfs.pushAndSetReached(s); 808 //pred.set(s, AugEdge(INVALID)); 809 } 810 } 811 } 812 813 814 815 //dfs.pushAndSetReached(s); 816 typename EAugGraph::Node n; 817 while (!dfs.finished()) { 818 ++dfs; 819 if (res_graph.valid(EAugOutEdgeIt(dfs))) { 820 if (dfs.isBNodeNewlyReached()) { 764 821 765 // typename EAugGraph::Node v=res_graph.aNode(dfs); 766 // typename EAugGraph::Node w=res_graph.bNode(dfs); 767 768 // pred.set(w, EAugOutEdgeIt(dfs)); 769 // if (res_graph.valid(pred.get(v))) { 770 // free.set(w, std::min(free.get(v), res_graph.free(dfs))); 771 // } else { 772 // free.set(w, res_graph.free(dfs)); 773 // } 774 775 // if (w==t) { 776 // __augment=true; 777 // _augment=true; 778 // break; 779 // } 780 // } else { 781 // res_graph.erase(dfs); 782 // } 783 // } 784 785 // } 786 787 // if (__augment) { 788 // typename EAugGraph::Node n=t; 789 // Number augment_value=free.get(t); 790 // while (res_graph.valid(pred.get(n))) { 791 // EAugEdge e=pred.get(n); 792 // res_graph.augment(e, augment_value); 793 // n=res_graph.tail(e); 794 // if (res_graph.free(e)==0) 795 // res_graph.erase(e); 796 // } 797 // } 798 799 // } 822 typename EAugGraph::Node v=res_graph.aNode(dfs); 823 typename EAugGraph::Node w=res_graph.bNode(dfs); 824 825 pred.set(w, EAugOutEdgeIt(dfs)); 826 if (res_graph.valid(pred.get(v))) { 827 free.set(w, std::min(free.get(v), res_graph.free(dfs))); 828 } else { 829 free.set(w, res_graph.free(dfs)); 830 } 831 832 n=w; 833 if (T>get(w)) { 834 Number u=0; 835 for(InEdgeIt f=G>template first<InEdgeIt>(n); G>valid(f); G>next(f)) 836 u+=flow>get(f); 837 if (u<1) { 838 __augment=true; 839 _augment=true; 840 break; 841 } 842 } 843 } else { 844 res_graph.erase(dfs); 845 } 846 } 847 848 } 849 850 if (__augment) { 851 // typename EAugGraph::Node n=t; 852 Number augment_value=free.get(n); 853 while (res_graph.valid(pred.get(n))) { 854 EAugEdge e=pred.get(n); 855 res_graph.augment(e, augment_value); 856 n=res_graph.tail(e); 857 if (res_graph.free(e)==0) 858 res_graph.erase(e); 859 } 860 } 861 862 } 800 863 801 //return _augment;802 //}864 return _augment; 865 } 803 866 void run() { 804 867 //int num_of_augmentations=0; 
src/work/marci/max_bipartite_matching_demo.cc
r196 r197 5 5 #include <cstdlib> 6 6 7 //#include <LEDA/graph.h> 8 //#include <leda_graph_wrapper.h> 7 #include <LEDA/graph.h> 8 #include <LEDA/mcb_matching.h> 9 #include <LEDA/list.h> 10 11 #include <leda_graph_wrapper.h> 9 12 #include <list_graph.h> 10 13 #include <dimacs.h> … … 37 40 38 41 using std::cout; 42 using std::cin; 39 43 using std::endl; 40 44 41 45 int main() { 42 //leda::graph g;43 //typedef LedaGraphWrapper<leda::graph> Graph;44 //Graph G(g);45 typedef ListGraph Graph;46 Graph G;46 leda::graph g; 47 typedef LedaGraphWrapper<leda::graph> Graph; 48 Graph G(g); 49 // typedef ListGraph Graph; 50 // Graph G; 47 51 48 52 typedef Graph::Node Node; … … 59 63 std::vector<Node> t_nodes; 60 64 61 for(int i=0; i<4; ++i) { 65 int a; 66 cout << "number of nodes in the first color class="; 67 cin >> a; 68 int b; 69 cout << "number of nodes in the second color class="; 70 cin >> b; 71 int m; 72 cout << "number of edges="; 73 cin >> m; 74 75 76 for(int i=0; i<a; ++i) { 62 77 s_nodes.push_back(G.addNode()); 63 78 } 64 for(int i=0; i< 4; ++i) {79 for(int i=0; i<a; ++i) { 65 80 t_nodes.push_back(G.addNode()); 66 81 } 67 82 random_init(); 68 for(int i=0; i<6; ++i) { 69 G.addEdge(s_nodes[random(4)], t_nodes[random(4)]); 70 } 71 83 for(int i=0; i<m; ++i) { 84 G.addEdge(s_nodes[random(a)], t_nodes[random(b)]); 85 } 86 87 // G.addEdge(s_nodes[1], t_nodes[54]); 88 // G.addEdge(s_nodes[1], t_nodes[54]); 89 // G.addEdge(s_nodes[1], t_nodes[44]); 90 // G.addEdge(s_nodes[1], t_nodes[44]); 72 91 // G.addEdge(s_nodes[2], t_nodes[44]); 73 // G.addEdge(s_nodes[2], t_nodes[74]); 74 // G.addEdge(s_nodes[2], t_nodes[44]); 75 // G.addEdge(s_nodes[3], t_nodes[64]); 76 // G.addEdge(s_nodes[3], t_nodes[54]); 77 // G.addEdge(s_nodes[3], t_nodes[54]); 92 // G.addEdge(s_nodes[3], t_nodes[44]); 78 93 79 94 … … 81 96 Graph::NodeMap<bool> t_map(G); //false 82 97 83 for(int i=0; i<4; ++i) { 84 s_map.set(s_nodes[i], true); 85 t_map.set(t_nodes[i], true); 86 } 87 88 cout << "bfs and dfs iterator demo on the directed graph" << endl; 89 for(NodeIt n=G.first<NodeIt>(); G.valid(n); G.next(n)) { 90 cout << G.id(n) << ": "; 91 cout << "out edges: "; 92 for(OutEdgeIt e=G.first<OutEdgeIt>(n); G.valid(e); G.next(e)) 93 cout << G.id(G.tail(e)) << ">" << G.id(G.head(e)) << " "; 94 cout << "in edges: "; 95 for(InEdgeIt e=G.first<InEdgeIt>(n); G.valid(e); G.next(e)) 96 cout << G.id(G.tail(e)) << ">" << G.id(G.head(e)) << " "; 97 cout << endl; 98 } 98 for(int i=0; i<a; ++i) s_map.set(s_nodes[i], true); 99 for(int i=0; i<b; ++i) t_map.set(t_nodes[i], true); 100 101 // cout << "bfs and dfs iterator demo on the directed graph" << endl; 102 // for(NodeIt n=G.first<NodeIt>(); G.valid(n); G.next(n)) { 103 // cout << G.id(n) << ": "; 104 // cout << "out edges: "; 105 // for(OutEdgeIt e=G.first<OutEdgeIt>(n); G.valid(e); G.next(e)) 106 // cout << G.id(G.tail(e)) << ">" << G.id(G.head(e)) << " "; 107 // cout << "in edges: "; 108 // for(InEdgeIt e=G.first<InEdgeIt>(n); G.valid(e); G.next(e)) 109 // cout << G.id(G.tail(e)) << ">" << G.id(G.head(e)) << " "; 110 // cout << endl; 111 // } 99 112 100 113 … … 108 121 109 122 MaxMatching<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> > max_flow_test(G, s_map, t_map, flow, cap); 110 //max_flow_test.augmentWithBlockingFlow<Graph>();111 123 int i=0; 112 124 while (max_flow_test.augmentOnShortestPath()) { 113 // for(EdgeIt e=G.template first<EdgeIt>(); e.valid(); ++e) { 114 // std::cout<<"("<<G.tail(e)<< ""<<flow.get(e)<<">"<<G.head(e)<<") "; 115 // } 116 // std::cout<<std::endl; 125 // for(EdgeIt e=G.first<EdgeIt>(); G.valid(e); G.next(e)) 126 // std::cout << G.id(G.tail(e)) << "" << flow.get(e) << ">" << G.id(G.head(e)) << " "; 127 // std::cout<<std::endl; 117 128 ++i; 118 129 } 119 130 120 std::cout << "maximum matching: "<< std::endl;121 for(EdgeIt e=G.first<EdgeIt>(); G.valid(e); G.next(e))122 if (flow.get(e))123 std::cout << G.id(G.tail(e)) << "" << flow.get(e) << ">" << G.id(G.head(e)) << " ";124 std::cout<<std::endl;125 std::cout << "edges which are not in this maximum matching: "<< std::endl;126 for(EdgeIt e=G.first<EdgeIt>(); G.valid(e); G.next(e))127 if (!flow.get(e))128 std::cout << G.id(G.tail(e)) << "" << flow.get(e) << ">" << G.id(G.head(e)) << " ";129 std::cout<<std::endl;131 // std::cout << "maximum matching: "<< std::endl; 132 // for(EdgeIt e=G.first<EdgeIt>(); G.valid(e); G.next(e)) 133 // if (flow.get(e)) 134 // std::cout << G.id(G.tail(e)) << "" << flow.get(e) << ">" << G.id(G.head(e)) << " "; 135 // std::cout<<std::endl; 136 // std::cout << "edges which are not in this maximum matching: "<< std::endl; 137 // for(EdgeIt e=G.first<EdgeIt>(); G.valid(e); G.next(e)) 138 // if (!flow.get(e)) 139 // std::cout << G.id(G.tail(e)) << "" << flow.get(e) << ">" << G.id(G.head(e)) << " "; 140 // std::cout<<std::endl; 130 141 131 142 std::cout << "elapsed time: " << ts << std::endl; … … 133 144 std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl; 134 145 } 146 147 { 148 std::cout << "onthefly max bipartite matching demo (HopcroftKarp) on wrapped leda graph..." << std::endl; 149 Graph::EdgeMap<int> flow(G); //0 flow 150 Graph::EdgeMap<int> cap(G, 1); 151 152 Timer ts; 153 ts.reset(); 154 155 MaxMatching<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> > max_flow_test(G, s_map, t_map, flow, cap); 156 int i=0; 157 while (max_flow_test.augmentOnBlockingFlow2()) { 158 // for(EdgeIt e=G.first<EdgeIt>(); G.valid(e); G.next(e)) 159 // std::cout << G.id(G.tail(e)) << "" << flow.get(e) << ">" << G.id(G.head(e)) << " "; 160 // std::cout<<std::endl; 161 ++i; 162 } 163 164 // std::cout << "maximum matching: "<< std::endl; 165 // for(EdgeIt e=G.first<EdgeIt>(); G.valid(e); G.next(e)) 166 // if (flow.get(e)) 167 // std::cout << G.id(G.tail(e)) << "" << flow.get(e) << ">" << G.id(G.head(e)) << " "; 168 // std::cout<<std::endl; 169 // std::cout << "edges which are not in this maximum matching: "<< std::endl; 170 // for(EdgeIt e=G.first<EdgeIt>(); G.valid(e); G.next(e)) 171 // if (!flow.get(e)) 172 // std::cout << G.id(G.tail(e)) << "" << flow.get(e) << ">" << G.id(G.head(e)) << " "; 173 // std::cout<<std::endl; 174 175 std::cout << "elapsed time: " << ts << std::endl; 176 std::cout << "number of augmentation phases: " << i << std::endl; 177 std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl; 178 } 179 180 { 181 std::cout << "max bipartite matching (LEDA)..." << std::endl; 182 //Graph::EdgeMap<int> flow(G); //0 flow 183 //Graph::EdgeMap<int> cap(G, 1); 184 185 Timer ts; 186 ts.reset(); 187 188 //MaxMatching<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> > max_flow_test(G, s_map, t_map, flow, cap); 189 //int i=0; 190 //while (max_flow_test.augmentOnShortestPath()) { ++i; } 191 192 leda_list<leda_edge> l=MAX_CARD_BIPARTITE_MATCHING(g); 193 194 195 // std::cout << "maximum matching: "<< std::endl; 196 // for(EdgeIt e=G.first<EdgeIt>(); G.valid(e); G.next(e)) 197 // if (flow.get(e)) 198 // std::cout << G.id(G.tail(e)) << "" << flow.get(e) << ">" << G.id(G.head(e)) << " "; 199 // std::cout<<std::endl; 200 // std::cout << "edges which are not in this maximum matching: "<< std::endl; 201 // for(EdgeIt e=G.first<EdgeIt>(); G.valid(e); G.next(e)) 202 // if (!flow.get(e)) 203 // std::cout << G.id(G.tail(e)) << "" << flow.get(e) << ">" << G.id(G.head(e)) << " "; 204 // std::cout<<std::endl; 205 206 207 std::cout << "elapsed time: " << ts << std::endl; 208 //std::cout << "number of augmentation phases: " << i << std::endl; 209 std::cout << "flow value: "<< l.size() << std::endl; 210 } 211 135 212 136 213
Note: See TracChangeset
for help on using the changeset viewer.