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