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