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