1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/src/work/jacint/max_matching.cc Wed May 05 17:29:41 2004 +0000
1.3 @@ -0,0 +1,270 @@
1.4 +///Generates a random graph, and tests max_matching.h on it.
1.5 +#include <iostream>
1.6 +#include <queue>
1.7 +#include <math.h>
1.8 +
1.9 +#include <list_graph.h>
1.10 +#include <dimacs.h>
1.11 +#include <graph_gen.h>
1.12 +#include <max_matching.h>
1.13 +#include <time_measure.h>
1.14 +#include <graph_wrapper.h>
1.15 +
1.16 +using namespace hugo;
1.17 +
1.18 +int main(int, char **) {
1.19 +
1.20 + typedef UndirGraph<ListGraph> UGW;
1.21 + typedef UGW::Edge Edge;
1.22 + typedef UGW::EdgeIt EdgeIt;
1.23 + typedef UGW::OutEdgeIt OutEdgeIt;
1.24 + typedef UGW::NodeIt NodeIt;
1.25 + typedef UGW::Node Node;
1.26 +
1.27 + UGW G;
1.28 +
1.29 + // random_init(); //If you want to use a random graph with a random
1.30 + // number of edges and nodes.
1.31 +
1.32 + int i;
1.33 + int j;
1.34 + std::cout<<"Number of nodes: ";
1.35 + std::cin >> i;
1.36 + std::cout<<"Number of edges: ";
1.37 + std::cin >> j;
1.38 +
1.39 + // readDimacs(std::cin, G);
1.40 + randomGraph(G, i, j );
1.41 +
1.42 + Timer ts;
1.43 + bool noerror=true;
1.44 +
1.45 + std::cout <<
1.46 + "\n Testing max_matching.h on a random graph with " <<
1.47 + G.nodeNum() << " nodes and " << G.edgeNum() << " edges...\n"
1.48 + << std::endl;
1.49 + MaxMatching<UGW> max_matching(G);
1.50 +
1.51 +
1.52 + std::cout <<
1.53 + "Running the plain edmonds algorithm runEdmonds(0) using no heuristic... "
1.54 + <<std::endl;
1.55 + ts.reset();
1.56 + max_matching.runEdmonds(0);
1.57 + std::cout<<"Elapsed time: "<<ts<<std::endl;
1.58 + int s=0;
1.59 + UGW::NodeMap<Node> mate(G,INVALID);
1.60 + max_matching.writeNMapNode(mate);
1.61 + NodeIt v;
1.62 + for(G.first(v); G.valid(v); G.next(v) ) {
1.63 + if ( G.valid(mate[v]) ) {
1.64 + ++s;
1.65 + }
1.66 + }
1.67 + int size=(int)s/2; //size will be used as the size of a maxmatching
1.68 + std::cout << size << " is the size of the matching found by runEdmonds(0),"<<std::endl;
1.69 + if ( size == max_matching.size() ) {
1.70 + std::cout<< "which equals to the size of the actual matching reported by size().\n"<< std::endl;
1.71 + } else {
1.72 + std::cout<< "which does not equal to the size of the actual matching reported by size()!\n"<< std::endl;
1.73 + noerror=false;
1.74 + }
1.75 +
1.76 +
1.77 + std::cout<<"Writing the position by calling writePos...";
1.78 + UGW::NodeMap<MaxMatching<UGW>::pos_enum> pos0(G);
1.79 + max_matching.writePos(pos0);
1.80 + std::cout << "OK" << std::endl;
1.81 +
1.82 +
1.83 + std::cout << "Resetting the matching and the position by calling"<< std::endl;
1.84 + std::cout<<"resetPos() and resetMatching()...";
1.85 + max_matching.resetPos();
1.86 + max_matching.resetMatching();
1.87 + std::cout <<"OK" << std::endl;
1.88 +
1.89 +
1.90 + std::cout << "\nRunning runEdmonds(1) using the 'postpone shrink' heuristic ... " <<std::endl;
1.91 + ts.reset();
1.92 + max_matching.runEdmonds(1);
1.93 + std::cout<<"Elapsed time: "<<ts<<std::endl;
1.94 + s=0;
1.95 + max_matching.writeNMapNode(mate);
1.96 + for(G.first(v); G.valid(v); G.next(v) ) {
1.97 + if ( G.valid(mate[v]) ) {
1.98 + ++s;
1.99 + }
1.100 + }
1.101 + std::cout << (int)s/2 <<
1.102 + " is the size of the matching found by runEdmonds(1),"<<std::endl;
1.103 + if ( (int)s/2 == size ) {
1.104 + std::cout<< "which equals to the size of the matching found by runEdmonds(0)."<< std::endl;
1.105 + } else {
1.106 + std::cout<< "which does not equal to the size of the matching found by runEdmonds(0)!"<< std::endl;
1.107 + noerror=false;
1.108 + }
1.109 + UGW::NodeMap<MaxMatching<UGW>::pos_enum> pos1(G);
1.110 + max_matching.writePos(pos1);
1.111 +
1.112 +
1.113 + std::cout << "\nStarting run() from the matching given by runEdmonds(1)... " <<std::endl;
1.114 + max_matching.resetPos();
1.115 + ts.reset();
1.116 + max_matching.run();
1.117 + std::cout<<"Elapsed time: "<<ts<<std::endl;
1.118 + s=0;
1.119 + max_matching.writeNMapNode(mate);
1.120 + for(G.first(v); G.valid(v); G.next(v) ) {
1.121 + if ( G.valid(mate[v]) ) {
1.122 + ++s;
1.123 + }
1.124 + }
1.125 + if ( (int)s/2 == size ) {
1.126 + std::cout<< "Found a matching of proper size."<< std::endl;
1.127 + } else {
1.128 + std::cout<< "Found a matching of inproper size!"<< std::endl;
1.129 + noerror=false;
1.130 + }
1.131 + UGW::NodeMap<MaxMatching<UGW>::pos_enum> pos2(G);
1.132 + max_matching.writePos(pos2);
1.133 +
1.134 +
1.135 + std::cout << "\nCalling resetPos() and resetMatching()...";
1.136 + max_matching.resetPos();
1.137 + max_matching.resetMatching();
1.138 + std::cout<<"OK"<<std::endl;
1.139 + std::cout <<"Calling greedyMatching() and then runEdmonds(1)... " <<std::endl;
1.140 + ts.reset();
1.141 + max_matching.run();
1.142 + std::cout<<"Elapsed time: "<<ts<<std::endl;
1.143 + s=0;
1.144 + max_matching.writeNMapNode(mate);
1.145 + for(G.first(v); G.valid(v); G.next(v) ) {
1.146 + if ( G.valid(mate[v]) ) {
1.147 + ++s;
1.148 + }
1.149 + }
1.150 + std::cout << (int)s/2 << " is the size of the matching found by run(),"<<std::endl;
1.151 + if ( (int)s/2 == size ) {
1.152 + std::cout<< "which equals to the size of the matching found by runEdmonds(0)."<< std::endl;
1.153 + } else {
1.154 + std::cout<< "which does not equal to the size of the matching found by runEdmonds(0)!"<< std::endl;
1.155 + noerror=false;
1.156 + }
1.157 + UGW::NodeMap<MaxMatching<UGW>::pos_enum> pos(G);
1.158 + max_matching.writePos(pos);
1.159 +
1.160 +
1.161 + std::cout<<"\nChecking if the output is a matching...";
1.162 + bool ismatching=true;
1.163 + for(G.first(v); G.valid(v); G.next(v) )
1.164 + if ( G.valid(mate[v]) ) {
1.165 + Node u=mate[v];
1.166 + if (mate[u]!=v) ismatching=false;
1.167 + }
1.168 + if ( ismatching ) std::cout<<"OK"<<std::endl;
1.169 + else std::cout<< "It is not a matching!"<< std::endl;
1.170 + noerror = noerror && ismatching;
1.171 +
1.172 +
1.173 + std::cout<<"\nChecking the dual..."<<std::endl;
1.174 +
1.175 + std::cout<<"Checking if the four position outputs coincide...";
1.176 + bool coincide=true;
1.177 + int err_node=0;
1.178 + for(G.first(v); G.valid(v); G.next(v) ) {
1.179 + if ( pos0[v] != pos1[v] || pos1[v]!=pos2[v] || pos2[v]!=pos[v] ) {
1.180 + ++err_node;
1.181 + coincide=false;
1.182 + }
1.183 + }
1.184 + if ( coincide ) std::cout << "OK" <<std::endl;
1.185 + else {
1.186 + std::cout << "They do not coincide! Number of erroneous nodes: "
1.187 + << err_node << std::endl;
1.188 + }
1.189 + noerror=noerror && coincide;
1.190 +
1.191 +
1.192 + std::cout<<"Checking if there is no edge between D and C...";
1.193 + bool noedge=true;
1.194 + EdgeIt e;
1.195 + for(G.first(e); G.valid(e); G.next(e) ) {
1.196 + if ( (pos[G.head(e)]==max_matching.C && pos[G.tail(e)]==max_matching.D) ||
1.197 + (pos[G.head(e)]==max_matching.D && pos[G.tail(e)]==max_matching.C) )
1.198 + noedge=false;
1.199 + }
1.200 + if ( noedge ) std::cout<<"OK"<<std::endl;
1.201 + else std::cout<< "There are edges between D and C!"<< std::endl;
1.202 + noerror = noerror && noedge;
1.203 +
1.204 +
1.205 + std::cout<<"Checking if all the components of G[D] are odd...";
1.206 + bool oddcomp=true;
1.207 + UGW::NodeMap<bool> todo(G,true);
1.208 + int num_comp=0;
1.209 + for(G.first(v); G.valid(v); G.next(v) ) {
1.210 + if ( pos[v]==max_matching.D && todo[v] ) {
1.211 + int comp_size=1;
1.212 + ++num_comp;
1.213 + std::queue<Node> Q;
1.214 + Q.push(v);
1.215 + todo.set(v,false);
1.216 + while (!Q.empty()) {
1.217 + Node w=Q.front();
1.218 + Q.pop();
1.219 + OutEdgeIt e;
1.220 + for(G.first(e,w); G.valid(e); G.next(e)) {
1.221 + Node u=G.bNode(e);
1.222 + if ( pos[u]==max_matching.D && todo[u] ) {
1.223 + ++comp_size;
1.224 + Q.push(u);
1.225 + todo.set(u,false);
1.226 + }
1.227 + }
1.228 + }
1.229 + if ( !(comp_size % 2) ) oddcomp=false;
1.230 + }
1.231 + }
1.232 + std::cout << "\n found " << num_comp << " component(s) of G[D],";
1.233 + if ( oddcomp ) std::cout<<" each is odd."<<std::endl;
1.234 + else std::cout<< " but not all are odd!"<< std::endl;
1.235 + noerror = noerror && oddcomp;
1.236 +
1.237 +
1.238 + int barrier=0;
1.239 + for(G.first(v); G.valid(v); G.next(v) )
1.240 + if ( pos[v]==max_matching.A ) ++barrier;
1.241 + std::cout << barrier << " is the number of nodes in A (i.e. the size of the barrier), so" << std::endl;
1.242 + std::cout << num_comp - barrier << " is the deficiency of the graph, and hence" << std::endl;
1.243 + int expected_size=(int)(G.nodeNum()-num_comp+barrier)/2;
1.244 + std::cout << expected_size << " should be the size of the maximum matching," << std::endl;
1.245 + if ( size==expected_size )
1.246 + std::cout<<"which equals to the number of vertices missed by the found matching!"<<std::endl;
1.247 + else {
1.248 + std::cout<<"which does not equal to the number of vertices missed by the matchings found!"
1.249 + <<std::endl;
1.250 + noerror=false;
1.251 + }
1.252 +
1.253 +
1.254 + if ( num_comp == 1 && barrier == 0 )
1.255 + std::cout<<"\nThis graph is factor-critical."<<std::endl;
1.256 + if ( num_comp == 0 && barrier == 0 )
1.257 + std::cout<<"\nThis graph has a perfect matching."<<std::endl;
1.258 +
1.259 +
1.260 + if( noerror ) std::cout<<"\nNo errors found.\n"<<std::endl;
1.261 + else std::cout<<"\nSome errors found!\n"<<std::endl;
1.262 +
1.263 + return 0;
1.264 +}
1.265 +
1.266 +
1.267 +
1.268 +
1.269 +
1.270 +
1.271 +
1.272 +
1.273 +