COIN-OR::LEMON - Graph Library

Changeset 1405:3feba0ea1bda in lemon for test/vf2_test.cc


Ignore:
Timestamp:
09/19/17 14:08:20 (2 years ago)
Author:
Peter Madarasi <madarasip@…>
Branch:
default
Phase:
public
Message:

Vf2 improvements and Vf2pp implementation (#597)

File:
1 edited

Legend:

Unmodified
Added
Removed
  • test/vf2_test.cc

    r1352 r1405  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2015
     5 * Copyright (C) 2015-2017
    66 * EMAXA Kutato-fejleszto Kft. (EMAXA Research Ltd.)
    77 *
     
    184184class EqComparable {
    185185public:
    186   bool operator==(const EqComparable&) { return false; }
     186  bool operator==(const EqComparable&) {
     187    return false;
     188  }
    187189};
    188190
     
    190192class EqClass {
    191193public:
    192   bool operator()(A, B) { return false; }
     194  bool operator()(A, B){
     195    return false;
     196  }
    193197};
    194198
    195199template<class G1,class G2>
    196 void checkVf2Compile()
    197 {
     200void checkVf2Compile() {
    198201  G1 g;
    199202  G2 h;
     
    206209  succ = vf2(g,h).iso().run();
    207210  succ = vf2(g,h).mapping(r).run();
     211
     212  Vf2<G1,G2,concepts::ReadWriteMap<typename G1::Node, typename G2::Node>,
     213      EqClass<typename G1::Node,typename G2::Node> >
     214    myVf2(g,h,r,EqClass<typename G1::Node,typename G2::Node>());
     215  myVf2.find();
     216
    208217  succ = vf2(g,h).induced().mapping(r).run();
    209218  succ = vf2(g,h).iso().mapping(r).run();
     219
    210220  concepts::ReadMap<typename G1::Node, EqComparable> l1;
    211221  concepts::ReadMap<typename G2::Node, EqComparable> l2;
     
    215225}
    216226
    217 void justCompile()
    218 {
     227void justCompile() {
    219228  checkVf2Compile<concepts::Graph,concepts::Graph>();
    220229  checkVf2Compile<concepts::Graph,SmartGraph>();
     
    223232
    224233template<class G1, class G2, class I>
    225 void checkSub(const G1 &g1, const G2 &g2, const I &i)
    226 {
     234void checkSub(const G1 &g1, const G2 &g2, const I &i) {
    227235  {
    228236    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       }
     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    }
    235242  }
    236243  for(typename G1::EdgeIt e(g1);e!=INVALID;++e)
     
    240247
    241248template<class G1, class G2, class I>
    242 void checkInd(const G1 &g1, const G2 &g2, const I &i)
    243   {
     249void checkInd(const G1 &g1, const G2 &g2, const I &i) {
    244250  std::set<typename G2::Node> image;
    245   for(typename G1::NodeIt n(g1);n!=INVALID;++n)
    246     {
     251  for(typename G1::NodeIt n(g1);n!=INVALID;++n) {
    247252    check(i[n]!=INVALID, "Wrong isomorphism: incomplete mapping.");
    248253    check(image.count(i[n])==0,"Wrong isomorphism: not injective.");
    249254    image.insert(i[n]);
    250     }
     255  }
    251256  for(typename G1::NodeIt n(g1); n!=INVALID; ++n)
    252257    for(typename G1::NodeIt m(g1); m!=INVALID; ++m)
    253       if((findEdge(g1,n,m)==INVALID) != (findEdge(g2,i[n],i[m])==INVALID))
    254         {
     258      if((findEdge(g1,n,m)==INVALID) != (findEdge(g2,i[n],i[m])==INVALID)) {
    255259        std::cout << "Wrong isomorphism: edge mismatch";
    256260        exit(1);
    257         }
    258   }
     261      }
     262}
    259263
    260264template<class G1,class G2>
    261 int checkSub(const G1 &g1, const G2 &g2)
    262 {
     265int checkSub(const G1 &g1, const G2 &g2) {
    263266  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;
     267  if(vf2(g1,g2).mapping(iso).run()) {
     268    checkSub(g1,g2,iso);
     269    return true;
     270  }
     271  else
     272    return false;
    270273}
    271274
    272275template<class G1,class G2>
    273 int checkInd(const G1 &g1, const G2 &g2)
    274 {
     276int checkInd(const G1 &g1, const G2 &g2) {
    275277  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;
     278  if(vf2(g1,g2).induced().mapping(iso).run()) {
     279    checkInd(g1,g2,iso);
     280    return true;
     281  }
     282  else
     283    return false;
    282284}
    283285
    284286template<class G1,class G2>
    285 int checkIso(const G1 &g1, const G2 &g2)
    286 {
     287int checkIso(const G1 &g1, const G2 &g2) {
    287288  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;
     289  if(vf2(g1,g2).iso().mapping(iso).run()) {
     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
     296    return false;
    296297}
    297298
    298299template<class G1, class G2, class L1, class L2, class I>
    299300void checkLabel(const G1 &g1, const G2 &,
    300                 const L1 &l1, const L2 &l2,const I &i)
    301 {
     301                const L1 &l1, const L2 &l2,const I &i) {
    302302  for(typename G1::NodeIt n(g1);n!=INVALID;++n)
    303     {
    304       check(l1[n]==l2[i[n]],"Wrong isomorphism: label mismatch.");
    305     }
     303    check(l1[n]==l2[i[n]],"Wrong isomorphism: label mismatch.");
    306304}
    307305
    308306template<class G1,class G2,class L1,class L2>
    309 int checkSub(const G1 &g1, const G2 &g2, const L1 &l1, const L2 &l2)
    310 {
     307int checkSub(const G1 &g1, const G2 &g2, const L1 &l1, const L2 &l2) {
    311308  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;
     309  if(vf2(g1,g2).nodeLabels(l1,l2).mapping(iso).run()){
     310    checkSub(g1,g2,iso);
     311    checkLabel(g1,g2,l1,l2,iso);
     312    return true;
     313  }
     314  else
     315    return false;
    319316}
    320317
    321318int main() {
    322319  make_graphs();
     320  //   justCompile();
    323321  check(checkSub(c5,petersen), "There should exist a C5->Petersen mapping.");
    324322  check(!checkSub(c7,petersen),
Note: See TracChangeset for help on using the changeset viewer.