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