--- /dev/null
+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
Code Review / simantics / platform.git / blobdiff