1 package org.simantics.graph.matching;
3 import gnu.trove.list.array.TIntArrayList;
4 import gnu.trove.map.hash.TObjectIntHashMap;
5 import gnu.trove.set.hash.TIntHashSet;
7 import java.util.Arrays;
8 import java.util.Comparator;
10 import org.simantics.databoard.binding.mutable.Variant;
12 public enum CanonicalizingMatchingStrategy implements GraphMatchingStrategy {
15 private static class Vertex {
21 public Vertex(int graph, int original, int pos, Stat[] stats) {
23 this.original = original;
29 private static final Comparator<Vertex> VERTEX_COMPARATOR = new Comparator<Vertex>() {
31 public int compare(Vertex o1, Vertex o2) {
38 Stat[] stats1 = o1.stats;
39 Stat[] stats2 = o2.stats;
40 if(stats1.length < stats2.length)
42 if(stats1.length > stats2.length)
44 for(int i=0;i<stats1.length;++i) {
45 int comp = Stat.STAT_COMPARATOR.compare(stats1[i], stats2[i]);
49 if(o1.graph < o2.graph)
51 if(o1.graph > o2.graph)
53 if(o1.original < o2.original)
55 if(o1.original > o2.original)
61 private static int[] generateMapA(int[] aToB) {
62 int[] map = new int[aToB.length];
63 for(int i=0;i<aToB.length;++i) {
73 private static int[] generateMapB(int[] bToA) {
74 int[] map = new int[bToA.length];
75 for(int i=0;i<bToA.length;++i) {
85 private static Vertex[] generateVertices(int graph, int[] map, Stat[][] statements) {
87 for(int s=0;s<map.length;++s)
90 Vertex[] vertices = new Vertex[size];
91 for(int s=0,i=0;s<map.length;++s)
93 Stat[] ns = statements[s];
94 Stat[] stats = new Stat[ns.length];
95 for(int j=0;j<ns.length;++j) {
97 stats[j] = new Stat(map[n.p], map[n.o]);
99 Arrays.sort(stats, Stat.STAT_COMPARATOR);
100 vertices[i++] = new Vertex(graph, s, 0, stats);
105 private static void updateVertices(Vertex[] vertices, int[] map, Stat[][] statements) {
106 for(int i=0;i<vertices.length;++i) {
107 int s = vertices[i].original;
108 Stat[] ns = statements[s];
109 Stat[] stats = vertices[i].stats;
110 for(int j=0;j<ns.length;++j) {
112 Stat stat = stats[j];
116 Arrays.sort(stats, Stat.STAT_COMPARATOR);
120 private static Vertex[] concat(Vertex[] as, Vertex[] bs) {
121 Vertex[] result = new Vertex[as.length + bs.length];
122 System.arraycopy(as, 0, result, 0, as.length);
123 System.arraycopy(bs, 0, result, as.length, bs.length);
127 static boolean equals(Stat[] stats1, Stat[] stats2) {
128 if(stats1.length != stats2.length)
130 for(int i=0;i<stats1.length;++i) {
131 Stat stat1 = stats1[i];
132 Stat stat2 = stats2[i];
133 if(stat1.p != stat2.p || stat1.o != stat2.o)
139 private static boolean updatePositions(Vertex[] can) {
140 boolean modified = false;
141 int oldPos = can[0].pos;
142 Vertex oldVertex = can[0];
143 for(int i=1;i<can.length;++i) {
144 Vertex curVertex = can[i];
145 int curPos = curVertex.pos;
146 if(curPos == oldPos) {
147 if(equals(oldVertex.stats, curVertex.stats))
148 curVertex.pos = oldVertex.pos;
156 oldVertex = curVertex;
161 private static void updateMap(Vertex[] vertices, int[] map) {
162 for(Vertex vertex : vertices)
163 map[vertex.original] = vertex.pos;
166 private static int[] groupPositions(Vertex[] can) {
167 TIntArrayList result = new TIntArrayList();
168 for(int i=0;i<can.length;++i)
171 result.add(can.length);
172 return result.toArray();
175 static class TByteArrayIntHashMap extends TObjectIntHashMap<byte[]> {
177 protected boolean equals(Object one, Object two) {
178 return Arrays.equals((byte[])one, (byte[])two);
182 protected int hash(Object obj) {
183 return Arrays.hashCode((byte[])obj);
187 private boolean separateByValues(Vertex[] can, int begin, int end, Variant[] aValues, Variant[] bValues) {
189 TObjectIntHashMap<Variant> valueIds = new TObjectIntHashMap<Variant>();
190 int[] ids = new int[end-begin];
191 for(int i=begin;i<end;++i) {
193 Variant value = v.graph==0 ? aValues[v.original] : bValues[v.original];
194 int valueId = valueIds.get(value);
196 valueIds.put(value, ++valueCount);
197 ids[i-begin] = valueCount-1;
200 ids[i-begin] = valueId-1;
203 Vertex[] vs = Arrays.copyOfRange(can, begin, end);
204 int[] temp = new int[valueCount];
208 for(int i=0;i<temp.length;++i) {
213 for(int i=0;i<ids.length;++i)
214 vs[i].pos = temp[ids[i]];
215 for(int i=0;i<ids.length;++i)
216 can[temp[ids[i]]++] = vs[i];
223 private boolean separateByValues(Vertex[] can, int[] groupPos, Variant[] aValues, Variant[] bValues) {
224 boolean modified = false;
225 for(int i=0;i<groupPos.length-1;++i) {
226 int begin = groupPos[i];
227 int end = groupPos[i+1];
229 modified |= separateByValues(can, begin, end, aValues, bValues);
234 private boolean hasBigGroups(Vertex[] can, int[] groupPos) {
235 for(int i=0;i<groupPos.length-1;++i) {
236 int begin = groupPos[i];
237 int end = groupPos[i+1];
238 if(end - begin > 2 && can[begin].graph == 0 && can[end-1].graph == 1)
244 static class UnionFind {
247 public UnionFind(int size) {
248 canonical = new int[size];
249 for(int i=0;i<size;++i)
253 public int canonical(int a) {
254 int b = canonical[a];
256 int c = canonical[b];
267 public void merge(int a, int b) {
274 private static void guessIsomorphism(Vertex[] can, int[] groupPos) {
275 UnionFind uf = new UnionFind(can.length);
276 for(int i=0;i<can.length;++i) {
277 uf.merge(i, can[i].pos);
278 for(Stat stat : can[i].stats) {
286 TIntHashSet done = new TIntHashSet();
287 for(int i=0;i<groupPos.length-1;++i) {
288 int begin = groupPos[i];
289 int end = groupPos[i+1];
290 if(end - begin > 2 && can[begin].graph == 0 && can[end-1].graph == 1) {
291 int c = uf.canonical(begin);
293 int middle = begin+1;
294 while(can[middle].graph==0)
297 for(j=0;begin+j < middle && middle+j < end;++j) {
298 can[begin+j].pos = begin + j*2;
299 can[middle+j].pos = begin + j*2;
302 for(;begin+j < middle;++j)
303 can[begin+j].pos = pos;
304 for(;middle+j < end;++j)
305 can[middle+j].pos = pos;
312 public void applyTo(GraphMatching matching) {
313 if(matching.size == matching.aGraph.resourceCount ||
314 matching.size == matching.bGraph.resourceCount)
316 long begin1 = System.nanoTime();
317 int[] aMap = generateMapA(matching.aToB);
318 int[] bMap = generateMapB(matching.bToA);
319 Vertex[] aVertices = generateVertices(0,
320 aMap, matching.aGraph.statements);
321 Vertex[] bVertices = generateVertices(1,
322 bMap, matching.bGraph.statements);
323 Vertex[] can = concat(aVertices, bVertices);
324 if(GraphMatching.TIMING)
325 System.out.println(" Init: " + (System.nanoTime()-begin1)*1e-6 + "ms");
327 int[] groupPos = null;
328 boolean doneSeparationByValues = false;
330 long begin2 = System.nanoTime();
331 Arrays.sort(can, VERTEX_COMPARATOR);
332 if(GraphMatching.TIMING)
333 System.out.println(" Sort: " + (System.nanoTime()-begin2)*1e-6 + "ms");
335 long begin3 = System.nanoTime();
336 if(!updatePositions(can)) {
337 groupPos = groupPositions(can);
338 if(!hasBigGroups(can, groupPos))
341 boolean modified = false;
342 if(!doneSeparationByValues) {
343 modified = separateByValues(can, groupPos, matching.aGraph.values, matching.bGraph.values);
344 doneSeparationByValues = true;
345 if(GraphMatching.TIMING)
346 System.out.println(" - separate by values");
350 guessIsomorphism(can, groupPos);
351 if(GraphMatching.TIMING)
352 System.out.println(" - guess isomorphism");
355 if(GraphMatching.TIMING)
356 System.out.println(" Update1: " + (System.nanoTime()-begin3)*1e-6 + "ms");
358 long begin4 = System.nanoTime();
359 updateMap(aVertices, aMap);
360 updateMap(bVertices, bMap);
361 if(GraphMatching.TIMING)
362 System.out.println(" Update2: " + (System.nanoTime()-begin4)*1e-6 + "ms");
363 long begin5 = System.nanoTime();
364 updateVertices(aVertices, aMap, matching.aGraph.statements);
365 updateVertices(bVertices, bMap, matching.bGraph.statements);
366 if(GraphMatching.TIMING)
367 System.out.println(" Update3: " + (System.nanoTime()-begin5)*1e-6 + "ms");
370 for(int i=0;i<groupPos.length-1;++i) {
371 int begin = groupPos[i];
372 int end = groupPos[i+1];
373 if(end - begin == 2) {
374 Vertex a = can[begin];
375 Vertex b = can[end-1];
376 if(a.graph == 0 && b.graph == 1)
377 matching.map(a.original, b.original);
381 if(GraphMatching.DEBUG)
382 for(int i=0;i<groupPos.length-1;++i) {
383 int begin = groupPos[i];
384 int end = groupPos[i+1];
385 if(end - begin > 2) {
386 System.out.println("----");
387 for(int j=begin;j<end;++j) {
388 if(can[j].graph == 0) {
389 int org = can[j].original;
390 String name = matching.aGraph.names[org];
391 System.out.println(name + " (A)");
392 for(Stat stat : matching.aGraph.statements[org])
393 System.out.println(" " + stat.toString(matching.aGraph.names));
394 Variant value = matching.aGraph.values[org];
396 System.out.println(" " + value);
399 int org = can[j].original;
400 String name = matching.bGraph.names[org];
401 System.out.println(name + " (B)");
402 for(Stat stat : matching.bGraph.statements[org])
403 System.out.println(" " + stat.toString(matching.bGraph.names));
404 Variant value = matching.bGraph.values[org];
406 System.out.println(" " + value);