1 // -*- c++ -*- |
|
2 #include <iostream> |
|
3 #include <fstream> |
|
4 #include <vector> |
|
5 #include <cstdlib> |
|
6 |
|
7 #include <LEDA/graph.h> |
|
8 #include <LEDA/mcb_matching.h> |
|
9 #include <LEDA/list.h> |
|
10 |
|
11 #include <leda_graph_wrapper.h> |
|
12 #include <sage_graph.h> |
|
13 #include <dimacs.h> |
|
14 #include <time_measure.h> |
|
15 #include <edmonds_karp.h> |
|
16 |
|
17 /** |
|
18 * Inicializalja a veletlenszamgeneratort. |
|
19 * Figyelem, ez nem jo igazi random szamokhoz, |
|
20 * erre ne bizzad a titkaidat! |
|
21 */ |
|
22 void random_init() |
|
23 { |
|
24 unsigned int seed = getpid(); |
|
25 seed |= seed << 15; |
|
26 seed ^= time(0); |
|
27 |
|
28 srand(seed); |
|
29 } |
|
30 |
|
31 /** |
|
32 * Egy veletlen int-et ad vissza 0 es m-1 kozott. |
|
33 */ |
|
34 int random(int m) |
|
35 { |
|
36 return int( double(m) * rand() / (RAND_MAX + 1.0) ); |
|
37 } |
|
38 |
|
39 using namespace hugo; |
|
40 |
|
41 using std::cout; |
|
42 using std::cin; |
|
43 using std::endl; |
|
44 |
|
45 int main() { |
|
46 leda::graph g; |
|
47 typedef LedaGraphWrapper<leda::graph> Graph; |
|
48 Graph G(g); |
|
49 // typedef ListGraph Graph; |
|
50 // Graph G; |
|
51 |
|
52 typedef Graph::Node Node; |
|
53 typedef Graph::NodeIt NodeIt; |
|
54 typedef Graph::Edge Edge; |
|
55 typedef Graph::EdgeIt EdgeIt; |
|
56 typedef Graph::OutEdgeIt OutEdgeIt; |
|
57 typedef Graph::InEdgeIt InEdgeIt; |
|
58 |
|
59 //Node s, t; |
|
60 //Graph::EdgeMap<int> cap(G); |
|
61 //readDimacsMaxFlow(std::cin, G, s, t, cap); |
|
62 std::vector<Node> s_nodes; |
|
63 std::vector<Node> t_nodes; |
|
64 |
|
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 for(int i=0; i<a; ++i) { |
|
76 s_nodes.push_back(G.addNode()); |
|
77 } |
|
78 for(int i=0; i<a; ++i) { |
|
79 t_nodes.push_back(G.addNode()); |
|
80 } |
|
81 random_init(); |
|
82 for(int i=0; i<m; ++i) { |
|
83 G.addEdge(s_nodes[random(a)], t_nodes[random(b)]); |
|
84 } |
|
85 |
|
86 // G.addEdge(s_nodes[1], t_nodes[5-4]); |
|
87 // G.addEdge(s_nodes[1], t_nodes[5-4]); |
|
88 // G.addEdge(s_nodes[1], t_nodes[4-4]); |
|
89 // G.addEdge(s_nodes[1], t_nodes[4-4]); |
|
90 // G.addEdge(s_nodes[2], t_nodes[4-4]); |
|
91 // G.addEdge(s_nodes[3], t_nodes[4-4]); |
|
92 |
|
93 leda_list<leda_node> A; |
|
94 leda_list<leda_node> B; |
|
95 Graph::NodeMap<bool> s_map(G); //false |
|
96 Graph::NodeMap<bool> t_map(G); //false |
|
97 |
|
98 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); B+=t_nodes[i]; } |
|
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 // } |
|
112 |
|
113 |
|
114 { |
|
115 std::cout << "on-the-fly max bipartite matching (Edmonds-Karp) demo on wrapped leda graph..." << std::endl; |
|
116 Graph::EdgeMap<int> flow(G); //0 flow |
|
117 Graph::EdgeMap<int> cap(G, 1); |
|
118 |
|
119 Timer ts; |
|
120 ts.reset(); |
|
121 |
|
122 MaxMatching<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> > max_flow_test(G, s_map, t_map, flow, cap); |
|
123 int i=0; |
|
124 while (max_flow_test.augmentOnShortestPath()) { |
|
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; |
|
128 ++i; |
|
129 } |
|
130 |
|
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; |
|
141 |
|
142 std::cout << "elapsed time: " << ts << std::endl; |
|
143 std::cout << "number of augmentation phases: " << i << std::endl; |
|
144 std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl; |
|
145 } |
|
146 |
|
147 // { |
|
148 // 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> 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 leda_node_array<bool> NC(g); |
|
186 |
|
187 Timer ts; |
|
188 ts.reset(); |
|
189 |
|
190 //MaxMatching<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> > max_flow_test(G, s_map, t_map, flow, cap); |
|
191 //int i=0; |
|
192 //while (max_flow_test.augmentOnShortestPath()) { ++i; } |
|
193 |
|
194 //leda_list<leda_edge> l=MAX_CARD_BIPARTITE_MATCHING_HK(g, A, B, NC, false); |
|
195 leda_list<leda_edge> l=MAX_CARD_BIPARTITE_MATCHING(g); |
|
196 |
|
197 |
|
198 // std::cout << "maximum matching: "<< std::endl; |
|
199 // for(EdgeIt e=G.first<EdgeIt>(); G.valid(e); G.next(e)) |
|
200 // if (flow.get(e)) |
|
201 // std::cout << G.id(G.tail(e)) << "-" << flow.get(e) << "->" << G.id(G.head(e)) << " "; |
|
202 // std::cout<<std::endl; |
|
203 // std::cout << "edges which are not in this maximum matching: "<< std::endl; |
|
204 // for(EdgeIt e=G.first<EdgeIt>(); G.valid(e); G.next(e)) |
|
205 // if (!flow.get(e)) |
|
206 // std::cout << G.id(G.tail(e)) << "-" << flow.get(e) << "->" << G.id(G.head(e)) << " "; |
|
207 // std::cout<<std::endl; |
|
208 |
|
209 |
|
210 std::cout << "elapsed time: " << ts << std::endl; |
|
211 //std::cout << "number of augmentation phases: " << i << std::endl; |
|
212 std::cout << "flow value: "<< l.size() << std::endl; |
|
213 } |
|
214 |
|
215 |
|
216 |
|
217 return 0; |
|
218 } |
|