--- /dev/null
+package org.simantics.graph.matching;\r
+\r
+import gnu.trove.list.array.TIntArrayList;\r
+import gnu.trove.map.hash.TObjectIntHashMap;\r
+import gnu.trove.set.hash.TIntHashSet;\r
+\r
+import java.util.Arrays;\r
+import java.util.Comparator;\r
+\r
+import org.simantics.databoard.binding.mutable.Variant;\r
+\r
+public enum CanonicalizingMatchingStrategy implements GraphMatchingStrategy {\r
+ INSTANCE;\r
+\r
+ private static class Vertex {\r
+ int graph;\r
+ int original;\r
+ int pos;\r
+ Stat[] stats;\r
+ \r
+ public Vertex(int graph, int original, int pos, Stat[] stats) {\r
+ this.graph = graph;\r
+ this.original = original;\r
+ this.pos = pos;\r
+ this.stats = stats;\r
+ }\r
+ }\r
+ \r
+ private static final Comparator<Vertex> VERTEX_COMPARATOR = new Comparator<Vertex>() {\r
+ @Override\r
+ public int compare(Vertex o1, Vertex o2) {\r
+ int pos1 = o1.pos;\r
+ int pos2 = o2.pos;\r
+ if(pos1 < pos2)\r
+ return -1;\r
+ if(pos1 > pos2)\r
+ return 1;\r
+ Stat[] stats1 = o1.stats;\r
+ Stat[] stats2 = o2.stats;\r
+ if(stats1.length < stats2.length)\r
+ return -1;\r
+ if(stats1.length > stats2.length)\r
+ return 1;\r
+ for(int i=0;i<stats1.length;++i) {\r
+ int comp = Stat.STAT_COMPARATOR.compare(stats1[i], stats2[i]);\r
+ if(comp != 0)\r
+ return comp;\r
+ }\r
+ if(o1.graph < o2.graph)\r
+ return -1;\r
+ if(o1.graph > o2.graph)\r
+ return 1; \r
+ if(o1.original < o2.original)\r
+ return -1;\r
+ if(o1.original > o2.original)\r
+ return 1;\r
+ return 0;\r
+ }\r
+ };\r
+ \r
+ private static int[] generateMapA(int[] aToB) {\r
+ int[] map = new int[aToB.length];\r
+ for(int i=0;i<aToB.length;++i) {\r
+ int c = aToB[i];\r
+ if(c >= 0)\r
+ map[i] = -1 - c;\r
+ else\r
+ map[i] = 0;\r
+ }\r
+ return map;\r
+ }\r
+ \r
+ private static int[] generateMapB(int[] bToA) {\r
+ int[] map = new int[bToA.length];\r
+ for(int i=0;i<bToA.length;++i) {\r
+ int c = bToA[i];\r
+ if(c >= 0)\r
+ map[i] = -1 - i;\r
+ else\r
+ map[i] = 0;\r
+ }\r
+ return map;\r
+ }\r
+ \r
+ private static Vertex[] generateVertices(int graph, int[] map, Stat[][] statements) {\r
+ int size = 0;\r
+ for(int s=0;s<map.length;++s)\r
+ if(map[s] == 0)\r
+ ++size;\r
+ Vertex[] vertices = new Vertex[size];\r
+ for(int s=0,i=0;s<map.length;++s)\r
+ if(map[s] == 0) {\r
+ Stat[] ns = statements[s];\r
+ Stat[] stats = new Stat[ns.length];\r
+ for(int j=0;j<ns.length;++j) {\r
+ Stat n = ns[j];\r
+ stats[j] = new Stat(map[n.p], map[n.o]);\r
+ }\r
+ Arrays.sort(stats, Stat.STAT_COMPARATOR);\r
+ vertices[i++] = new Vertex(graph, s, 0, stats);\r
+ }\r
+ return vertices;\r
+ }\r
+ \r
+ private static void updateVertices(Vertex[] vertices, int[] map, Stat[][] statements) {\r
+ for(int i=0;i<vertices.length;++i) {\r
+ int s = vertices[i].original;\r
+ Stat[] ns = statements[s];\r
+ Stat[] stats = vertices[i].stats;\r
+ for(int j=0;j<ns.length;++j) {\r
+ Stat n = ns[j];\r
+ Stat stat = stats[j];\r
+ stat.p = map[n.p];\r
+ stat.o = map[n.o];\r
+ }\r
+ Arrays.sort(stats, Stat.STAT_COMPARATOR);\r
+ }\r
+ }\r
+ \r
+ private static Vertex[] concat(Vertex[] as, Vertex[] bs) {\r
+ Vertex[] result = new Vertex[as.length + bs.length];\r
+ System.arraycopy(as, 0, result, 0, as.length);\r
+ System.arraycopy(bs, 0, result, as.length, bs.length);\r
+ return result;\r
+ }\r
+ \r
+ static boolean equals(Stat[] stats1, Stat[] stats2) {\r
+ if(stats1.length != stats2.length)\r
+ return false;\r
+ for(int i=0;i<stats1.length;++i) {\r
+ Stat stat1 = stats1[i];\r
+ Stat stat2 = stats2[i];\r
+ if(stat1.p != stat2.p || stat1.o != stat2.o)\r
+ return false;\r
+ }\r
+ return true;\r
+ }\r
+ \r
+ private static boolean updatePositions(Vertex[] can) {\r
+ boolean modified = false;\r
+ int oldPos = can[0].pos;\r
+ Vertex oldVertex = can[0];\r
+ for(int i=1;i<can.length;++i) {\r
+ Vertex curVertex = can[i];\r
+ int curPos = curVertex.pos;\r
+ if(curPos == oldPos) {\r
+ if(equals(oldVertex.stats, curVertex.stats))\r
+ curVertex.pos = oldVertex.pos;\r
+ else {\r
+ curVertex.pos = i;\r
+ modified = true;\r
+ }\r
+ }\r
+ else\r
+ oldPos = curPos;\r
+ oldVertex = curVertex;\r
+ }\r
+ return modified;\r
+ }\r
+ \r
+ private static void updateMap(Vertex[] vertices, int[] map) {\r
+ for(Vertex vertex : vertices)\r
+ map[vertex.original] = vertex.pos;\r
+ }\r
+\r
+ private static int[] groupPositions(Vertex[] can) {\r
+ TIntArrayList result = new TIntArrayList();\r
+ for(int i=0;i<can.length;++i)\r
+ if(can[i].pos == i)\r
+ result.add(i);\r
+ result.add(can.length);\r
+ return result.toArray();\r
+ } \r
+ \r
+ static class TByteArrayIntHashMap extends TObjectIntHashMap<byte[]> {\r
+ @Override\r
+ protected boolean equals(Object one, Object two) {\r
+ return Arrays.equals((byte[])one, (byte[])two);\r
+ }\r
+ \r
+ @Override\r
+ protected int hash(Object obj) {\r
+ return Arrays.hashCode((byte[])obj);\r
+ }\r
+ }\r
+ \r
+ private boolean separateByValues(Vertex[] can, int begin, int end, Variant[] aValues, Variant[] bValues) { \r
+ int valueCount = 0;\r
+ TObjectIntHashMap<Variant> valueIds = new TObjectIntHashMap<Variant>();\r
+ int[] ids = new int[end-begin];\r
+ for(int i=begin;i<end;++i) {\r
+ Vertex v = can[i];\r
+ Variant value = v.graph==0 ? aValues[v.original] : bValues[v.original];\r
+ int valueId = valueIds.get(value);\r
+ if(valueId == 0) {\r
+ valueIds.put(value, ++valueCount);\r
+ ids[i-begin] = valueCount-1;\r
+ }\r
+ else\r
+ ids[i-begin] = valueId-1;\r
+ }\r
+ if(valueCount > 1) {\r
+ Vertex[] vs = Arrays.copyOfRange(can, begin, end);\r
+ int[] temp = new int[valueCount];\r
+ for(int id : ids)\r
+ ++temp[id];\r
+ int cur = begin;\r
+ for(int i=0;i<temp.length;++i) {\r
+ int count = temp[i];\r
+ temp[i] = cur;\r
+ cur += count;\r
+ }\r
+ for(int i=0;i<ids.length;++i)\r
+ vs[i].pos = temp[ids[i]];\r
+ for(int i=0;i<ids.length;++i)\r
+ can[temp[ids[i]]++] = vs[i];\r
+ return true;\r
+ }\r
+ else\r
+ return false;\r
+ }\r
+ \r
+ private boolean separateByValues(Vertex[] can, int[] groupPos, Variant[] aValues, Variant[] bValues) {\r
+ boolean modified = false;\r
+ for(int i=0;i<groupPos.length-1;++i) {\r
+ int begin = groupPos[i];\r
+ int end = groupPos[i+1];\r
+ if(end - begin > 2)\r
+ modified |= separateByValues(can, begin, end, aValues, bValues); \r
+ }\r
+ return modified;\r
+ }\r
+ \r
+ private boolean hasBigGroups(Vertex[] can, int[] groupPos) {\r
+ for(int i=0;i<groupPos.length-1;++i) {\r
+ int begin = groupPos[i];\r
+ int end = groupPos[i+1];\r
+ if(end - begin > 2 && can[begin].graph == 0 && can[end-1].graph == 1)\r
+ return true;\r
+ }\r
+ return false;\r
+ }\r
+ \r
+ static class UnionFind {\r
+ int[] canonical;\r
+ \r
+ public UnionFind(int size) {\r
+ canonical = new int[size];\r
+ for(int i=0;i<size;++i)\r
+ canonical[i] = i;\r
+ }\r
+ \r
+ public int canonical(int a) {\r
+ int b = canonical[a];\r
+ if(b != a) {\r
+ int c = canonical[b];\r
+ if(b != c) {\r
+ c = canonical(c);\r
+ canonical[b] = c; \r
+ canonical[a] = c;\r
+ return c;\r
+ }\r
+ }\r
+ return b;\r
+ }\r
+ \r
+ public void merge(int a, int b) {\r
+ a = canonical(a);\r
+ b = canonical(b);\r
+ canonical[a] = b;\r
+ }\r
+ }\r
+ \r
+ private static void guessIsomorphism(Vertex[] can, int[] groupPos) {\r
+ UnionFind uf = new UnionFind(can.length);\r
+ for(int i=0;i<can.length;++i) {\r
+ uf.merge(i, can[i].pos);\r
+ for(Stat stat : can[i].stats) {\r
+ if(stat.p >= 0)\r
+ uf.merge(i, stat.p);\r
+ if(stat.o >= 0)\r
+ uf.merge(i, stat.o);\r
+ }\r
+ }\r
+ \r
+ TIntHashSet done = new TIntHashSet();\r
+ for(int i=0;i<groupPos.length-1;++i) {\r
+ int begin = groupPos[i];\r
+ int end = groupPos[i+1];\r
+ if(end - begin > 2 && can[begin].graph == 0 && can[end-1].graph == 1) {\r
+ int c = uf.canonical(begin);\r
+ if(done.add(c)) {\r
+ int middle = begin+1;\r
+ while(can[middle].graph==0)\r
+ ++middle;\r
+ int j;\r
+ for(j=0;begin+j < middle && middle+j < end;++j) {\r
+ can[begin+j].pos = begin + j*2;\r
+ can[middle+j].pos = begin + j*2;\r
+ }\r
+ int pos = begin+j*2; \r
+ for(;begin+j < middle;++j)\r
+ can[begin+j].pos = pos;\r
+ for(;middle+j < end;++j)\r
+ can[middle+j].pos = pos;\r
+ }\r
+ }\r
+ }\r
+ }\r
+ \r
+ @Override\r
+ public void applyTo(GraphMatching matching) {\r
+ if(matching.size == matching.aGraph.resourceCount ||\r
+ matching.size == matching.bGraph.resourceCount)\r
+ return;\r
+ long begin1 = System.nanoTime();\r
+ int[] aMap = generateMapA(matching.aToB);\r
+ int[] bMap = generateMapB(matching.bToA);\r
+ Vertex[] aVertices = generateVertices(0,\r
+ aMap, matching.aGraph.statements);\r
+ Vertex[] bVertices = generateVertices(1,\r
+ bMap, matching.bGraph.statements);\r
+ Vertex[] can = concat(aVertices, bVertices);\r
+ if(GraphMatching.TIMING)\r
+ System.out.println(" Init: " + (System.nanoTime()-begin1)*1e-6 + "ms");\r
+ \r
+ int[] groupPos = null;\r
+ boolean doneSeparationByValues = false;\r
+ while(true) {\r
+ long begin2 = System.nanoTime();\r
+ Arrays.sort(can, VERTEX_COMPARATOR);\r
+ if(GraphMatching.TIMING)\r
+ System.out.println(" Sort: " + (System.nanoTime()-begin2)*1e-6 + "ms");\r
+ \r
+ long begin3 = System.nanoTime();\r
+ if(!updatePositions(can)) { \r
+ groupPos = groupPositions(can); \r
+ if(!hasBigGroups(can, groupPos))\r
+ break;\r
+ \r
+ boolean modified = false;\r
+ if(!doneSeparationByValues) {\r
+ modified = separateByValues(can, groupPos, matching.aGraph.values, matching.bGraph.values); \r
+ doneSeparationByValues = true;\r
+ if(GraphMatching.TIMING)\r
+ System.out.println(" - separate by values");\r
+ }\r
+ \r
+ if(!modified) {\r
+ guessIsomorphism(can, groupPos);\r
+ if(GraphMatching.TIMING)\r
+ System.out.println(" - guess isomorphism");\r
+ }\r
+ }\r
+ if(GraphMatching.TIMING)\r
+ System.out.println(" Update1: " + (System.nanoTime()-begin3)*1e-6 + "ms");\r
+ \r
+ long begin4 = System.nanoTime();\r
+ updateMap(aVertices, aMap); \r
+ updateMap(bVertices, bMap);\r
+ if(GraphMatching.TIMING)\r
+ System.out.println(" Update2: " + (System.nanoTime()-begin4)*1e-6 + "ms"); \r
+ long begin5 = System.nanoTime();\r
+ updateVertices(aVertices, aMap, matching.aGraph.statements);\r
+ updateVertices(bVertices, bMap, matching.bGraph.statements);\r
+ if(GraphMatching.TIMING)\r
+ System.out.println(" Update3: " + (System.nanoTime()-begin5)*1e-6 + "ms");\r
+ }\r
+ \r
+ for(int i=0;i<groupPos.length-1;++i) {\r
+ int begin = groupPos[i];\r
+ int end = groupPos[i+1];\r
+ if(end - begin == 2) {\r
+ Vertex a = can[begin];\r
+ Vertex b = can[end-1];\r
+ if(a.graph == 0 && b.graph == 1)\r
+ matching.map(a.original, b.original);\r
+ }\r
+ }\r
+ \r
+ if(GraphMatching.DEBUG)\r
+ for(int i=0;i<groupPos.length-1;++i) {\r
+ int begin = groupPos[i];\r
+ int end = groupPos[i+1];\r
+ if(end - begin > 2) { \r
+ System.out.println("----");\r
+ for(int j=begin;j<end;++j) {\r
+ if(can[j].graph == 0) {\r
+ int org = can[j].original;\r
+ String name = matching.aGraph.names[org];\r
+ System.out.println(name + " (A)");\r
+ for(Stat stat : matching.aGraph.statements[org])\r
+ System.out.println(" " + stat.toString(matching.aGraph.names));\r
+ Variant value = matching.aGraph.values[org];\r
+ if(value != null)\r
+ System.out.println(" " + value);\r
+ }\r
+ else {\r
+ int org = can[j].original;\r
+ String name = matching.bGraph.names[org];\r
+ System.out.println(name + " (B)");\r
+ for(Stat stat : matching.bGraph.statements[org])\r
+ System.out.println(" " + stat.toString(matching.bGraph.names));\r
+ Variant value = matching.bGraph.values[org];\r
+ if(value != null)\r
+ System.out.println(" " + value);\r
+ }\r
+ }\r
+ }\r
+ }\r
+ }\r
+}\r
Code Review / simantics / platform.git / blobdiff