Changeset 1098:e3b3667c6857 in lemon-0.x
- Timestamp:
- 01/27/05 17:11:54 (20 years ago)
- Branch:
- default
- Phase:
- public
- Convert:
- svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@1497
- File:
-
- 1 edited
Legend:
- Unmodified
- Added
- Removed
-
src/test/max_matching_test.cc
r1092 r1098 16 16 17 17 #include <iostream> 18 #include <vector> 18 19 #include <queue> 19 20 #include <math.h> … … 24 25 #include <lemon/list_graph.h> 25 26 #include <lemon/max_matching.h> 26 //temporarily27 #include <work/jacint/graph_gen.h>28 27 29 28 using namespace std; … … 40 39 typedef Graph::Node Node; 41 40 42 Graph G; 41 Graph g; 42 g.clear(); 43 43 44 random_init(); 45 randomGraph(G, random(5000), random(20000) ); 44 std::vector<Graph::Node> nodes; 45 for (int i=0; i<13; ++i) 46 nodes.push_back(g.addNode()); 46 47 47 MaxMatching<Graph> max_matching(G); 48 g.addEdge(nodes[0], nodes[0]); 49 g.addEdge(nodes[6], nodes[10]); 50 g.addEdge(nodes[5], nodes[10]); 51 g.addEdge(nodes[4], nodes[10]); 52 g.addEdge(nodes[3], nodes[11]); 53 g.addEdge(nodes[1], nodes[6]); 54 g.addEdge(nodes[4], nodes[7]); 55 g.addEdge(nodes[1], nodes[8]); 56 g.addEdge(nodes[0], nodes[8]); 57 g.addEdge(nodes[3], nodes[12]); 58 g.addEdge(nodes[6], nodes[9]); 59 g.addEdge(nodes[9], nodes[11]); 60 g.addEdge(nodes[2], nodes[10]); 61 g.addEdge(nodes[10], nodes[8]); 62 g.addEdge(nodes[5], nodes[8]); 63 g.addEdge(nodes[6], nodes[3]); 64 g.addEdge(nodes[0], nodes[5]); 65 g.addEdge(nodes[6], nodes[12]); 66 67 MaxMatching<Graph> max_matching(g); 48 68 max_matching.runEdmonds(0); 49 69 50 70 int s=0; 51 Graph::NodeMap<Node> mate( G,INVALID);71 Graph::NodeMap<Node> mate(g,INVALID); 52 72 max_matching.writeNMapNode(mate); 53 for(NodeIt v( G); v!=INVALID; ++v) {73 for(NodeIt v(g); v!=INVALID; ++v) { 54 74 if ( mate[v]!=INVALID ) ++s; 55 75 } 56 76 int size=(int)s/2; //size will be used as the size of a maxmatching 57 77 58 for(NodeIt v( G); v!=INVALID; ++v) {78 for(NodeIt v(g); v!=INVALID; ++v) { 59 79 max_matching.mate(v); 60 80 } … … 62 82 check ( size == max_matching.size(), "mate() returns a different size matching than max_matching.size()" ); 63 83 64 Graph::NodeMap<MaxMatching<Graph>::pos_enum> pos0( G);84 Graph::NodeMap<MaxMatching<Graph>::pos_enum> pos0(g); 65 85 max_matching.writePos(pos0); 66 86 … … 69 89 s=0; 70 90 max_matching.writeNMapNode(mate); 71 for(NodeIt v( G); v!=INVALID; ++v) {91 for(NodeIt v(g); v!=INVALID; ++v) { 72 92 if ( mate[v]!=INVALID ) ++s; 73 93 } 74 94 check ( (int)s/2 == size, "The size does not equal!" ); 75 95 76 Graph::NodeMap<MaxMatching<Graph>::pos_enum> pos1( G);96 Graph::NodeMap<MaxMatching<Graph>::pos_enum> pos1(g); 77 97 max_matching.writePos(pos1); 78 98 … … 80 100 s=0; 81 101 max_matching.writeNMapNode(mate); 82 for(NodeIt v( G); v!=INVALID; ++v) {102 for(NodeIt v(g); v!=INVALID; ++v) { 83 103 if ( mate[v]!=INVALID ) ++s; 84 104 } 85 105 check ( (int)s/2 == size, "The size does not equal!" ); 86 106 87 Graph::NodeMap<MaxMatching<Graph>::pos_enum> pos2( G);107 Graph::NodeMap<MaxMatching<Graph>::pos_enum> pos2(g); 88 108 max_matching.writePos(pos2); 89 109 … … 92 112 s=0; 93 113 max_matching.writeNMapNode(mate); 94 for(NodeIt v( G); v!=INVALID; ++v) {114 for(NodeIt v(g); v!=INVALID; ++v) { 95 115 if ( mate[v]!=INVALID ) ++s; 96 116 } 97 117 check ( (int)s/2 == size, "The size does not equal!" ); 98 118 99 Graph::NodeMap<MaxMatching<Graph>::pos_enum> pos( G);119 Graph::NodeMap<MaxMatching<Graph>::pos_enum> pos(g); 100 120 max_matching.writePos(pos); 101 121 102 122 bool ismatching=true; 103 for(NodeIt v( G); v!=INVALID; ++v) {123 for(NodeIt v(g); v!=INVALID; ++v) { 104 124 if ( mate[v]!=INVALID ) { 105 125 Node u=mate[v]; … … 110 130 111 131 bool coincide=true; 112 for(NodeIt v( G); v!=INVALID; ++v) {132 for(NodeIt v(g); v!=INVALID; ++v) { 113 133 if ( pos0[v] != pos1[v] || pos1[v]!=pos2[v] || pos2[v]!=pos[v] ) { 114 134 coincide=false; … … 118 138 119 139 bool noedge=true; 120 for(UndirEdgeIt e( G); e!=INVALID; ++e) {121 if ( (pos[ G.target(e)]==max_matching.C && pos[G.source(e)]==max_matching.D) ||122 (pos[ G.target(e)]==max_matching.D && pos[G.source(e)]==max_matching.C) )140 for(UndirEdgeIt e(g); e!=INVALID; ++e) { 141 if ( (pos[g.target(e)]==max_matching.C && pos[g.source(e)]==max_matching.D) || 142 (pos[g.target(e)]==max_matching.D && pos[g.source(e)]==max_matching.C) ) 123 143 noedge=false; 124 144 } … … 126 146 127 147 bool oddcomp=true; 128 Graph::NodeMap<bool> todo( G,true);148 Graph::NodeMap<bool> todo(g,true); 129 149 int num_comp=0; 130 for(NodeIt v( G); v!=INVALID; ++v) {150 for(NodeIt v(g); v!=INVALID; ++v) { 131 151 if ( pos[v]==max_matching.D && todo[v] ) { 132 152 int comp_size=1; … … 138 158 Node w=Q.front(); 139 159 Q.pop(); 140 for(IncEdgeIt e( G,w); e!=INVALID; ++e) {141 Node u= G.target(e);160 for(IncEdgeIt e(g,w); e!=INVALID; ++e) { 161 Node u=g.target(e); 142 162 if ( pos[u]==max_matching.D && todo[u] ) { 143 163 ++comp_size; … … 150 170 } 151 171 } 152 check ( oddcomp, "A component of G[D] is not odd." );172 check ( oddcomp, "A component of g[D] is not odd." ); 153 173 154 174 int barrier=0; 155 for(NodeIt v( G); v!=INVALID; ++v) {175 for(NodeIt v(g); v!=INVALID; ++v) { 156 176 if ( pos[v]==max_matching.A ) ++barrier; 157 177 } 158 int expected_size=(int)( countNodes( G)-num_comp+barrier)/2;178 int expected_size=(int)( countNodes(g)-num_comp+barrier)/2; 159 179 check ( size==expected_size, "The size of the matching is wrong." ); 160 180 161 181 return 0; 162 182 } 163 164 165 void random_init()166 {167 unsigned int seed = getpid();168 seed |= seed << 15;169 seed ^= time(0);170 171 srand(seed);172 }173 174 175 int random(int m)176 {177 return int( double(m) * rand() / (RAND_MAX + 1.0) );178 }179 180 181 /// Generates a random graph with n nodes and m edges.182 /// Before generating the random graph, \c g.clear() is called.183 template<typename Graph>184 void randomGraph(Graph& g, int n, int m) {185 g.clear();186 std::vector<typename Graph::Node> nodes;187 for (int i=0; i<n; ++i)188 nodes.push_back(g.addNode());189 for (int i=0; i<m; ++i)190 g.addEdge(nodes[random(n)], nodes[random(n)]);191 }
Note: See TracChangeset
for help on using the changeset viewer.