Mercuriallemon / file revision
summary | shortlog | changelog | graph | tags | bookmarks | branches | files | changeset | file | latest | revisions | annotate | diff | comparison | raw | help
test/vf2_test.cc
author Peter Kovacs <kpeter@inf.elte.hu>
Sat, 07 Oct 2017 15:45:56 +0200
changeset 1408 b9fad0f9f8ab
parent 1405 3feba0ea1bda
permissions -rw-r--r--
Unify naming scheme of fields in Vf2 and Vf2pp (#597) 
     1 /* -*- mode: C++; indent-tabs-mode: nil; -*-

     2  *

     3  * This file is a part of LEMON, a generic C++ optimization library.

     4  *

     5  * Copyright (C) 2015-2017

     6  * EMAXA Kutato-fejleszto Kft. (EMAXA Research Ltd.)

     7  *

     8  * Permission to use, modify and distribute this software is granted

     9  * provided that this copyright notice appears in all copies. For

    10  * precise terms see the accompanying LICENSE file.

    11  *

    12  * This software is provided "AS IS" with no warranty of any kind,

    13  * express or implied, and with no claim as to its suitability for any

    14  * purpose.

    15  *

    16  */

    17 

    18 #include <lemon/vf2.h>

    19 #include <lemon/vf2pp.h>

    20 #include <lemon/concepts/digraph.h>

    21 #include <lemon/smart_graph.h>

    22 #include <lemon/lgf_reader.h>

    23 #include <lemon/concepts/maps.h>

    24 

    25 #include <test/test_tools.h>

    26 #include <sstream>

    27 

    28 using namespace lemon;

    29 

    30 char petersen_lgf[] =

    31   "@nodes\n"

    32   "label col1 col2\n"

    33   "0 1 1\n"

    34   "1 1 2\n"

    35   "2 1 3\n"

    36   "3 1 4\n"

    37   "4 2 5\n"

    38   "5 2 1\n"

    39   "6 2 2\n"

    40   "7 2 3\n"

    41   "8 2 4\n"

    42   "9 2 5\n"

    43   "@arcs\n"

    44   "     -\n"

    45   "0 1\n"

    46   "1 2\n"

    47   "2 3\n"

    48   "3 4\n"

    49   "4 0\n"

    50   "0 5\n"

    51   "1 6\n"

    52   "2 7\n"

    53   "3 8\n"

    54   "4 9\n"

    55   "5 8\n"

    56   "5 7\n"

    57   "9 6\n"

    58   "9 7\n"

    59   "6 8\n";

    60 

    61 char c5_lgf[] =

    62   "@nodes\n"

    63   "label col\n"

    64   "0 1\n"

    65   "1 2\n"

    66   "2 3\n"

    67   "3 4\n"

    68   "4 5\n"

    69   "@arcs\n"

    70   "     -\n"

    71   "0 1\n"

    72   "1 2\n"

    73   "2 3\n"

    74   "3 4\n"

    75   "4 0\n";

    76 

    77 char c7_lgf[] =

    78   "@nodes\n"

    79   "label\n"

    80   "0\n"

    81   "1\n"

    82   "2\n"

    83   "3\n"

    84   "4\n"

    85   "5\n"

    86   "6\n"

    87   "@arcs\n"

    88   "     -\n"

    89   "0 1\n"

    90   "1 2\n"

    91   "2 3\n"

    92   "3 4\n"

    93   "4 5\n"

    94   "5 6\n"

    95   "6 0\n";

    96 

    97 char c10_lgf[] =

    98   "@nodes\n"

    99   "label\n"

   100   "0\n"

   101   "1\n"

   102   "2\n"

   103   "3\n"

   104   "4\n"

   105   "5\n"

   106   "6\n"

   107   "7\n"

   108   "8\n"

   109   "9\n"

   110   "@arcs\n"

   111   "     -\n"

   112   "0 1\n"

   113   "1 2\n"

   114   "2 3\n"

   115   "3 4\n"

   116   "4 5\n"

   117   "5 6\n"

   118   "6 7\n"

   119   "7 8\n"

   120   "8 9\n"

   121   "9 0\n";

   122 

   123 char p10_lgf[] =

   124   "@nodes\n"

   125   "label\n"

   126   "0\n"

   127   "1\n"

   128   "2\n"

   129   "3\n"

   130   "4\n"

   131   "5\n"

   132   "6\n"

   133   "7\n"

   134   "8\n"

   135   "9\n"

   136   "@arcs\n"

   137   "     -\n"

   138   "0 1\n"

   139   "1 2\n"

   140   "2 3\n"

   141   "3 4\n"

   142   "4 5\n"

   143   "5 6\n"

   144   "6 7\n"

   145   "7 8\n"

   146   "8 9\n";

   147 

   148 SmartGraph petersen, c5, c7, c10, p10;

   149 SmartGraph::NodeMap<int> petersen_col1(petersen);

   150 SmartGraph::NodeMap<int> petersen_col2(petersen);

   151 SmartGraph::NodeMap<int> c5_col(c5);

   152 

   153 void make_graphs() {

   154   std::stringstream ss(petersen_lgf);

   155   graphReader(petersen, ss)

   156     .nodeMap("col1", petersen_col1)

   157     .nodeMap("col2", petersen_col2)

   158     .run();

   159 

   160   ss.clear();

   161   ss.str("");

   162   ss << c5_lgf;

   163   //std::stringstream ss2(c5_lgf);

   164   graphReader(c5, ss)

   165     .nodeMap("col", c5_col)

   166     .run();

   167 

   168   ss.clear();

   169   ss.str("");

   170   ss << c7_lgf;

   171   graphReader(c7, ss).run();

   172 

   173   ss.clear();

   174   ss.str("");

   175   ss << c10_lgf;

   176   graphReader(c10, ss).run();

   177 

   178   ss.clear();

   179   ss.str("");

   180   ss << p10_lgf;

   181   graphReader(p10, ss).run();

   182 

   183 }

   184 

   185 class EqComparable {

   186 public:

   187   bool operator==(const EqComparable&) {

   188     return false;

   189   }

   190 };

   191 

   192 template<class A, class B>

   193 class EqClass {

   194 public:

   195   bool operator()(A, B){

   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;

   211   }

   212 };

   213 

   214 template<class G1,class G2>

   215 void checkVf2Compile() {

   216   G1 g;

   217   G2 h;

   218   concepts::ReadWriteMap<typename G1::Node, typename G2::Node> r;

   219   bool succ;

   220   ::lemon::ignore_unused_variable_warning(succ);

   221 

   222   succ = vf2(g,h).run();

   223   succ = vf2(g,h).induced().run();

   224   succ = vf2(g,h).iso().run();

   225   succ = vf2(g,h).mapping(r).run();

   226 

   227   Vf2<G1,G2,concepts::ReadWriteMap<typename G1::Node, typename G2::Node>,

   228       EqClass<typename G1::Node,typename G2::Node> >

   229     myVf2(g,h,r,EqClass<typename G1::Node,typename G2::Node>());

   230   myVf2.find();

   231 

   232   succ = vf2(g,h).induced().mapping(r).run();

   233   succ = vf2(g,h).iso().mapping(r).run();

   234 

   235   concepts::ReadMap<typename G1::Node, EqComparable> l1;

   236   concepts::ReadMap<typename G2::Node, EqComparable> l2;

   237   succ = vf2(g,h).nodeLabels(l1,l2).mapping(r).run();

   238   succ = vf2(g,h).nodeEq(EqClass<typename G1::Node,typename G2::Node>())

   239     .mapping(r).run();

   240 }

   241 

   242 void vf2Compile() {

   243   checkVf2Compile<concepts::Graph,concepts::Graph>();

   244   checkVf2Compile<concepts::Graph,SmartGraph>();

   245   checkVf2Compile<SmartGraph,concepts::Graph>();

   246 }

   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 

   303 template<class G1, class G2, class I>

   304 void checkSubIso(const G1 &g1, const G2 &g2, const I &i) {

   305   std::set<typename G2::Node> image;

   306   for (typename G1::NodeIt n(g1);n!=INVALID;++n){

   307     check(i[n]!=INVALID, "Wrong isomorphism: incomplete mapping.");

   308     check(image.count(i[n])==0,"Wrong isomorphism: not injective.");

   309     image.insert(i[n]);

   310   }

   311   for (typename G1::EdgeIt e(g1);e!=INVALID;++e) {

   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) {

   327       if((findEdge(g1,n,m)==INVALID) != (findEdge(g2,i[n],i[m])==INVALID)) {

   328         std::cout << "Wrong isomorphism: edge mismatch";

   329         exit(1);

   330       }

   331     }

   332   }

   333 }

   334 

   335 template<class G1,class G2,class T>

   336 bool checkSub(const G1 &g1, const G2 &g2, const T &vf2) {

   337   typename G1:: template NodeMap<typename G2::Node> iso(g1,INVALID);

   338   if (const_cast<T&>(vf2).mapping(iso).run()) {

   339     checkSubIso(g1,g2,iso);

   340     return true;

   341   }

   342   return false;

   343 }

   344 

   345 template<class G1,class G2,class T>

   346 bool checkInd(const G1 &g1, const G2 &g2, const T &vf2) {

   347   typename G1:: template NodeMap<typename G2::Node> iso(g1,INVALID);

   348   if (const_cast<T&>(vf2).induced().mapping(iso).run()) {

   349     checkIndIso(g1,g2,iso);

   350     return true;

   351   }

   352   return false;

   353 }

   354 

   355 template<class G1,class G2,class T>

   356 bool checkIso(const G1 &g1, const G2 &g2, const T &vf2) {

   357   typename G1:: template NodeMap<typename G2::Node> iso(g1,INVALID);

   358   if (const_cast<T&>(vf2).iso().mapping(iso).run()) {

   359     check(countNodes(g1)==countNodes(g2),

   360           "Wrong iso alg.: they are not isomophic.");

   361     checkIndIso(g1,g2,iso);

   362     return true;

   363   }

   364   return false;

   365 }

   366 

   367 template<class G1, class G2, class L1, class L2, class I>

   368 void checkLabel(const G1 &g1, const G2 &,

   369                 const L1 &l1, const L2 &l2, const I &i) {

   370   for (typename G1::NodeIt n(g1);n!=INVALID;++n) {

   371     check(l1[n]==l2[i[n]],"Wrong isomorphism: label mismatch.");

   372   }

   373 }

   374 

   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) {

   377   typename G1:: template NodeMap<typename G2::Node> iso(g1,INVALID);

   378   if (const_cast<T&>(vf2).nodeLabels(l1,l2).mapping(iso).run()){

   379     checkSubIso(g1,g2,iso);

   380     checkLabel(g1,g2,l1,l2,iso);

   381     return true;

   382   }

   383   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);

   408 }

   409 

   410 int main() {

   411   make_graphs();

   412 

   413   checkSub(c5,petersen,true,

   414       "There should exist a C5->Petersen mapping.");

   415   checkSub(c7,petersen,false,

   416       "There should not exist a C7->Petersen mapping.");

   417   checkSub(p10,petersen,true,

   418       "There should exist a P10->Petersen mapping.");

   419   checkSub(c10,petersen,false,

   420       "There should not exist a C10->Petersen mapping.");

   421   checkSub(petersen,petersen,true,

   422       "There should exist a Petersen->Petersen mapping.");

   423 

   424   checkInd(c5,petersen,true,

   425       "There should exist a C5->Petersen spanned mapping.");

   426   checkInd(c7,petersen,false,

   427       "There should exist a C7->Petersen spanned mapping.");

   428   checkInd(p10,petersen,false,

   429       "There should not exist a P10->Petersen spanned mapping.");

   430   checkInd(c10,petersen,false,

   431       "There should not exist a C10->Petersen spanned mapping.");

   432   checkInd(petersen,petersen,true,

   433         "There should exist a Petersen->Petersen spanned mapping.");

   434 

   435   checkSub(petersen,c10,false,

   436       "There should not exist a Petersen->C10 mapping.");

   437   checkSub(p10,c10,true,

   438       "There should exist a P10->C10 mapping.");

   439   checkInd(p10,c10,false,

   440       "There should not exist a P10->C10 spanned mapping.");

   441   checkSub(c10,p10,false,

   442       "There should not exist a C10->P10 mapping.");

   443 

   444   checkIso(p10,c10,false,

   445       "P10 and C10 are not isomorphic.");

   446   checkIso(c10,c10,true,

   447       "C10 and C10 are isomorphic.");

   448 

   449   checkSub(c5,petersen,c5_col,petersen_col1,false,

   450       "There should exist a C5->Petersen mapping.");

   451   checkSub(c5,petersen,c5_col,petersen_col2,true,

   452       "There should exist a C5->Petersen mapping.");

   453 

   454   check(!vf2(p10,c10).iso().run(), "P10 and C10 are not isomorphic.");

   455   check(!vf2pp(p10,c10).iso().run(), "P10 and C10 are not isomorphic.");

   456 

   457   check(vf2(c10,c10).iso().run(), "C10 and C10 are isomorphic.");

   458   check(vf2pp(c10,c10).iso().run(), "C10 and C10 are isomorphic.");

   459 }
lemon