test/vf2_test.cc
changeset 1186 3feba0ea1bda
parent 1143 f85ee41c84bc
child 1187 120b9031eada
equal deleted inserted replaced
1:a369d3935dc9 2:580c6f315a11
     1 /* -*- mode: C++; indent-tabs-mode: nil; -*-
     1 /* -*- mode: C++; indent-tabs-mode: nil; -*-
     2  *
     2  *
     3  * This file is a part of LEMON, a generic C++ optimization library.
     3  * This file is a part of LEMON, a generic C++ optimization library.
     4  *
     4  *
     5  * Copyright (C) 2015
     5  * Copyright (C) 2015-2017
     6  * EMAXA Kutato-fejleszto Kft. (EMAXA Research Ltd.)
     6  * EMAXA Kutato-fejleszto Kft. (EMAXA Research Ltd.)
     7  *
     7  *
     8  * Permission to use, modify and distribute this software is granted
     8  * Permission to use, modify and distribute this software is granted
     9  * provided that this copyright notice appears in all copies. For
     9  * provided that this copyright notice appears in all copies. For
    10  * precise terms see the accompanying LICENSE file.
    10  * precise terms see the accompanying LICENSE file.
   181 
   181 
   182 }
   182 }
   183 
   183 
   184 class EqComparable {
   184 class EqComparable {
   185 public:
   185 public:
   186   bool operator==(const EqComparable&) { return false; }
   186   bool operator==(const EqComparable&) {
       
   187     return false;
       
   188   }
   187 };
   189 };
   188 
   190 
   189 template<class A, class B>
   191 template<class A, class B>
   190 class EqClass {
   192 class EqClass {
   191 public:
   193 public:
   192   bool operator()(A, B) { return false; }
   194   bool operator()(A, B){
       
   195     return false;
       
   196   }
   193 };
   197 };
   194 
   198 
   195 template<class G1,class G2>
   199 template<class G1,class G2>
   196 void checkVf2Compile()
   200 void checkVf2Compile() {
   197 {
       
   198   G1 g;
   201   G1 g;
   199   G2 h;
   202   G2 h;
   200   concepts::ReadWriteMap<typename G1::Node, typename G2::Node> r;
   203   concepts::ReadWriteMap<typename G1::Node, typename G2::Node> r;
   201   bool succ;
   204   bool succ;
   202   ::lemon::ignore_unused_variable_warning(succ);
   205   ::lemon::ignore_unused_variable_warning(succ);
   203 
   206 
   204   succ = vf2(g,h).run();
   207   succ = vf2(g,h).run();
   205   succ = vf2(g,h).induced().run();
   208   succ = vf2(g,h).induced().run();
   206   succ = vf2(g,h).iso().run();
   209   succ = vf2(g,h).iso().run();
   207   succ = vf2(g,h).mapping(r).run();
   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   succ = vf2(g,h).induced().mapping(r).run();
   217   succ = vf2(g,h).induced().mapping(r).run();
   209   succ = vf2(g,h).iso().mapping(r).run();
   218   succ = vf2(g,h).iso().mapping(r).run();
       
   219 
   210   concepts::ReadMap<typename G1::Node, EqComparable> l1;
   220   concepts::ReadMap<typename G1::Node, EqComparable> l1;
   211   concepts::ReadMap<typename G2::Node, EqComparable> l2;
   221   concepts::ReadMap<typename G2::Node, EqComparable> l2;
   212   succ = vf2(g,h).nodeLabels(l1,l2).mapping(r).run();
   222   succ = vf2(g,h).nodeLabels(l1,l2).mapping(r).run();
   213   succ = vf2(g,h).nodeEq(EqClass<typename G1::Node,typename G2::Node>())
   223   succ = vf2(g,h).nodeEq(EqClass<typename G1::Node,typename G2::Node>())
   214     .mapping(r).run();
   224     .mapping(r).run();
   215 }
   225 }
   216 
   226 
   217 void justCompile()
   227 void justCompile() {
   218 {
       
   219   checkVf2Compile<concepts::Graph,concepts::Graph>();
   228   checkVf2Compile<concepts::Graph,concepts::Graph>();
   220   checkVf2Compile<concepts::Graph,SmartGraph>();
   229   checkVf2Compile<concepts::Graph,SmartGraph>();
   221   checkVf2Compile<SmartGraph,concepts::Graph>();
   230   checkVf2Compile<SmartGraph,concepts::Graph>();
   222 }
   231 }
   223 
   232 
   224 template<class G1, class G2, class I>
   233 template<class G1, class G2, class I>
   225 void checkSub(const G1 &g1, const G2 &g2, const I &i)
   234 void checkSub(const G1 &g1, const G2 &g2, const I &i) {
   226 {
       
   227   {
   235   {
   228     std::set<typename G2::Node> image;
   236     std::set<typename G2::Node> image;
   229     for(typename G1::NodeIt n(g1);n!=INVALID;++n)
   237     for(typename G1::NodeIt n(g1);n!=INVALID;++n){
   230       {
   238       check(i[n]!=INVALID, "Wrong isomorphism: incomplete mapping.");
   231           check(i[n]!=INVALID, "Wrong isomorphism: incomplete mapping.");
   239       check(image.count(i[n])==0,"Wrong isomorphism: not injective.");
   232           check(image.count(i[n])==0,"Wrong isomorphism: not injective.");
   240       image.insert(i[n]);
   233           image.insert(i[n]);
   241     }
   234       }
       
   235   }
   242   }
   236   for(typename G1::EdgeIt e(g1);e!=INVALID;++e)
   243   for(typename G1::EdgeIt e(g1);e!=INVALID;++e)
   237     check(findEdge(g2,i[g1.u(e)],i[g1.v(e)])!=INVALID,
   244     check(findEdge(g2,i[g1.u(e)],i[g1.v(e)])!=INVALID,
   238           "Wrong isomorphism: missing edge(checkSub).");
   245           "Wrong isomorphism: missing edge(checkSub).");
   239 }
   246 }
   240 
   247 
   241 template<class G1, class G2, class I>
   248 template<class G1, class G2, class I>
   242 void checkInd(const G1 &g1, const G2 &g2, const I &i)
   249 void checkInd(const G1 &g1, const G2 &g2, const I &i) {
   243   {
       
   244   std::set<typename G2::Node> image;
   250   std::set<typename G2::Node> image;
   245   for(typename G1::NodeIt n(g1);n!=INVALID;++n)
   251   for(typename G1::NodeIt n(g1);n!=INVALID;++n) {
   246     {
       
   247     check(i[n]!=INVALID, "Wrong isomorphism: incomplete mapping.");
   252     check(i[n]!=INVALID, "Wrong isomorphism: incomplete mapping.");
   248     check(image.count(i[n])==0,"Wrong isomorphism: not injective.");
   253     check(image.count(i[n])==0,"Wrong isomorphism: not injective.");
   249     image.insert(i[n]);
   254     image.insert(i[n]);
   250     }
   255   }
   251   for(typename G1::NodeIt n(g1); n!=INVALID; ++n)
   256   for(typename G1::NodeIt n(g1); n!=INVALID; ++n)
   252     for(typename G1::NodeIt m(g1); m!=INVALID; ++m)
   257     for(typename G1::NodeIt m(g1); m!=INVALID; ++m)
   253       if((findEdge(g1,n,m)==INVALID) != (findEdge(g2,i[n],i[m])==INVALID))
   258       if((findEdge(g1,n,m)==INVALID) != (findEdge(g2,i[n],i[m])==INVALID)) {
   254         {
       
   255         std::cout << "Wrong isomorphism: edge mismatch";
   259         std::cout << "Wrong isomorphism: edge mismatch";
   256         exit(1);
   260         exit(1);
   257         }
   261       }
   258   }
   262 }
   259 
   263 
   260 template<class G1,class G2>
   264 template<class G1,class G2>
   261 int checkSub(const G1 &g1, const G2 &g2)
   265 int checkSub(const G1 &g1, const G2 &g2) {
   262 {
       
   263   typename G1:: template NodeMap<typename G2::Node> iso(g1,INVALID);
   266   typename G1:: template NodeMap<typename G2::Node> iso(g1,INVALID);
   264   if(vf2(g1,g2).mapping(iso).run())
   267   if(vf2(g1,g2).mapping(iso).run()) {
   265     {
   268     checkSub(g1,g2,iso);
   266       checkSub(g1,g2,iso);
   269     return true;
   267       return true;
   270   }
   268     }
   271   else
   269   else return false;
   272     return false;
   270 }
   273 }
   271 
   274 
   272 template<class G1,class G2>
   275 template<class G1,class G2>
   273 int checkInd(const G1 &g1, const G2 &g2)
   276 int checkInd(const G1 &g1, const G2 &g2) {
   274 {
       
   275   typename G1:: template NodeMap<typename G2::Node> iso(g1,INVALID);
   277   typename G1:: template NodeMap<typename G2::Node> iso(g1,INVALID);
   276   if(vf2(g1,g2).induced().mapping(iso).run())
   278   if(vf2(g1,g2).induced().mapping(iso).run()) {
   277     {
   279     checkInd(g1,g2,iso);
   278       checkInd(g1,g2,iso);
   280     return true;
   279       return true;
   281   }
   280     }
   282   else
   281   else return false;
   283     return false;
   282 }
   284 }
   283 
   285 
   284 template<class G1,class G2>
   286 template<class G1,class G2>
   285 int checkIso(const G1 &g1, const G2 &g2)
   287 int checkIso(const G1 &g1, const G2 &g2) {
   286 {
       
   287   typename G1:: template NodeMap<typename G2::Node> iso(g1,INVALID);
   288   typename G1:: template NodeMap<typename G2::Node> iso(g1,INVALID);
   288   if(vf2(g1,g2).iso().mapping(iso).run())
   289   if(vf2(g1,g2).iso().mapping(iso).run()) {
   289     {
   290     check(countNodes(g1)==countNodes(g2),
   290       check(countNodes(g1)==countNodes(g2),
   291           "Wrong iso alg.: they are not isomophic.");
   291             "Wrong iso alg.: they are not isomophic.");
   292     checkInd(g1,g2,iso);
   292       checkInd(g1,g2,iso);
   293     return true;
   293       return true;
   294   }
   294     }
   295   else
   295   else return false;
   296     return false;
   296 }
   297 }
   297 
   298 
   298 template<class G1, class G2, class L1, class L2, class I>
   299 template<class G1, class G2, class L1, class L2, class I>
   299 void checkLabel(const G1 &g1, const G2 &,
   300 void checkLabel(const G1 &g1, const G2 &,
   300                 const L1 &l1, const L2 &l2,const I &i)
   301                 const L1 &l1, const L2 &l2,const I &i) {
   301 {
       
   302   for(typename G1::NodeIt n(g1);n!=INVALID;++n)
   302   for(typename G1::NodeIt n(g1);n!=INVALID;++n)
   303     {
   303     check(l1[n]==l2[i[n]],"Wrong isomorphism: label mismatch.");
   304       check(l1[n]==l2[i[n]],"Wrong isomorphism: label mismatch.");
       
   305     }
       
   306 }
   304 }
   307 
   305 
   308 template<class G1,class G2,class L1,class L2>
   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)
   307 int checkSub(const G1 &g1, const G2 &g2, const L1 &l1, const L2 &l2) {
   310 {
       
   311   typename G1:: template NodeMap<typename G2::Node> iso(g1,INVALID);
   308   typename G1:: template NodeMap<typename G2::Node> iso(g1,INVALID);
   312   if(vf2(g1,g2).nodeLabels(l1,l2).mapping(iso).run())
   309   if(vf2(g1,g2).nodeLabels(l1,l2).mapping(iso).run()){
   313     {
   310     checkSub(g1,g2,iso);
   314       checkSub(g1,g2,iso);
   311     checkLabel(g1,g2,l1,l2,iso);
   315       checkLabel(g1,g2,l1,l2,iso);
   312     return true;
   316       return true;
   313   }
   317     }
   314   else
   318   else return false;
   315     return false;
   319 }
   316 }
   320 
   317 
   321 int main() {
   318 int main() {
   322   make_graphs();
   319   make_graphs();
       
   320   //   justCompile();
   323   check(checkSub(c5,petersen), "There should exist a C5->Petersen mapping.");
   321   check(checkSub(c5,petersen), "There should exist a C5->Petersen mapping.");
   324   check(!checkSub(c7,petersen),
   322   check(!checkSub(c7,petersen),
   325         "There should not exist a C7->Petersen mapping.");
   323         "There should not exist a C7->Petersen mapping.");
   326   check(checkSub(p10,petersen), "There should exist a P10->Petersen mapping.");
   324   check(checkSub(p10,petersen), "There should exist a P10->Petersen mapping.");
   327   check(!checkSub(c10,petersen),
   325   check(!checkSub(c10,petersen),