Changeset 1405:3feba0ea1bda in lemon for test

Timestamp:

09/19/17 14:08:20 (7 years ago)

Author:

Peter Madarasi <madarasip@…>

Branch:

default

Phase:

public

Message:

Vf2 improvements and Vf2pp implementation (#597)

Location:

test

Files:

• CMakeLists.txt (modified) (1 diff)
• vf2_test.cc (modified) (7 diffs)
• vf2pp_test.cc (added)

test/CMakeLists.txt

@@ -56 +56 @@
   unionfind_test
   vf2_test
+  vf2pp_test
 )
 

test/vf2_test.cc

@@ -3 +3 @@
  * This file is a part of LEMON, a generic C++ optimization library.
  *
- * Copyright (C) 2015
+ * Copyright (C) 2015-2017
  * EMAXA Kutato-fejleszto Kft. (EMAXA Research Ltd.)
  *
@@ -184 +184 @@
 class EqComparable {
 public:
-  bool operator==(const EqComparable&) { return false; }
+  bool operator==(const EqComparable&) {
+    return false;
+  }
 };
 
@@ -190 +192 @@
 class EqClass {
 public:
-  bool operator()(A, B) { return false; }
+  bool operator()(A, B){
+    return false;
+  }
 };
 
 template<class G1,class G2>
-void checkVf2Compile()
-{
+void checkVf2Compile() {
   G1 g;
   G2 h;
@@ -206 +209 @@
   succ = vf2(g,h).iso().run();
   succ = vf2(g,h).mapping(r).run();
+
+  Vf2<G1,G2,concepts::ReadWriteMap<typename G1::Node, typename G2::Node>,
+      EqClass<typename G1::Node,typename G2::Node> >
+    myVf2(g,h,r,EqClass<typename G1::Node,typename G2::Node>());
+  myVf2.find();
+
   succ = vf2(g,h).induced().mapping(r).run();
   succ = vf2(g,h).iso().mapping(r).run();
+
   concepts::ReadMap<typename G1::Node, EqComparable> l1;
   concepts::ReadMap<typename G2::Node, EqComparable> l2;
@@ -215 +225 @@
 }
 
-void justCompile()
-{
+void justCompile() {
   checkVf2Compile<concepts::Graph,concepts::Graph>();
   checkVf2Compile<concepts::Graph,SmartGraph>();
@@ -223 +232 @@
 
 template<class G1, class G2, class I>
-void checkSub(const G1 &g1, const G2 &g2, const I &i)
-{
+void checkSub(const G1 &g1, const G2 &g2, const I &i) {
   {
     std::set<typename G2::Node> image;
-    for(typename G1::NodeIt n(g1);n!=INVALID;++n)
-      {
-          check(i[n]!=INVALID, "Wrong isomorphism: incomplete mapping.");
-          check(image.count(i[n])==0,"Wrong isomorphism: not injective.");
-          image.insert(i[n]);
-      }
+    for(typename G1::NodeIt n(g1);n!=INVALID;++n){
+      check(i[n]!=INVALID, "Wrong isomorphism: incomplete mapping.");
+      check(image.count(i[n])==0,"Wrong isomorphism: not injective.");
+      image.insert(i[n]);
+    }
   }
   for(typename G1::EdgeIt e(g1);e!=INVALID;++e)
@@ -240 +247 @@
 
 template<class G1, class G2, class I>
-void checkInd(const G1 &g1, const G2 &g2, const I &i)
-  {
+void checkInd(const G1 &g1, const G2 &g2, const I &i) {
   std::set<typename G2::Node> image;
-  for(typename G1::NodeIt n(g1);n!=INVALID;++n)
-    {
+  for(typename G1::NodeIt n(g1);n!=INVALID;++n) {
     check(i[n]!=INVALID, "Wrong isomorphism: incomplete mapping.");
     check(image.count(i[n])==0,"Wrong isomorphism: not injective.");
     image.insert(i[n]);
-    }
+  }
   for(typename G1::NodeIt n(g1); n!=INVALID; ++n)
     for(typename G1::NodeIt m(g1); m!=INVALID; ++m)
-      if((findEdge(g1,n,m)==INVALID) != (findEdge(g2,i[n],i[m])==INVALID))
-        {
+      if((findEdge(g1,n,m)==INVALID) != (findEdge(g2,i[n],i[m])==INVALID)) {
         std::cout << "Wrong isomorphism: edge mismatch";
         exit(1);
-        }
-  }
+      }
+}
 
 template<class G1,class G2>
-int checkSub(const G1 &g1, const G2 &g2)
-{
+int checkSub(const G1 &g1, const G2 &g2) {
   typename G1:: template NodeMap<typename G2::Node> iso(g1,INVALID);
-  if(vf2(g1,g2).mapping(iso).run())
-    {
-      checkSub(g1,g2,iso);
-      return true;
-    }
-  else return false;
+  if(vf2(g1,g2).mapping(iso).run()) {
+    checkSub(g1,g2,iso);
+    return true;
+  }
+  else
+    return false;
 }
 
 template<class G1,class G2>
-int checkInd(const G1 &g1, const G2 &g2)
-{
+int checkInd(const G1 &g1, const G2 &g2) {
   typename G1:: template NodeMap<typename G2::Node> iso(g1,INVALID);
-  if(vf2(g1,g2).induced().mapping(iso).run())
-    {
-      checkInd(g1,g2,iso);
-      return true;
-    }
-  else return false;
+  if(vf2(g1,g2).induced().mapping(iso).run()) {
+    checkInd(g1,g2,iso);
+    return true;
+  }
+  else
+    return false;
 }
 
 template<class G1,class G2>
-int checkIso(const G1 &g1, const G2 &g2)
-{
+int checkIso(const G1 &g1, const G2 &g2) {
   typename G1:: template NodeMap<typename G2::Node> iso(g1,INVALID);
-  if(vf2(g1,g2).iso().mapping(iso).run())
-    {
-      check(countNodes(g1)==countNodes(g2),
-            "Wrong iso alg.: they are not isomophic.");
-      checkInd(g1,g2,iso);
-      return true;
-    }
-  else return false;
+  if(vf2(g1,g2).iso().mapping(iso).run()) {
+    check(countNodes(g1)==countNodes(g2),
+          "Wrong iso alg.: they are not isomophic.");
+    checkInd(g1,g2,iso);
+    return true;
+  }
+  else
+    return false;
 }
 
 template<class G1, class G2, class L1, class L2, class I>
 void checkLabel(const G1 &g1, const G2 &,
-                const L1 &l1, const L2 &l2,const I &i)
-{
+                const L1 &l1, const L2 &l2,const I &i) {
   for(typename G1::NodeIt n(g1);n!=INVALID;++n)
-    {
-      check(l1[n]==l2[i[n]],"Wrong isomorphism: label mismatch.");
-    }
+    check(l1[n]==l2[i[n]],"Wrong isomorphism: label mismatch.");
 }
 
 template<class G1,class G2,class L1,class L2>
-int checkSub(const G1 &g1, const G2 &g2, const L1 &l1, const L2 &l2)
-{
+int checkSub(const G1 &g1, const G2 &g2, const L1 &l1, const L2 &l2) {
   typename G1:: template NodeMap<typename G2::Node> iso(g1,INVALID);
-  if(vf2(g1,g2).nodeLabels(l1,l2).mapping(iso).run())
-    {
-      checkSub(g1,g2,iso);
-      checkLabel(g1,g2,l1,l2,iso);
-      return true;
-    }
-  else return false;
+  if(vf2(g1,g2).nodeLabels(l1,l2).mapping(iso).run()){
+    checkSub(g1,g2,iso);
+    checkLabel(g1,g2,l1,l2,iso);
+    return true;
+  }
+  else
+    return false;
 }
 
 int main() {
   make_graphs();
+  //   justCompile();
   check(checkSub(c5,petersen), "There should exist a C5->Petersen mapping.");
   check(!checkSub(c7,petersen),