1 package org.simantics.graph.matching;
\r
3 import gnu.trove.list.array.TIntArrayList;
\r
4 import gnu.trove.map.hash.THashMap;
\r
5 import gnu.trove.map.hash.TIntIntHashMap;
\r
6 import gnu.trove.map.hash.TIntObjectHashMap;
\r
7 import gnu.trove.procedure.TObjectProcedure;
\r
9 import java.util.ArrayList;
\r
10 import java.util.Arrays;
\r
11 import java.util.Comparator;
\r
14 * Matches isomorphic components of the not yet matched graphs together.
\r
16 * @author Hannu Niemistö
\r
18 public enum ComponentMatchingStrategy implements GraphMatchingStrategy {
\r
21 static class UnionFind {
\r
24 public UnionFind(int size) {
\r
25 canonical = new int[size];
\r
26 for(int i=0;i<size;++i)
\r
30 public int canonical(int a) {
\r
31 int b = canonical[a];
\r
33 int c = canonical[b];
\r
44 public void merge(int a, int b) {
\r
51 public static int[][] findComponents(int[] map, Stat[][] statements, TIntIntHashMap inverses) {
\r
52 int resourceCount = map.length;
\r
54 UnionFind uf = new UnionFind(resourceCount);
\r
55 for(int s=0;s<resourceCount;++s)
\r
57 for(Stat stat : statements[s]) {
\r
59 if(s < o && map[o] < 0)
\r
62 /*if(inverses.containsKey(s))
\r
63 uf.merge(s, inverses.get(s));
\r
67 TIntObjectHashMap<TIntArrayList> components = new TIntObjectHashMap<TIntArrayList>();
\r
68 for(int i=0;i<resourceCount;++i)
\r
70 int c = uf.canonical(i);
\r
71 TIntArrayList els = components.get(c);
\r
73 els = new TIntArrayList(2);
\r
74 components.put(c, els);
\r
79 final int[][] result = new int[components.size()][];
\r
80 components.forEachValue(new TObjectProcedure<TIntArrayList>() {
\r
83 public boolean execute(TIntArrayList els) {
\r
84 result[i++] = els.toArray();
\r
91 public static Stat[][] neighbors(int[] map, Stat[][] statements) {
\r
92 int resourceCount = map.length;
\r
93 Stat[][] neighbors = new Stat[resourceCount][];
\r
95 ArrayList<Stat> stats = new ArrayList<Stat>();
\r
96 for(int s=0;s<resourceCount;++s) {
\r
98 neighbors[s] = Stat.NO_STATS;
\r
102 for(Stat stat : statements[s]) {
\r
103 int pp = map[stat.p] >= 0 ? stat.p : -1;
\r
104 int oo = map[stat.o] >= 0 ? stat.o : -1;
\r
105 stats.add(new Stat(pp, oo));
\r
108 if(stats.isEmpty())
\r
109 neighbors[s] = Stat.NO_STATS;
\r
111 neighbors[s] = stats.toArray(new Stat[stats.size()]);
\r
119 static class Component {
\r
121 Stat[][] neighbors;
\r
123 public Component(int[] elements, Stat[][] neighbors) {
\r
124 this.elements = elements;
\r
125 this.neighbors = new Stat[elements.length][];
\r
126 for(int i=0;i<elements.length;++i)
\r
127 this.neighbors[i] = neighbors[elements[i]];
\r
130 public void map(int[] map) {
\r
131 for(Stat[] stats : neighbors)
\r
132 for(Stat stat : stats)
\r
140 public PP(int element, Stat[] stats) {
\r
141 this.element = element;
\r
142 Arrays.sort(stats, Stat.STAT_COMPARATOR);
\r
143 this.stats = stats;
\r
147 static final Comparator<PP> PP_COMPARATOR = new Comparator<PP>() {
\r
149 public int compare(PP o1, PP o2) {
\r
150 Stat[] stats1 = o1.stats;
\r
151 Stat[] stats2 = o2.stats;
\r
152 int l1 = stats1.length;
\r
153 int l2 = stats2.length;
\r
158 for(int i=0;i<l1;++i) {
\r
159 Stat s1 = stats1[i];
\r
160 Stat s2 = stats2[i];
\r
163 else if(s1.p > s2.p)
\r
165 else if(s1.o < s2.o)
\r
167 else if(s1.o > s2.o)
\r
174 public void canonicalize(String[] elNames, String[] statNames) {
\r
175 PP[] pps = new PP[elements.length];
\r
176 for(int i=0;i<elements.length;++i)
\r
177 pps[i] = new PP(elements[i], neighbors[i]);
\r
178 Arrays.sort(pps, PP_COMPARATOR);
\r
179 for(int i=0;i<pps.length-1;++i)
\r
180 if(PP_COMPARATOR.compare(pps[i], pps[i+1]) == 0) {
\r
181 System.out.println("AMB " + pps.length + " " + (elNames==statNames));
\r
182 for(i=0;i<pps.length-1;++i) {
\r
183 if(PP_COMPARATOR.compare(pps[i], pps[i+1]) == 0)
\r
184 System.out.print("> ");
\r
186 System.out.print(" ");
\r
187 System.out.println(elNames[pps[i].element]);
\r
188 for(Stat stat : pps[i].stats)
\r
189 System.out.println(" " + stat.toString(statNames));
\r
193 for(int i=0;i<elements.length;++i) {
\r
195 elements[i] = pp.element;
\r
196 neighbors[i] = pp.stats;
\r
200 public boolean isIsolated() {
\r
201 for(Stat[] stats : neighbors)
\r
202 if(stats.length > 0)
\r
208 static class TNeighbourObjectHashMap<T> extends THashMap<Stat[][], T> {
\r
210 protected boolean equals(Object one, Object two) {
\r
211 Stat[][] o1 = (Stat[][])one;
\r
212 Stat[][] o2 = (Stat[][])two;
\r
213 if(o1.length != o2.length)
\r
215 for(int i=0;i<o1.length;++i) {
\r
216 Stat[] ss1 = o1[i];
\r
217 Stat[] ss2 = o2[i];
\r
218 if(ss1.length != ss2.length)
\r
220 for(int j=0;j<ss1.length;++j) {
\r
223 if(s1.p != s2.p || s1.o != s2.o)
\r
231 protected int hash(Object obj) {
\r
232 int result = 152433;
\r
233 for(Stat[] stats : (Stat[][])obj)
\r
234 for(Stat stat : stats)
\r
235 result = (result*31 + stat.p)*31 + stat.o;
\r
241 public void applyTo(GraphMatching matching) {
\r
242 System.out.println("ComponentMatchingStrategy");
\r
243 TNeighbourObjectHashMap<ArrayList<int[]>> aComponents = new TNeighbourObjectHashMap<ArrayList<int[]>>();
\r
245 Stat[][] neighbors = neighbors(matching.aToB, matching.aGraph.statements);
\r
246 //TIntIntHashMap componentSizes = new TIntIntHashMap();
\r
247 for(int[] els : findComponents(matching.aToB, matching.aGraph.statements, matching.aGraph.inverses)) {
\r
248 /*for(int el : els)
\r
249 System.out.print(matching.aGraph.names[el] + " ");
\r
250 System.out.println();
\r
251 componentSizes.adjustOrPutValue(els.length, 1, 1);*/
\r
252 Component component = new Component(els, neighbors);
\r
253 if(component.isIsolated())
\r
255 component.map(matching.aToB);
\r
256 component.canonicalize(matching.aGraph.names, matching.bGraph.names);
\r
257 ArrayList<int[]> values = aComponents.get(component.neighbors);
\r
258 if(values == null) {
\r
259 values = new ArrayList<int[]>(1);
\r
260 aComponents.put(component.neighbors, values);
\r
262 values.add(component.elements);
\r
264 /*componentSizes.forEachEntry(new TIntIntProcedure() {
\r
266 public boolean execute(int a, int b) {
\r
267 System.out.println("Components of size " + a + ": " + b);
\r
273 ArrayList<Component> bComponents = new ArrayList<Component>();
\r
275 Stat[][] neighbors = neighbors(matching.bToA, matching.bGraph.statements);
\r
276 for(int[] els : findComponents(matching.bToA, matching.bGraph.statements, matching.bGraph.inverses)) {
\r
277 Component component = new Component(els, neighbors);
\r
278 if(component.isIsolated())
\r
280 component.canonicalize(matching.bGraph.names, matching.bGraph.names);
\r
281 bComponents.add(component);
\r
285 for(Component c : bComponents) {
\r
286 ArrayList<int[]> candidates = aComponents.get(c.neighbors);
\r
287 if(candidates != null)
\r
288 for(int i=0;i<candidates.size();++i) {
\r
289 int[] els = candidates.get(i);
\r
291 matching.map(els, c.elements);
\r
292 if(matching.checkMatch(els, c.elements)) {
\r
293 if(candidates.size() == 1)
\r
294 aComponents.remove(c.neighbors);
\r
296 int last = candidates.size()-1;
\r
297 int[] temp = candidates.remove(last);
\r
299 candidates.set(i, temp);
\r
304 matching.unmap(els, c.elements);
\r