COIN-OR::LEMON - Graph Library

Changeset 1187:120b9031eada in lemon-main


Ignore:
Timestamp:
10/07/17 00:14:05 (7 years ago)
Author:
Peter Kovacs <kpeter@…>
Branch:
default
Phase:
public
Message:

Merge tests of VF2 and VF2++ (#597)

Location:
test
Files:
1 deleted
2 edited

Legend:

Unmodified
Added
Removed
  • test/CMakeLists.txt

    r1186 r1187  
    5656  unionfind_test
    5757  vf2_test
    58   vf2pp_test
    5958)
    6059
  • test/vf2_test.cc

    r1186 r1187  
    1717
    1818#include <lemon/vf2.h>
     19#include <lemon/vf2pp.h>
    1920#include <lemon/concepts/digraph.h>
    2021#include <lemon/smart_graph.h>
     
    153154  std::stringstream ss(petersen_lgf);
    154155  graphReader(petersen, ss)
    155     .nodeMap("col1",petersen_col1)
    156     .nodeMap("col2",petersen_col2)
     156    .nodeMap("col1", petersen_col1)
     157    .nodeMap("col2", petersen_col2)
    157158    .run();
    158159
    159160  ss.clear();
    160161  ss.str("");
    161   ss<<c5_lgf;
     162  ss << c5_lgf;
    162163  //std::stringstream ss2(c5_lgf);
    163164  graphReader(c5, ss)
    164     .nodeMap("col",c5_col)
     165    .nodeMap("col", c5_col)
    165166    .run();
    166167
    167168  ss.clear();
    168169  ss.str("");
    169   ss<<c7_lgf;
     170  ss << c7_lgf;
    170171  graphReader(c7, ss).run();
    171172
    172173  ss.clear();
    173174  ss.str("");
    174   ss<<c10_lgf;
     175  ss << c10_lgf;
    175176  graphReader(c10, ss).run();
    176177
    177178  ss.clear();
    178179  ss.str("");
    179   ss<<p10_lgf;
     180  ss << p10_lgf;
    180181  graphReader(p10, ss).run();
    181182
     
    194195  bool operator()(A, B){
    195196    return false;
     197  }
     198};
     199
     200class IntConvertible1 {
     201public:
     202  operator int() {
     203    return 0;
     204  }
     205};
     206
     207class IntConvertible2 {
     208public:
     209  operator int() {
     210    return 0;
    196211  }
    197212};
     
    225240}
    226241
    227 void justCompile() {
     242void vf2Compile() {
    228243  checkVf2Compile<concepts::Graph,concepts::Graph>();
    229244  checkVf2Compile<concepts::Graph,SmartGraph>();
     
    231246}
    232247
     248template<class G1,class G2>
     249void 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
     297void vf2ppCompile() {
     298  checkVf2ppCompile<concepts::Graph,concepts::Graph>();
     299  checkVf2ppCompile<concepts::Graph,SmartGraph>();
     300  checkVf2ppCompile<SmartGraph,concepts::Graph>();
     301}
     302
    233303template<class G1, class G2, class I>
    234 void checkSub(const G1 &g1, const G2 &g2, const I &i) {
    235   {
    236     std::set<typename G2::Node> image;
    237     for(typename G1::NodeIt n(g1);n!=INVALID;++n){
    238       check(i[n]!=INVALID, "Wrong isomorphism: incomplete mapping.");
    239       check(image.count(i[n])==0,"Wrong isomorphism: not injective.");
    240       image.insert(i[n]);
    241     }
    242   }
    243   for(typename G1::EdgeIt e(g1);e!=INVALID;++e)
    244     check(findEdge(g2,i[g1.u(e)],i[g1.v(e)])!=INVALID,
    245           "Wrong isomorphism: missing edge(checkSub).");
    246 }
    247 
    248 template<class G1, class G2, class I>
    249 void checkInd(const G1 &g1, const G2 &g2, const I &i) {
     304void checkSubIso(const G1 &g1, const G2 &g2, const I &i) {
    250305  std::set<typename G2::Node> image;
    251   for(typename G1::NodeIt n(g1);n!=INVALID;++n) {
     306  for (typename G1::NodeIt n(g1);n!=INVALID;++n){
    252307    check(i[n]!=INVALID, "Wrong isomorphism: incomplete mapping.");
    253308    check(image.count(i[n])==0,"Wrong isomorphism: not injective.");
    254309    image.insert(i[n]);
    255310  }
    256   for(typename G1::NodeIt n(g1); n!=INVALID; ++n)
    257     for(typename G1::NodeIt m(g1); m!=INVALID; ++m)
     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
     317template<class G1, class G2, class I>
     318void 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) {
    258327      if((findEdge(g1,n,m)==INVALID) != (findEdge(g2,i[n],i[m])==INVALID)) {
    259328        std::cout << "Wrong isomorphism: edge mismatch";
    260329        exit(1);
    261330      }
    262 }
    263 
    264 template<class G1,class G2>
    265 int checkSub(const G1 &g1, const G2 &g2) {
     331    }
     332  }
     333}
     334
     335template<class G1,class G2,class T>
     336bool checkSub(const G1 &g1, const G2 &g2, const T &vf2) {
    266337  typename G1:: template NodeMap<typename G2::Node> iso(g1,INVALID);
    267   if(vf2(g1,g2).mapping(iso).run()) {
    268     checkSub(g1,g2,iso);
     338  if (const_cast<T&>(vf2).mapping(iso).run()) {
     339    checkSubIso(g1,g2,iso);
    269340    return true;
    270341  }
    271   else
    272     return false;
    273 }
    274 
    275 template<class G1,class G2>
    276 int checkInd(const G1 &g1, const G2 &g2) {
     342  return false;
     343}
     344
     345template<class G1,class G2,class T>
     346bool checkInd(const G1 &g1, const G2 &g2, const T &vf2) {
    277347  typename G1:: template NodeMap<typename G2::Node> iso(g1,INVALID);
    278   if(vf2(g1,g2).induced().mapping(iso).run()) {
    279     checkInd(g1,g2,iso);
     348  if (const_cast<T&>(vf2).induced().mapping(iso).run()) {
     349    checkIndIso(g1,g2,iso);
    280350    return true;
    281351  }
    282   else
    283     return false;
    284 }
    285 
    286 template<class G1,class G2>
    287 int checkIso(const G1 &g1, const G2 &g2) {
     352  return false;
     353}
     354
     355template<class G1,class G2,class T>
     356bool checkIso(const G1 &g1, const G2 &g2, const T &vf2) {
    288357  typename G1:: template NodeMap<typename G2::Node> iso(g1,INVALID);
    289   if(vf2(g1,g2).iso().mapping(iso).run()) {
     358  if (const_cast<T&>(vf2).iso().mapping(iso).run()) {
    290359    check(countNodes(g1)==countNodes(g2),
    291360          "Wrong iso alg.: they are not isomophic.");
    292     checkInd(g1,g2,iso);
     361    checkIndIso(g1,g2,iso);
    293362    return true;
    294363  }
    295   else
    296     return false;
     364  return false;
    297365}
    298366
    299367template<class G1, class G2, class L1, class L2, class I>
    300368void checkLabel(const G1 &g1, const G2 &,
    301                 const L1 &l1, const L2 &l2,const I &i) {
    302   for(typename G1::NodeIt n(g1);n!=INVALID;++n)
     369                const L1 &l1, const L2 &l2, const I &i) {
     370  for (typename G1::NodeIt n(g1);n!=INVALID;++n) {
    303371    check(l1[n]==l2[i[n]],"Wrong isomorphism: label mismatch.");
    304 }
    305 
    306 template<class G1,class G2,class L1,class L2>
    307 int checkSub(const G1 &g1, const G2 &g2, const L1 &l1, const L2 &l2) {
     372  }
     373}
     374
     375template<class G1,class G2,class L1,class L2,class T>
     376bool checkSub(const G1 &g1, const G2 &g2, const L1 &l1, const L2 &l2, const T &vf2) {
    308377  typename G1:: template NodeMap<typename G2::Node> iso(g1,INVALID);
    309   if(vf2(g1,g2).nodeLabels(l1,l2).mapping(iso).run()){
    310     checkSub(g1,g2,iso);
     378  if (const_cast<T&>(vf2).nodeLabels(l1,l2).mapping(iso).run()){
     379    checkSubIso(g1,g2,iso);
    311380    checkLabel(g1,g2,l1,l2,iso);
    312381    return true;
    313382  }
    314   else
    315     return false;
     383  return false;
     384}
     385
     386template<class G1,class G2>
     387void 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
     392template<class G1,class G2>
     393void 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
     398template<class G1,class G2>
     399void 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
     404template<class G1,class G2,class L1,class L2>
     405void 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);
    316408}
    317409
    318410int main() {
    319411  make_graphs();
    320   //   justCompile();
    321   check(checkSub(c5,petersen), "There should exist a C5->Petersen mapping.");
    322   check(!checkSub(c7,petersen),
    323         "There should not exist a C7->Petersen mapping.");
    324   check(checkSub(p10,petersen), "There should exist a P10->Petersen mapping.");
    325   check(!checkSub(c10,petersen),
    326         "There should not exist a C10->Petersen mapping.");
    327   check(checkSub(petersen,petersen),
    328         "There should exist a Petersen->Petersen mapping.");
    329 
    330   check(checkInd(c5,petersen),
    331         "There should exist a C5->Petersen spanned mapping.");
    332   check(!checkInd(c7,petersen),
    333         "There should exist a C7->Petersen spanned mapping.");
    334   check(!checkInd(p10,petersen),
    335         "There should not exist a P10->Petersen spanned mapping.");
    336   check(!checkInd(c10,petersen),
    337         "There should not exist a C10->Petersen spanned mapping.");
    338   check(checkInd(petersen,petersen),
     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,
    339433        "There should exist a Petersen->Petersen spanned mapping.");
    340434
    341   check(!checkSub(petersen,c10),
    342         "There should not exist a Petersen->C10 mapping.");
    343   check(checkSub(p10,c10),
    344         "There should exist a P10->C10 mapping.");
    345   check(!checkInd(p10,c10),
    346         "There should not exist a P10->C10 spanned mapping.");
    347   check(!checkSub(c10,p10),
    348         "There should not exist a C10->P10 mapping.");
    349 
    350   check(!checkIso(p10,c10),
    351         "P10 and C10 are not isomorphic.");
    352   check(checkIso(c10,c10),
    353         "C10 and C10 are isomorphic.");
    354 
    355   check(!vf2(p10,c10).iso().run(),
    356         "P10 and C10 are not isomorphic.");
    357   check(vf2(c10,c10).iso().run(),
    358         "C10 and C10 are isomorphic.");
    359 
    360   check(!checkSub(c5,petersen,c5_col,petersen_col1),
    361         "There should exist a C5->Petersen mapping.");
    362   check(checkSub(c5,petersen,c5_col,petersen_col2),
    363         "There should exist a C5->Petersen mapping.");
    364 }
     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}
Note: See TracChangeset for help on using the changeset viewer.