-package org.simantics.graph.matching;\r
-\r
-import gnu.trove.list.array.TIntArrayList;\r
-import gnu.trove.map.hash.TObjectIntHashMap;\r
-import gnu.trove.set.hash.TIntHashSet;\r
-\r
-import java.util.Arrays;\r
-import java.util.Comparator;\r
-\r
-import org.simantics.databoard.binding.mutable.Variant;\r
-\r
-public enum CanonicalizingMatchingStrategy implements GraphMatchingStrategy {\r
- INSTANCE;\r
-\r
- private static class Vertex {\r
- int graph;\r
- int original;\r
- int pos;\r
- Stat[] stats;\r
- \r
- public Vertex(int graph, int original, int pos, Stat[] stats) {\r
- this.graph = graph;\r
- this.original = original;\r
- this.pos = pos;\r
- this.stats = stats;\r
- }\r
- }\r
- \r
- private static final Comparator<Vertex> VERTEX_COMPARATOR = new Comparator<Vertex>() {\r
- @Override\r
- public int compare(Vertex o1, Vertex o2) {\r
- int pos1 = o1.pos;\r
- int pos2 = o2.pos;\r
- if(pos1 < pos2)\r
- return -1;\r
- if(pos1 > pos2)\r
- return 1;\r
- Stat[] stats1 = o1.stats;\r
- Stat[] stats2 = o2.stats;\r
- if(stats1.length < stats2.length)\r
- return -1;\r
- if(stats1.length > stats2.length)\r
- return 1;\r
- for(int i=0;i<stats1.length;++i) {\r
- int comp = Stat.STAT_COMPARATOR.compare(stats1[i], stats2[i]);\r
- if(comp != 0)\r
- return comp;\r
- }\r
- if(o1.graph < o2.graph)\r
- return -1;\r
- if(o1.graph > o2.graph)\r
- return 1; \r
- if(o1.original < o2.original)\r
- return -1;\r
- if(o1.original > o2.original)\r
- return 1;\r
- return 0;\r
- }\r
- };\r
- \r
- private static int[] generateMapA(int[] aToB) {\r
- int[] map = new int[aToB.length];\r
- for(int i=0;i<aToB.length;++i) {\r
- int c = aToB[i];\r
- if(c >= 0)\r
- map[i] = -1 - c;\r
- else\r
- map[i] = 0;\r
- }\r
- return map;\r
- }\r
- \r
- private static int[] generateMapB(int[] bToA) {\r
- int[] map = new int[bToA.length];\r
- for(int i=0;i<bToA.length;++i) {\r
- int c = bToA[i];\r
- if(c >= 0)\r
- map[i] = -1 - i;\r
- else\r
- map[i] = 0;\r
- }\r
- return map;\r
- }\r
- \r
- private static Vertex[] generateVertices(int graph, int[] map, Stat[][] statements) {\r
- int size = 0;\r
- for(int s=0;s<map.length;++s)\r
- if(map[s] == 0)\r
- ++size;\r
- Vertex[] vertices = new Vertex[size];\r
- for(int s=0,i=0;s<map.length;++s)\r
- if(map[s] == 0) {\r
- Stat[] ns = statements[s];\r
- Stat[] stats = new Stat[ns.length];\r
- for(int j=0;j<ns.length;++j) {\r
- Stat n = ns[j];\r
- stats[j] = new Stat(map[n.p], map[n.o]);\r
- }\r
- Arrays.sort(stats, Stat.STAT_COMPARATOR);\r
- vertices[i++] = new Vertex(graph, s, 0, stats);\r
- }\r
- return vertices;\r
- }\r
- \r
- private static void updateVertices(Vertex[] vertices, int[] map, Stat[][] statements) {\r
- for(int i=0;i<vertices.length;++i) {\r
- int s = vertices[i].original;\r
- Stat[] ns = statements[s];\r
- Stat[] stats = vertices[i].stats;\r
- for(int j=0;j<ns.length;++j) {\r
- Stat n = ns[j];\r
- Stat stat = stats[j];\r
- stat.p = map[n.p];\r
- stat.o = map[n.o];\r
- }\r
- Arrays.sort(stats, Stat.STAT_COMPARATOR);\r
- }\r
- }\r
- \r
- private static Vertex[] concat(Vertex[] as, Vertex[] bs) {\r
- Vertex[] result = new Vertex[as.length + bs.length];\r
- System.arraycopy(as, 0, result, 0, as.length);\r
- System.arraycopy(bs, 0, result, as.length, bs.length);\r
- return result;\r
- }\r
- \r
- static boolean equals(Stat[] stats1, Stat[] stats2) {\r
- if(stats1.length != stats2.length)\r
- return false;\r
- for(int i=0;i<stats1.length;++i) {\r
- Stat stat1 = stats1[i];\r
- Stat stat2 = stats2[i];\r
- if(stat1.p != stat2.p || stat1.o != stat2.o)\r
- return false;\r
- }\r
- return true;\r
- }\r
- \r
- private static boolean updatePositions(Vertex[] can) {\r
- boolean modified = false;\r
- int oldPos = can[0].pos;\r
- Vertex oldVertex = can[0];\r
- for(int i=1;i<can.length;++i) {\r
- Vertex curVertex = can[i];\r
- int curPos = curVertex.pos;\r
- if(curPos == oldPos) {\r
- if(equals(oldVertex.stats, curVertex.stats))\r
- curVertex.pos = oldVertex.pos;\r
- else {\r
- curVertex.pos = i;\r
- modified = true;\r
- }\r
- }\r
- else\r
- oldPos = curPos;\r
- oldVertex = curVertex;\r
- }\r
- return modified;\r
- }\r
- \r
- private static void updateMap(Vertex[] vertices, int[] map) {\r
- for(Vertex vertex : vertices)\r
- map[vertex.original] = vertex.pos;\r
- }\r
-\r
- private static int[] groupPositions(Vertex[] can) {\r
- TIntArrayList result = new TIntArrayList();\r
- for(int i=0;i<can.length;++i)\r
- if(can[i].pos == i)\r
- result.add(i);\r
- result.add(can.length);\r
- return result.toArray();\r
- } \r
- \r
- static class TByteArrayIntHashMap extends TObjectIntHashMap<byte[]> {\r
- @Override\r
- protected boolean equals(Object one, Object two) {\r
- return Arrays.equals((byte[])one, (byte[])two);\r
- }\r
- \r
- @Override\r
- protected int hash(Object obj) {\r
- return Arrays.hashCode((byte[])obj);\r
- }\r
- }\r
- \r
- private boolean separateByValues(Vertex[] can, int begin, int end, Variant[] aValues, Variant[] bValues) { \r
- int valueCount = 0;\r
- TObjectIntHashMap<Variant> valueIds = new TObjectIntHashMap<Variant>();\r
- int[] ids = new int[end-begin];\r
- for(int i=begin;i<end;++i) {\r
- Vertex v = can[i];\r
- Variant value = v.graph==0 ? aValues[v.original] : bValues[v.original];\r
- int valueId = valueIds.get(value);\r
- if(valueId == 0) {\r
- valueIds.put(value, ++valueCount);\r
- ids[i-begin] = valueCount-1;\r
- }\r
- else\r
- ids[i-begin] = valueId-1;\r
- }\r
- if(valueCount > 1) {\r
- Vertex[] vs = Arrays.copyOfRange(can, begin, end);\r
- int[] temp = new int[valueCount];\r
- for(int id : ids)\r
- ++temp[id];\r
- int cur = begin;\r
- for(int i=0;i<temp.length;++i) {\r
- int count = temp[i];\r
- temp[i] = cur;\r
- cur += count;\r
- }\r
- for(int i=0;i<ids.length;++i)\r
- vs[i].pos = temp[ids[i]];\r
- for(int i=0;i<ids.length;++i)\r
- can[temp[ids[i]]++] = vs[i];\r
- return true;\r
- }\r
- else\r
- return false;\r
- }\r
- \r
- private boolean separateByValues(Vertex[] can, int[] groupPos, Variant[] aValues, Variant[] bValues) {\r
- boolean modified = false;\r
- for(int i=0;i<groupPos.length-1;++i) {\r
- int begin = groupPos[i];\r
- int end = groupPos[i+1];\r
- if(end - begin > 2)\r
- modified |= separateByValues(can, begin, end, aValues, bValues); \r
- }\r
- return modified;\r
- }\r
- \r
- private boolean hasBigGroups(Vertex[] can, int[] groupPos) {\r
- for(int i=0;i<groupPos.length-1;++i) {\r
- int begin = groupPos[i];\r
- int end = groupPos[i+1];\r
- if(end - begin > 2 && can[begin].graph == 0 && can[end-1].graph == 1)\r
- return true;\r
- }\r
- return false;\r
- }\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
- private static void guessIsomorphism(Vertex[] can, int[] groupPos) {\r
- UnionFind uf = new UnionFind(can.length);\r
- for(int i=0;i<can.length;++i) {\r
- uf.merge(i, can[i].pos);\r
- for(Stat stat : can[i].stats) {\r
- if(stat.p >= 0)\r
- uf.merge(i, stat.p);\r
- if(stat.o >= 0)\r
- uf.merge(i, stat.o);\r
- }\r
- }\r
- \r
- TIntHashSet done = new TIntHashSet();\r
- for(int i=0;i<groupPos.length-1;++i) {\r
- int begin = groupPos[i];\r
- int end = groupPos[i+1];\r
- if(end - begin > 2 && can[begin].graph == 0 && can[end-1].graph == 1) {\r
- int c = uf.canonical(begin);\r
- if(done.add(c)) {\r
- int middle = begin+1;\r
- while(can[middle].graph==0)\r
- ++middle;\r
- int j;\r
- for(j=0;begin+j < middle && middle+j < end;++j) {\r
- can[begin+j].pos = begin + j*2;\r
- can[middle+j].pos = begin + j*2;\r
- }\r
- int pos = begin+j*2; \r
- for(;begin+j < middle;++j)\r
- can[begin+j].pos = pos;\r
- for(;middle+j < end;++j)\r
- can[middle+j].pos = pos;\r
- }\r
- }\r
- }\r
- }\r
- \r
- @Override\r
- public void applyTo(GraphMatching matching) {\r
- if(matching.size == matching.aGraph.resourceCount ||\r
- matching.size == matching.bGraph.resourceCount)\r
- return;\r
- long begin1 = System.nanoTime();\r
- int[] aMap = generateMapA(matching.aToB);\r
- int[] bMap = generateMapB(matching.bToA);\r
- Vertex[] aVertices = generateVertices(0,\r
- aMap, matching.aGraph.statements);\r
- Vertex[] bVertices = generateVertices(1,\r
- bMap, matching.bGraph.statements);\r
- Vertex[] can = concat(aVertices, bVertices);\r
- if(GraphMatching.TIMING)\r
- System.out.println(" Init: " + (System.nanoTime()-begin1)*1e-6 + "ms");\r
- \r
- int[] groupPos = null;\r
- boolean doneSeparationByValues = false;\r
- while(true) {\r
- long begin2 = System.nanoTime();\r
- Arrays.sort(can, VERTEX_COMPARATOR);\r
- if(GraphMatching.TIMING)\r
- System.out.println(" Sort: " + (System.nanoTime()-begin2)*1e-6 + "ms");\r
- \r
- long begin3 = System.nanoTime();\r
- if(!updatePositions(can)) { \r
- groupPos = groupPositions(can); \r
- if(!hasBigGroups(can, groupPos))\r
- break;\r
- \r
- boolean modified = false;\r
- if(!doneSeparationByValues) {\r
- modified = separateByValues(can, groupPos, matching.aGraph.values, matching.bGraph.values); \r
- doneSeparationByValues = true;\r
- if(GraphMatching.TIMING)\r
- System.out.println(" - separate by values");\r
- }\r
- \r
- if(!modified) {\r
- guessIsomorphism(can, groupPos);\r
- if(GraphMatching.TIMING)\r
- System.out.println(" - guess isomorphism");\r
- }\r
- }\r
- if(GraphMatching.TIMING)\r
- System.out.println(" Update1: " + (System.nanoTime()-begin3)*1e-6 + "ms");\r
- \r
- long begin4 = System.nanoTime();\r
- updateMap(aVertices, aMap); \r
- updateMap(bVertices, bMap);\r
- if(GraphMatching.TIMING)\r
- System.out.println(" Update2: " + (System.nanoTime()-begin4)*1e-6 + "ms"); \r
- long begin5 = System.nanoTime();\r
- updateVertices(aVertices, aMap, matching.aGraph.statements);\r
- updateVertices(bVertices, bMap, matching.bGraph.statements);\r
- if(GraphMatching.TIMING)\r
- System.out.println(" Update3: " + (System.nanoTime()-begin5)*1e-6 + "ms");\r
- }\r
- \r
- for(int i=0;i<groupPos.length-1;++i) {\r
- int begin = groupPos[i];\r
- int end = groupPos[i+1];\r
- if(end - begin == 2) {\r
- Vertex a = can[begin];\r
- Vertex b = can[end-1];\r
- if(a.graph == 0 && b.graph == 1)\r
- matching.map(a.original, b.original);\r
- }\r
- }\r
- \r
- if(GraphMatching.DEBUG)\r
- for(int i=0;i<groupPos.length-1;++i) {\r
- int begin = groupPos[i];\r
- int end = groupPos[i+1];\r
- if(end - begin > 2) { \r
- System.out.println("----");\r
- for(int j=begin;j<end;++j) {\r
- if(can[j].graph == 0) {\r
- int org = can[j].original;\r
- String name = matching.aGraph.names[org];\r
- System.out.println(name + " (A)");\r
- for(Stat stat : matching.aGraph.statements[org])\r
- System.out.println(" " + stat.toString(matching.aGraph.names));\r
- Variant value = matching.aGraph.values[org];\r
- if(value != null)\r
- System.out.println(" " + value);\r
- }\r
- else {\r
- int org = can[j].original;\r
- String name = matching.bGraph.names[org];\r
- System.out.println(name + " (B)");\r
- for(Stat stat : matching.bGraph.statements[org])\r
- System.out.println(" " + stat.toString(matching.bGraph.names));\r
- Variant value = matching.bGraph.values[org];\r
- if(value != null)\r
- System.out.println(" " + value);\r
- }\r
- }\r
- }\r
- }\r
- }\r
-}\r
+package org.simantics.graph.matching;
+
+import gnu.trove.list.array.TIntArrayList;
+import gnu.trove.map.hash.TObjectIntHashMap;
+import gnu.trove.set.hash.TIntHashSet;
+
+import java.util.Arrays;
+import java.util.Comparator;
+
+import org.simantics.databoard.binding.mutable.Variant;
+
+public enum CanonicalizingMatchingStrategy implements GraphMatchingStrategy {
+ INSTANCE;
+
+ private static class Vertex {
+ int graph;
+ int original;
+ int pos;
+ Stat[] stats;
+
+ public Vertex(int graph, int original, int pos, Stat[] stats) {
+ this.graph = graph;
+ this.original = original;
+ this.pos = pos;
+ this.stats = stats;
+ }
+ }
+
+ private static final Comparator<Vertex> VERTEX_COMPARATOR = new Comparator<Vertex>() {
+ @Override
+ public int compare(Vertex o1, Vertex o2) {
+ int pos1 = o1.pos;
+ int pos2 = o2.pos;
+ if(pos1 < pos2)
+ return -1;
+ if(pos1 > pos2)
+ return 1;
+ Stat[] stats1 = o1.stats;
+ Stat[] stats2 = o2.stats;
+ if(stats1.length < stats2.length)
+ return -1;
+ if(stats1.length > stats2.length)
+ return 1;
+ for(int i=0;i<stats1.length;++i) {
+ int comp = Stat.STAT_COMPARATOR.compare(stats1[i], stats2[i]);
+ if(comp != 0)
+ return comp;
+ }
+ if(o1.graph < o2.graph)
+ return -1;
+ if(o1.graph > o2.graph)
+ return 1;
+ if(o1.original < o2.original)
+ return -1;
+ if(o1.original > o2.original)
+ return 1;
+ return 0;
+ }
+ };
+
+ private static int[] generateMapA(int[] aToB) {
+ int[] map = new int[aToB.length];
+ for(int i=0;i<aToB.length;++i) {
+ int c = aToB[i];
+ if(c >= 0)
+ map[i] = -1 - c;
+ else
+ map[i] = 0;
+ }
+ return map;
+ }
+
+ private static int[] generateMapB(int[] bToA) {
+ int[] map = new int[bToA.length];
+ for(int i=0;i<bToA.length;++i) {
+ int c = bToA[i];
+ if(c >= 0)
+ map[i] = -1 - i;
+ else
+ map[i] = 0;
+ }
+ return map;
+ }
+
+ private static Vertex[] generateVertices(int graph, int[] map, Stat[][] statements) {
+ int size = 0;
+ for(int s=0;s<map.length;++s)
+ if(map[s] == 0)
+ ++size;
+ Vertex[] vertices = new Vertex[size];
+ for(int s=0,i=0;s<map.length;++s)
+ if(map[s] == 0) {
+ Stat[] ns = statements[s];
+ Stat[] stats = new Stat[ns.length];
+ for(int j=0;j<ns.length;++j) {
+ Stat n = ns[j];
+ stats[j] = new Stat(map[n.p], map[n.o]);
+ }
+ Arrays.sort(stats, Stat.STAT_COMPARATOR);
+ vertices[i++] = new Vertex(graph, s, 0, stats);
+ }
+ return vertices;
+ }
+
+ private static void updateVertices(Vertex[] vertices, int[] map, Stat[][] statements) {
+ for(int i=0;i<vertices.length;++i) {
+ int s = vertices[i].original;
+ Stat[] ns = statements[s];
+ Stat[] stats = vertices[i].stats;
+ for(int j=0;j<ns.length;++j) {
+ Stat n = ns[j];
+ Stat stat = stats[j];
+ stat.p = map[n.p];
+ stat.o = map[n.o];
+ }
+ Arrays.sort(stats, Stat.STAT_COMPARATOR);
+ }
+ }
+
+ private static Vertex[] concat(Vertex[] as, Vertex[] bs) {
+ Vertex[] result = new Vertex[as.length + bs.length];
+ System.arraycopy(as, 0, result, 0, as.length);
+ System.arraycopy(bs, 0, result, as.length, bs.length);
+ return result;
+ }
+
+ static boolean equals(Stat[] stats1, Stat[] stats2) {
+ if(stats1.length != stats2.length)
+ return false;
+ for(int i=0;i<stats1.length;++i) {
+ Stat stat1 = stats1[i];
+ Stat stat2 = stats2[i];
+ if(stat1.p != stat2.p || stat1.o != stat2.o)
+ return false;
+ }
+ return true;
+ }
+
+ private static boolean updatePositions(Vertex[] can) {
+ boolean modified = false;
+ int oldPos = can[0].pos;
+ Vertex oldVertex = can[0];
+ for(int i=1;i<can.length;++i) {
+ Vertex curVertex = can[i];
+ int curPos = curVertex.pos;
+ if(curPos == oldPos) {
+ if(equals(oldVertex.stats, curVertex.stats))
+ curVertex.pos = oldVertex.pos;
+ else {
+ curVertex.pos = i;
+ modified = true;
+ }
+ }
+ else
+ oldPos = curPos;
+ oldVertex = curVertex;
+ }
+ return modified;
+ }
+
+ private static void updateMap(Vertex[] vertices, int[] map) {
+ for(Vertex vertex : vertices)
+ map[vertex.original] = vertex.pos;
+ }
+
+ private static int[] groupPositions(Vertex[] can) {
+ TIntArrayList result = new TIntArrayList();
+ for(int i=0;i<can.length;++i)
+ if(can[i].pos == i)
+ result.add(i);
+ result.add(can.length);
+ return result.toArray();
+ }
+
+ static class TByteArrayIntHashMap extends TObjectIntHashMap<byte[]> {
+ @Override
+ protected boolean equals(Object one, Object two) {
+ return Arrays.equals((byte[])one, (byte[])two);
+ }
+
+ @Override
+ protected int hash(Object obj) {
+ return Arrays.hashCode((byte[])obj);
+ }
+ }
+
+ private boolean separateByValues(Vertex[] can, int begin, int end, Variant[] aValues, Variant[] bValues) {
+ int valueCount = 0;
+ TObjectIntHashMap<Variant> valueIds = new TObjectIntHashMap<Variant>();
+ int[] ids = new int[end-begin];
+ for(int i=begin;i<end;++i) {
+ Vertex v = can[i];
+ Variant value = v.graph==0 ? aValues[v.original] : bValues[v.original];
+ int valueId = valueIds.get(value);
+ if(valueId == 0) {
+ valueIds.put(value, ++valueCount);
+ ids[i-begin] = valueCount-1;
+ }
+ else
+ ids[i-begin] = valueId-1;
+ }
+ if(valueCount > 1) {
+ Vertex[] vs = Arrays.copyOfRange(can, begin, end);
+ int[] temp = new int[valueCount];
+ for(int id : ids)
+ ++temp[id];
+ int cur = begin;
+ for(int i=0;i<temp.length;++i) {
+ int count = temp[i];
+ temp[i] = cur;
+ cur += count;
+ }
+ for(int i=0;i<ids.length;++i)
+ vs[i].pos = temp[ids[i]];
+ for(int i=0;i<ids.length;++i)
+ can[temp[ids[i]]++] = vs[i];
+ return true;
+ }
+ else
+ return false;
+ }
+
+ private boolean separateByValues(Vertex[] can, int[] groupPos, Variant[] aValues, Variant[] bValues) {
+ boolean modified = false;
+ for(int i=0;i<groupPos.length-1;++i) {
+ int begin = groupPos[i];
+ int end = groupPos[i+1];
+ if(end - begin > 2)
+ modified |= separateByValues(can, begin, end, aValues, bValues);
+ }
+ return modified;
+ }
+
+ private boolean hasBigGroups(Vertex[] can, int[] groupPos) {
+ for(int i=0;i<groupPos.length-1;++i) {
+ int begin = groupPos[i];
+ int end = groupPos[i+1];
+ if(end - begin > 2 && can[begin].graph == 0 && can[end-1].graph == 1)
+ return true;
+ }
+ return false;
+ }
+
+ 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;
+ }
+ }
+
+ private static void guessIsomorphism(Vertex[] can, int[] groupPos) {
+ UnionFind uf = new UnionFind(can.length);
+ for(int i=0;i<can.length;++i) {
+ uf.merge(i, can[i].pos);
+ for(Stat stat : can[i].stats) {
+ if(stat.p >= 0)
+ uf.merge(i, stat.p);
+ if(stat.o >= 0)
+ uf.merge(i, stat.o);
+ }
+ }
+
+ TIntHashSet done = new TIntHashSet();
+ for(int i=0;i<groupPos.length-1;++i) {
+ int begin = groupPos[i];
+ int end = groupPos[i+1];
+ if(end - begin > 2 && can[begin].graph == 0 && can[end-1].graph == 1) {
+ int c = uf.canonical(begin);
+ if(done.add(c)) {
+ int middle = begin+1;
+ while(can[middle].graph==0)
+ ++middle;
+ int j;
+ for(j=0;begin+j < middle && middle+j < end;++j) {
+ can[begin+j].pos = begin + j*2;
+ can[middle+j].pos = begin + j*2;
+ }
+ int pos = begin+j*2;
+ for(;begin+j < middle;++j)
+ can[begin+j].pos = pos;
+ for(;middle+j < end;++j)
+ can[middle+j].pos = pos;
+ }
+ }
+ }
+ }
+
+ @Override
+ public void applyTo(GraphMatching matching) {
+ if(matching.size == matching.aGraph.resourceCount ||
+ matching.size == matching.bGraph.resourceCount)
+ return;
+ long begin1 = System.nanoTime();
+ int[] aMap = generateMapA(matching.aToB);
+ int[] bMap = generateMapB(matching.bToA);
+ Vertex[] aVertices = generateVertices(0,
+ aMap, matching.aGraph.statements);
+ Vertex[] bVertices = generateVertices(1,
+ bMap, matching.bGraph.statements);
+ Vertex[] can = concat(aVertices, bVertices);
+ if(GraphMatching.TIMING)
+ System.out.println(" Init: " + (System.nanoTime()-begin1)*1e-6 + "ms");
+
+ int[] groupPos = null;
+ boolean doneSeparationByValues = false;
+ while(true) {
+ long begin2 = System.nanoTime();
+ Arrays.sort(can, VERTEX_COMPARATOR);
+ if(GraphMatching.TIMING)
+ System.out.println(" Sort: " + (System.nanoTime()-begin2)*1e-6 + "ms");
+
+ long begin3 = System.nanoTime();
+ if(!updatePositions(can)) {
+ groupPos = groupPositions(can);
+ if(!hasBigGroups(can, groupPos))
+ break;
+
+ boolean modified = false;
+ if(!doneSeparationByValues) {
+ modified = separateByValues(can, groupPos, matching.aGraph.values, matching.bGraph.values);
+ doneSeparationByValues = true;
+ if(GraphMatching.TIMING)
+ System.out.println(" - separate by values");
+ }
+
+ if(!modified) {
+ guessIsomorphism(can, groupPos);
+ if(GraphMatching.TIMING)
+ System.out.println(" - guess isomorphism");
+ }
+ }
+ if(GraphMatching.TIMING)
+ System.out.println(" Update1: " + (System.nanoTime()-begin3)*1e-6 + "ms");
+
+ long begin4 = System.nanoTime();
+ updateMap(aVertices, aMap);
+ updateMap(bVertices, bMap);
+ if(GraphMatching.TIMING)
+ System.out.println(" Update2: " + (System.nanoTime()-begin4)*1e-6 + "ms");
+ long begin5 = System.nanoTime();
+ updateVertices(aVertices, aMap, matching.aGraph.statements);
+ updateVertices(bVertices, bMap, matching.bGraph.statements);
+ if(GraphMatching.TIMING)
+ System.out.println(" Update3: " + (System.nanoTime()-begin5)*1e-6 + "ms");
+ }
+
+ for(int i=0;i<groupPos.length-1;++i) {
+ int begin = groupPos[i];
+ int end = groupPos[i+1];
+ if(end - begin == 2) {
+ Vertex a = can[begin];
+ Vertex b = can[end-1];
+ if(a.graph == 0 && b.graph == 1)
+ matching.map(a.original, b.original);
+ }
+ }
+
+ if(GraphMatching.DEBUG)
+ for(int i=0;i<groupPos.length-1;++i) {
+ int begin = groupPos[i];
+ int end = groupPos[i+1];
+ if(end - begin > 2) {
+ System.out.println("----");
+ for(int j=begin;j<end;++j) {
+ if(can[j].graph == 0) {
+ int org = can[j].original;
+ String name = matching.aGraph.names[org];
+ System.out.println(name + " (A)");
+ for(Stat stat : matching.aGraph.statements[org])
+ System.out.println(" " + stat.toString(matching.aGraph.names));
+ Variant value = matching.aGraph.values[org];
+ if(value != null)
+ System.out.println(" " + value);
+ }
+ else {
+ int org = can[j].original;
+ String name = matching.bGraph.names[org];
+ System.out.println(name + " (B)");
+ for(Stat stat : matching.bGraph.statements[org])
+ System.out.println(" " + stat.toString(matching.bGraph.names));
+ Variant value = matching.bGraph.values[org];
+ if(value != null)
+ System.out.println(" " + value);
+ }
+ }
+ }
+ }
+ }
+}
Code Review / simantics / platform.git / blobdiff