76 std::cin >> m; |
74 std::cin >> m; |
77 int k; |
75 int k; |
78 std::cout << "A bipartite graph is a random group graph if the color classes \nA and B are partitiones to A_0, A_1, ..., A_{k-1} and B_0, B_1, ..., B_{k-1} \nas equally as possible \nand the edges from A_i goes to A_{i-1 mod k} and A_{i+1 mod k}.\n"; |
76 std::cout << "A bipartite graph is a random group graph if the color classes \nA and B are partitiones to A_0, A_1, ..., A_{k-1} and B_0, B_1, ..., B_{k-1} \nas equally as possible \nand the edges from A_i goes to A_{i-1 mod k} and A_{i+1 mod k}.\n"; |
79 std::cout << "number of groups in LEDA random group graph="; |
77 std::cout << "number of groups in LEDA random group graph="; |
80 std::cin >> k; |
78 std::cin >> k; |
81 |
79 std::cout << std::endl; |
|
80 |
82 leda_list<leda_node> lS; |
81 leda_list<leda_node> lS; |
83 leda_list<leda_node> lT; |
82 leda_list<leda_node> lT; |
84 random_bigraph(lg, a, b, m, lS, lT, k); |
83 random_bigraph(lg, a, b, m, lS, lT, k); |
85 |
84 |
86 // for (int i=0; i<a; ++i) s_nodes.push_back(g.addNode()); |
85 Graph::NodeMap<int> ref_map(g, -1); |
87 // for (int i=0; i<b; ++i) t_nodes.push_back(g.addNode()); |
86 IterableBoolMap< Graph::NodeMap<int> > bipartite_map(ref_map); |
88 |
87 |
89 // random_init(); |
88 //generating leda random group graph |
90 // for(int i=0; i<m; ++i) { |
|
91 // g.addEdge(s_nodes[random(a)], t_nodes[random(b)]); |
|
92 // } |
|
93 |
|
94 Graph::NodeMap<int> ref_map(g, -1); |
|
95 |
|
96 IterableBoolMap< Graph::NodeMap<int> > bipartite_map(ref_map); |
|
97 // for (int i=0; i<a; ++i) bipartite_map.insert(s_nodes[i], false); |
|
98 // for (int i=0; i<b; ++i) bipartite_map.insert(t_nodes[i], true); |
|
99 leda_node ln; |
89 leda_node ln; |
100 forall(ln, lS) bipartite_map.insert(ln, false); |
90 forall(ln, lS) bipartite_map.insert(ln, false); |
101 forall(ln, lT) bipartite_map.insert(ln, true); |
91 forall(ln, lT) bipartite_map.insert(ln, true); |
102 |
92 |
|
93 //making bipartite graph |
103 typedef BipartiteGraphWrapper<Graph> BGW; |
94 typedef BipartiteGraphWrapper<Graph> BGW; |
104 BGW bgw(g, bipartite_map); |
95 BGW bgw(g, bipartite_map); |
105 |
96 |
106 // BGW::NodeMap<int> dbyj(bgw); |
|
107 // BGW::EdgeMap<int> dbyxcj(bgw); |
|
108 |
97 |
|
98 //st-wrapper |
109 typedef stGraphWrapper<BGW> stGW; |
99 typedef stGraphWrapper<BGW> stGW; |
110 stGW stgw(bgw); |
100 stGW stgw(bgw); |
111 ConstMap<stGW::Edge, int> const1map(1); |
101 ConstMap<stGW::Edge, int> const1map(1); |
112 stGW::EdgeMap<int> flow(stgw); |
102 stGW::EdgeMap<int> flow(stgw); |
113 |
103 |
114 Timer ts; |
104 Timer ts; |
|
105 |
|
106 ts.reset(); |
115 FOR_EACH_LOC(stGW::EdgeIt, e, stgw) flow.set(e, 0); |
107 FOR_EACH_LOC(stGW::EdgeIt, e, stgw) flow.set(e, 0); |
116 ts.reset(); |
108 MaxFlow<stGW, int, ConstMap<stGW::Edge, int>, stGW::EdgeMap<int> > |
117 // stGW::EdgeMap<int> pre_flow(stgw); |
109 max_flow_test(stgw, stgw.S_NODE, stgw.T_NODE, const1map, flow/*, true*/); |
118 Preflow<stGW, int, ConstMap<stGW::Edge, int>, stGW::EdgeMap<int> > |
110 max_flow_test.run(); |
119 pre_flow_test(stgw, stgw.S_NODE, stgw.T_NODE, const1map, flow/*, true*/); |
111 std::cout << "HUGO max matching algorithm based on preflow." << std::endl |
120 pre_flow_test.run(); |
112 << "Size of matching: " |
121 std::cout << "HUGO pre flow value: " << pre_flow_test.flowValue() << std::endl; |
113 << max_flow_test.flowValue() << std::endl; |
122 std::cout << "elapsed time: " << ts << std::endl; |
114 std::cout << "elapsed time: " << ts << std::endl << std::endl; |
123 // FOR_EACH_LOC(stGW::EdgeIt, e, stgw) { |
|
124 // std::cout << e << ": " << pre_flow[e] << "\n"; |
|
125 // } |
|
126 std::cout << "\n"; |
|
127 |
115 |
128 ts.reset(); |
116 ts.reset(); |
129 leda_list<leda_edge> ml=MAX_CARD_BIPARTITE_MATCHING(lg); |
117 leda_list<leda_edge> ml=MAX_CARD_BIPARTITE_MATCHING(lg); |
130 // stGW::EdgeMap<int> pre_flow(stgw); |
118 std::cout << "LEDA max matching algorithm." << std::endl |
131 //Preflow<stGW, int, ConstMap<stGW::Edge, int>, stGW::EdgeMap<int> > |
119 << "Size of matching: " |
132 // pre_flow_test(stgw, stgw.S_NODE, stgw.T_NODE, const1map, pre_flow, true); |
120 << ml.size() << std::endl; |
133 //pre_flow_test.run(); |
|
134 std::cout << "LEDA matching value: " << ml.size() << std::endl; |
|
135 std::cout << "elapsed time: " << ts << std::endl; |
121 std::cout << "elapsed time: " << ts << std::endl; |
136 // FOR_EACH_LOC(stGW::EdgeIt, e, stgw) { |
|
137 // std::cout << e << ": " << pre_flow[e] << "\n"; |
|
138 // } |
|
139 std::cout << "\n"; |
122 std::cout << "\n"; |
140 |
123 |
|
124 ts.reset(); |
141 FOR_EACH_LOC(stGW::EdgeIt, e, stgw) flow.set(e, 0); |
125 FOR_EACH_LOC(stGW::EdgeIt, e, stgw) flow.set(e, 0); |
142 ts.reset(); |
|
143 MaxFlow<stGW, int, ConstMap<stGW::Edge, int>, stGW::EdgeMap<int> > |
|
144 max_flow_test(stgw, stgw.S_NODE, stgw.T_NODE, const1map, flow); |
|
145 // while (max_flow_test.augmentOnShortestPath()) { } |
|
146 typedef ListGraph MutableGraph; |
126 typedef ListGraph MutableGraph; |
147 // while (max_flow_test.augmentOnBlockingFlow1<MutableGraph>()) { |
127 while (max_flow_test.augmentOnBlockingFlow<MutableGraph>()) { } |
148 while (max_flow_test.augmentOnBlockingFlow2()) { |
128 std::cout << "HUGO max matching algorithm based on blocking flow augmentation." |
149 std::cout << max_flow_test.flowValue() << std::endl; |
129 << std::endl << "Matching size: " |
150 } |
130 << max_flow_test.flowValue() << std::endl; |
151 std::cout << "HUGO blocking flow value: " << max_flow_test.flowValue() << std::endl; |
|
152 std::cout << "elapsed time: " << ts << std::endl; |
131 std::cout << "elapsed time: " << ts << std::endl; |
153 // FOR_EACH_LOC(stGW::EdgeIt, e, stgw) { |
|
154 // std::cout << e << ": " << max_flow[e] << "\n"; |
|
155 // } |
|
156 // std::cout << "\n"; |
|
157 |
132 |
158 return 0; |
133 return 0; |
159 } |
134 } |