--- /dev/null
+package org.simantics.graph.matching;\r
+\r
+import gnu.trove.list.array.TIntArrayList;\r
+import gnu.trove.map.hash.THashMap;\r
+import gnu.trove.map.hash.TIntIntHashMap;\r
+import gnu.trove.map.hash.TIntObjectHashMap;\r
+import gnu.trove.procedure.TObjectProcedure;\r
+\r
+import java.util.ArrayList;\r
+import java.util.Arrays;\r
+import java.util.Comparator;\r
+\r
+/**\r
+ * Matches isomorphic components of the not yet matched graphs together.\r
+ * \r
+ * @author Hannu Niemistö\r
+ */\r
+public enum ComponentMatchingStrategy implements GraphMatchingStrategy {\r
+ INSTANCE;\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
+ public static int[][] findComponents(int[] map, Stat[][] statements, TIntIntHashMap inverses) {\r
+ int resourceCount = map.length;\r
+ \r
+ UnionFind uf = new UnionFind(resourceCount);\r
+ for(int s=0;s<resourceCount;++s)\r
+ if(map[s] < 0) {\r
+ for(Stat stat : statements[s]) {\r
+ int o = stat.o;\r
+ if(s < o && map[o] < 0)\r
+ uf.merge(s, o);\r
+ }\r
+ /*if(inverses.containsKey(s))\r
+ uf.merge(s, inverses.get(s));\r
+ */\r
+ }\r
+ \r
+ TIntObjectHashMap<TIntArrayList> components = new TIntObjectHashMap<TIntArrayList>();\r
+ for(int i=0;i<resourceCount;++i)\r
+ if(map[i] < 0) {\r
+ int c = uf.canonical(i);\r
+ TIntArrayList els = components.get(c);\r
+ if(els == null) {\r
+ els = new TIntArrayList(2);\r
+ components.put(c, els);\r
+ }\r
+ els.add(i);\r
+ }\r
+ \r
+ final int[][] result = new int[components.size()][];\r
+ components.forEachValue(new TObjectProcedure<TIntArrayList>() {\r
+ int i = 0;\r
+ @Override\r
+ public boolean execute(TIntArrayList els) {\r
+ result[i++] = els.toArray();\r
+ return true;\r
+ }\r
+ });\r
+ return result;\r
+ } \r
+ \r
+ public static Stat[][] neighbors(int[] map, Stat[][] statements) {\r
+ int resourceCount = map.length;\r
+ Stat[][] neighbors = new Stat[resourceCount][];\r
+ \r
+ ArrayList<Stat> stats = new ArrayList<Stat>();\r
+ for(int s=0;s<resourceCount;++s) {\r
+ if(map[s] >= 0) {\r
+ neighbors[s] = Stat.NO_STATS;\r
+ continue;\r
+ }\r
+ \r
+ for(Stat stat : statements[s]) {\r
+ int pp = map[stat.p] >= 0 ? stat.p : -1;\r
+ int oo = map[stat.o] >= 0 ? stat.o : -1; \r
+ stats.add(new Stat(pp, oo));\r
+ }\r
+ \r
+ if(stats.isEmpty())\r
+ neighbors[s] = Stat.NO_STATS;\r
+ else {\r
+ neighbors[s] = stats.toArray(new Stat[stats.size()]);\r
+ stats.clear();\r
+ }\r
+ }\r
+ \r
+ return neighbors;\r
+ }\r
+ \r
+ static class Component {\r
+ int[] elements;\r
+ Stat[][] neighbors;\r
+ \r
+ public Component(int[] elements, Stat[][] neighbors) {\r
+ this.elements = elements;\r
+ this.neighbors = new Stat[elements.length][];\r
+ for(int i=0;i<elements.length;++i)\r
+ this.neighbors[i] = neighbors[elements[i]];\r
+ }\r
+ \r
+ public void map(int[] map) {\r
+ for(Stat[] stats : neighbors)\r
+ for(Stat stat : stats)\r
+ stat.map(map);\r
+ }\r
+ \r
+ static class PP {\r
+ int element;\r
+ Stat[] stats;\r
+ \r
+ public PP(int element, Stat[] stats) {\r
+ this.element = element;\r
+ Arrays.sort(stats, Stat.STAT_COMPARATOR);\r
+ this.stats = stats;\r
+ }\r
+ }\r
+ \r
+ static final Comparator<PP> PP_COMPARATOR = new Comparator<PP>() {\r
+ @Override\r
+ public int compare(PP o1, PP o2) {\r
+ Stat[] stats1 = o1.stats;\r
+ Stat[] stats2 = o2.stats;\r
+ int l1 = stats1.length;\r
+ int l2 = stats2.length;\r
+ if(l1 < l2)\r
+ return -1;\r
+ else if(l1 > l2)\r
+ return 1;\r
+ for(int i=0;i<l1;++i) {\r
+ Stat s1 = stats1[i];\r
+ Stat s2 = stats2[i];\r
+ if(s1.p < s2.p)\r
+ return -1;\r
+ else if(s1.p > s2.p)\r
+ return 1;\r
+ else if(s1.o < s2.o)\r
+ return -1;\r
+ else if(s1.o > s2.o)\r
+ return 1;\r
+ }\r
+ return 0;\r
+ } \r
+ };\r
+ \r
+ public void canonicalize(String[] elNames, String[] statNames) {\r
+ PP[] pps = new PP[elements.length];\r
+ for(int i=0;i<elements.length;++i)\r
+ pps[i] = new PP(elements[i], neighbors[i]);\r
+ Arrays.sort(pps, PP_COMPARATOR);\r
+ for(int i=0;i<pps.length-1;++i)\r
+ if(PP_COMPARATOR.compare(pps[i], pps[i+1]) == 0) {\r
+ System.out.println("AMB " + pps.length + " " + (elNames==statNames));\r
+ for(i=0;i<pps.length-1;++i) {\r
+ if(PP_COMPARATOR.compare(pps[i], pps[i+1]) == 0)\r
+ System.out.print("> ");\r
+ else\r
+ System.out.print(" ");\r
+ System.out.println(elNames[pps[i].element]);\r
+ for(Stat stat : pps[i].stats)\r
+ System.out.println(" " + stat.toString(statNames));\r
+ }\r
+ break;\r
+ }\r
+ for(int i=0;i<elements.length;++i) {\r
+ PP pp = pps[i];\r
+ elements[i] = pp.element;\r
+ neighbors[i] = pp.stats;\r
+ }\r
+ }\r
+\r
+ public boolean isIsolated() {\r
+ for(Stat[] stats : neighbors)\r
+ if(stats.length > 0)\r
+ return false;\r
+ return true;\r
+ }\r
+ }\r
+ \r
+ static class TNeighbourObjectHashMap<T> extends THashMap<Stat[][], T> {\r
+ @Override\r
+ protected boolean equals(Object one, Object two) {\r
+ Stat[][] o1 = (Stat[][])one;\r
+ Stat[][] o2 = (Stat[][])two;\r
+ if(o1.length != o2.length)\r
+ return false;\r
+ for(int i=0;i<o1.length;++i) {\r
+ Stat[] ss1 = o1[i];\r
+ Stat[] ss2 = o2[i];\r
+ if(ss1.length != ss2.length)\r
+ return false;\r
+ for(int j=0;j<ss1.length;++j) {\r
+ Stat s1 = ss1[j];\r
+ Stat s2 = ss2[j];\r
+ if(s1.p != s2.p || s1.o != s2.o)\r
+ return false;\r
+ }\r
+ }\r
+ return true;\r
+ }\r
+ \r
+ @Override\r
+ protected int hash(Object obj) {\r
+ int result = 152433;\r
+ for(Stat[] stats : (Stat[][])obj)\r
+ for(Stat stat : stats)\r
+ result = (result*31 + stat.p)*31 + stat.o;\r
+ return result;\r
+ }\r
+ }\r
+ \r
+ @Override\r
+ public void applyTo(GraphMatching matching) {\r
+ System.out.println("ComponentMatchingStrategy");\r
+ TNeighbourObjectHashMap<ArrayList<int[]>> aComponents = new TNeighbourObjectHashMap<ArrayList<int[]>>(); \r
+ { \r
+ Stat[][] neighbors = neighbors(matching.aToB, matching.aGraph.statements);\r
+ //TIntIntHashMap componentSizes = new TIntIntHashMap();\r
+ for(int[] els : findComponents(matching.aToB, matching.aGraph.statements, matching.aGraph.inverses)) {\r
+ /*for(int el : els)\r
+ System.out.print(matching.aGraph.names[el] + " ");\r
+ System.out.println();\r
+ componentSizes.adjustOrPutValue(els.length, 1, 1);*/\r
+ Component component = new Component(els, neighbors);\r
+ if(component.isIsolated())\r
+ continue;\r
+ component.map(matching.aToB);\r
+ component.canonicalize(matching.aGraph.names, matching.bGraph.names);\r
+ ArrayList<int[]> values = aComponents.get(component.neighbors);\r
+ if(values == null) {\r
+ values = new ArrayList<int[]>(1);\r
+ aComponents.put(component.neighbors, values);\r
+ }\r
+ values.add(component.elements);\r
+ }\r
+ /*componentSizes.forEachEntry(new TIntIntProcedure() { \r
+ @Override\r
+ public boolean execute(int a, int b) {\r
+ System.out.println("Components of size " + a + ": " + b);\r
+ return true;\r
+ }\r
+ });*/\r
+ }\r
+ \r
+ ArrayList<Component> bComponents = new ArrayList<Component>(); \r
+ {\r
+ Stat[][] neighbors = neighbors(matching.bToA, matching.bGraph.statements);\r
+ for(int[] els : findComponents(matching.bToA, matching.bGraph.statements, matching.bGraph.inverses)) {\r
+ Component component = new Component(els, neighbors);\r
+ if(component.isIsolated())\r
+ continue;\r
+ component.canonicalize(matching.bGraph.names, matching.bGraph.names);\r
+ bComponents.add(component);\r
+ }\r
+ }\r
+ \r
+ for(Component c : bComponents) {\r
+ ArrayList<int[]> candidates = aComponents.get(c.neighbors);\r
+ if(candidates != null)\r
+ for(int i=0;i<candidates.size();++i) {\r
+ int[] els = candidates.get(i);\r
+ if(els != null) {\r
+ matching.map(els, c.elements);\r
+ if(matching.checkMatch(els, c.elements)) {\r
+ if(candidates.size() == 1)\r
+ aComponents.remove(c.neighbors);\r
+ else {\r
+ int last = candidates.size()-1;\r
+ int[] temp = candidates.remove(last);\r
+ if(i < last)\r
+ candidates.set(i, temp);\r
+ }\r
+ break;\r
+ }\r
+ else\r
+ matching.unmap(els, c.elements);\r
+ } \r
+ } \r
+ }\r
+ }\r
+}\r
Code Review / simantics / platform.git / blobdiff