-package org.simantics.graph.matching;\r
-\r
-import gnu.trove.set.hash.THashSet;\r
-\r
-import java.util.Arrays;\r
-\r
-import org.simantics.graph.representation.TransferableGraph1;\r
-\r
-/**\r
- * Matching of two transferable graphs.\r
- * \r
- * @author Hannu Niemistö\r
- */\r
-public class GraphMatching {\r
- public static final boolean DEBUG = false;\r
- public static final boolean TIMING = false;\r
-\r
- int aOriginalSize;\r
- int bOriginalSize;\r
- CanonicalGraph aGraph;\r
- CanonicalGraph bGraph;\r
- protected int[] aToB;\r
- protected int[] bToA;\r
- int size;\r
- \r
- public GraphMatching(TransferableGraph1 a, TransferableGraph1 b) {\r
- long begin = System.nanoTime();\r
- this.aGraph = new CanonicalGraph(a);\r
- this.bGraph = new CanonicalGraph(b);\r
- aToB = new int[this.aGraph.resourceCount];\r
- Arrays.fill(aToB, -1);\r
- bToA = new int[this.bGraph.resourceCount];\r
- Arrays.fill(bToA, -1);\r
- this.aOriginalSize = a.resourceCount;\r
- this.bOriginalSize = b.resourceCount;\r
- if(TIMING) {\r
- long end = System.nanoTime();\r
- System.out.println("Initialization: " + (end-begin)*1e-6 + "ms");\r
- }\r
- }\r
-\r
- public void print() {\r
- System.out.println("Resources in a: " + aGraph.resourceCount);\r
- System.out.println("Identities in a: " + aGraph.identities.length);\r
- System.out.println("Statements in a: " + aGraph.statements.length/6);\r
- System.out.println();\r
- System.out.println("Resources in b: " + bGraph.resourceCount);\r
- System.out.println("Identities in b: " + bGraph.identities.length);\r
- System.out.println("Statements in b: " + bGraph.statements.length/6);\r
- System.out.println();\r
- System.out.println("Match size: " + size());\r
- }\r
-\r
- public int size() { \r
- return size;\r
- }\r
- \r
- public void recomputeSize() {\r
- int count = 0;\r
- for(int b : aToB)\r
- if(b >= 0)\r
- ++count;\r
- size = count;\r
- }\r
-\r
- public void map(int a, int b) {\r
- //if(aToB[a] < 0 && bToA[b] < 0) {\r
- ++size;\r
- aToB[a] = b;\r
- bToA[b] = a;\r
- /*if(aGraph.inverses.contains(a) && bGraph.inverses.contains(b) &&\r
- aGraph.inverses.get(a) != a) {\r
- int invA = aGraph.inverses.get(a);\r
- int invB = bGraph.inverses.get(b);\r
- ++size;\r
- aToB[invA] = invB; \r
- bToA[invB] = invA; \r
- }*/\r
- /*}\r
- else\r
- System.out.println("ERR");*/\r
- }\r
- \r
- public void map(int[] as, int[] bs) {\r
- for(int i=0;i<as.length;++i)\r
- map(as[i], bs[i]);\r
- }\r
- \r
- public void unmap(int a, int b) {\r
- --size;\r
- aToB[a] = -1;\r
- bToA[b] = -1;\r
- /*if(aGraph.inverses.contains(a) && bGraph.inverses.contains(b) &&\r
- aGraph.inverses.get(a) != a) {\r
- int invA = aGraph.inverses.get(a);\r
- int invB = bGraph.inverses.get(b);\r
- --size;\r
- aToB[invA] = -1;\r
- bToA[invB] = -1;\r
- }*/\r
- }\r
- \r
- public void unmap(int[] as, int[] bs) {\r
- for(int i=0;i<as.length;++i)\r
- unmap(as[i], bs[i]);\r
- }\r
-\r
- public boolean checkMatch(int[] as, int[] bs) {\r
- for(int i=0;i<as.length;++i)\r
- if(!checkMatch(as[i], bs[i]))\r
- return false;\r
- return true;\r
- }\r
-\r
- public boolean checkMatch(int a, int b) {\r
- Stat[] aStats = aGraph.statements[a];\r
- Stat[] bStats = bGraph.statements[b];\r
- if(aStats.length != bStats.length)\r
- return false;\r
- THashSet<Stat> mappedStats = new THashSet<Stat>();\r
- int[] aToB = this.aToB;\r
- for(Stat stat : aStats) {\r
- int mp = aToB[stat.p];\r
- int mo = aToB[stat.o];\r
- if(mp < 0 || mo < 0)\r
- return false;\r
- mappedStats.add(new Stat(mp, mo));\r
- }\r
- for(Stat stat : bStats)\r
- if(!mappedStats.contains(stat))\r
- return false;\r
- return true;\r
- }\r
- \r
- public int maxSize() {\r
- return Math.min(aGraph.resourceCount, bGraph.resourceCount);\r
- }\r
- \r
- public int[] getAToB() {\r
- return aToB;\r
- }\r
- \r
- public int[] getBToA() {\r
- return bToA;\r
- }\r
- \r
- public static int[] cut(int[] map, int domainSize, int rangeSize) {\r
- int[] newMap = new int[domainSize];\r
- for(int i=0;i<domainSize;++i) {\r
- int temp = map[i];\r
- if(temp >= rangeSize)\r
- newMap[i] = -1;\r
- else\r
- newMap[i] = temp;\r
- }\r
- return newMap;\r
- }\r
- \r
- public void match() {\r
- apply(IdentityMatchingStrategy.INSTANCE);\r
- apply(CanonicalizingMatchingStrategy.INSTANCE);\r
- while(true) {\r
- if(size == maxSize())\r
- break;\r
- int curSize = size;\r
- apply(VotingMatchingStrategy.INSTANCE);\r
- if(size == curSize)\r
- break;\r
- }\r
- aToB = cut(aToB, aOriginalSize, bOriginalSize);\r
- bToA = cut(bToA, bOriginalSize, aOriginalSize);\r
- }\r
- \r
- private void apply(GraphMatchingStrategy strategy) {\r
- if(TIMING) {\r
- long begin = System.nanoTime();\r
- strategy.applyTo(this);\r
- long end = System.nanoTime(); \r
- System.out.println(strategy.getClass().getSimpleName() + ": " + \r
- (end - begin)*1e-6 + "ms");\r
- }\r
- else\r
- strategy.applyTo(this);\r
- }\r
-}\r
+package org.simantics.graph.matching;
+
+import gnu.trove.set.hash.THashSet;
+
+import java.util.Arrays;
+
+import org.simantics.graph.representation.TransferableGraph1;
+
+/**
+ * Matching of two transferable graphs.
+ *
+ * @author Hannu Niemistö
+ */
+public class GraphMatching {
+ public static final boolean DEBUG = false;
+ public static final boolean TIMING = false;
+
+ int aOriginalSize;
+ int bOriginalSize;
+ CanonicalGraph aGraph;
+ CanonicalGraph bGraph;
+ protected int[] aToB;
+ protected int[] bToA;
+ int size;
+
+ public GraphMatching(TransferableGraph1 a, TransferableGraph1 b) {
+ long begin = System.nanoTime();
+ this.aGraph = new CanonicalGraph(a);
+ this.bGraph = new CanonicalGraph(b);
+ aToB = new int[this.aGraph.resourceCount];
+ Arrays.fill(aToB, -1);
+ bToA = new int[this.bGraph.resourceCount];
+ Arrays.fill(bToA, -1);
+ this.aOriginalSize = a.resourceCount;
+ this.bOriginalSize = b.resourceCount;
+ if(TIMING) {
+ long end = System.nanoTime();
+ System.out.println("Initialization: " + (end-begin)*1e-6 + "ms");
+ }
+ }
+
+ public void print() {
+ System.out.println("Resources in a: " + aGraph.resourceCount);
+ System.out.println("Identities in a: " + aGraph.identities.length);
+ System.out.println("Statements in a: " + aGraph.statements.length/6);
+ System.out.println();
+ System.out.println("Resources in b: " + bGraph.resourceCount);
+ System.out.println("Identities in b: " + bGraph.identities.length);
+ System.out.println("Statements in b: " + bGraph.statements.length/6);
+ System.out.println();
+ System.out.println("Match size: " + size());
+ }
+
+ public int size() {
+ return size;
+ }
+
+ public void recomputeSize() {
+ int count = 0;
+ for(int b : aToB)
+ if(b >= 0)
+ ++count;
+ size = count;
+ }
+
+ public void map(int a, int b) {
+ //if(aToB[a] < 0 && bToA[b] < 0) {
+ ++size;
+ aToB[a] = b;
+ bToA[b] = a;
+ /*if(aGraph.inverses.contains(a) && bGraph.inverses.contains(b) &&
+ aGraph.inverses.get(a) != a) {
+ int invA = aGraph.inverses.get(a);
+ int invB = bGraph.inverses.get(b);
+ ++size;
+ aToB[invA] = invB;
+ bToA[invB] = invA;
+ }*/
+ /*}
+ else
+ System.out.println("ERR");*/
+ }
+
+ public void map(int[] as, int[] bs) {
+ for(int i=0;i<as.length;++i)
+ map(as[i], bs[i]);
+ }
+
+ public void unmap(int a, int b) {
+ --size;
+ aToB[a] = -1;
+ bToA[b] = -1;
+ /*if(aGraph.inverses.contains(a) && bGraph.inverses.contains(b) &&
+ aGraph.inverses.get(a) != a) {
+ int invA = aGraph.inverses.get(a);
+ int invB = bGraph.inverses.get(b);
+ --size;
+ aToB[invA] = -1;
+ bToA[invB] = -1;
+ }*/
+ }
+
+ public void unmap(int[] as, int[] bs) {
+ for(int i=0;i<as.length;++i)
+ unmap(as[i], bs[i]);
+ }
+
+ public boolean checkMatch(int[] as, int[] bs) {
+ for(int i=0;i<as.length;++i)
+ if(!checkMatch(as[i], bs[i]))
+ return false;
+ return true;
+ }
+
+ public boolean checkMatch(int a, int b) {
+ Stat[] aStats = aGraph.statements[a];
+ Stat[] bStats = bGraph.statements[b];
+ if(aStats.length != bStats.length)
+ return false;
+ THashSet<Stat> mappedStats = new THashSet<Stat>();
+ int[] aToB = this.aToB;
+ for(Stat stat : aStats) {
+ int mp = aToB[stat.p];
+ int mo = aToB[stat.o];
+ if(mp < 0 || mo < 0)
+ return false;
+ mappedStats.add(new Stat(mp, mo));
+ }
+ for(Stat stat : bStats)
+ if(!mappedStats.contains(stat))
+ return false;
+ return true;
+ }
+
+ public int maxSize() {
+ return Math.min(aGraph.resourceCount, bGraph.resourceCount);
+ }
+
+ public int[] getAToB() {
+ return aToB;
+ }
+
+ public int[] getBToA() {
+ return bToA;
+ }
+
+ public static int[] cut(int[] map, int domainSize, int rangeSize) {
+ int[] newMap = new int[domainSize];
+ for(int i=0;i<domainSize;++i) {
+ int temp = map[i];
+ if(temp >= rangeSize)
+ newMap[i] = -1;
+ else
+ newMap[i] = temp;
+ }
+ return newMap;
+ }
+
+ public void match() {
+ apply(IdentityMatchingStrategy.INSTANCE);
+ apply(CanonicalizingMatchingStrategy.INSTANCE);
+ while(true) {
+ if(size == maxSize())
+ break;
+ int curSize = size;
+ apply(VotingMatchingStrategy.INSTANCE);
+ if(size == curSize)
+ break;
+ }
+ aToB = cut(aToB, aOriginalSize, bOriginalSize);
+ bToA = cut(bToA, bOriginalSize, aOriginalSize);
+ }
+
+ private void apply(GraphMatchingStrategy strategy) {
+ if(TIMING) {
+ long begin = System.nanoTime();
+ strategy.applyTo(this);
+ long end = System.nanoTime();
+ System.out.println(strategy.getClass().getSimpleName() + ": " +
+ (end - begin)*1e-6 + "ms");
+ }
+ else
+ strategy.applyTo(this);
+ }
+}
Code Review / simantics / platform.git / blobdiff