Changeset 1405:3feba0ea1bda in lemon for test/vf2_test.cc
 Timestamp:
 09/19/17 14:08:20 (2 years ago)
 Branch:
 default
 Phase:
 public
 File:

 1 edited
Legend:
 Unmodified
 Added
 Removed

test/vf2_test.cc
r1352 r1405 3 3 * This file is a part of LEMON, a generic C++ optimization library. 4 4 * 5 * Copyright (C) 2015 5 * Copyright (C) 20152017 6 6 * EMAXA Kutatofejleszto Kft. (EMAXA Research Ltd.) 7 7 * … … 184 184 class EqComparable { 185 185 public: 186 bool operator==(const EqComparable&) { return false; } 186 bool operator==(const EqComparable&) { 187 return false; 188 } 187 189 }; 188 190 … … 190 192 class EqClass { 191 193 public: 192 bool operator()(A, B) { return false; } 194 bool operator()(A, B){ 195 return false; 196 } 193 197 }; 194 198 195 199 template<class G1,class G2> 196 void checkVf2Compile() 197 { 200 void checkVf2Compile() { 198 201 G1 g; 199 202 G2 h; … … 206 209 succ = vf2(g,h).iso().run(); 207 210 succ = vf2(g,h).mapping(r).run(); 211 212 Vf2<G1,G2,concepts::ReadWriteMap<typename G1::Node, typename G2::Node>, 213 EqClass<typename G1::Node,typename G2::Node> > 214 myVf2(g,h,r,EqClass<typename G1::Node,typename G2::Node>()); 215 myVf2.find(); 216 208 217 succ = vf2(g,h).induced().mapping(r).run(); 209 218 succ = vf2(g,h).iso().mapping(r).run(); 219 210 220 concepts::ReadMap<typename G1::Node, EqComparable> l1; 211 221 concepts::ReadMap<typename G2::Node, EqComparable> l2; … … 215 225 } 216 226 217 void justCompile() 218 { 227 void justCompile() { 219 228 checkVf2Compile<concepts::Graph,concepts::Graph>(); 220 229 checkVf2Compile<concepts::Graph,SmartGraph>(); … … 223 232 224 233 template<class G1, class G2, class I> 225 void checkSub(const G1 &g1, const G2 &g2, const I &i) 226 { 234 void checkSub(const G1 &g1, const G2 &g2, const I &i) { 227 235 { 228 236 std::set<typename G2::Node> image; 229 for(typename G1::NodeIt n(g1);n!=INVALID;++n) 230 { 231 check(i[n]!=INVALID, "Wrong isomorphism: incomplete mapping."); 232 check(image.count(i[n])==0,"Wrong isomorphism: not injective."); 233 image.insert(i[n]); 234 } 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 } 235 242 } 236 243 for(typename G1::EdgeIt e(g1);e!=INVALID;++e) … … 240 247 241 248 template<class G1, class G2, class I> 242 void checkInd(const G1 &g1, const G2 &g2, const I &i) 243 { 249 void checkInd(const G1 &g1, const G2 &g2, const I &i) { 244 250 std::set<typename G2::Node> image; 245 for(typename G1::NodeIt n(g1);n!=INVALID;++n) 246 { 251 for(typename G1::NodeIt n(g1);n!=INVALID;++n) { 247 252 check(i[n]!=INVALID, "Wrong isomorphism: incomplete mapping."); 248 253 check(image.count(i[n])==0,"Wrong isomorphism: not injective."); 249 254 image.insert(i[n]); 250 255 } 251 256 for(typename G1::NodeIt n(g1); n!=INVALID; ++n) 252 257 for(typename G1::NodeIt m(g1); m!=INVALID; ++m) 253 if((findEdge(g1,n,m)==INVALID) != (findEdge(g2,i[n],i[m])==INVALID)) 254 { 258 if((findEdge(g1,n,m)==INVALID) != (findEdge(g2,i[n],i[m])==INVALID)) { 255 259 std::cout << "Wrong isomorphism: edge mismatch"; 256 260 exit(1); 257 258 261 } 262 } 259 263 260 264 template<class G1,class G2> 261 int checkSub(const G1 &g1, const G2 &g2) 262 { 265 int checkSub(const G1 &g1, const G2 &g2) { 263 266 typename G1:: template NodeMap<typename G2::Node> iso(g1,INVALID); 264 if(vf2(g1,g2).mapping(iso).run()) 265 {266 checkSub(g1,g2,iso);267 return true;268 }269 elsereturn false;267 if(vf2(g1,g2).mapping(iso).run()) { 268 checkSub(g1,g2,iso); 269 return true; 270 } 271 else 272 return false; 270 273 } 271 274 272 275 template<class G1,class G2> 273 int checkInd(const G1 &g1, const G2 &g2) 274 { 276 int checkInd(const G1 &g1, const G2 &g2) { 275 277 typename G1:: template NodeMap<typename G2::Node> iso(g1,INVALID); 276 if(vf2(g1,g2).induced().mapping(iso).run()) 277 {278 checkInd(g1,g2,iso);279 return true;280 }281 elsereturn false;278 if(vf2(g1,g2).induced().mapping(iso).run()) { 279 checkInd(g1,g2,iso); 280 return true; 281 } 282 else 283 return false; 282 284 } 283 285 284 286 template<class G1,class G2> 285 int checkIso(const G1 &g1, const G2 &g2) 286 { 287 int checkIso(const G1 &g1, const G2 &g2) { 287 288 typename G1:: template NodeMap<typename G2::Node> iso(g1,INVALID); 288 if(vf2(g1,g2).iso().mapping(iso).run()) 289 {290 check(countNodes(g1)==countNodes(g2),291 "Wrong iso alg.: they are not isomophic.");292 checkInd(g1,g2,iso);293 return true;294 }295 elsereturn false;289 if(vf2(g1,g2).iso().mapping(iso).run()) { 290 check(countNodes(g1)==countNodes(g2), 291 "Wrong iso alg.: they are not isomophic."); 292 checkInd(g1,g2,iso); 293 return true; 294 } 295 else 296 return false; 296 297 } 297 298 298 299 template<class G1, class G2, class L1, class L2, class I> 299 300 void checkLabel(const G1 &g1, const G2 &, 300 const L1 &l1, const L2 &l2,const I &i) 301 { 301 const L1 &l1, const L2 &l2,const I &i) { 302 302 for(typename G1::NodeIt n(g1);n!=INVALID;++n) 303 { 304 check(l1[n]==l2[i[n]],"Wrong isomorphism: label mismatch."); 305 } 303 check(l1[n]==l2[i[n]],"Wrong isomorphism: label mismatch."); 306 304 } 307 305 308 306 template<class G1,class G2,class L1,class L2> 309 int checkSub(const G1 &g1, const G2 &g2, const L1 &l1, const L2 &l2) 310 { 307 int checkSub(const G1 &g1, const G2 &g2, const L1 &l1, const L2 &l2) { 311 308 typename G1:: template NodeMap<typename G2::Node> iso(g1,INVALID); 312 if(vf2(g1,g2).nodeLabels(l1,l2).mapping(iso).run()) 313 {314 checkSub(g1,g2,iso);315 checkLabel(g1,g2,l1,l2,iso);316 return true;317 }318 elsereturn false;309 if(vf2(g1,g2).nodeLabels(l1,l2).mapping(iso).run()){ 310 checkSub(g1,g2,iso); 311 checkLabel(g1,g2,l1,l2,iso); 312 return true; 313 } 314 else 315 return false; 319 316 } 320 317 321 318 int main() { 322 319 make_graphs(); 320 // justCompile(); 323 321 check(checkSub(c5,petersen), "There should exist a C5>Petersen mapping."); 324 322 check(!checkSub(c7,petersen),
Note: See TracChangeset
for help on using the changeset viewer.