1 ///Generates a random graph, and tests max_matching.h on it. |
|
2 #include <iostream> |
|
3 #include <queue> |
|
4 #include <math.h> |
|
5 |
|
6 #include <list_graph.h> |
|
7 #include <dimacs.h> |
|
8 #include <graph_gen.h> |
|
9 #include <max_matching.h> |
|
10 #include <time_measure.h> |
|
11 #include <graph_wrapper.h> |
|
12 |
|
13 using namespace lemon; |
|
14 |
|
15 int main(int, char **) { |
|
16 |
|
17 typedef UndirGraph<ListGraph> UGW; |
|
18 typedef UGW::Edge Edge; |
|
19 typedef UGW::EdgeIt EdgeIt; |
|
20 typedef UGW::OutEdgeIt OutEdgeIt; |
|
21 typedef UGW::NodeIt NodeIt; |
|
22 typedef UGW::Node Node; |
|
23 |
|
24 UGW G; |
|
25 |
|
26 // random_init(); //If you want to use a random graph with a random |
|
27 // number of edges and nodes. |
|
28 |
|
29 int i; |
|
30 int j; |
|
31 std::cout<<"Number of nodes: "; |
|
32 std::cin >> i; |
|
33 std::cout<<"Number of edges: "; |
|
34 std::cin >> j; |
|
35 |
|
36 // readDimacs(std::cin, G); |
|
37 randomGraph(G, i, j ); |
|
38 |
|
39 Timer ts; |
|
40 bool noerror=true; |
|
41 |
|
42 std::cout << |
|
43 "\n Testing max_matching.h on a random graph with " << |
|
44 G.nodeNum() << " nodes and " << G.edgeNum() << " edges...\n" |
|
45 << std::endl; |
|
46 MaxMatching<UGW> max_matching(G); |
|
47 |
|
48 |
|
49 std::cout << |
|
50 "Running the plain edmonds algorithm runEdmonds(0) using no heuristic... " |
|
51 <<std::endl; |
|
52 ts.reset(); |
|
53 max_matching.runEdmonds(0); |
|
54 std::cout<<"Elapsed time: "<<ts<<std::endl; |
|
55 int s=0; |
|
56 UGW::NodeMap<Node> mate(G,INVALID); |
|
57 max_matching.writeNMapNode(mate); |
|
58 NodeIt v; |
|
59 for(G.first(v); G.valid(v); G.next(v) ) { |
|
60 if ( G.valid(mate[v]) ) { |
|
61 ++s; |
|
62 } |
|
63 } |
|
64 int size=(int)s/2; //size will be used as the size of a maxmatching |
|
65 std::cout << size << " is the size of the matching found by runEdmonds(0),"<<std::endl; |
|
66 if ( size == max_matching.size() ) { |
|
67 std::cout<< "which equals to the size of the actual matching reported by size().\n"<< std::endl; |
|
68 } else { |
|
69 std::cout<< "which does not equal to the size of the actual matching reported by size()!\n"<< std::endl; |
|
70 noerror=false; |
|
71 } |
|
72 |
|
73 |
|
74 std::cout<<"Writing the position by calling writePos..."; |
|
75 UGW::NodeMap<MaxMatching<UGW>::pos_enum> pos0(G); |
|
76 max_matching.writePos(pos0); |
|
77 std::cout << "OK" << std::endl; |
|
78 |
|
79 |
|
80 std::cout << "Resetting the matching and the position by calling"<< std::endl; |
|
81 std::cout<<"resetPos() and resetMatching()..."; |
|
82 max_matching.resetPos(); |
|
83 max_matching.resetMatching(); |
|
84 std::cout <<"OK" << std::endl; |
|
85 |
|
86 |
|
87 std::cout << "\nRunning runEdmonds(1) using the 'postpone shrink' heuristic ... " <<std::endl; |
|
88 ts.reset(); |
|
89 max_matching.runEdmonds(1); |
|
90 std::cout<<"Elapsed time: "<<ts<<std::endl; |
|
91 s=0; |
|
92 max_matching.writeNMapNode(mate); |
|
93 for(G.first(v); G.valid(v); G.next(v) ) { |
|
94 if ( G.valid(mate[v]) ) { |
|
95 ++s; |
|
96 } |
|
97 } |
|
98 std::cout << (int)s/2 << |
|
99 " is the size of the matching found by runEdmonds(1),"<<std::endl; |
|
100 if ( (int)s/2 == size ) { |
|
101 std::cout<< "which equals to the size of the matching found by runEdmonds(0)."<< std::endl; |
|
102 } else { |
|
103 std::cout<< "which does not equal to the size of the matching found by runEdmonds(0)!"<< std::endl; |
|
104 noerror=false; |
|
105 } |
|
106 UGW::NodeMap<MaxMatching<UGW>::pos_enum> pos1(G); |
|
107 max_matching.writePos(pos1); |
|
108 |
|
109 |
|
110 std::cout << "\nStarting run() from the matching given by runEdmonds(1)... " <<std::endl; |
|
111 max_matching.resetPos(); |
|
112 ts.reset(); |
|
113 max_matching.run(); |
|
114 std::cout<<"Elapsed time: "<<ts<<std::endl; |
|
115 s=0; |
|
116 max_matching.writeNMapNode(mate); |
|
117 for(G.first(v); G.valid(v); G.next(v) ) { |
|
118 if ( G.valid(mate[v]) ) { |
|
119 ++s; |
|
120 } |
|
121 } |
|
122 if ( (int)s/2 == size ) { |
|
123 std::cout<< "Found a matching of proper size."<< std::endl; |
|
124 } else { |
|
125 std::cout<< "Found a matching of inproper size!"<< std::endl; |
|
126 noerror=false; |
|
127 } |
|
128 UGW::NodeMap<MaxMatching<UGW>::pos_enum> pos2(G); |
|
129 max_matching.writePos(pos2); |
|
130 |
|
131 |
|
132 std::cout << "\nCalling resetPos() and resetMatching()..."; |
|
133 max_matching.resetPos(); |
|
134 max_matching.resetMatching(); |
|
135 std::cout<<"OK"<<std::endl; |
|
136 std::cout <<"Calling greedyMatching() and then runEdmonds(1)... " <<std::endl; |
|
137 ts.reset(); |
|
138 max_matching.run(); |
|
139 std::cout<<"Elapsed time: "<<ts<<std::endl; |
|
140 s=0; |
|
141 max_matching.writeNMapNode(mate); |
|
142 for(G.first(v); G.valid(v); G.next(v) ) { |
|
143 if ( G.valid(mate[v]) ) { |
|
144 ++s; |
|
145 } |
|
146 } |
|
147 std::cout << (int)s/2 << " is the size of the matching found by run(),"<<std::endl; |
|
148 if ( (int)s/2 == size ) { |
|
149 std::cout<< "which equals to the size of the matching found by runEdmonds(0)."<< std::endl; |
|
150 } else { |
|
151 std::cout<< "which does not equal to the size of the matching found by runEdmonds(0)!"<< std::endl; |
|
152 noerror=false; |
|
153 } |
|
154 UGW::NodeMap<MaxMatching<UGW>::pos_enum> pos(G); |
|
155 max_matching.writePos(pos); |
|
156 |
|
157 |
|
158 std::cout<<"\nChecking if the output is a matching..."; |
|
159 bool ismatching=true; |
|
160 for(G.first(v); G.valid(v); G.next(v) ) |
|
161 if ( G.valid(mate[v]) ) { |
|
162 Node u=mate[v]; |
|
163 if (mate[u]!=v) ismatching=false; |
|
164 } |
|
165 if ( ismatching ) std::cout<<"OK"<<std::endl; |
|
166 else std::cout<< "It is not a matching!"<< std::endl; |
|
167 noerror = noerror && ismatching; |
|
168 |
|
169 |
|
170 std::cout<<"\nChecking the dual..."<<std::endl; |
|
171 |
|
172 std::cout<<"Checking if the four position outputs coincide..."; |
|
173 bool coincide=true; |
|
174 int err_node=0; |
|
175 for(G.first(v); G.valid(v); G.next(v) ) { |
|
176 if ( pos0[v] != pos1[v] || pos1[v]!=pos2[v] || pos2[v]!=pos[v] ) { |
|
177 ++err_node; |
|
178 coincide=false; |
|
179 } |
|
180 } |
|
181 if ( coincide ) std::cout << "OK" <<std::endl; |
|
182 else { |
|
183 std::cout << "They do not coincide! Number of erroneous nodes: " |
|
184 << err_node << std::endl; |
|
185 } |
|
186 noerror=noerror && coincide; |
|
187 |
|
188 |
|
189 std::cout<<"Checking if there is no edge between D and C..."; |
|
190 bool noedge=true; |
|
191 EdgeIt e; |
|
192 for(G.first(e); G.valid(e); G.next(e) ) { |
|
193 if ( (pos[G.target(e)]==max_matching.C && pos[G.source(e)]==max_matching.D) || |
|
194 (pos[G.target(e)]==max_matching.D && pos[G.source(e)]==max_matching.C) ) |
|
195 noedge=false; |
|
196 } |
|
197 if ( noedge ) std::cout<<"OK"<<std::endl; |
|
198 else std::cout<< "There are edges between D and C!"<< std::endl; |
|
199 noerror = noerror && noedge; |
|
200 |
|
201 |
|
202 std::cout<<"Checking if all the components of G[D] are odd..."; |
|
203 bool oddcomp=true; |
|
204 UGW::NodeMap<bool> todo(G,true); |
|
205 int num_comp=0; |
|
206 for(G.first(v); G.valid(v); G.next(v) ) { |
|
207 if ( pos[v]==max_matching.D && todo[v] ) { |
|
208 int comp_size=1; |
|
209 ++num_comp; |
|
210 std::queue<Node> Q; |
|
211 Q.push(v); |
|
212 todo.set(v,false); |
|
213 while (!Q.empty()) { |
|
214 Node w=Q.front(); |
|
215 Q.pop(); |
|
216 OutEdgeIt e; |
|
217 for(G.first(e,w); G.valid(e); G.next(e)) { |
|
218 Node u=G.bNode(e); |
|
219 if ( pos[u]==max_matching.D && todo[u] ) { |
|
220 ++comp_size; |
|
221 Q.push(u); |
|
222 todo.set(u,false); |
|
223 } |
|
224 } |
|
225 } |
|
226 if ( !(comp_size % 2) ) oddcomp=false; |
|
227 } |
|
228 } |
|
229 std::cout << "\n found " << num_comp << " component(s) of G[D],"; |
|
230 if ( oddcomp ) std::cout<<" each is odd."<<std::endl; |
|
231 else std::cout<< " but not all are odd!"<< std::endl; |
|
232 noerror = noerror && oddcomp; |
|
233 |
|
234 |
|
235 int barrier=0; |
|
236 for(G.first(v); G.valid(v); G.next(v) ) |
|
237 if ( pos[v]==max_matching.A ) ++barrier; |
|
238 std::cout << barrier << " is the number of nodes in A (i.e. the size of the barrier), so" << std::endl; |
|
239 std::cout << num_comp - barrier << " is the deficiency of the graph, and hence" << std::endl; |
|
240 int expected_size=(int)(G.nodeNum()-num_comp+barrier)/2; |
|
241 std::cout << expected_size << " should be the size of the maximum matching," << std::endl; |
|
242 if ( size==expected_size ) |
|
243 std::cout<<"which equals to the number of vertices missed by the found matching!"<<std::endl; |
|
244 else { |
|
245 std::cout<<"which does not equal to the number of vertices missed by the matchings found!" |
|
246 <<std::endl; |
|
247 noerror=false; |
|
248 } |
|
249 |
|
250 |
|
251 if ( num_comp == 1 && barrier == 0 ) |
|
252 std::cout<<"\nThis graph is factor-critical."<<std::endl; |
|
253 if ( num_comp == 0 && barrier == 0 ) |
|
254 std::cout<<"\nThis graph has a perfect matching."<<std::endl; |
|
255 |
|
256 |
|
257 if( noerror ) std::cout<<"\nNo errors found.\n"<<std::endl; |
|
258 else std::cout<<"\nSome errors found!\n"<<std::endl; |
|
259 |
|
260 return 0; |
|
261 } |
|
262 |
|
263 |
|
264 |
|
265 |
|
266 |
|
267 |
|
268 |
|
269 |
|
270 |
|