1.1 --- a/test/vf2_test.cc Wed Oct 17 19:22:52 2018 +0200
1.2 +++ b/test/vf2_test.cc Wed Oct 17 22:56:43 2018 +0200
1.3 @@ -2,7 +2,7 @@
1.4 *
1.5 * This file is a part of LEMON, a generic C++ optimization library.
1.6 *
1.7 - * Copyright (C) 2015
1.8 + * Copyright (C) 2015-2017
1.9 * EMAXA Kutato-fejleszto Kft. (EMAXA Research Ltd.)
1.10 *
1.11 * Permission to use, modify and distribute this software is granted
1.12 @@ -16,6 +16,7 @@
1.13 */
1.14
1.15 #include <lemon/vf2.h>
1.16 +#include <lemon/vf2pp.h>
1.17 #include <lemon/concepts/digraph.h>
1.18 #include <lemon/smart_graph.h>
1.19 #include <lemon/lgf_reader.h>
1.20 @@ -152,49 +153,66 @@
1.21 void make_graphs() {
1.22 std::stringstream ss(petersen_lgf);
1.23 graphReader(petersen, ss)
1.24 - .nodeMap("col1",petersen_col1)
1.25 - .nodeMap("col2",petersen_col2)
1.26 + .nodeMap("col1", petersen_col1)
1.27 + .nodeMap("col2", petersen_col2)
1.28 .run();
1.29
1.30 ss.clear();
1.31 ss.str("");
1.32 - ss<<c5_lgf;
1.33 + ss << c5_lgf;
1.34 //std::stringstream ss2(c5_lgf);
1.35 graphReader(c5, ss)
1.36 - .nodeMap("col",c5_col)
1.37 + .nodeMap("col", c5_col)
1.38 .run();
1.39
1.40 ss.clear();
1.41 ss.str("");
1.42 - ss<<c7_lgf;
1.43 + ss << c7_lgf;
1.44 graphReader(c7, ss).run();
1.45
1.46 ss.clear();
1.47 ss.str("");
1.48 - ss<<c10_lgf;
1.49 + ss << c10_lgf;
1.50 graphReader(c10, ss).run();
1.51
1.52 ss.clear();
1.53 ss.str("");
1.54 - ss<<p10_lgf;
1.55 + ss << p10_lgf;
1.56 graphReader(p10, ss).run();
1.57
1.58 }
1.59
1.60 class EqComparable {
1.61 public:
1.62 - bool operator==(const EqComparable&) { return false; }
1.63 + bool operator==(const EqComparable&) {
1.64 + return false;
1.65 + }
1.66 };
1.67
1.68 template<class A, class B>
1.69 class EqClass {
1.70 public:
1.71 - bool operator()(A, B) { return false; }
1.72 + bool operator()(A, B){
1.73 + return false;
1.74 + }
1.75 +};
1.76 +
1.77 +class IntConvertible1 {
1.78 +public:
1.79 + operator int() {
1.80 + return 0;
1.81 + }
1.82 +};
1.83 +
1.84 +class IntConvertible2 {
1.85 +public:
1.86 + operator int() {
1.87 + return 0;
1.88 + }
1.89 };
1.90
1.91 template<class G1,class G2>
1.92 -void checkVf2Compile()
1.93 -{
1.94 +void checkVf2Compile() {
1.95 G1 g;
1.96 G2 h;
1.97 concepts::ReadWriteMap<typename G1::Node, typename G2::Node> r;
1.98 @@ -205,8 +223,15 @@
1.99 succ = vf2(g,h).induced().run();
1.100 succ = vf2(g,h).iso().run();
1.101 succ = vf2(g,h).mapping(r).run();
1.102 +
1.103 + Vf2<G1,G2,concepts::ReadWriteMap<typename G1::Node, typename G2::Node>,
1.104 + EqClass<typename G1::Node,typename G2::Node> >
1.105 + myVf2(g,h,r,EqClass<typename G1::Node,typename G2::Node>());
1.106 + myVf2.find();
1.107 +
1.108 succ = vf2(g,h).induced().mapping(r).run();
1.109 succ = vf2(g,h).iso().mapping(r).run();
1.110 +
1.111 concepts::ReadMap<typename G1::Node, EqComparable> l1;
1.112 concepts::ReadMap<typename G2::Node, EqComparable> l2;
1.113 succ = vf2(g,h).nodeLabels(l1,l2).mapping(r).run();
1.114 @@ -214,153 +239,221 @@
1.115 .mapping(r).run();
1.116 }
1.117
1.118 -void justCompile()
1.119 -{
1.120 +void vf2Compile() {
1.121 checkVf2Compile<concepts::Graph,concepts::Graph>();
1.122 checkVf2Compile<concepts::Graph,SmartGraph>();
1.123 checkVf2Compile<SmartGraph,concepts::Graph>();
1.124 }
1.125
1.126 -template<class G1, class G2, class I>
1.127 -void checkSub(const G1 &g1, const G2 &g2, const I &i)
1.128 -{
1.129 - {
1.130 - std::set<typename G2::Node> image;
1.131 - for(typename G1::NodeIt n(g1);n!=INVALID;++n)
1.132 - {
1.133 - check(i[n]!=INVALID, "Wrong isomorphism: incomplete mapping.");
1.134 - check(image.count(i[n])==0,"Wrong isomorphism: not injective.");
1.135 - image.insert(i[n]);
1.136 - }
1.137 - }
1.138 - for(typename G1::EdgeIt e(g1);e!=INVALID;++e)
1.139 - check(findEdge(g2,i[g1.u(e)],i[g1.v(e)])!=INVALID,
1.140 - "Wrong isomorphism: missing edge(checkSub).");
1.141 +template<class G1,class G2>
1.142 +void checkVf2ppCompile() {
1.143 + G1 g;
1.144 + G2 h;
1.145 + concepts::ReadWriteMap<typename G1::Node, typename G2::Node> r;
1.146 + bool succ;
1.147 + ::lemon::ignore_unused_variable_warning(succ);
1.148 +
1.149 + succ = vf2pp(g,h).run();
1.150 + succ = vf2pp(g,h).induced().run();
1.151 + succ = vf2pp(g,h).iso().run();
1.152 + succ = vf2pp(g,h).mapping(r).run();
1.153 + succ = vf2pp(g,h).induced().mapping(r).run();
1.154 + succ = vf2pp(g,h).iso().mapping(r).run();
1.155 +
1.156 + concepts::ReadMap<typename G1::Node, int> c1;
1.157 + concepts::ReadMap<typename G2::Node, int> c2;
1.158 + Vf2pp<G1,G2,concepts::ReadWriteMap<typename G1::Node, typename G2::Node>,
1.159 + concepts::ReadMap<typename G1::Node, int>,
1.160 + concepts::ReadMap<typename G2::Node, int> >
1.161 + myVf2pp(g,h,r,c1,c2);
1.162 + myVf2pp.find();
1.163 +
1.164 + succ = vf2pp(g,h).nodeLabels(c1,c2).mapping(r).run();
1.165 + succ = vf2pp(g,h).nodeLabels(c1,c2).mapping(r).run();
1.166 +
1.167 + concepts::ReadMap<typename G1::Node, char> c1_c;
1.168 + concepts::ReadMap<typename G2::Node, char> c2_c;
1.169 + Vf2pp<G1,G2,concepts::ReadWriteMap<typename G1::Node, typename G2::Node>,
1.170 + concepts::ReadMap<typename G1::Node, char>,
1.171 + concepts::ReadMap<typename G2::Node, char> >
1.172 + myVf2pp_c(g,h,r,c1_c,c2_c);
1.173 + myVf2pp_c.find();
1.174 +
1.175 + succ = vf2pp(g,h).nodeLabels(c1_c,c2_c).mapping(r).run();
1.176 + succ = vf2pp(g,h).nodeLabels(c1_c,c2_c).mapping(r).run();
1.177 +
1.178 + concepts::ReadMap<typename G1::Node, IntConvertible1> c1_IntConv;
1.179 + concepts::ReadMap<typename G2::Node, IntConvertible2> c2_IntConv;
1.180 + Vf2pp<G1,G2,concepts::ReadWriteMap<typename G1::Node, typename G2::Node>,
1.181 + concepts::ReadMap<typename G1::Node, IntConvertible1>,
1.182 + concepts::ReadMap<typename G2::Node, IntConvertible2> >
1.183 + myVf2pp_IntConv(g,h,r,c1_IntConv,c2_IntConv);
1.184 + myVf2pp_IntConv.find();
1.185 +
1.186 + succ = vf2pp(g,h).nodeLabels(c1_IntConv,c2_IntConv).mapping(r).run();
1.187 + succ = vf2pp(g,h).nodeLabels(c1_IntConv,c2_IntConv).mapping(r).run();
1.188 +}
1.189 +
1.190 +void vf2ppCompile() {
1.191 + checkVf2ppCompile<concepts::Graph,concepts::Graph>();
1.192 + checkVf2ppCompile<concepts::Graph,SmartGraph>();
1.193 + checkVf2ppCompile<SmartGraph,concepts::Graph>();
1.194 }
1.195
1.196 template<class G1, class G2, class I>
1.197 -void checkInd(const G1 &g1, const G2 &g2, const I &i)
1.198 - {
1.199 +void checkSubIso(const G1 &g1, const G2 &g2, const I &i) {
1.200 std::set<typename G2::Node> image;
1.201 - for(typename G1::NodeIt n(g1);n!=INVALID;++n)
1.202 - {
1.203 + for (typename G1::NodeIt n(g1);n!=INVALID;++n){
1.204 check(i[n]!=INVALID, "Wrong isomorphism: incomplete mapping.");
1.205 check(image.count(i[n])==0,"Wrong isomorphism: not injective.");
1.206 image.insert(i[n]);
1.207 - }
1.208 - for(typename G1::NodeIt n(g1); n!=INVALID; ++n)
1.209 - for(typename G1::NodeIt m(g1); m!=INVALID; ++m)
1.210 - if((findEdge(g1,n,m)==INVALID) != (findEdge(g2,i[n],i[m])==INVALID))
1.211 - {
1.212 + }
1.213 + for (typename G1::EdgeIt e(g1);e!=INVALID;++e) {
1.214 + check(findEdge(g2,i[g1.u(e)],i[g1.v(e)])!=INVALID,
1.215 + "Wrong isomorphism: missing edge(checkSub).");
1.216 + }
1.217 +}
1.218 +
1.219 +template<class G1, class G2, class I>
1.220 +void checkIndIso(const G1 &g1, const G2 &g2, const I &i) {
1.221 + std::set<typename G2::Node> image;
1.222 + for (typename G1::NodeIt n(g1);n!=INVALID;++n) {
1.223 + check(i[n]!=INVALID, "Wrong isomorphism: incomplete mapping.");
1.224 + check(image.count(i[n])==0,"Wrong isomorphism: not injective.");
1.225 + image.insert(i[n]);
1.226 + }
1.227 + for (typename G1::NodeIt n(g1); n!=INVALID; ++n) {
1.228 + for (typename G1::NodeIt m(g1); m!=INVALID; ++m) {
1.229 + if((findEdge(g1,n,m)==INVALID) != (findEdge(g2,i[n],i[m])==INVALID)) {
1.230 std::cout << "Wrong isomorphism: edge mismatch";
1.231 exit(1);
1.232 - }
1.233 + }
1.234 + }
1.235 }
1.236 -
1.237 -template<class G1,class G2>
1.238 -int checkSub(const G1 &g1, const G2 &g2)
1.239 -{
1.240 - typename G1:: template NodeMap<typename G2::Node> iso(g1,INVALID);
1.241 - if(vf2(g1,g2).mapping(iso).run())
1.242 - {
1.243 - checkSub(g1,g2,iso);
1.244 - return true;
1.245 - }
1.246 - else return false;
1.247 }
1.248
1.249 -template<class G1,class G2>
1.250 -int checkInd(const G1 &g1, const G2 &g2)
1.251 -{
1.252 +template<class G1,class G2,class T>
1.253 +bool checkSub(const G1 &g1, const G2 &g2, const T &vf2) {
1.254 typename G1:: template NodeMap<typename G2::Node> iso(g1,INVALID);
1.255 - if(vf2(g1,g2).induced().mapping(iso).run())
1.256 - {
1.257 - checkInd(g1,g2,iso);
1.258 - return true;
1.259 - }
1.260 - else return false;
1.261 + if (const_cast<T&>(vf2).mapping(iso).run()) {
1.262 + checkSubIso(g1,g2,iso);
1.263 + return true;
1.264 + }
1.265 + return false;
1.266 }
1.267
1.268 -template<class G1,class G2>
1.269 -int checkIso(const G1 &g1, const G2 &g2)
1.270 -{
1.271 +template<class G1,class G2,class T>
1.272 +bool checkInd(const G1 &g1, const G2 &g2, const T &vf2) {
1.273 typename G1:: template NodeMap<typename G2::Node> iso(g1,INVALID);
1.274 - if(vf2(g1,g2).iso().mapping(iso).run())
1.275 - {
1.276 - check(countNodes(g1)==countNodes(g2),
1.277 - "Wrong iso alg.: they are not isomophic.");
1.278 - checkInd(g1,g2,iso);
1.279 - return true;
1.280 - }
1.281 - else return false;
1.282 + if (const_cast<T&>(vf2).induced().mapping(iso).run()) {
1.283 + checkIndIso(g1,g2,iso);
1.284 + return true;
1.285 + }
1.286 + return false;
1.287 +}
1.288 +
1.289 +template<class G1,class G2,class T>
1.290 +bool checkIso(const G1 &g1, const G2 &g2, const T &vf2) {
1.291 + typename G1:: template NodeMap<typename G2::Node> iso(g1,INVALID);
1.292 + if (const_cast<T&>(vf2).iso().mapping(iso).run()) {
1.293 + check(countNodes(g1)==countNodes(g2),
1.294 + "Wrong iso alg.: they are not isomophic.");
1.295 + checkIndIso(g1,g2,iso);
1.296 + return true;
1.297 + }
1.298 + return false;
1.299 }
1.300
1.301 template<class G1, class G2, class L1, class L2, class I>
1.302 void checkLabel(const G1 &g1, const G2 &,
1.303 - const L1 &l1, const L2 &l2,const I &i)
1.304 -{
1.305 - for(typename G1::NodeIt n(g1);n!=INVALID;++n)
1.306 - {
1.307 - check(l1[n]==l2[i[n]],"Wrong isomorphism: label mismatch.");
1.308 - }
1.309 + const L1 &l1, const L2 &l2, const I &i) {
1.310 + for (typename G1::NodeIt n(g1);n!=INVALID;++n) {
1.311 + check(l1[n]==l2[i[n]],"Wrong isomorphism: label mismatch.");
1.312 + }
1.313 +}
1.314 +
1.315 +template<class G1,class G2,class L1,class L2,class T>
1.316 +bool checkSub(const G1 &g1, const G2 &g2, const L1 &l1, const L2 &l2, const T &vf2) {
1.317 + typename G1:: template NodeMap<typename G2::Node> iso(g1,INVALID);
1.318 + if (const_cast<T&>(vf2).nodeLabels(l1,l2).mapping(iso).run()){
1.319 + checkSubIso(g1,g2,iso);
1.320 + checkLabel(g1,g2,l1,l2,iso);
1.321 + return true;
1.322 + }
1.323 + return false;
1.324 +}
1.325 +
1.326 +template<class G1,class G2>
1.327 +void checkSub(const G1 &g1, const G2 &g2, bool expected, const char* msg) {
1.328 + check(checkSub(g1,g2,vf2(g1,g2)) == expected, msg);
1.329 + check(checkSub(g1,g2,vf2pp(g1,g2)) == expected, msg);
1.330 +}
1.331 +
1.332 +template<class G1,class G2>
1.333 +void checkInd(const G1 &g1, const G2 &g2, bool expected, const char* msg) {
1.334 + check(checkInd(g1,g2,vf2(g1,g2)) == expected, msg);
1.335 + check(checkInd(g1,g2,vf2pp(g1,g2)) == expected, msg);
1.336 +}
1.337 +
1.338 +template<class G1,class G2>
1.339 +void checkIso(const G1 &g1, const G2 &g2, bool expected, const char* msg) {
1.340 + check(checkIso(g1,g2,vf2(g1,g2)) == expected, msg);
1.341 + check(checkIso(g1,g2,vf2pp(g1,g2)) == expected, msg);
1.342 }
1.343
1.344 template<class G1,class G2,class L1,class L2>
1.345 -int checkSub(const G1 &g1, const G2 &g2, const L1 &l1, const L2 &l2)
1.346 -{
1.347 - typename G1:: template NodeMap<typename G2::Node> iso(g1,INVALID);
1.348 - if(vf2(g1,g2).nodeLabels(l1,l2).mapping(iso).run())
1.349 - {
1.350 - checkSub(g1,g2,iso);
1.351 - checkLabel(g1,g2,l1,l2,iso);
1.352 - return true;
1.353 - }
1.354 - else return false;
1.355 +void checkSub(const G1 &g1, const G2 &g2, const L1 &l1, const L2 &l2, bool expected, const char* msg) {
1.356 + check(checkSub(g1,g2,l1,l2,vf2(g1,g2)) == expected, msg);
1.357 + check(checkSub(g1,g2,l1,l2,vf2pp(g1,g2)) == expected, msg);
1.358 }
1.359
1.360 int main() {
1.361 make_graphs();
1.362 - check(checkSub(c5,petersen), "There should exist a C5->Petersen mapping.");
1.363 - check(!checkSub(c7,petersen),
1.364 - "There should not exist a C7->Petersen mapping.");
1.365 - check(checkSub(p10,petersen), "There should exist a P10->Petersen mapping.");
1.366 - check(!checkSub(c10,petersen),
1.367 - "There should not exist a C10->Petersen mapping.");
1.368 - check(checkSub(petersen,petersen),
1.369 - "There should exist a Petersen->Petersen mapping.");
1.370
1.371 - check(checkInd(c5,petersen),
1.372 - "There should exist a C5->Petersen spanned mapping.");
1.373 - check(!checkInd(c7,petersen),
1.374 - "There should exist a C7->Petersen spanned mapping.");
1.375 - check(!checkInd(p10,petersen),
1.376 - "There should not exist a P10->Petersen spanned mapping.");
1.377 - check(!checkInd(c10,petersen),
1.378 - "There should not exist a C10->Petersen spanned mapping.");
1.379 - check(checkInd(petersen,petersen),
1.380 + checkSub(c5,petersen,true,
1.381 + "There should exist a C5->Petersen mapping.");
1.382 + checkSub(c7,petersen,false,
1.383 + "There should not exist a C7->Petersen mapping.");
1.384 + checkSub(p10,petersen,true,
1.385 + "There should exist a P10->Petersen mapping.");
1.386 + checkSub(c10,petersen,false,
1.387 + "There should not exist a C10->Petersen mapping.");
1.388 + checkSub(petersen,petersen,true,
1.389 + "There should exist a Petersen->Petersen mapping.");
1.390 +
1.391 + checkInd(c5,petersen,true,
1.392 + "There should exist a C5->Petersen spanned mapping.");
1.393 + checkInd(c7,petersen,false,
1.394 + "There should exist a C7->Petersen spanned mapping.");
1.395 + checkInd(p10,petersen,false,
1.396 + "There should not exist a P10->Petersen spanned mapping.");
1.397 + checkInd(c10,petersen,false,
1.398 + "There should not exist a C10->Petersen spanned mapping.");
1.399 + checkInd(petersen,petersen,true,
1.400 "There should exist a Petersen->Petersen spanned mapping.");
1.401
1.402 - check(!checkSub(petersen,c10),
1.403 - "There should not exist a Petersen->C10 mapping.");
1.404 - check(checkSub(p10,c10),
1.405 - "There should exist a P10->C10 mapping.");
1.406 - check(!checkInd(p10,c10),
1.407 - "There should not exist a P10->C10 spanned mapping.");
1.408 - check(!checkSub(c10,p10),
1.409 - "There should not exist a C10->P10 mapping.");
1.410 + checkSub(petersen,c10,false,
1.411 + "There should not exist a Petersen->C10 mapping.");
1.412 + checkSub(p10,c10,true,
1.413 + "There should exist a P10->C10 mapping.");
1.414 + checkInd(p10,c10,false,
1.415 + "There should not exist a P10->C10 spanned mapping.");
1.416 + checkSub(c10,p10,false,
1.417 + "There should not exist a C10->P10 mapping.");
1.418
1.419 - check(!checkIso(p10,c10),
1.420 - "P10 and C10 are not isomorphic.");
1.421 - check(checkIso(c10,c10),
1.422 - "C10 and C10 are isomorphic.");
1.423 + checkIso(p10,c10,false,
1.424 + "P10 and C10 are not isomorphic.");
1.425 + checkIso(c10,c10,true,
1.426 + "C10 and C10 are isomorphic.");
1.427
1.428 - check(!vf2(p10,c10).iso().run(),
1.429 - "P10 and C10 are not isomorphic.");
1.430 - check(vf2(c10,c10).iso().run(),
1.431 - "C10 and C10 are isomorphic.");
1.432 + checkSub(c5,petersen,c5_col,petersen_col1,false,
1.433 + "There should exist a C5->Petersen mapping.");
1.434 + checkSub(c5,petersen,c5_col,petersen_col2,true,
1.435 + "There should exist a C5->Petersen mapping.");
1.436
1.437 - check(!checkSub(c5,petersen,c5_col,petersen_col1),
1.438 - "There should exist a C5->Petersen mapping.");
1.439 - check(checkSub(c5,petersen,c5_col,petersen_col2),
1.440 - "There should exist a C5->Petersen mapping.");
1.441 + check(!vf2(p10,c10).iso().run(), "P10 and C10 are not isomorphic.");
1.442 + check(!vf2pp(p10,c10).iso().run(), "P10 and C10 are not isomorphic.");
1.443 +
1.444 + check(vf2(c10,c10).iso().run(), "C10 and C10 are isomorphic.");
1.445 + check(vf2pp(c10,c10).iso().run(), "C10 and C10 are isomorphic.");
1.446 }