1.1 --- a/src/test/max_matching_test.cc Wed Jan 26 15:54:06 2005 +0000
1.2 +++ b/src/test/max_matching_test.cc Thu Jan 27 16:11:54 2005 +0000
1.3 @@ -15,6 +15,7 @@
1.4 */
1.5
1.6 #include <iostream>
1.7 +#include <vector>
1.8 #include <queue>
1.9 #include <math.h>
1.10 #include <cstdlib>
1.11 @@ -23,8 +24,6 @@
1.12 #include <lemon/invalid.h>
1.13 #include <lemon/list_graph.h>
1.14 #include <lemon/max_matching.h>
1.15 -//temporarily
1.16 -#include <work/jacint/graph_gen.h>
1.17
1.18 using namespace std;
1.19 using namespace lemon;
1.20 @@ -39,68 +38,89 @@
1.21 typedef Graph::NodeIt NodeIt;
1.22 typedef Graph::Node Node;
1.23
1.24 - Graph G;
1.25 + Graph g;
1.26 + g.clear();
1.27
1.28 - random_init();
1.29 - randomGraph(G, random(5000), random(20000) );
1.30 + std::vector<Graph::Node> nodes;
1.31 + for (int i=0; i<13; ++i)
1.32 + nodes.push_back(g.addNode());
1.33
1.34 - MaxMatching<Graph> max_matching(G);
1.35 + g.addEdge(nodes[0], nodes[0]);
1.36 + g.addEdge(nodes[6], nodes[10]);
1.37 + g.addEdge(nodes[5], nodes[10]);
1.38 + g.addEdge(nodes[4], nodes[10]);
1.39 + g.addEdge(nodes[3], nodes[11]);
1.40 + g.addEdge(nodes[1], nodes[6]);
1.41 + g.addEdge(nodes[4], nodes[7]);
1.42 + g.addEdge(nodes[1], nodes[8]);
1.43 + g.addEdge(nodes[0], nodes[8]);
1.44 + g.addEdge(nodes[3], nodes[12]);
1.45 + g.addEdge(nodes[6], nodes[9]);
1.46 + g.addEdge(nodes[9], nodes[11]);
1.47 + g.addEdge(nodes[2], nodes[10]);
1.48 + g.addEdge(nodes[10], nodes[8]);
1.49 + g.addEdge(nodes[5], nodes[8]);
1.50 + g.addEdge(nodes[6], nodes[3]);
1.51 + g.addEdge(nodes[0], nodes[5]);
1.52 + g.addEdge(nodes[6], nodes[12]);
1.53 +
1.54 + MaxMatching<Graph> max_matching(g);
1.55 max_matching.runEdmonds(0);
1.56
1.57 int s=0;
1.58 - Graph::NodeMap<Node> mate(G,INVALID);
1.59 + Graph::NodeMap<Node> mate(g,INVALID);
1.60 max_matching.writeNMapNode(mate);
1.61 - for(NodeIt v(G); v!=INVALID; ++v) {
1.62 + for(NodeIt v(g); v!=INVALID; ++v) {
1.63 if ( mate[v]!=INVALID ) ++s;
1.64 }
1.65 int size=(int)s/2; //size will be used as the size of a maxmatching
1.66
1.67 - for(NodeIt v(G); v!=INVALID; ++v) {
1.68 + for(NodeIt v(g); v!=INVALID; ++v) {
1.69 max_matching.mate(v);
1.70 }
1.71
1.72 check ( size == max_matching.size(), "mate() returns a different size matching than max_matching.size()" );
1.73
1.74 - Graph::NodeMap<MaxMatching<Graph>::pos_enum> pos0(G);
1.75 + Graph::NodeMap<MaxMatching<Graph>::pos_enum> pos0(g);
1.76 max_matching.writePos(pos0);
1.77
1.78 max_matching.resetMatching();
1.79 max_matching.runEdmonds(1);
1.80 s=0;
1.81 max_matching.writeNMapNode(mate);
1.82 - for(NodeIt v(G); v!=INVALID; ++v) {
1.83 + for(NodeIt v(g); v!=INVALID; ++v) {
1.84 if ( mate[v]!=INVALID ) ++s;
1.85 }
1.86 check ( (int)s/2 == size, "The size does not equal!" );
1.87
1.88 - Graph::NodeMap<MaxMatching<Graph>::pos_enum> pos1(G);
1.89 + Graph::NodeMap<MaxMatching<Graph>::pos_enum> pos1(g);
1.90 max_matching.writePos(pos1);
1.91
1.92 max_matching.run();
1.93 s=0;
1.94 max_matching.writeNMapNode(mate);
1.95 - for(NodeIt v(G); v!=INVALID; ++v) {
1.96 + for(NodeIt v(g); v!=INVALID; ++v) {
1.97 if ( mate[v]!=INVALID ) ++s;
1.98 }
1.99 check ( (int)s/2 == size, "The size does not equal!" );
1.100
1.101 - Graph::NodeMap<MaxMatching<Graph>::pos_enum> pos2(G);
1.102 + Graph::NodeMap<MaxMatching<Graph>::pos_enum> pos2(g);
1.103 max_matching.writePos(pos2);
1.104
1.105 max_matching.resetMatching();
1.106 max_matching.run();
1.107 s=0;
1.108 max_matching.writeNMapNode(mate);
1.109 - for(NodeIt v(G); v!=INVALID; ++v) {
1.110 + for(NodeIt v(g); v!=INVALID; ++v) {
1.111 if ( mate[v]!=INVALID ) ++s;
1.112 }
1.113 check ( (int)s/2 == size, "The size does not equal!" );
1.114
1.115 - Graph::NodeMap<MaxMatching<Graph>::pos_enum> pos(G);
1.116 + Graph::NodeMap<MaxMatching<Graph>::pos_enum> pos(g);
1.117 max_matching.writePos(pos);
1.118
1.119 bool ismatching=true;
1.120 - for(NodeIt v(G); v!=INVALID; ++v) {
1.121 + for(NodeIt v(g); v!=INVALID; ++v) {
1.122 if ( mate[v]!=INVALID ) {
1.123 Node u=mate[v];
1.124 if (mate[u]!=v) ismatching=false;
1.125 @@ -109,7 +129,7 @@
1.126 check ( ismatching, "It is not a matching!" );
1.127
1.128 bool coincide=true;
1.129 - for(NodeIt v(G); v!=INVALID; ++v) {
1.130 + for(NodeIt v(g); v!=INVALID; ++v) {
1.131 if ( pos0[v] != pos1[v] || pos1[v]!=pos2[v] || pos2[v]!=pos[v] ) {
1.132 coincide=false;
1.133 }
1.134 @@ -117,17 +137,17 @@
1.135 check ( coincide, "The decompositions do not coincide! " );
1.136
1.137 bool noedge=true;
1.138 - for(UndirEdgeIt e(G); e!=INVALID; ++e) {
1.139 - if ( (pos[G.target(e)]==max_matching.C && pos[G.source(e)]==max_matching.D) ||
1.140 - (pos[G.target(e)]==max_matching.D && pos[G.source(e)]==max_matching.C) )
1.141 + for(UndirEdgeIt e(g); e!=INVALID; ++e) {
1.142 + if ( (pos[g.target(e)]==max_matching.C && pos[g.source(e)]==max_matching.D) ||
1.143 + (pos[g.target(e)]==max_matching.D && pos[g.source(e)]==max_matching.C) )
1.144 noedge=false;
1.145 }
1.146 check ( noedge, "There are edges between D and C!" );
1.147
1.148 bool oddcomp=true;
1.149 - Graph::NodeMap<bool> todo(G,true);
1.150 + Graph::NodeMap<bool> todo(g,true);
1.151 int num_comp=0;
1.152 - for(NodeIt v(G); v!=INVALID; ++v) {
1.153 + for(NodeIt v(g); v!=INVALID; ++v) {
1.154 if ( pos[v]==max_matching.D && todo[v] ) {
1.155 int comp_size=1;
1.156 ++num_comp;
1.157 @@ -137,8 +157,8 @@
1.158 while (!Q.empty()) {
1.159 Node w=Q.front();
1.160 Q.pop();
1.161 - for(IncEdgeIt e(G,w); e!=INVALID; ++e) {
1.162 - Node u=G.target(e);
1.163 + for(IncEdgeIt e(g,w); e!=INVALID; ++e) {
1.164 + Node u=g.target(e);
1.165 if ( pos[u]==max_matching.D && todo[u] ) {
1.166 ++comp_size;
1.167 Q.push(u);
1.168 @@ -149,43 +169,14 @@
1.169 if ( !(comp_size % 2) ) oddcomp=false;
1.170 }
1.171 }
1.172 - check ( oddcomp, "A component of G[D] is not odd." );
1.173 + check ( oddcomp, "A component of g[D] is not odd." );
1.174
1.175 int barrier=0;
1.176 - for(NodeIt v(G); v!=INVALID; ++v) {
1.177 + for(NodeIt v(g); v!=INVALID; ++v) {
1.178 if ( pos[v]==max_matching.A ) ++barrier;
1.179 }
1.180 - int expected_size=(int)( countNodes(G)-num_comp+barrier)/2;
1.181 + int expected_size=(int)( countNodes(g)-num_comp+barrier)/2;
1.182 check ( size==expected_size, "The size of the matching is wrong." );
1.183
1.184 return 0;
1.185 }
1.186 -
1.187 -
1.188 -void random_init()
1.189 -{
1.190 - unsigned int seed = getpid();
1.191 - seed |= seed << 15;
1.192 - seed ^= time(0);
1.193 -
1.194 - srand(seed);
1.195 -}
1.196 -
1.197 -
1.198 -int random(int m)
1.199 -{
1.200 - return int( double(m) * rand() / (RAND_MAX + 1.0) );
1.201 -}
1.202 -
1.203 -
1.204 -/// Generates a random graph with n nodes and m edges.
1.205 -/// Before generating the random graph, \c g.clear() is called.
1.206 -template<typename Graph>
1.207 -void randomGraph(Graph& g, int n, int m) {
1.208 - g.clear();
1.209 - std::vector<typename Graph::Node> nodes;
1.210 - for (int i=0; i<n; ++i)
1.211 - nodes.push_back(g.addNode());
1.212 - for (int i=0; i<m; ++i)
1.213 - g.addEdge(nodes[random(n)], nodes[random(n)]);
1.214 -}