89 // G.addEdge(s_nodes[1], t_nodes[4-4]); |
89 // G.addEdge(s_nodes[1], t_nodes[4-4]); |
90 // G.addEdge(s_nodes[1], t_nodes[4-4]); |
90 // G.addEdge(s_nodes[1], t_nodes[4-4]); |
91 // G.addEdge(s_nodes[2], t_nodes[4-4]); |
91 // G.addEdge(s_nodes[2], t_nodes[4-4]); |
92 // G.addEdge(s_nodes[3], t_nodes[4-4]); |
92 // G.addEdge(s_nodes[3], t_nodes[4-4]); |
93 |
93 |
94 |
94 leda_list<leda_node> A; |
|
95 leda_list<leda_node> B; |
95 Graph::NodeMap<bool> s_map(G); //false |
96 Graph::NodeMap<bool> s_map(G); //false |
96 Graph::NodeMap<bool> t_map(G); //false |
97 Graph::NodeMap<bool> t_map(G); //false |
97 |
98 |
98 for(int i=0; i<a; ++i) s_map.set(s_nodes[i], true); |
99 for(int i=0; i<a; ++i) { s_map.set(s_nodes[i], true); A+=s_nodes[i]; } |
99 for(int i=0; i<b; ++i) t_map.set(t_nodes[i], true); |
100 for(int i=0; i<b; ++i) { t_map.set(t_nodes[i], true); B+=t_nodes[i]; } |
100 |
101 |
101 // cout << "bfs and dfs iterator demo on the directed graph" << endl; |
102 // 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 // for(NodeIt n=G.first<NodeIt>(); G.valid(n); G.next(n)) { |
103 // cout << G.id(n) << ": "; |
104 // cout << G.id(n) << ": "; |
104 // cout << "out edges: "; |
105 // cout << "out edges: "; |
142 std::cout << "elapsed time: " << ts << std::endl; |
143 std::cout << "elapsed time: " << ts << std::endl; |
143 std::cout << "number of augmentation phases: " << i << std::endl; |
144 std::cout << "number of augmentation phases: " << i << std::endl; |
144 std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl; |
145 std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl; |
145 } |
146 } |
146 |
147 |
147 { |
148 // { |
148 std::cout << "on-the-fly max bipartite matching demo (Hopcroft-Karp) on wrapped leda graph..." << std::endl; |
149 // std::cout << "on-the-fly max bipartite matching demo (Hopcroft-Karp) on wrapped leda graph..." << std::endl; |
149 Graph::EdgeMap<int> flow(G); //0 flow |
150 // Graph::EdgeMap<int> flow(G); //0 flow |
150 Graph::EdgeMap<int> cap(G, 1); |
151 // Graph::EdgeMap<int> cap(G, 1); |
151 |
152 |
152 Timer ts; |
153 // Timer ts; |
153 ts.reset(); |
154 // ts.reset(); |
154 |
155 |
155 MaxMatching<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> > max_flow_test(G, s_map, t_map, flow, cap); |
156 // MaxMatching<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> > max_flow_test(G, s_map, t_map, flow, cap); |
156 int i=0; |
157 // int i=0; |
157 while (max_flow_test.augmentOnBlockingFlow2()) { |
158 // while (max_flow_test.augmentOnBlockingFlow2()) { |
158 // for(EdgeIt e=G.first<EdgeIt>(); G.valid(e); G.next(e)) |
159 // // 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 << G.id(G.tail(e)) << "-" << flow.get(e) << "->" << G.id(G.head(e)) << " "; |
160 // std::cout<<std::endl; |
161 // // std::cout<<std::endl; |
161 ++i; |
162 // ++i; |
162 } |
163 // } |
163 |
164 |
164 // std::cout << "maximum matching: "<< std::endl; |
165 // // std::cout << "maximum matching: "<< std::endl; |
165 // for(EdgeIt e=G.first<EdgeIt>(); G.valid(e); G.next(e)) |
166 // // for(EdgeIt e=G.first<EdgeIt>(); G.valid(e); G.next(e)) |
166 // if (flow.get(e)) |
167 // // if (flow.get(e)) |
167 // std::cout << G.id(G.tail(e)) << "-" << flow.get(e) << "->" << G.id(G.head(e)) << " "; |
168 // // std::cout << G.id(G.tail(e)) << "-" << flow.get(e) << "->" << G.id(G.head(e)) << " "; |
168 // std::cout<<std::endl; |
169 // // std::cout<<std::endl; |
169 // std::cout << "edges which are not in this maximum matching: "<< std::endl; |
170 // // 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 // // for(EdgeIt e=G.first<EdgeIt>(); G.valid(e); G.next(e)) |
171 // if (!flow.get(e)) |
172 // // if (!flow.get(e)) |
172 // std::cout << G.id(G.tail(e)) << "-" << flow.get(e) << "->" << G.id(G.head(e)) << " "; |
173 // // std::cout << G.id(G.tail(e)) << "-" << flow.get(e) << "->" << G.id(G.head(e)) << " "; |
173 // std::cout<<std::endl; |
174 // // std::cout<<std::endl; |
174 |
175 |
175 std::cout << "elapsed time: " << ts << std::endl; |
176 // std::cout << "elapsed time: " << ts << std::endl; |
176 std::cout << "number of augmentation phases: " << i << std::endl; |
177 // std::cout << "number of augmentation phases: " << i << std::endl; |
177 std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl; |
178 // std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl; |
178 } |
179 // } |
179 |
180 |
180 { |
181 { |
181 std::cout << "max bipartite matching (LEDA)..." << std::endl; |
182 std::cout << "max bipartite matching (LEDA)..." << std::endl; |
182 //Graph::EdgeMap<int> flow(G); //0 flow |
183 //Graph::EdgeMap<int> flow(G); //0 flow |
183 //Graph::EdgeMap<int> cap(G, 1); |
184 //Graph::EdgeMap<int> cap(G, 1); |
184 |
185 |
|
186 leda_node_array<bool> NC(g); |
|
187 |
185 Timer ts; |
188 Timer ts; |
186 ts.reset(); |
189 ts.reset(); |
187 |
190 |
188 //MaxMatching<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> > max_flow_test(G, s_map, t_map, flow, cap); |
191 //MaxMatching<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> > max_flow_test(G, s_map, t_map, flow, cap); |
189 //int i=0; |
192 //int i=0; |
190 //while (max_flow_test.augmentOnShortestPath()) { ++i; } |
193 //while (max_flow_test.augmentOnShortestPath()) { ++i; } |
191 |
194 |
|
195 //leda_list<leda_edge> l=MAX_CARD_BIPARTITE_MATCHING_HK(g, A, B, NC, false); |
192 leda_list<leda_edge> l=MAX_CARD_BIPARTITE_MATCHING(g); |
196 leda_list<leda_edge> l=MAX_CARD_BIPARTITE_MATCHING(g); |
193 |
197 |
194 |
198 |
195 // std::cout << "maximum matching: "<< std::endl; |
199 // std::cout << "maximum matching: "<< std::endl; |
196 // for(EdgeIt e=G.first<EdgeIt>(); G.valid(e); G.next(e)) |
200 // for(EdgeIt e=G.first<EdgeIt>(); G.valid(e); G.next(e)) |