1 package org.simantics.graph.matching;
\r
3 import gnu.trove.set.hash.THashSet;
\r
5 import java.util.Arrays;
\r
7 import org.simantics.graph.representation.TransferableGraph1;
\r
10 * Matching of two transferable graphs.
\r
12 * @author Hannu Niemistö
\r
14 public class GraphMatching {
\r
15 public static final boolean DEBUG = false;
\r
16 public static final boolean TIMING = false;
\r
20 CanonicalGraph aGraph;
\r
21 CanonicalGraph bGraph;
\r
22 protected int[] aToB;
\r
23 protected int[] bToA;
\r
26 public GraphMatching(TransferableGraph1 a, TransferableGraph1 b) {
\r
27 long begin = System.nanoTime();
\r
28 this.aGraph = new CanonicalGraph(a);
\r
29 this.bGraph = new CanonicalGraph(b);
\r
30 aToB = new int[this.aGraph.resourceCount];
\r
31 Arrays.fill(aToB, -1);
\r
32 bToA = new int[this.bGraph.resourceCount];
\r
33 Arrays.fill(bToA, -1);
\r
34 this.aOriginalSize = a.resourceCount;
\r
35 this.bOriginalSize = b.resourceCount;
\r
37 long end = System.nanoTime();
\r
38 System.out.println("Initialization: " + (end-begin)*1e-6 + "ms");
\r
42 public void print() {
\r
43 System.out.println("Resources in a: " + aGraph.resourceCount);
\r
44 System.out.println("Identities in a: " + aGraph.identities.length);
\r
45 System.out.println("Statements in a: " + aGraph.statements.length/6);
\r
46 System.out.println();
\r
47 System.out.println("Resources in b: " + bGraph.resourceCount);
\r
48 System.out.println("Identities in b: " + bGraph.identities.length);
\r
49 System.out.println("Statements in b: " + bGraph.statements.length/6);
\r
50 System.out.println();
\r
51 System.out.println("Match size: " + size());
\r
54 public int size() {
\r
58 public void recomputeSize() {
\r
66 public void map(int a, int b) {
\r
67 //if(aToB[a] < 0 && bToA[b] < 0) {
\r
71 /*if(aGraph.inverses.contains(a) && bGraph.inverses.contains(b) &&
\r
72 aGraph.inverses.get(a) != a) {
\r
73 int invA = aGraph.inverses.get(a);
\r
74 int invB = bGraph.inverses.get(b);
\r
81 System.out.println("ERR");*/
\r
84 public void map(int[] as, int[] bs) {
\r
85 for(int i=0;i<as.length;++i)
\r
89 public void unmap(int a, int b) {
\r
93 /*if(aGraph.inverses.contains(a) && bGraph.inverses.contains(b) &&
\r
94 aGraph.inverses.get(a) != a) {
\r
95 int invA = aGraph.inverses.get(a);
\r
96 int invB = bGraph.inverses.get(b);
\r
103 public void unmap(int[] as, int[] bs) {
\r
104 for(int i=0;i<as.length;++i)
\r
105 unmap(as[i], bs[i]);
\r
108 public boolean checkMatch(int[] as, int[] bs) {
\r
109 for(int i=0;i<as.length;++i)
\r
110 if(!checkMatch(as[i], bs[i]))
\r
115 public boolean checkMatch(int a, int b) {
\r
116 Stat[] aStats = aGraph.statements[a];
\r
117 Stat[] bStats = bGraph.statements[b];
\r
118 if(aStats.length != bStats.length)
\r
120 THashSet<Stat> mappedStats = new THashSet<Stat>();
\r
121 int[] aToB = this.aToB;
\r
122 for(Stat stat : aStats) {
\r
123 int mp = aToB[stat.p];
\r
124 int mo = aToB[stat.o];
\r
125 if(mp < 0 || mo < 0)
\r
127 mappedStats.add(new Stat(mp, mo));
\r
129 for(Stat stat : bStats)
\r
130 if(!mappedStats.contains(stat))
\r
135 public int maxSize() {
\r
136 return Math.min(aGraph.resourceCount, bGraph.resourceCount);
\r
139 public int[] getAToB() {
\r
143 public int[] getBToA() {
\r
147 public static int[] cut(int[] map, int domainSize, int rangeSize) {
\r
148 int[] newMap = new int[domainSize];
\r
149 for(int i=0;i<domainSize;++i) {
\r
151 if(temp >= rangeSize)
\r
159 public void match() {
\r
160 apply(IdentityMatchingStrategy.INSTANCE);
\r
161 apply(CanonicalizingMatchingStrategy.INSTANCE);
\r
163 if(size == maxSize())
\r
165 int curSize = size;
\r
166 apply(VotingMatchingStrategy.INSTANCE);
\r
167 if(size == curSize)
\r
170 aToB = cut(aToB, aOriginalSize, bOriginalSize);
\r
171 bToA = cut(bToA, bOriginalSize, aOriginalSize);
\r
174 private void apply(GraphMatchingStrategy strategy) {
\r
176 long begin = System.nanoTime();
\r
177 strategy.applyTo(this);
\r
178 long end = System.nanoTime();
\r
179 System.out.println(strategy.getClass().getSimpleName() + ": " +
\r
180 (end - begin)*1e-6 + "ms");
\r
183 strategy.applyTo(this);
\r