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 Alpar Juttner <alpar@cs.elte.hu>
Fri, 23 Mar 2018 15:43:30 +0100
changeset 1389 57167d92e96c
parent 1350 a037254714b3
child 1405 3feba0ea1bda
permissions -rw-r--r--
Merge #602 
     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

     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/concepts/digraph.h>

    20 #include <lemon/smart_graph.h>

    21 #include <lemon/lgf_reader.h>

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

    23 

    24 #include <test/test_tools.h>

    25 #include <sstream>

    26 

    27 using namespace lemon;

    28 

    29 char petersen_lgf[] =

    30   "@nodes\n"

    31   "label col1 col2\n"

    32   "0 1 1\n"

    33   "1 1 2\n"

    34   "2 1 3\n"

    35   "3 1 4\n"

    36   "4 2 5\n"

    37   "5 2 1\n"

    38   "6 2 2\n"

    39   "7 2 3\n"

    40   "8 2 4\n"

    41   "9 2 5\n"

    42   "@arcs\n"

    43   "     -\n"

    44   "0 1\n"

    45   "1 2\n"

    46   "2 3\n"

    47   "3 4\n"

    48   "4 0\n"

    49   "0 5\n"

    50   "1 6\n"

    51   "2 7\n"

    52   "3 8\n"

    53   "4 9\n"

    54   "5 8\n"

    55   "5 7\n"

    56   "9 6\n"

    57   "9 7\n"

    58   "6 8\n";

    59 

    60 char c5_lgf[] =

    61   "@nodes\n"

    62   "label col\n"

    63   "0 1\n"

    64   "1 2\n"

    65   "2 3\n"

    66   "3 4\n"

    67   "4 5\n"

    68   "@arcs\n"

    69   "     -\n"

    70   "0 1\n"

    71   "1 2\n"

    72   "2 3\n"

    73   "3 4\n"

    74   "4 0\n";

    75 

    76 char c7_lgf[] =

    77   "@nodes\n"

    78   "label\n"

    79   "0\n"

    80   "1\n"

    81   "2\n"

    82   "3\n"

    83   "4\n"

    84   "5\n"

    85   "6\n"

    86   "@arcs\n"

    87   "     -\n"

    88   "0 1\n"

    89   "1 2\n"

    90   "2 3\n"

    91   "3 4\n"

    92   "4 5\n"

    93   "5 6\n"

    94   "6 0\n";

    95 

    96 char c10_lgf[] =

    97   "@nodes\n"

    98   "label\n"

    99   "0\n"

   100   "1\n"

   101   "2\n"

   102   "3\n"

   103   "4\n"

   104   "5\n"

   105   "6\n"

   106   "7\n"

   107   "8\n"

   108   "9\n"

   109   "@arcs\n"

   110   "     -\n"

   111   "0 1\n"

   112   "1 2\n"

   113   "2 3\n"

   114   "3 4\n"

   115   "4 5\n"

   116   "5 6\n"

   117   "6 7\n"

   118   "7 8\n"

   119   "8 9\n"

   120   "9 0\n";

   121 

   122 char p10_lgf[] =

   123   "@nodes\n"

   124   "label\n"

   125   "0\n"

   126   "1\n"

   127   "2\n"

   128   "3\n"

   129   "4\n"

   130   "5\n"

   131   "6\n"

   132   "7\n"

   133   "8\n"

   134   "9\n"

   135   "@arcs\n"

   136   "     -\n"

   137   "0 1\n"

   138   "1 2\n"

   139   "2 3\n"

   140   "3 4\n"

   141   "4 5\n"

   142   "5 6\n"

   143   "6 7\n"

   144   "7 8\n"

   145   "8 9\n";

   146 

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

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

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

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

   151 

   152 void make_graphs() {

   153   std::stringstream ss(petersen_lgf);

   154   graphReader(petersen, ss)

   155     .nodeMap("col1",petersen_col1)

   156     .nodeMap("col2",petersen_col2)

   157     .run();

   158 

   159   ss.clear();

   160   ss.str("");

   161   ss<<c5_lgf;

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

   163   graphReader(c5, ss)

   164     .nodeMap("col",c5_col)

   165     .run();

   166 

   167   ss.clear();

   168   ss.str("");

   169   ss<<c7_lgf;

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

   171 

   172   ss.clear();

   173   ss.str("");

   174   ss<<c10_lgf;

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

   176 

   177   ss.clear();

   178   ss.str("");

   179   ss<<p10_lgf;

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

   181 

   182 }

   183 

   184 class EqComparable {

   185 public:

   186   bool operator==(const EqComparable&) { return false; }

   187 };

   188 

   189 template<class A, class B>

   190 class EqClass {

   191 public:

   192   bool operator()(A, B) { return false; }

   193 };

   194 

   195 template<class G1,class G2>

   196 void checkVf2Compile()

   197 {

   198   G1 g;

   199   G2 h;

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

   201   bool succ;

   202   ::lemon::ignore_unused_variable_warning(succ);

   203 

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

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

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

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

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

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

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

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

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

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

   214     .mapping(r).run();

   215 }

   216 

   217 void justCompile()

   218 {

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

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

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

   222 }

   223 

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

   225 void checkSub(const G1 &g1, const G2 &g2, const I &i)

   226 {

   227   {

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

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

   230       {

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

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

   233           image.insert(i[n]);

   234       }

   235   }

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

   237     check(findEdge(g2,i[g1.u(e)],i[g1.v(e)])!=INVALID,

   238           "Wrong isomorphism: missing edge(checkSub).");

   239 }

   240 

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

   242 void checkInd(const G1 &g1, const G2 &g2, const I &i)

   243   {

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

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

   246     {

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

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

   249     image.insert(i[n]);

   250     }

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

   252     for(typename G1::NodeIt m(g1); m!=INVALID; ++m)

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

   254         {

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

   256         exit(1);

   257         }

   258   }

   259 

   260 template<class G1,class G2>

   261 int checkSub(const G1 &g1, const G2 &g2)

   262 {

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

   264   if(vf2(g1,g2).mapping(iso).run())

   265     {

   266       checkSub(g1,g2,iso);

   267       return true;

   268     }

   269   else return false;

   270 }

   271 

   272 template<class G1,class G2>

   273 int checkInd(const G1 &g1, const G2 &g2)

   274 {

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

   276   if(vf2(g1,g2).induced().mapping(iso).run())

   277     {

   278       checkInd(g1,g2,iso);

   279       return true;

   280     }

   281   else return false;

   282 }

   283 

   284 template<class G1,class G2>

   285 int checkIso(const G1 &g1, const G2 &g2)

   286 {

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

   288   if(vf2(g1,g2).iso().mapping(iso).run())

   289     {

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

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

   292       checkInd(g1,g2,iso);

   293       return true;

   294     }

   295   else return false;

   296 }

   297 

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

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

   300                 const L1 &l1, const L2 &l2,const I &i)

   301 {

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

   303     {

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

   305     }

   306 }

   307 

   308 template<class G1,class G2,class L1,class L2>

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

   312   if(vf2(g1,g2).nodeLabels(l1,l2).mapping(iso).run())

   313     {

   314       checkSub(g1,g2,iso);

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

   316       return true;

   317     }

   318   else return false;

   319 }

   320 

   321 int main() {

   322   make_graphs();

   323   check(checkSub(c5,petersen), "There should exist a C5->Petersen mapping.");

   324   check(!checkSub(c7,petersen),

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

   326   check(checkSub(p10,petersen), "There should exist a P10->Petersen mapping.");

   327   check(!checkSub(c10,petersen),

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

   329   check(checkSub(petersen,petersen),

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

   331 

   332   check(checkInd(c5,petersen),

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

   334   check(!checkInd(c7,petersen),

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

   336   check(!checkInd(p10,petersen),

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

   338   check(!checkInd(c10,petersen),

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

   340   check(checkInd(petersen,petersen),

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

   342 

   343   check(!checkSub(petersen,c10),

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

   345   check(checkSub(p10,c10),

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

   347   check(!checkInd(p10,c10),

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

   349   check(!checkSub(c10,p10),

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

   351 

   352   check(!checkIso(p10,c10),

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

   354   check(checkIso(c10,c10),

   355         "C10 and C10 are isomorphic.");

   356 

   357   check(!vf2(p10,c10).iso().run(),

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

   359   check(vf2(c10,c10).iso().run(),

   360         "C10 and C10 are isomorphic.");

   361 

   362   check(!checkSub(c5,petersen,c5_col,petersen_col1),

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

   364   check(checkSub(c5,petersen,c5_col,petersen_col2),

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

   366 }
lemon