test/vf2pp_test.cc
author Peter Madarasi <madarasip@caesar.elte.hu>
Tue, 19 Sep 2017 14:08:20 +0200
changeset 1186 3feba0ea1bda
permissions -rw-r--r--
Vf2 improvements and Vf2pp implementation (#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/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 }