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