Concept modification to resolve the item by its ID.
1 ///Generates a random graph, and tests max_matching.h on it.
6 #include <list_graph.h>
9 #include <max_matching.h>
10 #include <time_measure.h>
11 #include <graph_wrapper.h>
13 using namespace lemon;
15 int main(int, char **) {
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;
26 // random_init(); //If you want to use a random graph with a random
27 // number of edges and nodes.
31 std::cout<<"Number of nodes: ";
33 std::cout<<"Number of edges: ";
36 // readDimacs(std::cin, G);
37 randomGraph(G, i, j );
43 "\n Testing max_matching.h on a random graph with " <<
44 G.nodeNum() << " nodes and " << G.edgeNum() << " edges...\n"
46 MaxMatching<UGW> max_matching(G);
50 "Running the plain edmonds algorithm runEdmonds(0) using no heuristic... "
53 max_matching.runEdmonds(0);
54 std::cout<<"Elapsed time: "<<ts<<std::endl;
56 UGW::NodeMap<Node> mate(G,INVALID);
57 max_matching.writeNMapNode(mate);
59 for(G.first(v); G.valid(v); G.next(v) ) {
60 if ( G.valid(mate[v]) ) {
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;
69 std::cout<< "which does not equal to the size of the actual matching reported by size()!\n"<< std::endl;
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;
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;
87 std::cout << "\nRunning runEdmonds(1) using the 'postpone shrink' heuristic ... " <<std::endl;
89 max_matching.runEdmonds(1);
90 std::cout<<"Elapsed time: "<<ts<<std::endl;
92 max_matching.writeNMapNode(mate);
93 for(G.first(v); G.valid(v); G.next(v) ) {
94 if ( G.valid(mate[v]) ) {
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;
103 std::cout<< "which does not equal to the size of the matching found by runEdmonds(0)!"<< std::endl;
106 UGW::NodeMap<MaxMatching<UGW>::pos_enum> pos1(G);
107 max_matching.writePos(pos1);
110 std::cout << "\nStarting run() from the matching given by runEdmonds(1)... " <<std::endl;
111 max_matching.resetPos();
114 std::cout<<"Elapsed time: "<<ts<<std::endl;
116 max_matching.writeNMapNode(mate);
117 for(G.first(v); G.valid(v); G.next(v) ) {
118 if ( G.valid(mate[v]) ) {
122 if ( (int)s/2 == size ) {
123 std::cout<< "Found a matching of proper size."<< std::endl;
125 std::cout<< "Found a matching of inproper size!"<< std::endl;
128 UGW::NodeMap<MaxMatching<UGW>::pos_enum> pos2(G);
129 max_matching.writePos(pos2);
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;
139 std::cout<<"Elapsed time: "<<ts<<std::endl;
141 max_matching.writeNMapNode(mate);
142 for(G.first(v); G.valid(v); G.next(v) ) {
143 if ( G.valid(mate[v]) ) {
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;
151 std::cout<< "which does not equal to the size of the matching found by runEdmonds(0)!"<< std::endl;
154 UGW::NodeMap<MaxMatching<UGW>::pos_enum> pos(G);
155 max_matching.writePos(pos);
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]) ) {
163 if (mate[u]!=v) ismatching=false;
165 if ( ismatching ) std::cout<<"OK"<<std::endl;
166 else std::cout<< "It is not a matching!"<< std::endl;
167 noerror = noerror && ismatching;
170 std::cout<<"\nChecking the dual..."<<std::endl;
172 std::cout<<"Checking if the four position outputs coincide...";
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] ) {
181 if ( coincide ) std::cout << "OK" <<std::endl;
183 std::cout << "They do not coincide! Number of erroneous nodes: "
184 << err_node << std::endl;
186 noerror=noerror && coincide;
189 std::cout<<"Checking if there is no edge between D and C...";
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) )
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;
202 std::cout<<"Checking if all the components of G[D] are odd...";
204 UGW::NodeMap<bool> todo(G,true);
206 for(G.first(v); G.valid(v); G.next(v) ) {
207 if ( pos[v]==max_matching.D && todo[v] ) {
217 for(G.first(e,w); G.valid(e); G.next(e)) {
219 if ( pos[u]==max_matching.D && todo[u] ) {
226 if ( !(comp_size % 2) ) oddcomp=false;
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;
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;
245 std::cout<<"which does not equal to the number of vertices missed by the matchings found!"
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;
257 if( noerror ) std::cout<<"\nNo errors found.\n"<<std::endl;
258 else std::cout<<"\nSome errors found!\n"<<std::endl;