Mercuriallemon / comparison
summary | shortlog | changelog | graph | tags | bookmarks | branches | files | changeset | file | latest | revisions | annotate | diff | comparison | raw | help
test/vf2_test.cc
changeset 1407 76349d8212d3
parent 1405 3feba0ea1bda
equal deleted inserted replaced
2:580c6f315a11 3:cc4ba3392194 
    14  * purpose.
 
    14  * purpose.
 
    15  *
 
    15  *
 
    16  */
 
    16  */
 
    17 
    17 
    18 #include <lemon/vf2.h>
 
    18 #include <lemon/vf2.h>
 
       
    19 #include <lemon/vf2pp.h>
 
    19 #include <lemon/concepts/digraph.h>
 
    20 #include <lemon/concepts/digraph.h>
 
    20 #include <lemon/smart_graph.h>
 
    21 #include <lemon/smart_graph.h>
 
    21 #include <lemon/lgf_reader.h>
 
    22 #include <lemon/lgf_reader.h>
 
    22 #include <lemon/concepts/maps.h>
 
    23 #include <lemon/concepts/maps.h>
 
    23 
    24 
   150 SmartGraph::NodeMap<int> c5_col(c5);
 
   151 SmartGraph::NodeMap<int> c5_col(c5);
 
   151 
   152 
   152 void make_graphs() {
 
   153 void make_graphs() {
 
   153   std::stringstream ss(petersen_lgf);
 
   154   std::stringstream ss(petersen_lgf);
 
   154   graphReader(petersen, ss)
 
   155   graphReader(petersen, ss)
 
   155     .nodeMap("col1",petersen_col1)
 
   156     .nodeMap("col1", petersen_col1)
 
   156     .nodeMap("col2",petersen_col2)
 
   157     .nodeMap("col2", petersen_col2)
 
   157     .run();
 
   158     .run();
 
   158 
   159 
   159   ss.clear();
 
   160   ss.clear();
 
   160   ss.str("");
 
   161   ss.str("");
 
   161   ss<<c5_lgf;
 
   162   ss << c5_lgf;
 
   162   //std::stringstream ss2(c5_lgf);
 
   163   //std::stringstream ss2(c5_lgf);
 
   163   graphReader(c5, ss)
 
   164   graphReader(c5, ss)
 
   164     .nodeMap("col",c5_col)
 
   165     .nodeMap("col", c5_col)
 
   165     .run();
 
   166     .run();
 
   166 
   167 
   167   ss.clear();
 
   168   ss.clear();
 
   168   ss.str("");
 
   169   ss.str("");
 
   169   ss<<c7_lgf;
 
   170   ss << c7_lgf;
 
   170   graphReader(c7, ss).run();
 
   171   graphReader(c7, ss).run();
 
   171 
   172 
   172   ss.clear();
 
   173   ss.clear();
 
   173   ss.str("");
 
   174   ss.str("");
 
   174   ss<<c10_lgf;
 
   175   ss << c10_lgf;
 
   175   graphReader(c10, ss).run();
 
   176   graphReader(c10, ss).run();
 
   176 
   177 
   177   ss.clear();
 
   178   ss.clear();
 
   178   ss.str("");
 
   179   ss.str("");
 
   179   ss<<p10_lgf;
 
   180   ss << p10_lgf;
 
   180   graphReader(p10, ss).run();
 
   181   graphReader(p10, ss).run();
 
   181 
   182 
   182 }
 
   183 }
 
   183 
   184 
   184 class EqComparable {
 
   185 class EqComparable {
 
   191 template<class A, class B>
 
   192 template<class A, class B>
 
   192 class EqClass {
 
   193 class EqClass {
 
   193 public:
 
   194 public:
 
   194   bool operator()(A, B){
 
   195   bool operator()(A, B){
 
   195     return false;
 
   196     return false;
 
       
   197   }
 
       
   198 };
 
       
   199 
       
   200 class IntConvertible1 {
 
       
   201 public:
 
       
   202   operator int() {
 
       
   203     return 0;
 
       
   204   }
 
       
   205 };
 
       
   206 
       
   207 class IntConvertible2 {
 
       
   208 public:
 
       
   209   operator int() {
 
       
   210     return 0;
 
   196   }
 
   211   }
 
   197 };
 
   212 };
 
   198 
   213 
   199 template<class G1,class G2>
 
   214 template<class G1,class G2>
 
   200 void checkVf2Compile() {
 
   215 void checkVf2Compile() {
 
   222   succ = vf2(g,h).nodeLabels(l1,l2).mapping(r).run();
 
   237   succ = vf2(g,h).nodeLabels(l1,l2).mapping(r).run();
 
   223   succ = vf2(g,h).nodeEq(EqClass<typename G1::Node,typename G2::Node>())
 
   238   succ = vf2(g,h).nodeEq(EqClass<typename G1::Node,typename G2::Node>())
 
   224     .mapping(r).run();
 
   239     .mapping(r).run();
 
   225 }
 
   240 }
 
   226 
   241 
   227 void justCompile() {
 
   242 void vf2Compile() {
 
   228   checkVf2Compile<concepts::Graph,concepts::Graph>();
 
   243   checkVf2Compile<concepts::Graph,concepts::Graph>();
 
   229   checkVf2Compile<concepts::Graph,SmartGraph>();
 
   244   checkVf2Compile<concepts::Graph,SmartGraph>();
 
   230   checkVf2Compile<SmartGraph,concepts::Graph>();
 
   245   checkVf2Compile<SmartGraph,concepts::Graph>();
 
   231 }
 
   246 }
 
   232 
   247 
       
   248 template<class G1,class G2>
 
       
   249 void checkVf2ppCompile() {
 
       
   250   G1 g;
 
       
   251   G2 h;
 
       
   252   concepts::ReadWriteMap<typename G1::Node, typename G2::Node> r;
 
       
   253   bool succ;
 
       
   254   ::lemon::ignore_unused_variable_warning(succ);
 
       
   255 
       
   256   succ = vf2pp(g,h).run();
 
       
   257   succ = vf2pp(g,h).induced().run();
 
       
   258   succ = vf2pp(g,h).iso().run();
 
       
   259   succ = vf2pp(g,h).mapping(r).run();
 
       
   260   succ = vf2pp(g,h).induced().mapping(r).run();
 
       
   261   succ = vf2pp(g,h).iso().mapping(r).run();
 
       
   262 
       
   263   concepts::ReadMap<typename G1::Node, int> c1;
 
       
   264   concepts::ReadMap<typename G2::Node, int> c2;
 
       
   265   Vf2pp<G1,G2,concepts::ReadWriteMap<typename G1::Node, typename G2::Node>,
 
       
   266         concepts::ReadMap<typename G1::Node, int>,
 
       
   267         concepts::ReadMap<typename G2::Node, int> >
 
       
   268     myVf2pp(g,h,r,c1,c2);
 
       
   269   myVf2pp.find();
 
       
   270 
       
   271   succ = vf2pp(g,h).nodeLabels(c1,c2).mapping(r).run();
 
       
   272   succ = vf2pp(g,h).nodeLabels(c1,c2).mapping(r).run();
 
       
   273 
       
   274   concepts::ReadMap<typename G1::Node, char> c1_c;
 
       
   275   concepts::ReadMap<typename G2::Node, char> c2_c;
 
       
   276   Vf2pp<G1,G2,concepts::ReadWriteMap<typename G1::Node, typename G2::Node>,
 
       
   277         concepts::ReadMap<typename G1::Node, char>,
 
       
   278         concepts::ReadMap<typename G2::Node, char> >
 
       
   279     myVf2pp_c(g,h,r,c1_c,c2_c);
 
       
   280   myVf2pp_c.find();
 
       
   281 
       
   282   succ = vf2pp(g,h).nodeLabels(c1_c,c2_c).mapping(r).run();
 
       
   283   succ = vf2pp(g,h).nodeLabels(c1_c,c2_c).mapping(r).run();
 
       
   284 
       
   285   concepts::ReadMap<typename G1::Node, IntConvertible1> c1_IntConv;
 
       
   286   concepts::ReadMap<typename G2::Node, IntConvertible2> c2_IntConv;
 
       
   287   Vf2pp<G1,G2,concepts::ReadWriteMap<typename G1::Node, typename G2::Node>,
 
       
   288         concepts::ReadMap<typename G1::Node, IntConvertible1>,
 
       
   289         concepts::ReadMap<typename G2::Node, IntConvertible2> >
 
       
   290     myVf2pp_IntConv(g,h,r,c1_IntConv,c2_IntConv);
 
       
   291   myVf2pp_IntConv.find();
 
       
   292 
       
   293   succ = vf2pp(g,h).nodeLabels(c1_IntConv,c2_IntConv).mapping(r).run();
 
       
   294   succ = vf2pp(g,h).nodeLabels(c1_IntConv,c2_IntConv).mapping(r).run();
 
       
   295 }
 
       
   296 
       
   297 void vf2ppCompile() {
 
       
   298   checkVf2ppCompile<concepts::Graph,concepts::Graph>();
 
       
   299   checkVf2ppCompile<concepts::Graph,SmartGraph>();
 
       
   300   checkVf2ppCompile<SmartGraph,concepts::Graph>();
 
       
   301 }
 
       
   302 
   233 template<class G1, class G2, class I>
 
   303 template<class G1, class G2, class I>
 
   234 void checkSub(const G1 &g1, const G2 &g2, const I &i) {
 
   304 void checkSubIso(const G1 &g1, const G2 &g2, const I &i) {
 
   235   {
 
       
   236     std::set<typename G2::Node> image;
 
       
   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     }
 
       
   242   }
 
       
   243   for(typename G1::EdgeIt e(g1);e!=INVALID;++e)
 
       
   244     check(findEdge(g2,i[g1.u(e)],i[g1.v(e)])!=INVALID,
 
       
   245           "Wrong isomorphism: missing edge(checkSub).");
 
       
   246 }
 
       
   247 
       
   248 template<class G1, class G2, class I>
 
       
   249 void checkInd(const G1 &g1, const G2 &g2, const I &i) {
 
       
   250   std::set<typename G2::Node> image;
 
   305   std::set<typename G2::Node> image;
 
   251   for(typename G1::NodeIt n(g1);n!=INVALID;++n) {
 
   306   for (typename G1::NodeIt n(g1);n!=INVALID;++n){
 
   252     check(i[n]!=INVALID, "Wrong isomorphism: incomplete mapping.");
 
   307     check(i[n]!=INVALID, "Wrong isomorphism: incomplete mapping.");
 
   253     check(image.count(i[n])==0,"Wrong isomorphism: not injective.");
 
   308     check(image.count(i[n])==0,"Wrong isomorphism: not injective.");
 
   254     image.insert(i[n]);
 
   309     image.insert(i[n]);
 
   255   }
 
   310   }
 
   256   for(typename G1::NodeIt n(g1); n!=INVALID; ++n)
 
   311   for (typename G1::EdgeIt e(g1);e!=INVALID;++e) {
 
   257     for(typename G1::NodeIt m(g1); m!=INVALID; ++m)
 
   312     check(findEdge(g2,i[g1.u(e)],i[g1.v(e)])!=INVALID,
 
       
   313           "Wrong isomorphism: missing edge(checkSub).");
 
       
   314   }
 
       
   315 }
 
       
   316 
       
   317 template<class G1, class G2, class I>
 
       
   318 void checkIndIso(const G1 &g1, const G2 &g2, const I &i) {
 
       
   319   std::set<typename G2::Node> image;
 
       
   320   for (typename G1::NodeIt n(g1);n!=INVALID;++n) {
 
       
   321     check(i[n]!=INVALID, "Wrong isomorphism: incomplete mapping.");
 
       
   322     check(image.count(i[n])==0,"Wrong isomorphism: not injective.");
 
       
   323     image.insert(i[n]);
 
       
   324   }
 
       
   325   for (typename G1::NodeIt n(g1); n!=INVALID; ++n) {
 
       
   326     for (typename G1::NodeIt m(g1); m!=INVALID; ++m) {
 
   258       if((findEdge(g1,n,m)==INVALID) != (findEdge(g2,i[n],i[m])==INVALID)) {
 
   327       if((findEdge(g1,n,m)==INVALID) != (findEdge(g2,i[n],i[m])==INVALID)) {
 
   259         std::cout << "Wrong isomorphism: edge mismatch";
 
   328         std::cout << "Wrong isomorphism: edge mismatch";
 
   260         exit(1);
 
   329         exit(1);
 
   261       }
 
   330       }
 
   262 }
 
   331     }
 
   263 
   332   }
 
   264 template<class G1,class G2>
 
   333 }
 
   265 int checkSub(const G1 &g1, const G2 &g2) {
 
   334 
       
   335 template<class G1,class G2,class T>
 
       
   336 bool checkSub(const G1 &g1, const G2 &g2, const T &vf2) {
 
   266   typename G1:: template NodeMap<typename G2::Node> iso(g1,INVALID);
 
   337   typename G1:: template NodeMap<typename G2::Node> iso(g1,INVALID);
 
   267   if(vf2(g1,g2).mapping(iso).run()) {
 
   338   if (const_cast<T&>(vf2).mapping(iso).run()) {
 
   268     checkSub(g1,g2,iso);
 
   339     checkSubIso(g1,g2,iso);
 
   269     return true;
 
   340     return true;
 
   270   }
 
   341   }
 
   271   else
 
   342   return false;
 
   272     return false;
 
   343 }
 
   273 }
 
   344 
   274 
   345 template<class G1,class G2,class T>
 
   275 template<class G1,class G2>
 
   346 bool checkInd(const G1 &g1, const G2 &g2, const T &vf2) {
 
   276 int checkInd(const G1 &g1, const G2 &g2) {
 
       
   277   typename G1:: template NodeMap<typename G2::Node> iso(g1,INVALID);
 
   347   typename G1:: template NodeMap<typename G2::Node> iso(g1,INVALID);
 
   278   if(vf2(g1,g2).induced().mapping(iso).run()) {
 
   348   if (const_cast<T&>(vf2).induced().mapping(iso).run()) {
 
   279     checkInd(g1,g2,iso);
 
   349     checkIndIso(g1,g2,iso);
 
   280     return true;
 
   350     return true;
 
   281   }
 
   351   }
 
   282   else
 
   352   return false;
 
   283     return false;
 
   353 }
 
   284 }
 
   354 
   285 
   355 template<class G1,class G2,class T>
 
   286 template<class G1,class G2>
 
   356 bool checkIso(const G1 &g1, const G2 &g2, const T &vf2) {
 
   287 int checkIso(const G1 &g1, const G2 &g2) {
 
       
   288   typename G1:: template NodeMap<typename G2::Node> iso(g1,INVALID);
 
   357   typename G1:: template NodeMap<typename G2::Node> iso(g1,INVALID);
 
   289   if(vf2(g1,g2).iso().mapping(iso).run()) {
 
   358   if (const_cast<T&>(vf2).iso().mapping(iso).run()) {
 
   290     check(countNodes(g1)==countNodes(g2),
 
   359     check(countNodes(g1)==countNodes(g2),
 
   291           "Wrong iso alg.: they are not isomophic.");
 
   360           "Wrong iso alg.: they are not isomophic.");
 
   292     checkInd(g1,g2,iso);
 
   361     checkIndIso(g1,g2,iso);
 
   293     return true;
 
   362     return true;
 
   294   }
 
   363   }
 
   295   else
 
   364   return false;
 
   296     return false;
 
       
   297 }
 
   365 }
 
   298 
   366 
   299 template<class G1, class G2, class L1, class L2, class I>
 
   367 template<class G1, class G2, class L1, class L2, class I>
 
   300 void checkLabel(const G1 &g1, const G2 &,
 
   368 void checkLabel(const G1 &g1, const G2 &,
 
   301                 const L1 &l1, const L2 &l2,const I &i) {
 
   369                 const L1 &l1, const L2 &l2, const I &i) {
 
   302   for(typename G1::NodeIt n(g1);n!=INVALID;++n)
 
   370   for (typename G1::NodeIt n(g1);n!=INVALID;++n) {
 
   303     check(l1[n]==l2[i[n]],"Wrong isomorphism: label mismatch.");
 
   371     check(l1[n]==l2[i[n]],"Wrong isomorphism: label mismatch.");
 
   304 }
 
   372   }
 
   305 
   373 }
 
   306 template<class G1,class G2,class L1,class L2>
 
   374 
   307 int checkSub(const G1 &g1, const G2 &g2, const L1 &l1, const L2 &l2) {
 
   375 template<class G1,class G2,class L1,class L2,class T>
 
       
   376 bool checkSub(const G1 &g1, const G2 &g2, const L1 &l1, const L2 &l2, const T &vf2) {
 
   308   typename G1:: template NodeMap<typename G2::Node> iso(g1,INVALID);
 
   377   typename G1:: template NodeMap<typename G2::Node> iso(g1,INVALID);
 
   309   if(vf2(g1,g2).nodeLabels(l1,l2).mapping(iso).run()){
 
   378   if (const_cast<T&>(vf2).nodeLabels(l1,l2).mapping(iso).run()){
 
   310     checkSub(g1,g2,iso);
 
   379     checkSubIso(g1,g2,iso);
 
   311     checkLabel(g1,g2,l1,l2,iso);
 
   380     checkLabel(g1,g2,l1,l2,iso);
 
   312     return true;
 
   381     return true;
 
   313   }
 
   382   }
 
   314   else
 
   383   return false;
 
   315     return false;
 
   384 }
 
       
   385 
       
   386 template<class G1,class G2>
 
       
   387 void checkSub(const G1 &g1, const G2 &g2, bool expected, const char* msg) {
 
       
   388   check(checkSub(g1,g2,vf2(g1,g2)) == expected, msg);
 
       
   389   check(checkSub(g1,g2,vf2pp(g1,g2)) == expected, msg);
 
       
   390 }
 
       
   391 
       
   392 template<class G1,class G2>
 
       
   393 void checkInd(const G1 &g1, const G2 &g2, bool expected, const char* msg) {
 
       
   394   check(checkInd(g1,g2,vf2(g1,g2)) == expected, msg);
 
       
   395   check(checkInd(g1,g2,vf2pp(g1,g2)) == expected, msg);
 
       
   396 }
 
       
   397 
       
   398 template<class G1,class G2>
 
       
   399 void checkIso(const G1 &g1, const G2 &g2, bool expected, const char* msg) {
 
       
   400   check(checkIso(g1,g2,vf2(g1,g2)) == expected, msg);
 
       
   401   check(checkIso(g1,g2,vf2pp(g1,g2)) == expected, msg);
 
       
   402 }
 
       
   403 
       
   404 template<class G1,class G2,class L1,class L2>
 
       
   405 void checkSub(const G1 &g1, const G2 &g2, const L1 &l1, const L2 &l2, bool expected, const char* msg) {
 
       
   406   check(checkSub(g1,g2,l1,l2,vf2(g1,g2)) == expected, msg);
 
       
   407   check(checkSub(g1,g2,l1,l2,vf2pp(g1,g2)) == expected, msg);
 
   316 }
 
   408 }
 
   317 
   409 
   318 int main() {
 
   410 int main() {
 
   319   make_graphs();
 
   411   make_graphs();
 
   320   //   justCompile();
 
   412 
   321   check(checkSub(c5,petersen), "There should exist a C5->Petersen mapping.");
 
   413   checkSub(c5,petersen,true,
 
   322   check(!checkSub(c7,petersen),
 
   414       "There should exist a C5->Petersen mapping.");
 
   323         "There should not exist a C7->Petersen mapping.");
 
   415   checkSub(c7,petersen,false,
 
   324   check(checkSub(p10,petersen), "There should exist a P10->Petersen mapping.");
 
   416       "There should not exist a C7->Petersen mapping.");
 
   325   check(!checkSub(c10,petersen),
 
   417   checkSub(p10,petersen,true,
 
   326         "There should not exist a C10->Petersen mapping.");
 
   418       "There should exist a P10->Petersen mapping.");
 
   327   check(checkSub(petersen,petersen),
 
   419   checkSub(c10,petersen,false,
 
   328         "There should exist a Petersen->Petersen mapping.");
 
   420       "There should not exist a C10->Petersen mapping.");
 
   329 
   421   checkSub(petersen,petersen,true,
 
   330   check(checkInd(c5,petersen),
 
   422       "There should exist a Petersen->Petersen mapping.");
 
   331         "There should exist a C5->Petersen spanned mapping.");
 
   423 
   332   check(!checkInd(c7,petersen),
 
   424   checkInd(c5,petersen,true,
 
   333         "There should exist a C7->Petersen spanned mapping.");
 
   425       "There should exist a C5->Petersen spanned mapping.");
 
   334   check(!checkInd(p10,petersen),
 
   426   checkInd(c7,petersen,false,
 
   335         "There should not exist a P10->Petersen spanned mapping.");
 
   427       "There should exist a C7->Petersen spanned mapping.");
 
   336   check(!checkInd(c10,petersen),
 
   428   checkInd(p10,petersen,false,
 
   337         "There should not exist a C10->Petersen spanned mapping.");
 
   429       "There should not exist a P10->Petersen spanned mapping.");
 
   338   check(checkInd(petersen,petersen),
 
   430   checkInd(c10,petersen,false,
 
       
   431       "There should not exist a C10->Petersen spanned mapping.");
 
       
   432   checkInd(petersen,petersen,true,
 
   339         "There should exist a Petersen->Petersen spanned mapping.");
 
   433         "There should exist a Petersen->Petersen spanned mapping.");
 
   340 
   434 
   341   check(!checkSub(petersen,c10),
 
   435   checkSub(petersen,c10,false,
 
   342         "There should not exist a Petersen->C10 mapping.");
 
   436       "There should not exist a Petersen->C10 mapping.");
 
   343   check(checkSub(p10,c10),
 
   437   checkSub(p10,c10,true,
 
   344         "There should exist a P10->C10 mapping.");
 
   438       "There should exist a P10->C10 mapping.");
 
   345   check(!checkInd(p10,c10),
 
   439   checkInd(p10,c10,false,
 
   346         "There should not exist a P10->C10 spanned mapping.");
 
   440       "There should not exist a P10->C10 spanned mapping.");
 
   347   check(!checkSub(c10,p10),
 
   441   checkSub(c10,p10,false,
 
   348         "There should not exist a C10->P10 mapping.");
 
   442       "There should not exist a C10->P10 mapping.");
 
   349 
   443 
   350   check(!checkIso(p10,c10),
 
   444   checkIso(p10,c10,false,
 
   351         "P10 and C10 are not isomorphic.");
 
   445       "P10 and C10 are not isomorphic.");
 
   352   check(checkIso(c10,c10),
 
   446   checkIso(c10,c10,true,
 
   353         "C10 and C10 are isomorphic.");
 
   447       "C10 and C10 are isomorphic.");
 
   354 
   448 
   355   check(!vf2(p10,c10).iso().run(),
 
   449   checkSub(c5,petersen,c5_col,petersen_col1,false,
 
   356         "P10 and C10 are not isomorphic.");
 
   450       "There should exist a C5->Petersen mapping.");
 
   357   check(vf2(c10,c10).iso().run(),
 
   451   checkSub(c5,petersen,c5_col,petersen_col2,true,
 
   358         "C10 and C10 are isomorphic.");
 
   452       "There should exist a C5->Petersen mapping.");
 
   359 
   453 
   360   check(!checkSub(c5,petersen,c5_col,petersen_col1),
 
   454   check(!vf2(p10,c10).iso().run(), "P10 and C10 are not isomorphic.");
 
   361         "There should exist a C5->Petersen mapping.");
 
   455   check(!vf2pp(p10,c10).iso().run(), "P10 and C10 are not isomorphic.");
 
   362   check(checkSub(c5,petersen,c5_col,petersen_col2),
 
   456 
   363         "There should exist a C5->Petersen mapping.");
 
   457   check(vf2(c10,c10).iso().run(), "C10 and C10 are isomorphic.");
 
   364 }
 
   458   check(vf2pp(c10,c10).iso().run(), "C10 and C10 are isomorphic.");
 
       
   459 }
lemon