Changeset 1406:120b9031eada in lemon
 Timestamp:
 10/07/17 00:14:05 (5 years ago)
 Branch:
 default
 Phase:
 public
 Location:
 test
 Files:

 1 deleted
 2 edited
Legend:
 Unmodified
 Added
 Removed

test/CMakeLists.txt
r1405 r1406 56 56 unionfind_test 57 57 vf2_test 58 vf2pp_test59 58 ) 60 59 
test/vf2_test.cc
r1405 r1406 17 17 18 18 #include <lemon/vf2.h> 19 #include <lemon/vf2pp.h> 19 20 #include <lemon/concepts/digraph.h> 20 21 #include <lemon/smart_graph.h> … … 153 154 std::stringstream ss(petersen_lgf); 154 155 graphReader(petersen, ss) 155 .nodeMap("col1", petersen_col1)156 .nodeMap("col2", petersen_col2)156 .nodeMap("col1", petersen_col1) 157 .nodeMap("col2", petersen_col2) 157 158 .run(); 158 159 159 160 ss.clear(); 160 161 ss.str(""); 161 ss <<c5_lgf;162 ss << c5_lgf; 162 163 //std::stringstream ss2(c5_lgf); 163 164 graphReader(c5, ss) 164 .nodeMap("col", c5_col)165 .nodeMap("col", c5_col) 165 166 .run(); 166 167 167 168 ss.clear(); 168 169 ss.str(""); 169 ss <<c7_lgf;170 ss << c7_lgf; 170 171 graphReader(c7, ss).run(); 171 172 172 173 ss.clear(); 173 174 ss.str(""); 174 ss <<c10_lgf;175 ss << c10_lgf; 175 176 graphReader(c10, ss).run(); 176 177 177 178 ss.clear(); 178 179 ss.str(""); 179 ss <<p10_lgf;180 ss << p10_lgf; 180 181 graphReader(p10, ss).run(); 181 182 … … 194 195 bool operator()(A, B){ 195 196 return false; 197 } 198 }; 199 200 class IntConvertible1 { 201 public: 202 operator int() { 203 return 0; 204 } 205 }; 206 207 class IntConvertible2 { 208 public: 209 operator int() { 210 return 0; 196 211 } 197 212 }; … … 225 240 } 226 241 227 void justCompile() {242 void vf2Compile() { 228 243 checkVf2Compile<concepts::Graph,concepts::Graph>(); 229 244 checkVf2Compile<concepts::Graph,SmartGraph>(); … … 231 246 } 232 247 248 template<class G1,class G2> 249 void checkVf2ppCompile() { 250 G1 g; 251 G2 h; 252 concepts::ReadWriteMap<typename G1::Node, typename G2::Node> r; 253 bool succ; 254 ::lemon::ignore_unused_variable_warning(succ); 255 256 succ = vf2pp(g,h).run(); 257 succ = vf2pp(g,h).induced().run(); 258 succ = vf2pp(g,h).iso().run(); 259 succ = vf2pp(g,h).mapping(r).run(); 260 succ = vf2pp(g,h).induced().mapping(r).run(); 261 succ = vf2pp(g,h).iso().mapping(r).run(); 262 263 concepts::ReadMap<typename G1::Node, int> c1; 264 concepts::ReadMap<typename G2::Node, int> c2; 265 Vf2pp<G1,G2,concepts::ReadWriteMap<typename G1::Node, typename G2::Node>, 266 concepts::ReadMap<typename G1::Node, int>, 267 concepts::ReadMap<typename G2::Node, int> > 268 myVf2pp(g,h,r,c1,c2); 269 myVf2pp.find(); 270 271 succ = vf2pp(g,h).nodeLabels(c1,c2).mapping(r).run(); 272 succ = vf2pp(g,h).nodeLabels(c1,c2).mapping(r).run(); 273 274 concepts::ReadMap<typename G1::Node, char> c1_c; 275 concepts::ReadMap<typename G2::Node, char> c2_c; 276 Vf2pp<G1,G2,concepts::ReadWriteMap<typename G1::Node, typename G2::Node>, 277 concepts::ReadMap<typename G1::Node, char>, 278 concepts::ReadMap<typename G2::Node, char> > 279 myVf2pp_c(g,h,r,c1_c,c2_c); 280 myVf2pp_c.find(); 281 282 succ = vf2pp(g,h).nodeLabels(c1_c,c2_c).mapping(r).run(); 283 succ = vf2pp(g,h).nodeLabels(c1_c,c2_c).mapping(r).run(); 284 285 concepts::ReadMap<typename G1::Node, IntConvertible1> c1_IntConv; 286 concepts::ReadMap<typename G2::Node, IntConvertible2> c2_IntConv; 287 Vf2pp<G1,G2,concepts::ReadWriteMap<typename G1::Node, typename G2::Node>, 288 concepts::ReadMap<typename G1::Node, IntConvertible1>, 289 concepts::ReadMap<typename G2::Node, IntConvertible2> > 290 myVf2pp_IntConv(g,h,r,c1_IntConv,c2_IntConv); 291 myVf2pp_IntConv.find(); 292 293 succ = vf2pp(g,h).nodeLabels(c1_IntConv,c2_IntConv).mapping(r).run(); 294 succ = vf2pp(g,h).nodeLabels(c1_IntConv,c2_IntConv).mapping(r).run(); 295 } 296 297 void vf2ppCompile() { 298 checkVf2ppCompile<concepts::Graph,concepts::Graph>(); 299 checkVf2ppCompile<concepts::Graph,SmartGraph>(); 300 checkVf2ppCompile<SmartGraph,concepts::Graph>(); 301 } 302 233 303 template<class G1, class G2, class I> 234 void checkSub(const G1 &g1, const G2 &g2, const I &i) { 235 { 236 std::set<typename G2::Node> image; 237 for(typename G1::NodeIt n(g1);n!=INVALID;++n){ 238 check(i[n]!=INVALID, "Wrong isomorphism: incomplete mapping."); 239 check(image.count(i[n])==0,"Wrong isomorphism: not injective."); 240 image.insert(i[n]); 241 } 242 } 243 for(typename G1::EdgeIt e(g1);e!=INVALID;++e) 244 check(findEdge(g2,i[g1.u(e)],i[g1.v(e)])!=INVALID, 245 "Wrong isomorphism: missing edge(checkSub)."); 246 } 247 248 template<class G1, class G2, class I> 249 void checkInd(const G1 &g1, const G2 &g2, const I &i) { 304 void checkSubIso(const G1 &g1, const G2 &g2, const I &i) { 250 305 std::set<typename G2::Node> image; 251 for (typename G1::NodeIt n(g1);n!=INVALID;++n){306 for (typename G1::NodeIt n(g1);n!=INVALID;++n){ 252 307 check(i[n]!=INVALID, "Wrong isomorphism: incomplete mapping."); 253 308 check(image.count(i[n])==0,"Wrong isomorphism: not injective."); 254 309 image.insert(i[n]); 255 310 } 256 for(typename G1::NodeIt n(g1); n!=INVALID; ++n) 257 for(typename G1::NodeIt m(g1); m!=INVALID; ++m) 311 for (typename G1::EdgeIt e(g1);e!=INVALID;++e) { 312 check(findEdge(g2,i[g1.u(e)],i[g1.v(e)])!=INVALID, 313 "Wrong isomorphism: missing edge(checkSub)."); 314 } 315 } 316 317 template<class G1, class G2, class I> 318 void checkIndIso(const G1 &g1, const G2 &g2, const I &i) { 319 std::set<typename G2::Node> image; 320 for (typename G1::NodeIt n(g1);n!=INVALID;++n) { 321 check(i[n]!=INVALID, "Wrong isomorphism: incomplete mapping."); 322 check(image.count(i[n])==0,"Wrong isomorphism: not injective."); 323 image.insert(i[n]); 324 } 325 for (typename G1::NodeIt n(g1); n!=INVALID; ++n) { 326 for (typename G1::NodeIt m(g1); m!=INVALID; ++m) { 258 327 if((findEdge(g1,n,m)==INVALID) != (findEdge(g2,i[n],i[m])==INVALID)) { 259 328 std::cout << "Wrong isomorphism: edge mismatch"; 260 329 exit(1); 261 330 } 262 } 263 264 template<class G1,class G2> 265 int checkSub(const G1 &g1, const G2 &g2) { 331 } 332 } 333 } 334 335 template<class G1,class G2,class T> 336 bool checkSub(const G1 &g1, const G2 &g2, const T &vf2) { 266 337 typename G1:: template NodeMap<typename G2::Node> iso(g1,INVALID); 267 if (vf2(g1,g2).mapping(iso).run()) {268 checkSub (g1,g2,iso);338 if (const_cast<T&>(vf2).mapping(iso).run()) { 339 checkSubIso(g1,g2,iso); 269 340 return true; 270 341 } 271 else 272 return false; 273 } 274 275 template<class G1,class G2> 276 int checkInd(const G1 &g1, const G2 &g2) { 342 return false; 343 } 344 345 template<class G1,class G2,class T> 346 bool checkInd(const G1 &g1, const G2 &g2, const T &vf2) { 277 347 typename G1:: template NodeMap<typename G2::Node> iso(g1,INVALID); 278 if (vf2(g1,g2).induced().mapping(iso).run()) {279 checkInd (g1,g2,iso);348 if (const_cast<T&>(vf2).induced().mapping(iso).run()) { 349 checkIndIso(g1,g2,iso); 280 350 return true; 281 351 } 282 else 283 return false; 284 } 285 286 template<class G1,class G2> 287 int checkIso(const G1 &g1, const G2 &g2) { 352 return false; 353 } 354 355 template<class G1,class G2,class T> 356 bool checkIso(const G1 &g1, const G2 &g2, const T &vf2) { 288 357 typename G1:: template NodeMap<typename G2::Node> iso(g1,INVALID); 289 if (vf2(g1,g2).iso().mapping(iso).run()) {358 if (const_cast<T&>(vf2).iso().mapping(iso).run()) { 290 359 check(countNodes(g1)==countNodes(g2), 291 360 "Wrong iso alg.: they are not isomophic."); 292 checkInd (g1,g2,iso);361 checkIndIso(g1,g2,iso); 293 362 return true; 294 363 } 295 else 296 return false; 364 return false; 297 365 } 298 366 299 367 template<class G1, class G2, class L1, class L2, class I> 300 368 void checkLabel(const G1 &g1, const G2 &, 301 const L1 &l1, const L2 &l2, const I &i) {302 for (typename G1::NodeIt n(g1);n!=INVALID;++n)369 const L1 &l1, const L2 &l2, const I &i) { 370 for (typename G1::NodeIt n(g1);n!=INVALID;++n) { 303 371 check(l1[n]==l2[i[n]],"Wrong isomorphism: label mismatch."); 304 } 305 306 template<class G1,class G2,class L1,class L2> 307 int checkSub(const G1 &g1, const G2 &g2, const L1 &l1, const L2 &l2) { 372 } 373 } 374 375 template<class G1,class G2,class L1,class L2,class T> 376 bool checkSub(const G1 &g1, const G2 &g2, const L1 &l1, const L2 &l2, const T &vf2) { 308 377 typename G1:: template NodeMap<typename G2::Node> iso(g1,INVALID); 309 if (vf2(g1,g2).nodeLabels(l1,l2).mapping(iso).run()){310 checkSub (g1,g2,iso);378 if (const_cast<T&>(vf2).nodeLabels(l1,l2).mapping(iso).run()){ 379 checkSubIso(g1,g2,iso); 311 380 checkLabel(g1,g2,l1,l2,iso); 312 381 return true; 313 382 } 314 else 315 return false; 383 return false; 384 } 385 386 template<class G1,class G2> 387 void checkSub(const G1 &g1, const G2 &g2, bool expected, const char* msg) { 388 check(checkSub(g1,g2,vf2(g1,g2)) == expected, msg); 389 check(checkSub(g1,g2,vf2pp(g1,g2)) == expected, msg); 390 } 391 392 template<class G1,class G2> 393 void checkInd(const G1 &g1, const G2 &g2, bool expected, const char* msg) { 394 check(checkInd(g1,g2,vf2(g1,g2)) == expected, msg); 395 check(checkInd(g1,g2,vf2pp(g1,g2)) == expected, msg); 396 } 397 398 template<class G1,class G2> 399 void checkIso(const G1 &g1, const G2 &g2, bool expected, const char* msg) { 400 check(checkIso(g1,g2,vf2(g1,g2)) == expected, msg); 401 check(checkIso(g1,g2,vf2pp(g1,g2)) == expected, msg); 402 } 403 404 template<class G1,class G2,class L1,class L2> 405 void checkSub(const G1 &g1, const G2 &g2, const L1 &l1, const L2 &l2, bool expected, const char* msg) { 406 check(checkSub(g1,g2,l1,l2,vf2(g1,g2)) == expected, msg); 407 check(checkSub(g1,g2,l1,l2,vf2pp(g1,g2)) == expected, msg); 316 408 } 317 409 318 410 int main() { 319 411 make_graphs(); 320 // justCompile(); 321 check(checkSub(c5,petersen), "There should exist a C5>Petersen mapping."); 322 check(!checkSub(c7,petersen), 323 "There should not exist a C7>Petersen mapping."); 324 check(checkSub(p10,petersen), "There should exist a P10>Petersen mapping."); 325 check(!checkSub(c10,petersen), 326 "There should not exist a C10>Petersen mapping."); 327 check(checkSub(petersen,petersen), 328 "There should exist a Petersen>Petersen mapping."); 329 330 check(checkInd(c5,petersen), 331 "There should exist a C5>Petersen spanned mapping."); 332 check(!checkInd(c7,petersen), 333 "There should exist a C7>Petersen spanned mapping."); 334 check(!checkInd(p10,petersen), 335 "There should not exist a P10>Petersen spanned mapping."); 336 check(!checkInd(c10,petersen), 337 "There should not exist a C10>Petersen spanned mapping."); 338 check(checkInd(petersen,petersen), 412 413 checkSub(c5,petersen,true, 414 "There should exist a C5>Petersen mapping."); 415 checkSub(c7,petersen,false, 416 "There should not exist a C7>Petersen mapping."); 417 checkSub(p10,petersen,true, 418 "There should exist a P10>Petersen mapping."); 419 checkSub(c10,petersen,false, 420 "There should not exist a C10>Petersen mapping."); 421 checkSub(petersen,petersen,true, 422 "There should exist a Petersen>Petersen mapping."); 423 424 checkInd(c5,petersen,true, 425 "There should exist a C5>Petersen spanned mapping."); 426 checkInd(c7,petersen,false, 427 "There should exist a C7>Petersen spanned mapping."); 428 checkInd(p10,petersen,false, 429 "There should not exist a P10>Petersen spanned mapping."); 430 checkInd(c10,petersen,false, 431 "There should not exist a C10>Petersen spanned mapping."); 432 checkInd(petersen,petersen,true, 339 433 "There should exist a Petersen>Petersen spanned mapping."); 340 434 341 check(!checkSub(petersen,c10), 342 "There should not exist a Petersen>C10 mapping."); 343 check(checkSub(p10,c10), 344 "There should exist a P10>C10 mapping."); 345 check(!checkInd(p10,c10), 346 "There should not exist a P10>C10 spanned mapping."); 347 check(!checkSub(c10,p10), 348 "There should not exist a C10>P10 mapping."); 349 350 check(!checkIso(p10,c10), 351 "P10 and C10 are not isomorphic."); 352 check(checkIso(c10,c10), 353 "C10 and C10 are isomorphic."); 354 355 check(!vf2(p10,c10).iso().run(), 356 "P10 and C10 are not isomorphic."); 357 check(vf2(c10,c10).iso().run(), 358 "C10 and C10 are isomorphic."); 359 360 check(!checkSub(c5,petersen,c5_col,petersen_col1), 361 "There should exist a C5>Petersen mapping."); 362 check(checkSub(c5,petersen,c5_col,petersen_col2), 363 "There should exist a C5>Petersen mapping."); 364 } 435 checkSub(petersen,c10,false, 436 "There should not exist a Petersen>C10 mapping."); 437 checkSub(p10,c10,true, 438 "There should exist a P10>C10 mapping."); 439 checkInd(p10,c10,false, 440 "There should not exist a P10>C10 spanned mapping."); 441 checkSub(c10,p10,false, 442 "There should not exist a C10>P10 mapping."); 443 444 checkIso(p10,c10,false, 445 "P10 and C10 are not isomorphic."); 446 checkIso(c10,c10,true, 447 "C10 and C10 are isomorphic."); 448 449 checkSub(c5,petersen,c5_col,petersen_col1,false, 450 "There should exist a C5>Petersen mapping."); 451 checkSub(c5,petersen,c5_col,petersen_col2,true, 452 "There should exist a C5>Petersen mapping."); 453 454 check(!vf2(p10,c10).iso().run(), "P10 and C10 are not isomorphic."); 455 check(!vf2pp(p10,c10).iso().run(), "P10 and C10 are not isomorphic."); 456 457 check(vf2(c10,c10).iso().run(), "C10 and C10 are isomorphic."); 458 check(vf2pp(c10,c10).iso().run(), "C10 and C10 are isomorphic."); 459 }
Note: See TracChangeset
for help on using the changeset viewer.