1.1 --- a/test/CMakeLists.txt Tue Sep 19 14:08:20 2017 +0200
1.2 +++ b/test/CMakeLists.txt Sat Oct 07 00:14:05 2017 +0200
1.3 @@ -55,7 +55,6 @@
1.4 tsp_test
1.5 unionfind_test
1.6 vf2_test
1.7 - vf2pp_test
1.8 )
1.9
1.10 IF(LEMON_HAVE_LP)
2.1 --- a/test/vf2_test.cc Tue Sep 19 14:08:20 2017 +0200
2.2 +++ b/test/vf2_test.cc Sat Oct 07 00:14:05 2017 +0200
2.3 @@ -16,6 +16,7 @@
2.4 */
2.5
2.6 #include <lemon/vf2.h>
2.7 +#include <lemon/vf2pp.h>
2.8 #include <lemon/concepts/digraph.h>
2.9 #include <lemon/smart_graph.h>
2.10 #include <lemon/lgf_reader.h>
2.11 @@ -152,31 +153,31 @@
2.12 void make_graphs() {
2.13 std::stringstream ss(petersen_lgf);
2.14 graphReader(petersen, ss)
2.15 - .nodeMap("col1",petersen_col1)
2.16 - .nodeMap("col2",petersen_col2)
2.17 + .nodeMap("col1", petersen_col1)
2.18 + .nodeMap("col2", petersen_col2)
2.19 .run();
2.20
2.21 ss.clear();
2.22 ss.str("");
2.23 - ss<<c5_lgf;
2.24 + ss << c5_lgf;
2.25 //std::stringstream ss2(c5_lgf);
2.26 graphReader(c5, ss)
2.27 - .nodeMap("col",c5_col)
2.28 + .nodeMap("col", c5_col)
2.29 .run();
2.30
2.31 ss.clear();
2.32 ss.str("");
2.33 - ss<<c7_lgf;
2.34 + ss << c7_lgf;
2.35 graphReader(c7, ss).run();
2.36
2.37 ss.clear();
2.38 ss.str("");
2.39 - ss<<c10_lgf;
2.40 + ss << c10_lgf;
2.41 graphReader(c10, ss).run();
2.42
2.43 ss.clear();
2.44 ss.str("");
2.45 - ss<<p10_lgf;
2.46 + ss << p10_lgf;
2.47 graphReader(p10, ss).run();
2.48
2.49 }
2.50 @@ -196,6 +197,20 @@
2.51 }
2.52 };
2.53
2.54 +class IntConvertible1 {
2.55 +public:
2.56 + operator int() {
2.57 + return 0;
2.58 + }
2.59 +};
2.60 +
2.61 +class IntConvertible2 {
2.62 +public:
2.63 + operator int() {
2.64 + return 0;
2.65 + }
2.66 +};
2.67 +
2.68 template<class G1,class G2>
2.69 void checkVf2Compile() {
2.70 G1 g;
2.71 @@ -224,141 +239,221 @@
2.72 .mapping(r).run();
2.73 }
2.74
2.75 -void justCompile() {
2.76 +void vf2Compile() {
2.77 checkVf2Compile<concepts::Graph,concepts::Graph>();
2.78 checkVf2Compile<concepts::Graph,SmartGraph>();
2.79 checkVf2Compile<SmartGraph,concepts::Graph>();
2.80 }
2.81
2.82 -template<class G1, class G2, class I>
2.83 -void checkSub(const G1 &g1, const G2 &g2, const I &i) {
2.84 - {
2.85 - std::set<typename G2::Node> image;
2.86 - for(typename G1::NodeIt n(g1);n!=INVALID;++n){
2.87 - check(i[n]!=INVALID, "Wrong isomorphism: incomplete mapping.");
2.88 - check(image.count(i[n])==0,"Wrong isomorphism: not injective.");
2.89 - image.insert(i[n]);
2.90 - }
2.91 - }
2.92 - for(typename G1::EdgeIt e(g1);e!=INVALID;++e)
2.93 - check(findEdge(g2,i[g1.u(e)],i[g1.v(e)])!=INVALID,
2.94 - "Wrong isomorphism: missing edge(checkSub).");
2.95 +template<class G1,class G2>
2.96 +void checkVf2ppCompile() {
2.97 + G1 g;
2.98 + G2 h;
2.99 + concepts::ReadWriteMap<typename G1::Node, typename G2::Node> r;
2.100 + bool succ;
2.101 + ::lemon::ignore_unused_variable_warning(succ);
2.102 +
2.103 + succ = vf2pp(g,h).run();
2.104 + succ = vf2pp(g,h).induced().run();
2.105 + succ = vf2pp(g,h).iso().run();
2.106 + succ = vf2pp(g,h).mapping(r).run();
2.107 + succ = vf2pp(g,h).induced().mapping(r).run();
2.108 + succ = vf2pp(g,h).iso().mapping(r).run();
2.109 +
2.110 + concepts::ReadMap<typename G1::Node, int> c1;
2.111 + concepts::ReadMap<typename G2::Node, int> c2;
2.112 + Vf2pp<G1,G2,concepts::ReadWriteMap<typename G1::Node, typename G2::Node>,
2.113 + concepts::ReadMap<typename G1::Node, int>,
2.114 + concepts::ReadMap<typename G2::Node, int> >
2.115 + myVf2pp(g,h,r,c1,c2);
2.116 + myVf2pp.find();
2.117 +
2.118 + succ = vf2pp(g,h).nodeLabels(c1,c2).mapping(r).run();
2.119 + succ = vf2pp(g,h).nodeLabels(c1,c2).mapping(r).run();
2.120 +
2.121 + concepts::ReadMap<typename G1::Node, char> c1_c;
2.122 + concepts::ReadMap<typename G2::Node, char> c2_c;
2.123 + Vf2pp<G1,G2,concepts::ReadWriteMap<typename G1::Node, typename G2::Node>,
2.124 + concepts::ReadMap<typename G1::Node, char>,
2.125 + concepts::ReadMap<typename G2::Node, char> >
2.126 + myVf2pp_c(g,h,r,c1_c,c2_c);
2.127 + myVf2pp_c.find();
2.128 +
2.129 + succ = vf2pp(g,h).nodeLabels(c1_c,c2_c).mapping(r).run();
2.130 + succ = vf2pp(g,h).nodeLabels(c1_c,c2_c).mapping(r).run();
2.131 +
2.132 + concepts::ReadMap<typename G1::Node, IntConvertible1> c1_IntConv;
2.133 + concepts::ReadMap<typename G2::Node, IntConvertible2> c2_IntConv;
2.134 + Vf2pp<G1,G2,concepts::ReadWriteMap<typename G1::Node, typename G2::Node>,
2.135 + concepts::ReadMap<typename G1::Node, IntConvertible1>,
2.136 + concepts::ReadMap<typename G2::Node, IntConvertible2> >
2.137 + myVf2pp_IntConv(g,h,r,c1_IntConv,c2_IntConv);
2.138 + myVf2pp_IntConv.find();
2.139 +
2.140 + succ = vf2pp(g,h).nodeLabels(c1_IntConv,c2_IntConv).mapping(r).run();
2.141 + succ = vf2pp(g,h).nodeLabels(c1_IntConv,c2_IntConv).mapping(r).run();
2.142 +}
2.143 +
2.144 +void vf2ppCompile() {
2.145 + checkVf2ppCompile<concepts::Graph,concepts::Graph>();
2.146 + checkVf2ppCompile<concepts::Graph,SmartGraph>();
2.147 + checkVf2ppCompile<SmartGraph,concepts::Graph>();
2.148 }
2.149
2.150 template<class G1, class G2, class I>
2.151 -void checkInd(const G1 &g1, const G2 &g2, const I &i) {
2.152 +void checkSubIso(const G1 &g1, const G2 &g2, const I &i) {
2.153 std::set<typename G2::Node> image;
2.154 - for(typename G1::NodeIt n(g1);n!=INVALID;++n) {
2.155 + for (typename G1::NodeIt n(g1);n!=INVALID;++n){
2.156 check(i[n]!=INVALID, "Wrong isomorphism: incomplete mapping.");
2.157 check(image.count(i[n])==0,"Wrong isomorphism: not injective.");
2.158 image.insert(i[n]);
2.159 }
2.160 - for(typename G1::NodeIt n(g1); n!=INVALID; ++n)
2.161 - for(typename G1::NodeIt m(g1); m!=INVALID; ++m)
2.162 + for (typename G1::EdgeIt e(g1);e!=INVALID;++e) {
2.163 + check(findEdge(g2,i[g1.u(e)],i[g1.v(e)])!=INVALID,
2.164 + "Wrong isomorphism: missing edge(checkSub).");
2.165 + }
2.166 +}
2.167 +
2.168 +template<class G1, class G2, class I>
2.169 +void checkIndIso(const G1 &g1, const G2 &g2, const I &i) {
2.170 + std::set<typename G2::Node> image;
2.171 + for (typename G1::NodeIt n(g1);n!=INVALID;++n) {
2.172 + check(i[n]!=INVALID, "Wrong isomorphism: incomplete mapping.");
2.173 + check(image.count(i[n])==0,"Wrong isomorphism: not injective.");
2.174 + image.insert(i[n]);
2.175 + }
2.176 + for (typename G1::NodeIt n(g1); n!=INVALID; ++n) {
2.177 + for (typename G1::NodeIt m(g1); m!=INVALID; ++m) {
2.178 if((findEdge(g1,n,m)==INVALID) != (findEdge(g2,i[n],i[m])==INVALID)) {
2.179 std::cout << "Wrong isomorphism: edge mismatch";
2.180 exit(1);
2.181 }
2.182 + }
2.183 + }
2.184 }
2.185
2.186 -template<class G1,class G2>
2.187 -int checkSub(const G1 &g1, const G2 &g2) {
2.188 +template<class G1,class G2,class T>
2.189 +bool checkSub(const G1 &g1, const G2 &g2, const T &vf2) {
2.190 typename G1:: template NodeMap<typename G2::Node> iso(g1,INVALID);
2.191 - if(vf2(g1,g2).mapping(iso).run()) {
2.192 - checkSub(g1,g2,iso);
2.193 + if (const_cast<T&>(vf2).mapping(iso).run()) {
2.194 + checkSubIso(g1,g2,iso);
2.195 return true;
2.196 }
2.197 - else
2.198 - return false;
2.199 + return false;
2.200 }
2.201
2.202 -template<class G1,class G2>
2.203 -int checkInd(const G1 &g1, const G2 &g2) {
2.204 +template<class G1,class G2,class T>
2.205 +bool checkInd(const G1 &g1, const G2 &g2, const T &vf2) {
2.206 typename G1:: template NodeMap<typename G2::Node> iso(g1,INVALID);
2.207 - if(vf2(g1,g2).induced().mapping(iso).run()) {
2.208 - checkInd(g1,g2,iso);
2.209 + if (const_cast<T&>(vf2).induced().mapping(iso).run()) {
2.210 + checkIndIso(g1,g2,iso);
2.211 return true;
2.212 }
2.213 - else
2.214 - return false;
2.215 + return false;
2.216 }
2.217
2.218 -template<class G1,class G2>
2.219 -int checkIso(const G1 &g1, const G2 &g2) {
2.220 +template<class G1,class G2,class T>
2.221 +bool checkIso(const G1 &g1, const G2 &g2, const T &vf2) {
2.222 typename G1:: template NodeMap<typename G2::Node> iso(g1,INVALID);
2.223 - if(vf2(g1,g2).iso().mapping(iso).run()) {
2.224 + if (const_cast<T&>(vf2).iso().mapping(iso).run()) {
2.225 check(countNodes(g1)==countNodes(g2),
2.226 "Wrong iso alg.: they are not isomophic.");
2.227 - checkInd(g1,g2,iso);
2.228 + checkIndIso(g1,g2,iso);
2.229 return true;
2.230 }
2.231 - else
2.232 - return false;
2.233 + return false;
2.234 }
2.235
2.236 template<class G1, class G2, class L1, class L2, class I>
2.237 void checkLabel(const G1 &g1, const G2 &,
2.238 - const L1 &l1, const L2 &l2,const I &i) {
2.239 - for(typename G1::NodeIt n(g1);n!=INVALID;++n)
2.240 + const L1 &l1, const L2 &l2, const I &i) {
2.241 + for (typename G1::NodeIt n(g1);n!=INVALID;++n) {
2.242 check(l1[n]==l2[i[n]],"Wrong isomorphism: label mismatch.");
2.243 + }
2.244 +}
2.245 +
2.246 +template<class G1,class G2,class L1,class L2,class T>
2.247 +bool checkSub(const G1 &g1, const G2 &g2, const L1 &l1, const L2 &l2, const T &vf2) {
2.248 + typename G1:: template NodeMap<typename G2::Node> iso(g1,INVALID);
2.249 + if (const_cast<T&>(vf2).nodeLabels(l1,l2).mapping(iso).run()){
2.250 + checkSubIso(g1,g2,iso);
2.251 + checkLabel(g1,g2,l1,l2,iso);
2.252 + return true;
2.253 + }
2.254 + return false;
2.255 +}
2.256 +
2.257 +template<class G1,class G2>
2.258 +void checkSub(const G1 &g1, const G2 &g2, bool expected, const char* msg) {
2.259 + check(checkSub(g1,g2,vf2(g1,g2)) == expected, msg);
2.260 + check(checkSub(g1,g2,vf2pp(g1,g2)) == expected, msg);
2.261 +}
2.262 +
2.263 +template<class G1,class G2>
2.264 +void checkInd(const G1 &g1, const G2 &g2, bool expected, const char* msg) {
2.265 + check(checkInd(g1,g2,vf2(g1,g2)) == expected, msg);
2.266 + check(checkInd(g1,g2,vf2pp(g1,g2)) == expected, msg);
2.267 +}
2.268 +
2.269 +template<class G1,class G2>
2.270 +void checkIso(const G1 &g1, const G2 &g2, bool expected, const char* msg) {
2.271 + check(checkIso(g1,g2,vf2(g1,g2)) == expected, msg);
2.272 + check(checkIso(g1,g2,vf2pp(g1,g2)) == expected, msg);
2.273 }
2.274
2.275 template<class G1,class G2,class L1,class L2>
2.276 -int checkSub(const G1 &g1, const G2 &g2, const L1 &l1, const L2 &l2) {
2.277 - typename G1:: template NodeMap<typename G2::Node> iso(g1,INVALID);
2.278 - if(vf2(g1,g2).nodeLabels(l1,l2).mapping(iso).run()){
2.279 - checkSub(g1,g2,iso);
2.280 - checkLabel(g1,g2,l1,l2,iso);
2.281 - return true;
2.282 - }
2.283 - else
2.284 - return false;
2.285 +void checkSub(const G1 &g1, const G2 &g2, const L1 &l1, const L2 &l2, bool expected, const char* msg) {
2.286 + check(checkSub(g1,g2,l1,l2,vf2(g1,g2)) == expected, msg);
2.287 + check(checkSub(g1,g2,l1,l2,vf2pp(g1,g2)) == expected, msg);
2.288 }
2.289
2.290 int main() {
2.291 make_graphs();
2.292 - // justCompile();
2.293 - check(checkSub(c5,petersen), "There should exist a C5->Petersen mapping.");
2.294 - check(!checkSub(c7,petersen),
2.295 - "There should not exist a C7->Petersen mapping.");
2.296 - check(checkSub(p10,petersen), "There should exist a P10->Petersen mapping.");
2.297 - check(!checkSub(c10,petersen),
2.298 - "There should not exist a C10->Petersen mapping.");
2.299 - check(checkSub(petersen,petersen),
2.300 - "There should exist a Petersen->Petersen mapping.");
2.301
2.302 - check(checkInd(c5,petersen),
2.303 - "There should exist a C5->Petersen spanned mapping.");
2.304 - check(!checkInd(c7,petersen),
2.305 - "There should exist a C7->Petersen spanned mapping.");
2.306 - check(!checkInd(p10,petersen),
2.307 - "There should not exist a P10->Petersen spanned mapping.");
2.308 - check(!checkInd(c10,petersen),
2.309 - "There should not exist a C10->Petersen spanned mapping.");
2.310 - check(checkInd(petersen,petersen),
2.311 + checkSub(c5,petersen,true,
2.312 + "There should exist a C5->Petersen mapping.");
2.313 + checkSub(c7,petersen,false,
2.314 + "There should not exist a C7->Petersen mapping.");
2.315 + checkSub(p10,petersen,true,
2.316 + "There should exist a P10->Petersen mapping.");
2.317 + checkSub(c10,petersen,false,
2.318 + "There should not exist a C10->Petersen mapping.");
2.319 + checkSub(petersen,petersen,true,
2.320 + "There should exist a Petersen->Petersen mapping.");
2.321 +
2.322 + checkInd(c5,petersen,true,
2.323 + "There should exist a C5->Petersen spanned mapping.");
2.324 + checkInd(c7,petersen,false,
2.325 + "There should exist a C7->Petersen spanned mapping.");
2.326 + checkInd(p10,petersen,false,
2.327 + "There should not exist a P10->Petersen spanned mapping.");
2.328 + checkInd(c10,petersen,false,
2.329 + "There should not exist a C10->Petersen spanned mapping.");
2.330 + checkInd(petersen,petersen,true,
2.331 "There should exist a Petersen->Petersen spanned mapping.");
2.332
2.333 - check(!checkSub(petersen,c10),
2.334 - "There should not exist a Petersen->C10 mapping.");
2.335 - check(checkSub(p10,c10),
2.336 - "There should exist a P10->C10 mapping.");
2.337 - check(!checkInd(p10,c10),
2.338 - "There should not exist a P10->C10 spanned mapping.");
2.339 - check(!checkSub(c10,p10),
2.340 - "There should not exist a C10->P10 mapping.");
2.341 + checkSub(petersen,c10,false,
2.342 + "There should not exist a Petersen->C10 mapping.");
2.343 + checkSub(p10,c10,true,
2.344 + "There should exist a P10->C10 mapping.");
2.345 + checkInd(p10,c10,false,
2.346 + "There should not exist a P10->C10 spanned mapping.");
2.347 + checkSub(c10,p10,false,
2.348 + "There should not exist a C10->P10 mapping.");
2.349
2.350 - check(!checkIso(p10,c10),
2.351 - "P10 and C10 are not isomorphic.");
2.352 - check(checkIso(c10,c10),
2.353 - "C10 and C10 are isomorphic.");
2.354 + checkIso(p10,c10,false,
2.355 + "P10 and C10 are not isomorphic.");
2.356 + checkIso(c10,c10,true,
2.357 + "C10 and C10 are isomorphic.");
2.358
2.359 - check(!vf2(p10,c10).iso().run(),
2.360 - "P10 and C10 are not isomorphic.");
2.361 - check(vf2(c10,c10).iso().run(),
2.362 - "C10 and C10 are isomorphic.");
2.363 + checkSub(c5,petersen,c5_col,petersen_col1,false,
2.364 + "There should exist a C5->Petersen mapping.");
2.365 + checkSub(c5,petersen,c5_col,petersen_col2,true,
2.366 + "There should exist a C5->Petersen mapping.");
2.367
2.368 - check(!checkSub(c5,petersen,c5_col,petersen_col1),
2.369 - "There should exist a C5->Petersen mapping.");
2.370 - check(checkSub(c5,petersen,c5_col,petersen_col2),
2.371 - "There should exist a C5->Petersen mapping.");
2.372 + check(!vf2(p10,c10).iso().run(), "P10 and C10 are not isomorphic.");
2.373 + check(!vf2pp(p10,c10).iso().run(), "P10 and C10 are not isomorphic.");
2.374 +
2.375 + check(vf2(c10,c10).iso().run(), "C10 and C10 are isomorphic.");
2.376 + check(vf2pp(c10,c10).iso().run(), "C10 and C10 are isomorphic.");
2.377 }
3.1 --- a/test/vf2pp_test.cc Tue Sep 19 14:08:20 2017 +0200
3.2 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000
3.3 @@ -1,392 +0,0 @@
3.4 -/* -*- mode: C++; indent-tabs-mode: nil; -*-
3.5 - *
3.6 - * This file is a part of LEMON, a generic C++ optimization library.
3.7 - *
3.8 - * Copyright (C) 2015-2017
3.9 - * EMAXA Kutato-fejleszto Kft. (EMAXA Research Ltd.)
3.10 - *
3.11 - * Permission to use, modify and distribute this software is granted
3.12 - * provided that this copyright notice appears in all copies. For
3.13 - * precise terms see the accompanying LICENSE file.
3.14 - *
3.15 - * This software is provided "AS IS" with no warranty of any kind,
3.16 - * express or implied, and with no claim as to its suitability for any
3.17 - * purpose.
3.18 - *
3.19 - */
3.20 -
3.21 -#include <lemon/vf2pp.h>
3.22 -#include <lemon/concepts/digraph.h>
3.23 -#include <lemon/smart_graph.h>
3.24 -#include <lemon/lgf_reader.h>
3.25 -#include <lemon/concepts/maps.h>
3.26 -#include <lemon/maps.h>
3.27 -#include <lemon/list_graph.h>
3.28 -
3.29 -#include <test/test_tools.h>
3.30 -#include <sstream>
3.31 -
3.32 -using namespace lemon;
3.33 -
3.34 -char petersen_lgf[] =
3.35 - "@nodes\n"
3.36 - "label col1 col2\n"
3.37 - "0 1 1\n"
3.38 - "1 1 2\n"
3.39 - "2 1 3\n"
3.40 - "3 1 4\n"
3.41 - "4 2 5\n"
3.42 - "5 2 1\n"
3.43 - "6 2 2\n"
3.44 - "7 2 3\n"
3.45 - "8 2 4\n"
3.46 - "9 2 5\n"
3.47 - "@arcs\n"
3.48 - " -\n"
3.49 - "0 1\n"
3.50 - "1 2\n"
3.51 - "2 3\n"
3.52 - "3 4\n"
3.53 - "4 0\n"
3.54 - "0 5\n"
3.55 - "1 6\n"
3.56 - "2 7\n"
3.57 - "3 8\n"
3.58 - "4 9\n"
3.59 - "5 8\n"
3.60 - "5 7\n"
3.61 - "9 6\n"
3.62 - "9 7\n"
3.63 - "6 8\n";
3.64 -
3.65 -char c5_lgf[] =
3.66 - "@nodes\n"
3.67 - "label col\n"
3.68 - "0 1\n"
3.69 - "1 2\n"
3.70 - "2 3\n"
3.71 - "3 4\n"
3.72 - "4 5\n"
3.73 - "@arcs\n"
3.74 - " -\n"
3.75 - "0 1\n"
3.76 - "1 2\n"
3.77 - "2 3\n"
3.78 - "3 4\n"
3.79 - "4 0\n";
3.80 -
3.81 -char c7_lgf[] =
3.82 - "@nodes\n"
3.83 - "label\n"
3.84 - "0\n"
3.85 - "1\n"
3.86 - "2\n"
3.87 - "3\n"
3.88 - "4\n"
3.89 - "5\n"
3.90 - "6\n"
3.91 - "@arcs\n"
3.92 - " -\n"
3.93 - "0 1\n"
3.94 - "1 2\n"
3.95 - "2 3\n"
3.96 - "3 4\n"
3.97 - "4 5\n"
3.98 - "5 6\n"
3.99 - "6 0\n";
3.100 -
3.101 -char c10_lgf[] =
3.102 - "@nodes\n"
3.103 - "label\n"
3.104 - "0\n"
3.105 - "1\n"
3.106 - "2\n"
3.107 - "3\n"
3.108 - "4\n"
3.109 - "5\n"
3.110 - "6\n"
3.111 - "7\n"
3.112 - "8\n"
3.113 - "9\n"
3.114 - "@arcs\n"
3.115 - " -\n"
3.116 - "0 1\n"
3.117 - "1 2\n"
3.118 - "2 3\n"
3.119 - "3 4\n"
3.120 - "4 5\n"
3.121 - "5 6\n"
3.122 - "6 7\n"
3.123 - "7 8\n"
3.124 - "8 9\n"
3.125 - "9 0\n";
3.126 -
3.127 -char p10_lgf[] =
3.128 - "@nodes\n"
3.129 - "label\n"
3.130 - "0\n"
3.131 - "1\n"
3.132 - "2\n"
3.133 - "3\n"
3.134 - "4\n"
3.135 - "5\n"
3.136 - "6\n"
3.137 - "7\n"
3.138 - "8\n"
3.139 - "9\n"
3.140 - "@arcs\n"
3.141 - " -\n"
3.142 - "0 1\n"
3.143 - "1 2\n"
3.144 - "2 3\n"
3.145 - "3 4\n"
3.146 - "4 5\n"
3.147 - "5 6\n"
3.148 - "6 7\n"
3.149 - "7 8\n"
3.150 - "8 9\n";
3.151 -
3.152 -SmartGraph petersen, c5, c7, c10, p10;
3.153 -SmartGraph::NodeMap<int> petersen_col1(petersen);
3.154 -SmartGraph::NodeMap<int> petersen_col2(petersen);
3.155 -SmartGraph::NodeMap<int> c5_col(c5);
3.156 -
3.157 -void make_graphs(){
3.158 - std::stringstream ss(petersen_lgf);
3.159 - graphReader(petersen, ss)
3.160 - .nodeMap("col1",petersen_col1)
3.161 - .nodeMap("col2",petersen_col2)
3.162 - .run();
3.163 -
3.164 - ss.clear();
3.165 - ss.str("");
3.166 - ss<<c5_lgf;
3.167 -
3.168 - graphReader(c5, ss)
3.169 - .nodeMap("col",c5_col)
3.170 - .run();
3.171 -
3.172 - ss.clear();
3.173 - ss.str("");
3.174 - ss<<c7_lgf;
3.175 - graphReader(c7, ss).run();
3.176 -
3.177 - ss.clear();
3.178 - ss.str("");
3.179 - ss<<c10_lgf;
3.180 - graphReader(c10, ss).run();
3.181 -
3.182 - ss.clear();
3.183 - ss.str("");
3.184 - ss<<p10_lgf;
3.185 - graphReader(p10, ss).run();
3.186 -
3.187 -}
3.188 -
3.189 -class IntConvertible1{
3.190 -public:
3.191 - operator int(){
3.192 - return 0;
3.193 - }
3.194 -};
3.195 -
3.196 -class IntConvertible2{
3.197 -public:
3.198 - operator int(){
3.199 - return 0;
3.200 - }
3.201 -};
3.202 -
3.203 -template<class G1,class G2>
3.204 -void checkVf2Compile() {
3.205 - G1 g;
3.206 - G2 h;
3.207 - concepts::ReadWriteMap<typename G1::Node, typename G2::Node> r;
3.208 - bool succ;
3.209 - ::lemon::ignore_unused_variable_warning(succ);
3.210 -
3.211 - succ = vf2pp(g,h).run();
3.212 - succ = vf2pp(g,h).induced().run();
3.213 - succ = vf2pp(g,h).iso().run();
3.214 - succ = vf2pp(g,h).mapping(r).run();
3.215 - succ = vf2pp(g,h).induced().mapping(r).run();
3.216 - succ = vf2pp(g,h).iso().mapping(r).run();
3.217 -
3.218 -
3.219 - concepts::ReadMap<typename G1::Node, int> c1;
3.220 - concepts::ReadMap<typename G2::Node, int> c2;
3.221 - Vf2pp<G1,G2,concepts::ReadWriteMap<typename G1::Node, typename G2::Node>,
3.222 - concepts::ReadMap<typename G1::Node, int>,
3.223 - concepts::ReadMap<typename G2::Node, int> >
3.224 - myVf2pp(g,h,r,c1,c2);
3.225 - myVf2pp.find();
3.226 -
3.227 - succ = vf2pp(g,h).nodeLabels(c1,c2).mapping(r).run();
3.228 - succ = vf2pp(g,h).nodeLabels(c1,c2)
3.229 - .mapping(r).run();
3.230 -
3.231 -
3.232 - concepts::ReadMap<typename G1::Node, char> c1_c;
3.233 - concepts::ReadMap<typename G2::Node, char> c2_c;
3.234 - Vf2pp<G1,G2,concepts::ReadWriteMap<typename G1::Node, typename G2::Node>,
3.235 - concepts::ReadMap<typename G1::Node, char>,
3.236 - concepts::ReadMap<typename G2::Node, char> >
3.237 - myVf2pp_c(g,h,r,c1_c,c2_c);
3.238 - myVf2pp_c.find();
3.239 -
3.240 - succ = vf2pp(g,h).nodeLabels(c1_c,c2_c).mapping(r).run();
3.241 - succ = vf2pp(g,h).nodeLabels(c1_c,c2_c)
3.242 - .mapping(r).run();
3.243 -
3.244 -
3.245 - concepts::ReadMap<typename G1::Node, IntConvertible1> c1_IntConv;
3.246 - concepts::ReadMap<typename G2::Node, IntConvertible2> c2_IntConv;
3.247 - Vf2pp<G1,G2,concepts::ReadWriteMap<typename G1::Node, typename G2::Node>,
3.248 - concepts::ReadMap<typename G1::Node, IntConvertible1>,
3.249 - concepts::ReadMap<typename G2::Node, IntConvertible2> >
3.250 - myVf2pp_IntConv(g,h,r,c1_IntConv,c2_IntConv);
3.251 - myVf2pp_IntConv.find();
3.252 -
3.253 - succ = vf2pp(g,h).nodeLabels(c1_IntConv,c2_IntConv).mapping(r).run();
3.254 - succ = vf2pp(g,h).nodeLabels(c1_IntConv,c2_IntConv)
3.255 - .mapping(r).run();
3.256 -}
3.257 -
3.258 -void justCompile() {
3.259 - checkVf2Compile<concepts::Graph,concepts::Graph>();
3.260 - checkVf2Compile<concepts::Graph,SmartGraph>();
3.261 - checkVf2Compile<SmartGraph,concepts::Graph>();
3.262 -}
3.263 -
3.264 -template<class G1, class G2, class I>
3.265 -void checkSub(const G1 &g1, const G2 &g2, const I &i) {
3.266 - {
3.267 - std::set<typename G2::Node> image;
3.268 - for(typename G1::NodeIt n(g1);n!=INVALID;++n){
3.269 - check(i[n]!=INVALID, "Wrong isomorphism: incomplete mapping.");
3.270 - check(image.count(i[n])==0,"Wrong isomorphism: not injective.");
3.271 - image.insert(i[n]);
3.272 - }
3.273 - }
3.274 - for(typename G1::EdgeIt e(g1);e!=INVALID;++e)
3.275 - check(findEdge(g2,i[g1.u(e)],i[g1.v(e)])!=INVALID,
3.276 - "Wrong isomorphism: missing edge(checkSub).");
3.277 -}
3.278 -
3.279 -template<class G1, class G2, class I>
3.280 -void checkInd(const G1 &g1, const G2 &g2, const I &i) {
3.281 - std::set<typename G2::Node> image;
3.282 - for(typename G1::NodeIt n(g1);n!=INVALID;++n) {
3.283 - check(i[n]!=INVALID, "Wrong isomorphism: incomplete mapping.");
3.284 - check(image.count(i[n])==0,"Wrong isomorphism: not injective.");
3.285 - image.insert(i[n]);
3.286 - }
3.287 - for(typename G1::NodeIt n(g1); n!=INVALID; ++n)
3.288 - for(typename G1::NodeIt m(g1); m!=INVALID; ++m)
3.289 - if((findEdge(g1,n,m)==INVALID) != (findEdge(g2,i[n],i[m])==INVALID)) {
3.290 - std::cout << "Wrong isomorphism: edge mismatch";
3.291 - exit(1);
3.292 - }
3.293 -}
3.294 -
3.295 -template<class G1,class G2>
3.296 -int checkSub(const G1 &g1, const G2 &g2) {
3.297 - typename G1:: template NodeMap<typename G2::Node> iso(g1,INVALID);
3.298 - if(vf2pp(g1,g2).mapping(iso).run()){
3.299 - checkSub(g1,g2,iso);
3.300 - return true;
3.301 - }
3.302 - else
3.303 - return false;
3.304 -}
3.305 -
3.306 -template<class G1,class G2>
3.307 -int checkInd(const G1 &g1, const G2 &g2) {
3.308 - typename G1:: template NodeMap<typename G2::Node> iso(g1,INVALID);
3.309 - if(vf2pp(g1,g2).induced().mapping(iso).run()) {
3.310 - checkInd(g1,g2,iso);
3.311 - return true;
3.312 - }
3.313 - else
3.314 - return false;
3.315 -}
3.316 -
3.317 -template<class G1,class G2>
3.318 -int checkIso(const G1 &g1, const G2 &g2) {
3.319 - typename G1:: template NodeMap<typename G2::Node> iso(g1,INVALID);
3.320 - if(vf2pp(g1,g2).iso().mapping(iso).run()) {
3.321 - check(countNodes(g1)==countNodes(g2),
3.322 - "Wrong iso alg.: they are not isomophic.");
3.323 - checkInd(g1,g2,iso);
3.324 - return true;
3.325 - }
3.326 - else
3.327 - return false;
3.328 -}
3.329 -
3.330 -template<class G1, class G2, class L1, class L2, class I>
3.331 -void checkLabel(const G1 &g1, const G2 &,
3.332 - const L1 &l1, const L2 &l2,const I &i) {
3.333 - for(typename G1::NodeIt n(g1);n!=INVALID;++n)
3.334 - check(l1[n]==l2[i[n]],"Wrong isomorphism: label mismatch.");
3.335 -}
3.336 -
3.337 -template<class G1,class G2,class L1,class L2>
3.338 -int checkSub(const G1 &g1, const G2 &g2, const L1 &l1, const L2 &l2) {
3.339 - typename G1:: template NodeMap<typename G2::Node> iso(g1,INVALID);
3.340 - if(vf2pp(g1,g2).nodeLabels(l1,l2).mapping(iso).run()) {
3.341 - checkSub(g1,g2,iso);
3.342 - checkLabel(g1,g2,l1,l2,iso);
3.343 - return true;
3.344 - }
3.345 - else
3.346 - return false;
3.347 -}
3.348 -
3.349 -int main() {
3.350 - make_graphs();
3.351 -// justCompile();
3.352 - check(checkSub(c5,petersen), "There should exist a C5->Petersen mapping.");
3.353 - check(!checkSub(c7,petersen),
3.354 - "There should not exist a C7->Petersen mapping.");
3.355 - check(checkSub(p10,petersen), "There should exist a P10->Petersen mapping.");
3.356 - check(!checkSub(c10,petersen),
3.357 - "There should not exist a C10->Petersen mapping.");
3.358 - check(checkSub(petersen,petersen),
3.359 - "There should exist a Petersen->Petersen mapping.");
3.360 -
3.361 - check(checkInd(c5,petersen),
3.362 - "There should exist a C5->Petersen spanned mapping.");
3.363 - check(!checkInd(c7,petersen),
3.364 - "There should exist a C7->Petersen spanned mapping.");
3.365 - check(!checkInd(p10,petersen),
3.366 - "There should not exist a P10->Petersen spanned mapping.");
3.367 - check(!checkInd(c10,petersen),
3.368 - "There should not exist a C10->Petersen spanned mapping.");
3.369 - check(checkInd(petersen,petersen),
3.370 - "There should exist a Petersen->Petersen spanned mapping.");
3.371 -
3.372 - check(!checkSub(petersen,c10),
3.373 - "There should not exist a Petersen->C10 mapping.");
3.374 - check(checkSub(p10,c10),
3.375 - "There should exist a P10->C10 mapping.");
3.376 - check(!checkInd(p10,c10),
3.377 - "There should not exist a P10->C10 spanned mapping.");
3.378 - check(!checkSub(c10,p10),
3.379 - "There should not exist a C10->P10 mapping.");
3.380 -
3.381 - check(!checkIso(p10,c10),
3.382 - "P10 and C10 are not isomorphic.");
3.383 - check(checkIso(c10,c10),
3.384 - "C10 and C10 are isomorphic.");
3.385 -
3.386 - check(!vf2pp(p10,c10).iso().run(),
3.387 - "P10 and C10 are not isomorphic.");
3.388 - check(vf2pp(c10,c10).iso().run(),
3.389 - "C10 and C10 are isomorphic.");
3.390 -
3.391 - check(!checkSub(c5,petersen,c5_col,petersen_col1),
3.392 - "There should exist a C5->Petersen mapping.");
3.393 - check(checkSub(c5,petersen,c5_col,petersen_col2),
3.394 - "There should exist a C5->Petersen mapping.");
3.395 -}