jacint@536: ///Generates a random graph, and tests max_matching.h on it. jacint@536: #include <iostream> jacint@536: #include <queue> jacint@536: #include <math.h> jacint@536: jacint@536: #include <list_graph.h> jacint@536: #include <dimacs.h> jacint@536: #include <graph_gen.h> jacint@536: #include <max_matching.h> jacint@536: #include <time_measure.h> jacint@536: #include <graph_wrapper.h> jacint@536: alpar@921: using namespace lemon; jacint@536: jacint@536: int main(int, char **) { jacint@536: jacint@536: typedef UndirGraph<ListGraph> UGW; jacint@536: typedef UGW::Edge Edge; jacint@536: typedef UGW::EdgeIt EdgeIt; jacint@536: typedef UGW::OutEdgeIt OutEdgeIt; jacint@536: typedef UGW::NodeIt NodeIt; jacint@536: typedef UGW::Node Node; jacint@536: jacint@536: UGW G; jacint@536: jacint@536: // random_init(); //If you want to use a random graph with a random jacint@536: // number of edges and nodes. jacint@536: jacint@536: int i; jacint@536: int j; jacint@536: std::cout<<"Number of nodes: "; jacint@536: std::cin >> i; jacint@536: std::cout<<"Number of edges: "; jacint@536: std::cin >> j; jacint@536: jacint@536: // readDimacs(std::cin, G); jacint@536: randomGraph(G, i, j ); jacint@536: jacint@536: Timer ts; jacint@536: bool noerror=true; jacint@536: jacint@536: std::cout << jacint@536: "\n Testing max_matching.h on a random graph with " << jacint@536: G.nodeNum() << " nodes and " << G.edgeNum() << " edges...\n" jacint@536: << std::endl; jacint@536: MaxMatching<UGW> max_matching(G); jacint@536: jacint@536: jacint@536: std::cout << jacint@536: "Running the plain edmonds algorithm runEdmonds(0) using no heuristic... " jacint@536: <<std::endl; jacint@536: ts.reset(); jacint@536: max_matching.runEdmonds(0); jacint@536: std::cout<<"Elapsed time: "<<ts<<std::endl; jacint@536: int s=0; jacint@536: UGW::NodeMap<Node> mate(G,INVALID); jacint@536: max_matching.writeNMapNode(mate); jacint@536: NodeIt v; jacint@536: for(G.first(v); G.valid(v); G.next(v) ) { jacint@536: if ( G.valid(mate[v]) ) { jacint@536: ++s; jacint@536: } jacint@536: } jacint@536: int size=(int)s/2; //size will be used as the size of a maxmatching jacint@536: std::cout << size << " is the size of the matching found by runEdmonds(0),"<<std::endl; jacint@536: if ( size == max_matching.size() ) { jacint@536: std::cout<< "which equals to the size of the actual matching reported by size().\n"<< std::endl; jacint@536: } else { jacint@536: std::cout<< "which does not equal to the size of the actual matching reported by size()!\n"<< std::endl; jacint@536: noerror=false; jacint@536: } jacint@536: jacint@536: jacint@536: std::cout<<"Writing the position by calling writePos..."; jacint@536: UGW::NodeMap<MaxMatching<UGW>::pos_enum> pos0(G); jacint@536: max_matching.writePos(pos0); jacint@536: std::cout << "OK" << std::endl; jacint@536: jacint@536: jacint@536: std::cout << "Resetting the matching and the position by calling"<< std::endl; jacint@536: std::cout<<"resetPos() and resetMatching()..."; jacint@536: max_matching.resetPos(); jacint@536: max_matching.resetMatching(); jacint@536: std::cout <<"OK" << std::endl; jacint@536: jacint@536: jacint@536: std::cout << "\nRunning runEdmonds(1) using the 'postpone shrink' heuristic ... " <<std::endl; jacint@536: ts.reset(); jacint@536: max_matching.runEdmonds(1); jacint@536: std::cout<<"Elapsed time: "<<ts<<std::endl; jacint@536: s=0; jacint@536: max_matching.writeNMapNode(mate); jacint@536: for(G.first(v); G.valid(v); G.next(v) ) { jacint@536: if ( G.valid(mate[v]) ) { jacint@536: ++s; jacint@536: } jacint@536: } jacint@536: std::cout << (int)s/2 << jacint@536: " is the size of the matching found by runEdmonds(1),"<<std::endl; jacint@536: if ( (int)s/2 == size ) { jacint@536: std::cout<< "which equals to the size of the matching found by runEdmonds(0)."<< std::endl; jacint@536: } else { jacint@536: std::cout<< "which does not equal to the size of the matching found by runEdmonds(0)!"<< std::endl; jacint@536: noerror=false; jacint@536: } jacint@536: UGW::NodeMap<MaxMatching<UGW>::pos_enum> pos1(G); jacint@536: max_matching.writePos(pos1); jacint@536: jacint@536: jacint@536: std::cout << "\nStarting run() from the matching given by runEdmonds(1)... " <<std::endl; jacint@536: max_matching.resetPos(); jacint@536: ts.reset(); jacint@536: max_matching.run(); jacint@536: std::cout<<"Elapsed time: "<<ts<<std::endl; jacint@536: s=0; jacint@536: max_matching.writeNMapNode(mate); jacint@536: for(G.first(v); G.valid(v); G.next(v) ) { jacint@536: if ( G.valid(mate[v]) ) { jacint@536: ++s; jacint@536: } jacint@536: } jacint@536: if ( (int)s/2 == size ) { jacint@536: std::cout<< "Found a matching of proper size."<< std::endl; jacint@536: } else { jacint@536: std::cout<< "Found a matching of inproper size!"<< std::endl; jacint@536: noerror=false; jacint@536: } jacint@536: UGW::NodeMap<MaxMatching<UGW>::pos_enum> pos2(G); jacint@536: max_matching.writePos(pos2); jacint@536: jacint@536: jacint@536: std::cout << "\nCalling resetPos() and resetMatching()..."; jacint@536: max_matching.resetPos(); jacint@536: max_matching.resetMatching(); jacint@536: std::cout<<"OK"<<std::endl; jacint@536: std::cout <<"Calling greedyMatching() and then runEdmonds(1)... " <<std::endl; jacint@536: ts.reset(); jacint@536: max_matching.run(); jacint@536: std::cout<<"Elapsed time: "<<ts<<std::endl; jacint@536: s=0; jacint@536: max_matching.writeNMapNode(mate); jacint@536: for(G.first(v); G.valid(v); G.next(v) ) { jacint@536: if ( G.valid(mate[v]) ) { jacint@536: ++s; jacint@536: } jacint@536: } jacint@536: std::cout << (int)s/2 << " is the size of the matching found by run(),"<<std::endl; jacint@536: if ( (int)s/2 == size ) { jacint@536: std::cout<< "which equals to the size of the matching found by runEdmonds(0)."<< std::endl; jacint@536: } else { jacint@536: std::cout<< "which does not equal to the size of the matching found by runEdmonds(0)!"<< std::endl; jacint@536: noerror=false; jacint@536: } jacint@536: UGW::NodeMap<MaxMatching<UGW>::pos_enum> pos(G); jacint@536: max_matching.writePos(pos); jacint@536: jacint@536: jacint@536: std::cout<<"\nChecking if the output is a matching..."; jacint@536: bool ismatching=true; jacint@536: for(G.first(v); G.valid(v); G.next(v) ) jacint@536: if ( G.valid(mate[v]) ) { jacint@536: Node u=mate[v]; jacint@536: if (mate[u]!=v) ismatching=false; jacint@536: } jacint@536: if ( ismatching ) std::cout<<"OK"<<std::endl; jacint@536: else std::cout<< "It is not a matching!"<< std::endl; jacint@536: noerror = noerror && ismatching; jacint@536: jacint@536: jacint@536: std::cout<<"\nChecking the dual..."<<std::endl; jacint@536: jacint@536: std::cout<<"Checking if the four position outputs coincide..."; jacint@536: bool coincide=true; jacint@536: int err_node=0; jacint@536: for(G.first(v); G.valid(v); G.next(v) ) { jacint@536: if ( pos0[v] != pos1[v] || pos1[v]!=pos2[v] || pos2[v]!=pos[v] ) { jacint@536: ++err_node; jacint@536: coincide=false; jacint@536: } jacint@536: } jacint@536: if ( coincide ) std::cout << "OK" <<std::endl; jacint@536: else { jacint@536: std::cout << "They do not coincide! Number of erroneous nodes: " jacint@536: << err_node << std::endl; jacint@536: } jacint@536: noerror=noerror && coincide; jacint@536: jacint@536: jacint@536: std::cout<<"Checking if there is no edge between D and C..."; jacint@536: bool noedge=true; jacint@536: EdgeIt e; jacint@536: for(G.first(e); G.valid(e); G.next(e) ) { alpar@986: if ( (pos[G.target(e)]==max_matching.C && pos[G.source(e)]==max_matching.D) || alpar@986: (pos[G.target(e)]==max_matching.D && pos[G.source(e)]==max_matching.C) ) jacint@536: noedge=false; jacint@536: } jacint@536: if ( noedge ) std::cout<<"OK"<<std::endl; jacint@536: else std::cout<< "There are edges between D and C!"<< std::endl; jacint@536: noerror = noerror && noedge; jacint@536: jacint@536: jacint@536: std::cout<<"Checking if all the components of G[D] are odd..."; jacint@536: bool oddcomp=true; jacint@536: UGW::NodeMap<bool> todo(G,true); jacint@536: int num_comp=0; jacint@536: for(G.first(v); G.valid(v); G.next(v) ) { jacint@536: if ( pos[v]==max_matching.D && todo[v] ) { jacint@536: int comp_size=1; jacint@536: ++num_comp; jacint@536: std::queue<Node> Q; jacint@536: Q.push(v); jacint@536: todo.set(v,false); jacint@536: while (!Q.empty()) { jacint@536: Node w=Q.front(); jacint@536: Q.pop(); jacint@536: OutEdgeIt e; jacint@536: for(G.first(e,w); G.valid(e); G.next(e)) { jacint@536: Node u=G.bNode(e); jacint@536: if ( pos[u]==max_matching.D && todo[u] ) { jacint@536: ++comp_size; jacint@536: Q.push(u); jacint@536: todo.set(u,false); jacint@536: } jacint@536: } jacint@536: } jacint@536: if ( !(comp_size % 2) ) oddcomp=false; jacint@536: } jacint@536: } jacint@536: std::cout << "\n found " << num_comp << " component(s) of G[D],"; jacint@536: if ( oddcomp ) std::cout<<" each is odd."<<std::endl; jacint@536: else std::cout<< " but not all are odd!"<< std::endl; jacint@536: noerror = noerror && oddcomp; jacint@536: jacint@536: jacint@536: int barrier=0; jacint@536: for(G.first(v); G.valid(v); G.next(v) ) jacint@536: if ( pos[v]==max_matching.A ) ++barrier; jacint@536: std::cout << barrier << " is the number of nodes in A (i.e. the size of the barrier), so" << std::endl; jacint@536: std::cout << num_comp - barrier << " is the deficiency of the graph, and hence" << std::endl; jacint@536: int expected_size=(int)(G.nodeNum()-num_comp+barrier)/2; jacint@536: std::cout << expected_size << " should be the size of the maximum matching," << std::endl; jacint@536: if ( size==expected_size ) jacint@536: std::cout<<"which equals to the number of vertices missed by the found matching!"<<std::endl; jacint@536: else { jacint@536: std::cout<<"which does not equal to the number of vertices missed by the matchings found!" jacint@536: <<std::endl; jacint@536: noerror=false; jacint@536: } jacint@536: jacint@536: jacint@536: if ( num_comp == 1 && barrier == 0 ) jacint@536: std::cout<<"\nThis graph is factor-critical."<<std::endl; jacint@536: if ( num_comp == 0 && barrier == 0 ) jacint@536: std::cout<<"\nThis graph has a perfect matching."<<std::endl; jacint@536: jacint@536: jacint@536: if( noerror ) std::cout<<"\nNo errors found.\n"<<std::endl; jacint@536: else std::cout<<"\nSome errors found!\n"<<std::endl; jacint@536: jacint@536: return 0; jacint@536: } jacint@536: jacint@536: jacint@536: jacint@536: jacint@536: jacint@536: jacint@536: jacint@536: jacint@536: