Changeset 327:91d63b8b1a4c in lemon-main for test/max_matching_test.cc
- Timestamp:
- 10/13/08 14:00:11 (16 years ago)
- Branch:
- default
- Phase:
- public
- File:
-
- 1 edited
Legend:
- Unmodified
- Added
- Removed
-
test/max_matching_test.cc
r326 r327 18 18 19 19 #include <iostream> 20 #include <sstream> 20 21 #include <vector> 21 22 #include <queue> … … 23 24 #include <cstdlib> 24 25 26 #include <lemon/max_matching.h> 27 #include <lemon/smart_graph.h> 28 #include <lemon/lgf_reader.h> 29 25 30 #include "test_tools.h" 26 #include <lemon/list_graph.h>27 #include <lemon/max_matching.h>28 31 29 32 using namespace std; 30 33 using namespace lemon; 31 34 35 GRAPH_TYPEDEFS(SmartGraph); 36 37 38 const int lgfn = 3; 39 const std::string lgf[lgfn] = { 40 "@nodes\n" 41 "label\n" 42 "0\n" 43 "1\n" 44 "2\n" 45 "3\n" 46 "4\n" 47 "5\n" 48 "6\n" 49 "7\n" 50 "@edges\n" 51 " label weight\n" 52 "7 4 0 984\n" 53 "0 7 1 73\n" 54 "7 1 2 204\n" 55 "2 3 3 583\n" 56 "2 7 4 565\n" 57 "2 1 5 582\n" 58 "0 4 6 551\n" 59 "2 5 7 385\n" 60 "1 5 8 561\n" 61 "5 3 9 484\n" 62 "7 5 10 904\n" 63 "3 6 11 47\n" 64 "7 6 12 888\n" 65 "3 0 13 747\n" 66 "6 1 14 310\n", 67 68 "@nodes\n" 69 "label\n" 70 "0\n" 71 "1\n" 72 "2\n" 73 "3\n" 74 "4\n" 75 "5\n" 76 "6\n" 77 "7\n" 78 "@edges\n" 79 " label weight\n" 80 "2 5 0 710\n" 81 "0 5 1 241\n" 82 "2 4 2 856\n" 83 "2 6 3 762\n" 84 "4 1 4 747\n" 85 "6 1 5 962\n" 86 "4 7 6 723\n" 87 "1 7 7 661\n" 88 "2 3 8 376\n" 89 "1 0 9 416\n" 90 "6 7 10 391\n", 91 92 "@nodes\n" 93 "label\n" 94 "0\n" 95 "1\n" 96 "2\n" 97 "3\n" 98 "4\n" 99 "5\n" 100 "6\n" 101 "7\n" 102 "@edges\n" 103 " label weight\n" 104 "6 2 0 553\n" 105 "0 7 1 653\n" 106 "6 3 2 22\n" 107 "4 7 3 846\n" 108 "7 2 4 981\n" 109 "7 6 5 250\n" 110 "5 2 6 539\n", 111 }; 112 113 void checkMatching(const SmartGraph& graph, 114 const MaxMatching<SmartGraph>& mm) { 115 int num = 0; 116 117 IntNodeMap comp_index(graph); 118 UnionFind<IntNodeMap> comp(comp_index); 119 120 int barrier_num = 0; 121 122 for (NodeIt n(graph); n != INVALID; ++n) { 123 check(mm.decomposition(n) == MaxMatching<SmartGraph>::EVEN || 124 mm.matching(n) != INVALID, "Wrong Gallai-Edmonds decomposition"); 125 if (mm.decomposition(n) == MaxMatching<SmartGraph>::ODD) { 126 ++barrier_num; 127 } else { 128 comp.insert(n); 129 } 130 } 131 132 for (EdgeIt e(graph); e != INVALID; ++e) { 133 if (mm.matching(e)) { 134 check(e == mm.matching(graph.u(e)), "Wrong matching"); 135 check(e == mm.matching(graph.v(e)), "Wrong matching"); 136 ++num; 137 } 138 check(mm.decomposition(graph.u(e)) != MaxMatching<SmartGraph>::EVEN || 139 mm.decomposition(graph.v(e)) != MaxMatching<SmartGraph>::MATCHED, 140 "Wrong Gallai-Edmonds decomposition"); 141 142 check(mm.decomposition(graph.v(e)) != MaxMatching<SmartGraph>::EVEN || 143 mm.decomposition(graph.u(e)) != MaxMatching<SmartGraph>::MATCHED, 144 "Wrong Gallai-Edmonds decomposition"); 145 146 if (mm.decomposition(graph.u(e)) != MaxMatching<SmartGraph>::ODD && 147 mm.decomposition(graph.v(e)) != MaxMatching<SmartGraph>::ODD) { 148 comp.join(graph.u(e), graph.v(e)); 149 } 150 } 151 152 std::set<int> comp_root; 153 int odd_comp_num = 0; 154 for (NodeIt n(graph); n != INVALID; ++n) { 155 if (mm.decomposition(n) != MaxMatching<SmartGraph>::ODD) { 156 int root = comp.find(n); 157 if (comp_root.find(root) == comp_root.end()) { 158 comp_root.insert(root); 159 if (comp.size(n) % 2 == 1) { 160 ++odd_comp_num; 161 } 162 } 163 } 164 } 165 166 check(mm.matchingSize() == num, "Wrong matching"); 167 check(2 * num == countNodes(graph) - (odd_comp_num - barrier_num), 168 "Wrong matching"); 169 return; 170 } 171 172 void checkWeightedMatching(const SmartGraph& graph, 173 const SmartGraph::EdgeMap<int>& weight, 174 const MaxWeightedMatching<SmartGraph>& mwm) { 175 for (SmartGraph::EdgeIt e(graph); e != INVALID; ++e) { 176 if (graph.u(e) == graph.v(e)) continue; 177 int rw = mwm.nodeValue(graph.u(e)) + mwm.nodeValue(graph.v(e)); 178 179 for (int i = 0; i < mwm.blossomNum(); ++i) { 180 bool s = false, t = false; 181 for (MaxWeightedMatching<SmartGraph>::BlossomIt n(mwm, i); 182 n != INVALID; ++n) { 183 if (graph.u(e) == n) s = true; 184 if (graph.v(e) == n) t = true; 185 } 186 if (s == true && t == true) { 187 rw += mwm.blossomValue(i); 188 } 189 } 190 rw -= weight[e] * mwm.dualScale; 191 192 check(rw >= 0, "Negative reduced weight"); 193 check(rw == 0 || !mwm.matching(e), 194 "Non-zero reduced weight on matching edge"); 195 } 196 197 int pv = 0; 198 for (SmartGraph::NodeIt n(graph); n != INVALID; ++n) { 199 if (mwm.matching(n) != INVALID) { 200 check(mwm.nodeValue(n) >= 0, "Invalid node value"); 201 pv += weight[mwm.matching(n)]; 202 SmartGraph::Node o = graph.target(mwm.matching(n)); 203 check(mwm.mate(n) == o, "Invalid matching"); 204 check(mwm.matching(n) == graph.oppositeArc(mwm.matching(o)), 205 "Invalid matching"); 206 } else { 207 check(mwm.mate(n) == INVALID, "Invalid matching"); 208 check(mwm.nodeValue(n) == 0, "Invalid matching"); 209 } 210 } 211 212 int dv = 0; 213 for (SmartGraph::NodeIt n(graph); n != INVALID; ++n) { 214 dv += mwm.nodeValue(n); 215 } 216 217 for (int i = 0; i < mwm.blossomNum(); ++i) { 218 check(mwm.blossomValue(i) >= 0, "Invalid blossom value"); 219 check(mwm.blossomSize(i) % 2 == 1, "Even blossom size"); 220 dv += mwm.blossomValue(i) * ((mwm.blossomSize(i) - 1) / 2); 221 } 222 223 check(pv * mwm.dualScale == dv * 2, "Wrong duality"); 224 225 return; 226 } 227 228 void checkWeightedPerfectMatching(const SmartGraph& graph, 229 const SmartGraph::EdgeMap<int>& weight, 230 const MaxWeightedPerfectMatching<SmartGraph>& mwpm) { 231 for (SmartGraph::EdgeIt e(graph); e != INVALID; ++e) { 232 if (graph.u(e) == graph.v(e)) continue; 233 int rw = mwpm.nodeValue(graph.u(e)) + mwpm.nodeValue(graph.v(e)); 234 235 for (int i = 0; i < mwpm.blossomNum(); ++i) { 236 bool s = false, t = false; 237 for (MaxWeightedPerfectMatching<SmartGraph>::BlossomIt n(mwpm, i); 238 n != INVALID; ++n) { 239 if (graph.u(e) == n) s = true; 240 if (graph.v(e) == n) t = true; 241 } 242 if (s == true && t == true) { 243 rw += mwpm.blossomValue(i); 244 } 245 } 246 rw -= weight[e] * mwpm.dualScale; 247 248 check(rw >= 0, "Negative reduced weight"); 249 check(rw == 0 || !mwpm.matching(e), 250 "Non-zero reduced weight on matching edge"); 251 } 252 253 int pv = 0; 254 for (SmartGraph::NodeIt n(graph); n != INVALID; ++n) { 255 check(mwpm.matching(n) != INVALID, "Non perfect"); 256 pv += weight[mwpm.matching(n)]; 257 SmartGraph::Node o = graph.target(mwpm.matching(n)); 258 check(mwpm.mate(n) == o, "Invalid matching"); 259 check(mwpm.matching(n) == graph.oppositeArc(mwpm.matching(o)), 260 "Invalid matching"); 261 } 262 263 int dv = 0; 264 for (SmartGraph::NodeIt n(graph); n != INVALID; ++n) { 265 dv += mwpm.nodeValue(n); 266 } 267 268 for (int i = 0; i < mwpm.blossomNum(); ++i) { 269 check(mwpm.blossomValue(i) >= 0, "Invalid blossom value"); 270 check(mwpm.blossomSize(i) % 2 == 1, "Even blossom size"); 271 dv += mwpm.blossomValue(i) * ((mwpm.blossomSize(i) - 1) / 2); 272 } 273 274 check(pv * mwpm.dualScale == dv * 2, "Wrong duality"); 275 276 return; 277 } 278 279 32 280 int main() { 33 281 34 typedef ListGraph Graph; 35 36 GRAPH_TYPEDEFS(Graph); 37 38 Graph g; 39 g.clear(); 40 41 std::vector<Graph::Node> nodes; 42 for (int i=0; i<13; ++i) 43 nodes.push_back(g.addNode()); 44 45 g.addEdge(nodes[0], nodes[0]); 46 g.addEdge(nodes[6], nodes[10]); 47 g.addEdge(nodes[5], nodes[10]); 48 g.addEdge(nodes[4], nodes[10]); 49 g.addEdge(nodes[3], nodes[11]); 50 g.addEdge(nodes[1], nodes[6]); 51 g.addEdge(nodes[4], nodes[7]); 52 g.addEdge(nodes[1], nodes[8]); 53 g.addEdge(nodes[0], nodes[8]); 54 g.addEdge(nodes[3], nodes[12]); 55 g.addEdge(nodes[6], nodes[9]); 56 g.addEdge(nodes[9], nodes[11]); 57 g.addEdge(nodes[2], nodes[10]); 58 g.addEdge(nodes[10], nodes[8]); 59 g.addEdge(nodes[5], nodes[8]); 60 g.addEdge(nodes[6], nodes[3]); 61 g.addEdge(nodes[0], nodes[5]); 62 g.addEdge(nodes[6], nodes[12]); 63 64 MaxMatching<Graph> max_matching(g); 65 max_matching.init(); 66 max_matching.startDense(); 67 68 int s=0; 69 Graph::NodeMap<Node> mate(g,INVALID); 70 max_matching.mateMap(mate); 71 for(NodeIt v(g); v!=INVALID; ++v) { 72 if ( mate[v]!=INVALID ) ++s; 73 } 74 int size=int(s/2); //size will be used as the size of a maxmatching 75 76 for(NodeIt v(g); v!=INVALID; ++v) { 77 max_matching.mate(v); 78 } 79 80 check ( size == max_matching.size(), "mate() returns a different size matching than max_matching.size()" ); 81 82 Graph::NodeMap<MaxMatching<Graph>::DecompType> pos0(g); 83 max_matching.decomposition(pos0); 84 85 max_matching.init(); 86 max_matching.startSparse(); 87 s=0; 88 max_matching.mateMap(mate); 89 for(NodeIt v(g); v!=INVALID; ++v) { 90 if ( mate[v]!=INVALID ) ++s; 91 } 92 check ( int(s/2) == size, "The size does not equal!" ); 93 94 Graph::NodeMap<MaxMatching<Graph>::DecompType> pos1(g); 95 max_matching.decomposition(pos1); 96 97 max_matching.run(); 98 s=0; 99 max_matching.mateMap(mate); 100 for(NodeIt v(g); v!=INVALID; ++v) { 101 if ( mate[v]!=INVALID ) ++s; 102 } 103 check ( int(s/2) == size, "The size does not equal!" ); 104 105 Graph::NodeMap<MaxMatching<Graph>::DecompType> pos2(g); 106 max_matching.decomposition(pos2); 107 108 max_matching.run(); 109 s=0; 110 max_matching.mateMap(mate); 111 for(NodeIt v(g); v!=INVALID; ++v) { 112 if ( mate[v]!=INVALID ) ++s; 113 } 114 check ( int(s/2) == size, "The size does not equal!" ); 115 116 Graph::NodeMap<MaxMatching<Graph>::DecompType> pos(g); 117 max_matching.decomposition(pos); 118 119 bool ismatching=true; 120 for(NodeIt v(g); v!=INVALID; ++v) { 121 if ( mate[v]!=INVALID ) { 122 Node u=mate[v]; 123 if (mate[u]!=v) ismatching=false; 124 } 125 } 126 check ( ismatching, "It is not a matching!" ); 127 128 bool coincide=true; 129 for(NodeIt v(g); v!=INVALID; ++v) { 130 if ( pos0[v] != pos1[v] || pos1[v]!=pos2[v] || pos2[v]!=pos[v] ) { 131 coincide=false; 132 } 133 } 134 check ( coincide, "The decompositions do not coincide! " ); 135 136 bool noarc=true; 137 for(EdgeIt e(g); e!=INVALID; ++e) { 138 if ( (pos[g.v(e)]==max_matching.C && 139 pos[g.u(e)]==max_matching.D) || 140 (pos[g.v(e)]==max_matching.D && 141 pos[g.u(e)]==max_matching.C) ) 142 noarc=false; 143 } 144 check ( noarc, "There are arcs between D and C!" ); 145 146 bool oddcomp=true; 147 Graph::NodeMap<bool> todo(g,true); 148 int num_comp=0; 149 for(NodeIt v(g); v!=INVALID; ++v) { 150 if ( pos[v]==max_matching.D && todo[v] ) { 151 int comp_size=1; 152 ++num_comp; 153 std::queue<Node> Q; 154 Q.push(v); 155 todo.set(v,false); 156 while (!Q.empty()) { 157 Node w=Q.front(); 158 Q.pop(); 159 for(IncEdgeIt e(g,w); e!=INVALID; ++e) { 160 Node u=g.runningNode(e); 161 if ( pos[u]==max_matching.D && todo[u] ) { 162 ++comp_size; 163 Q.push(u); 164 todo.set(u,false); 165 } 166 } 167 } 168 if ( !(comp_size % 2) ) oddcomp=false; 169 } 170 } 171 check ( oddcomp, "A component of g[D] is not odd." ); 172 173 int barrier=0; 174 for(NodeIt v(g); v!=INVALID; ++v) { 175 if ( pos[v]==max_matching.A ) ++barrier; 176 } 177 int expected_size=int( countNodes(g)-num_comp+barrier)/2; 178 check ( size==expected_size, "The size of the matching is wrong." ); 282 for (int i = 0; i < lgfn; ++i) { 283 SmartGraph graph; 284 SmartGraph::EdgeMap<int> weight(graph); 285 286 istringstream lgfs(lgf[i]); 287 graphReader(graph, lgfs). 288 edgeMap("weight", weight).run(); 289 290 MaxMatching<SmartGraph> mm(graph); 291 mm.run(); 292 checkMatching(graph, mm); 293 294 MaxWeightedMatching<SmartGraph> mwm(graph, weight); 295 mwm.run(); 296 checkWeightedMatching(graph, weight, mwm); 297 298 MaxWeightedPerfectMatching<SmartGraph> mwpm(graph, weight); 299 bool perfect = mwpm.run(); 300 301 check(perfect == (mm.matchingSize() * 2 == countNodes(graph)), 302 "Perfect matching found"); 303 304 if (perfect) { 305 checkWeightedPerfectMatching(graph, weight, mwpm); 306 } 307 } 179 308 180 309 return 0;
Note: See TracChangeset
for help on using the changeset viewer.