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.head(e)]==max_matching.C && pos[G.tail(e)]==max_matching.D) || |
---|
194 | (pos[G.head(e)]==max_matching.D && pos[G.tail(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 | |
---|