1.1 --- a/test/vf2_test.cc Tue Sep 19 15:23:43 2017 +0200
1.2 +++ b/test/vf2_test.cc Tue Sep 19 14:08:20 2017 +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 @@ -183,18 +183,21 @@
1.13
1.14 class EqComparable {
1.15 public:
1.16 - bool operator==(const EqComparable&) { return false; }
1.17 + bool operator==(const EqComparable&) {
1.18 + return false;
1.19 + }
1.20 };
1.21
1.22 template<class A, class B>
1.23 class EqClass {
1.24 public:
1.25 - bool operator()(A, B) { return false; }
1.26 + bool operator()(A, B){
1.27 + return false;
1.28 + }
1.29 };
1.30
1.31 template<class G1,class G2>
1.32 -void checkVf2Compile()
1.33 -{
1.34 +void checkVf2Compile() {
1.35 G1 g;
1.36 G2 h;
1.37 concepts::ReadWriteMap<typename G1::Node, typename G2::Node> r;
1.38 @@ -205,8 +208,15 @@
1.39 succ = vf2(g,h).induced().run();
1.40 succ = vf2(g,h).iso().run();
1.41 succ = vf2(g,h).mapping(r).run();
1.42 +
1.43 + Vf2<G1,G2,concepts::ReadWriteMap<typename G1::Node, typename G2::Node>,
1.44 + EqClass<typename G1::Node,typename G2::Node> >
1.45 + myVf2(g,h,r,EqClass<typename G1::Node,typename G2::Node>());
1.46 + myVf2.find();
1.47 +
1.48 succ = vf2(g,h).induced().mapping(r).run();
1.49 succ = vf2(g,h).iso().mapping(r).run();
1.50 +
1.51 concepts::ReadMap<typename G1::Node, EqComparable> l1;
1.52 concepts::ReadMap<typename G2::Node, EqComparable> l2;
1.53 succ = vf2(g,h).nodeLabels(l1,l2).mapping(r).run();
1.54 @@ -214,24 +224,21 @@
1.55 .mapping(r).run();
1.56 }
1.57
1.58 -void justCompile()
1.59 -{
1.60 +void justCompile() {
1.61 checkVf2Compile<concepts::Graph,concepts::Graph>();
1.62 checkVf2Compile<concepts::Graph,SmartGraph>();
1.63 checkVf2Compile<SmartGraph,concepts::Graph>();
1.64 }
1.65
1.66 template<class G1, class G2, class I>
1.67 -void checkSub(const G1 &g1, const G2 &g2, const I &i)
1.68 -{
1.69 +void checkSub(const G1 &g1, const G2 &g2, const I &i) {
1.70 {
1.71 std::set<typename G2::Node> image;
1.72 - for(typename G1::NodeIt n(g1);n!=INVALID;++n)
1.73 - {
1.74 - check(i[n]!=INVALID, "Wrong isomorphism: incomplete mapping.");
1.75 - check(image.count(i[n])==0,"Wrong isomorphism: not injective.");
1.76 - image.insert(i[n]);
1.77 - }
1.78 + for(typename G1::NodeIt n(g1);n!=INVALID;++n){
1.79 + check(i[n]!=INVALID, "Wrong isomorphism: incomplete mapping.");
1.80 + check(image.count(i[n])==0,"Wrong isomorphism: not injective.");
1.81 + image.insert(i[n]);
1.82 + }
1.83 }
1.84 for(typename G1::EdgeIt e(g1);e!=INVALID;++e)
1.85 check(findEdge(g2,i[g1.u(e)],i[g1.v(e)])!=INVALID,
1.86 @@ -239,87 +246,78 @@
1.87 }
1.88
1.89 template<class G1, class G2, class I>
1.90 -void checkInd(const G1 &g1, const G2 &g2, const I &i)
1.91 - {
1.92 +void checkInd(const G1 &g1, const G2 &g2, const I &i) {
1.93 std::set<typename G2::Node> image;
1.94 - for(typename G1::NodeIt n(g1);n!=INVALID;++n)
1.95 - {
1.96 + for(typename G1::NodeIt n(g1);n!=INVALID;++n) {
1.97 check(i[n]!=INVALID, "Wrong isomorphism: incomplete mapping.");
1.98 check(image.count(i[n])==0,"Wrong isomorphism: not injective.");
1.99 image.insert(i[n]);
1.100 - }
1.101 + }
1.102 for(typename G1::NodeIt n(g1); n!=INVALID; ++n)
1.103 for(typename G1::NodeIt m(g1); m!=INVALID; ++m)
1.104 - if((findEdge(g1,n,m)==INVALID) != (findEdge(g2,i[n],i[m])==INVALID))
1.105 - {
1.106 + if((findEdge(g1,n,m)==INVALID) != (findEdge(g2,i[n],i[m])==INVALID)) {
1.107 std::cout << "Wrong isomorphism: edge mismatch";
1.108 exit(1);
1.109 - }
1.110 - }
1.111 -
1.112 -template<class G1,class G2>
1.113 -int checkSub(const G1 &g1, const G2 &g2)
1.114 -{
1.115 - typename G1:: template NodeMap<typename G2::Node> iso(g1,INVALID);
1.116 - if(vf2(g1,g2).mapping(iso).run())
1.117 - {
1.118 - checkSub(g1,g2,iso);
1.119 - return true;
1.120 - }
1.121 - else return false;
1.122 + }
1.123 }
1.124
1.125 template<class G1,class G2>
1.126 -int checkInd(const G1 &g1, const G2 &g2)
1.127 -{
1.128 +int checkSub(const G1 &g1, const G2 &g2) {
1.129 typename G1:: template NodeMap<typename G2::Node> iso(g1,INVALID);
1.130 - if(vf2(g1,g2).induced().mapping(iso).run())
1.131 - {
1.132 - checkInd(g1,g2,iso);
1.133 - return true;
1.134 - }
1.135 - else return false;
1.136 + if(vf2(g1,g2).mapping(iso).run()) {
1.137 + checkSub(g1,g2,iso);
1.138 + return true;
1.139 + }
1.140 + else
1.141 + return false;
1.142 }
1.143
1.144 template<class G1,class G2>
1.145 -int checkIso(const G1 &g1, const G2 &g2)
1.146 -{
1.147 +int checkInd(const G1 &g1, const G2 &g2) {
1.148 typename G1:: template NodeMap<typename G2::Node> iso(g1,INVALID);
1.149 - if(vf2(g1,g2).iso().mapping(iso).run())
1.150 - {
1.151 - check(countNodes(g1)==countNodes(g2),
1.152 - "Wrong iso alg.: they are not isomophic.");
1.153 - checkInd(g1,g2,iso);
1.154 - return true;
1.155 - }
1.156 - else return false;
1.157 + if(vf2(g1,g2).induced().mapping(iso).run()) {
1.158 + checkInd(g1,g2,iso);
1.159 + return true;
1.160 + }
1.161 + else
1.162 + return false;
1.163 +}
1.164 +
1.165 +template<class G1,class G2>
1.166 +int checkIso(const G1 &g1, const G2 &g2) {
1.167 + typename G1:: template NodeMap<typename G2::Node> iso(g1,INVALID);
1.168 + if(vf2(g1,g2).iso().mapping(iso).run()) {
1.169 + check(countNodes(g1)==countNodes(g2),
1.170 + "Wrong iso alg.: they are not isomophic.");
1.171 + checkInd(g1,g2,iso);
1.172 + return true;
1.173 + }
1.174 + else
1.175 + return false;
1.176 }
1.177
1.178 template<class G1, class G2, class L1, class L2, class I>
1.179 void checkLabel(const G1 &g1, const G2 &,
1.180 - const L1 &l1, const L2 &l2,const I &i)
1.181 -{
1.182 + const L1 &l1, const L2 &l2,const I &i) {
1.183 for(typename G1::NodeIt n(g1);n!=INVALID;++n)
1.184 - {
1.185 - check(l1[n]==l2[i[n]],"Wrong isomorphism: label mismatch.");
1.186 - }
1.187 + check(l1[n]==l2[i[n]],"Wrong isomorphism: label mismatch.");
1.188 }
1.189
1.190 template<class G1,class G2,class L1,class L2>
1.191 -int checkSub(const G1 &g1, const G2 &g2, const L1 &l1, const L2 &l2)
1.192 -{
1.193 +int checkSub(const G1 &g1, const G2 &g2, const L1 &l1, const L2 &l2) {
1.194 typename G1:: template NodeMap<typename G2::Node> iso(g1,INVALID);
1.195 - if(vf2(g1,g2).nodeLabels(l1,l2).mapping(iso).run())
1.196 - {
1.197 - checkSub(g1,g2,iso);
1.198 - checkLabel(g1,g2,l1,l2,iso);
1.199 - return true;
1.200 - }
1.201 - else return false;
1.202 + if(vf2(g1,g2).nodeLabels(l1,l2).mapping(iso).run()){
1.203 + checkSub(g1,g2,iso);
1.204 + checkLabel(g1,g2,l1,l2,iso);
1.205 + return true;
1.206 + }
1.207 + else
1.208 + return false;
1.209 }
1.210
1.211 int main() {
1.212 make_graphs();
1.213 + // justCompile();
1.214 check(checkSub(c5,petersen), "There should exist a C5->Petersen mapping.");
1.215 check(!checkSub(c7,petersen),
1.216 "There should not exist a C7->Petersen mapping.");