test/vf2pp_test.cc
changeset 1186 3feba0ea1bda
equal deleted inserted replaced
-1:000000000000 0:7fc8844bf092
       
     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/vf2pp.h>
       
    19 #include <lemon/concepts/digraph.h>
       
    20 #include <lemon/smart_graph.h>
       
    21 #include <lemon/lgf_reader.h>
       
    22 #include <lemon/concepts/maps.h>
       
    23 #include <lemon/maps.h>
       
    24 #include <lemon/list_graph.h>
       
    25 
       
    26 #include <test/test_tools.h>
       
    27 #include <sstream>
       
    28 
       
    29 using namespace lemon;
       
    30 
       
    31 char petersen_lgf[] =
       
    32   "@nodes\n"
       
    33   "label col1 col2\n"
       
    34   "0 1 1\n"
       
    35   "1 1 2\n"
       
    36   "2 1 3\n"
       
    37   "3 1 4\n"
       
    38   "4 2 5\n"
       
    39   "5 2 1\n"
       
    40   "6 2 2\n"
       
    41   "7 2 3\n"
       
    42   "8 2 4\n"
       
    43   "9 2 5\n"
       
    44   "@arcs\n"
       
    45   "     -\n"
       
    46   "0 1\n"
       
    47   "1 2\n"
       
    48   "2 3\n"
       
    49   "3 4\n"
       
    50   "4 0\n"
       
    51   "0 5\n"
       
    52   "1 6\n"
       
    53   "2 7\n"
       
    54   "3 8\n"
       
    55   "4 9\n"
       
    56   "5 8\n"
       
    57   "5 7\n"
       
    58   "9 6\n"
       
    59   "9 7\n"
       
    60   "6 8\n";
       
    61 
       
    62 char c5_lgf[] =
       
    63   "@nodes\n"
       
    64   "label col\n"
       
    65   "0 1\n"
       
    66   "1 2\n"
       
    67   "2 3\n"
       
    68   "3 4\n"
       
    69   "4 5\n"
       
    70   "@arcs\n"
       
    71   "     -\n"
       
    72   "0 1\n"
       
    73   "1 2\n"
       
    74   "2 3\n"
       
    75   "3 4\n"
       
    76   "4 0\n";
       
    77 
       
    78 char c7_lgf[] =
       
    79   "@nodes\n"
       
    80   "label\n"
       
    81   "0\n"
       
    82   "1\n"
       
    83   "2\n"
       
    84   "3\n"
       
    85   "4\n"
       
    86   "5\n"
       
    87   "6\n"
       
    88   "@arcs\n"
       
    89   "     -\n"
       
    90   "0 1\n"
       
    91   "1 2\n"
       
    92   "2 3\n"
       
    93   "3 4\n"
       
    94   "4 5\n"
       
    95   "5 6\n"
       
    96   "6 0\n";
       
    97 
       
    98 char c10_lgf[] =
       
    99   "@nodes\n"
       
   100   "label\n"
       
   101   "0\n"
       
   102   "1\n"
       
   103   "2\n"
       
   104   "3\n"
       
   105   "4\n"
       
   106   "5\n"
       
   107   "6\n"
       
   108   "7\n"
       
   109   "8\n"
       
   110   "9\n"
       
   111   "@arcs\n"
       
   112   "     -\n"
       
   113   "0 1\n"
       
   114   "1 2\n"
       
   115   "2 3\n"
       
   116   "3 4\n"
       
   117   "4 5\n"
       
   118   "5 6\n"
       
   119   "6 7\n"
       
   120   "7 8\n"
       
   121   "8 9\n"
       
   122   "9 0\n";
       
   123 
       
   124 char p10_lgf[] =
       
   125   "@nodes\n"
       
   126   "label\n"
       
   127   "0\n"
       
   128   "1\n"
       
   129   "2\n"
       
   130   "3\n"
       
   131   "4\n"
       
   132   "5\n"
       
   133   "6\n"
       
   134   "7\n"
       
   135   "8\n"
       
   136   "9\n"
       
   137   "@arcs\n"
       
   138   "     -\n"
       
   139   "0 1\n"
       
   140   "1 2\n"
       
   141   "2 3\n"
       
   142   "3 4\n"
       
   143   "4 5\n"
       
   144   "5 6\n"
       
   145   "6 7\n"
       
   146   "7 8\n"
       
   147   "8 9\n";
       
   148 
       
   149 SmartGraph petersen, c5, c7, c10, p10;
       
   150 SmartGraph::NodeMap<int> petersen_col1(petersen);
       
   151 SmartGraph::NodeMap<int> petersen_col2(petersen);
       
   152 SmartGraph::NodeMap<int> c5_col(c5);
       
   153 
       
   154 void make_graphs(){
       
   155   std::stringstream ss(petersen_lgf);
       
   156   graphReader(petersen, ss)
       
   157     .nodeMap("col1",petersen_col1)
       
   158     .nodeMap("col2",petersen_col2)
       
   159     .run();
       
   160 
       
   161   ss.clear();
       
   162   ss.str("");
       
   163   ss<<c5_lgf;
       
   164 
       
   165   graphReader(c5, ss)
       
   166     .nodeMap("col",c5_col)
       
   167     .run();
       
   168 
       
   169   ss.clear();
       
   170   ss.str("");
       
   171   ss<<c7_lgf;
       
   172   graphReader(c7, ss).run();
       
   173 
       
   174   ss.clear();
       
   175   ss.str("");
       
   176   ss<<c10_lgf;
       
   177   graphReader(c10, ss).run();
       
   178 
       
   179   ss.clear();
       
   180   ss.str("");
       
   181   ss<<p10_lgf;
       
   182   graphReader(p10, ss).run();
       
   183 
       
   184 }
       
   185 
       
   186 class IntConvertible1{
       
   187 public:
       
   188   operator int(){
       
   189     return 0;
       
   190   }
       
   191 };
       
   192 
       
   193 class IntConvertible2{
       
   194 public:
       
   195   operator int(){
       
   196     return 0;
       
   197   }
       
   198 };
       
   199 
       
   200 template<class G1,class G2>
       
   201 void checkVf2Compile() {
       
   202   G1 g;
       
   203   G2 h;
       
   204   concepts::ReadWriteMap<typename G1::Node, typename G2::Node> r;
       
   205   bool succ;
       
   206   ::lemon::ignore_unused_variable_warning(succ);
       
   207 
       
   208   succ = vf2pp(g,h).run();
       
   209   succ = vf2pp(g,h).induced().run();
       
   210   succ = vf2pp(g,h).iso().run();
       
   211   succ = vf2pp(g,h).mapping(r).run();
       
   212   succ = vf2pp(g,h).induced().mapping(r).run();
       
   213   succ = vf2pp(g,h).iso().mapping(r).run();
       
   214 
       
   215 
       
   216   concepts::ReadMap<typename G1::Node, int> c1;
       
   217   concepts::ReadMap<typename G2::Node, int> c2;
       
   218   Vf2pp<G1,G2,concepts::ReadWriteMap<typename G1::Node, typename G2::Node>,
       
   219         concepts::ReadMap<typename G1::Node, int>,
       
   220         concepts::ReadMap<typename G2::Node, int> >
       
   221     myVf2pp(g,h,r,c1,c2);
       
   222   myVf2pp.find();
       
   223 
       
   224   succ = vf2pp(g,h).nodeLabels(c1,c2).mapping(r).run();
       
   225   succ = vf2pp(g,h).nodeLabels(c1,c2)
       
   226     .mapping(r).run();
       
   227 
       
   228 
       
   229   concepts::ReadMap<typename G1::Node, char> c1_c;
       
   230   concepts::ReadMap<typename G2::Node, char> c2_c;
       
   231   Vf2pp<G1,G2,concepts::ReadWriteMap<typename G1::Node, typename G2::Node>,
       
   232         concepts::ReadMap<typename G1::Node, char>,
       
   233         concepts::ReadMap<typename G2::Node, char> >
       
   234     myVf2pp_c(g,h,r,c1_c,c2_c);
       
   235   myVf2pp_c.find();
       
   236 
       
   237   succ = vf2pp(g,h).nodeLabels(c1_c,c2_c).mapping(r).run();
       
   238   succ = vf2pp(g,h).nodeLabels(c1_c,c2_c)
       
   239     .mapping(r).run();
       
   240 
       
   241 
       
   242   concepts::ReadMap<typename G1::Node, IntConvertible1> c1_IntConv;
       
   243   concepts::ReadMap<typename G2::Node, IntConvertible2> c2_IntConv;
       
   244   Vf2pp<G1,G2,concepts::ReadWriteMap<typename G1::Node, typename G2::Node>,
       
   245         concepts::ReadMap<typename G1::Node, IntConvertible1>,
       
   246         concepts::ReadMap<typename G2::Node, IntConvertible2> >
       
   247     myVf2pp_IntConv(g,h,r,c1_IntConv,c2_IntConv);
       
   248   myVf2pp_IntConv.find();
       
   249 
       
   250   succ = vf2pp(g,h).nodeLabels(c1_IntConv,c2_IntConv).mapping(r).run();
       
   251   succ = vf2pp(g,h).nodeLabels(c1_IntConv,c2_IntConv)
       
   252     .mapping(r).run();
       
   253 }
       
   254 
       
   255 void justCompile() {
       
   256   checkVf2Compile<concepts::Graph,concepts::Graph>();
       
   257   checkVf2Compile<concepts::Graph,SmartGraph>();
       
   258   checkVf2Compile<SmartGraph,concepts::Graph>();
       
   259 }
       
   260 
       
   261 template<class G1, class G2, class I>
       
   262 void checkSub(const G1 &g1, const G2 &g2, const I &i) {
       
   263   {
       
   264     std::set<typename G2::Node> image;
       
   265     for(typename G1::NodeIt n(g1);n!=INVALID;++n){
       
   266       check(i[n]!=INVALID, "Wrong isomorphism: incomplete mapping.");
       
   267       check(image.count(i[n])==0,"Wrong isomorphism: not injective.");
       
   268       image.insert(i[n]);
       
   269     }
       
   270   }
       
   271   for(typename G1::EdgeIt e(g1);e!=INVALID;++e)
       
   272     check(findEdge(g2,i[g1.u(e)],i[g1.v(e)])!=INVALID,
       
   273           "Wrong isomorphism: missing edge(checkSub).");
       
   274 }
       
   275 
       
   276 template<class G1, class G2, class I>
       
   277 void checkInd(const G1 &g1, const G2 &g2, const I &i) {
       
   278   std::set<typename G2::Node> image;
       
   279   for(typename G1::NodeIt n(g1);n!=INVALID;++n) {
       
   280     check(i[n]!=INVALID, "Wrong isomorphism: incomplete mapping.");
       
   281     check(image.count(i[n])==0,"Wrong isomorphism: not injective.");
       
   282     image.insert(i[n]);
       
   283   }
       
   284   for(typename G1::NodeIt n(g1); n!=INVALID; ++n)
       
   285     for(typename G1::NodeIt m(g1); m!=INVALID; ++m)
       
   286       if((findEdge(g1,n,m)==INVALID) != (findEdge(g2,i[n],i[m])==INVALID)) {
       
   287         std::cout << "Wrong isomorphism: edge mismatch";
       
   288         exit(1);
       
   289       }
       
   290 }
       
   291 
       
   292 template<class G1,class G2>
       
   293 int checkSub(const G1 &g1, const G2 &g2) {
       
   294   typename G1:: template NodeMap<typename G2::Node> iso(g1,INVALID);
       
   295   if(vf2pp(g1,g2).mapping(iso).run()){
       
   296     checkSub(g1,g2,iso);
       
   297     return true;
       
   298   }
       
   299   else
       
   300     return false;
       
   301 }
       
   302 
       
   303 template<class G1,class G2>
       
   304 int checkInd(const G1 &g1, const G2 &g2) {
       
   305   typename G1:: template NodeMap<typename G2::Node> iso(g1,INVALID);
       
   306   if(vf2pp(g1,g2).induced().mapping(iso).run()) {
       
   307     checkInd(g1,g2,iso);
       
   308     return true;
       
   309   }
       
   310   else
       
   311     return false;
       
   312 }
       
   313 
       
   314 template<class G1,class G2>
       
   315 int checkIso(const G1 &g1, const G2 &g2) {
       
   316   typename G1:: template NodeMap<typename G2::Node> iso(g1,INVALID);
       
   317   if(vf2pp(g1,g2).iso().mapping(iso).run()) {
       
   318     check(countNodes(g1)==countNodes(g2),
       
   319           "Wrong iso alg.: they are not isomophic.");
       
   320     checkInd(g1,g2,iso);
       
   321     return true;
       
   322   }
       
   323   else
       
   324     return false;
       
   325 }
       
   326 
       
   327 template<class G1, class G2, class L1, class L2, class I>
       
   328 void checkLabel(const G1 &g1, const G2 &,
       
   329                 const L1 &l1, const L2 &l2,const I &i) {
       
   330   for(typename G1::NodeIt n(g1);n!=INVALID;++n)
       
   331     check(l1[n]==l2[i[n]],"Wrong isomorphism: label mismatch.");
       
   332 }
       
   333 
       
   334 template<class G1,class G2,class L1,class L2>
       
   335 int checkSub(const G1 &g1, const G2 &g2, const L1 &l1, const L2 &l2) {
       
   336   typename G1:: template NodeMap<typename G2::Node> iso(g1,INVALID);
       
   337   if(vf2pp(g1,g2).nodeLabels(l1,l2).mapping(iso).run()) {
       
   338     checkSub(g1,g2,iso);
       
   339     checkLabel(g1,g2,l1,l2,iso);
       
   340     return true;
       
   341   }
       
   342   else
       
   343     return false;
       
   344 }
       
   345 
       
   346 int main() {
       
   347   make_graphs();
       
   348 //   justCompile();
       
   349   check(checkSub(c5,petersen), "There should exist a C5->Petersen mapping.");
       
   350   check(!checkSub(c7,petersen),
       
   351         "There should not exist a C7->Petersen mapping.");
       
   352   check(checkSub(p10,petersen), "There should exist a P10->Petersen mapping.");
       
   353   check(!checkSub(c10,petersen),
       
   354         "There should not exist a C10->Petersen mapping.");
       
   355   check(checkSub(petersen,petersen),
       
   356         "There should exist a Petersen->Petersen mapping.");
       
   357 
       
   358   check(checkInd(c5,petersen),
       
   359         "There should exist a C5->Petersen spanned mapping.");
       
   360   check(!checkInd(c7,petersen),
       
   361         "There should exist a C7->Petersen spanned mapping.");
       
   362   check(!checkInd(p10,petersen),
       
   363         "There should not exist a P10->Petersen spanned mapping.");
       
   364   check(!checkInd(c10,petersen),
       
   365         "There should not exist a C10->Petersen spanned mapping.");
       
   366   check(checkInd(petersen,petersen),
       
   367         "There should exist a Petersen->Petersen spanned mapping.");
       
   368 
       
   369   check(!checkSub(petersen,c10),
       
   370         "There should not exist a Petersen->C10 mapping.");
       
   371   check(checkSub(p10,c10),
       
   372         "There should exist a P10->C10 mapping.");
       
   373   check(!checkInd(p10,c10),
       
   374         "There should not exist a P10->C10 spanned mapping.");
       
   375   check(!checkSub(c10,p10),
       
   376         "There should not exist a C10->P10 mapping.");
       
   377 
       
   378   check(!checkIso(p10,c10),
       
   379         "P10 and C10 are not isomorphic.");
       
   380   check(checkIso(c10,c10),
       
   381         "C10 and C10 are isomorphic.");
       
   382 
       
   383   check(!vf2pp(p10,c10).iso().run(),
       
   384         "P10 and C10 are not isomorphic.");
       
   385   check(vf2pp(c10,c10).iso().run(),
       
   386         "C10 and C10 are isomorphic.");
       
   387 
       
   388   check(!checkSub(c5,petersen,c5_col,petersen_col1),
       
   389         "There should exist a C5->Petersen mapping.");
       
   390   check(checkSub(c5,petersen,c5_col,petersen_col2),
       
   391         "There should exist a C5->Petersen mapping.");
       
   392 }