X-Git-Url: https://gerrit.simantics.org/r/gitweb?a=blobdiff_plain;f=bundles%2Forg.simantics.graph%2Fsrc%2Forg%2Fsimantics%2Fgraph%2Fmatching%2FGraphMatching.java;fp=bundles%2Forg.simantics.graph%2Fsrc%2Forg%2Fsimantics%2Fgraph%2Fmatching%2FGraphMatching.java;h=e68fa9322463f70ba752dd46f58ea7a1e5341ab3;hb=969bd23cab98a79ca9101af33334000879fb60c5;hp=0000000000000000000000000000000000000000;hpb=866dba5cd5a3929bbeae85991796acb212338a08;p=simantics%2Fplatform.git

diff --git a/bundles/org.simantics.graph/src/org/simantics/graph/matching/GraphMatching.java b/bundles/org.simantics.graph/src/org/simantics/graph/matching/GraphMatching.java
new file mode 100644
index 000000000..e68fa9322
--- /dev/null
+++ b/bundles/org.simantics.graph/src/org/simantics/graph/matching/GraphMatching.java
@@ -0,0 +1,185 @@
+package org.simantics.graph.matching;
+
+import gnu.trove.set.hash.THashSet;
+
+import java.util.Arrays;
+
+import org.simantics.graph.representation.TransferableGraph1;
+
+/**
+ * Matching of two transferable graphs.
+ * 
+ * @author Hannu Niemistö
+ */
+public class GraphMatching {
+	public static final boolean DEBUG = false;
+	public static final boolean TIMING = false;
+
+	int aOriginalSize;
+	int bOriginalSize;
+	CanonicalGraph aGraph;
+	CanonicalGraph bGraph;
+	protected int[] aToB;
+	protected int[] bToA;
+	int size;
+	
+	public GraphMatching(TransferableGraph1 a, TransferableGraph1 b) {
+		long begin = System.nanoTime();
+		this.aGraph = new CanonicalGraph(a);
+		this.bGraph = new CanonicalGraph(b);
+		aToB = new int[this.aGraph.resourceCount];
+		Arrays.fill(aToB, -1);
+		bToA = new int[this.bGraph.resourceCount];
+		Arrays.fill(bToA, -1);
+		this.aOriginalSize = a.resourceCount;
+		this.bOriginalSize = b.resourceCount;
+		if(TIMING) {
+			long end = System.nanoTime();
+			System.out.println("Initialization: " + (end-begin)*1e-6 + "ms");
+		}
+	}
+
+	public void print() {
+		System.out.println("Resources in a:  " + aGraph.resourceCount);
+		System.out.println("Identities in a: " + aGraph.identities.length);
+		System.out.println("Statements in a: " + aGraph.statements.length/6);
+		System.out.println();
+		System.out.println("Resources in b:  " + bGraph.resourceCount);
+		System.out.println("Identities in b: " + bGraph.identities.length);
+		System.out.println("Statements in b: " + bGraph.statements.length/6);
+		System.out.println();
+		System.out.println("Match size:      " + size());
+	}
+
+	public int size() {		
+		return size;
+	}
+	
+	public void recomputeSize() {
+		int count = 0;
+		for(int b : aToB)
+			if(b >= 0)
+				++count;
+		size = count;
+	}
+
+	public void map(int a, int b) {
+		//if(aToB[a] < 0 && bToA[b] < 0) {
+			++size;
+			aToB[a] = b;
+			bToA[b] = a;
+			/*if(aGraph.inverses.contains(a) && bGraph.inverses.contains(b) &&
+					aGraph.inverses.get(a) != a) {
+				int invA = aGraph.inverses.get(a);
+				int invB = bGraph.inverses.get(b);
+				++size;
+				aToB[invA] = invB;			
+				bToA[invB] = invA;			
+			}*/
+		/*}
+		else
+			System.out.println("ERR");*/
+	}
+	
+	public void map(int[] as, int[] bs) {
+		for(int i=0;i<as.length;++i)
+			map(as[i], bs[i]);
+	}
+	
+	public void unmap(int a, int b) {
+		--size;
+		aToB[a] = -1;
+		bToA[b] = -1;
+		/*if(aGraph.inverses.contains(a) && bGraph.inverses.contains(b) &&
+				aGraph.inverses.get(a) != a) {
+			int invA = aGraph.inverses.get(a);
+			int invB = bGraph.inverses.get(b);
+			--size;
+			aToB[invA] = -1;
+			bToA[invB] = -1;
+		}*/
+	}
+	
+	public void unmap(int[] as, int[] bs) {
+		for(int i=0;i<as.length;++i)
+			unmap(as[i], bs[i]);
+	}
+
+	public boolean checkMatch(int[] as, int[] bs) {
+		for(int i=0;i<as.length;++i)
+			if(!checkMatch(as[i], bs[i]))
+				return false;
+		return true;
+	}
+
+	public boolean checkMatch(int a, int b) {
+		Stat[] aStats = aGraph.statements[a];
+		Stat[] bStats = bGraph.statements[b];
+		if(aStats.length != bStats.length)
+			return false;
+		THashSet<Stat> mappedStats = new THashSet<Stat>();
+		int[] aToB = this.aToB;
+		for(Stat stat : aStats) {
+			int mp = aToB[stat.p];
+			int mo = aToB[stat.o];
+			if(mp < 0 || mo < 0)
+				return false;
+			mappedStats.add(new Stat(mp, mo));
+		}
+		for(Stat stat : bStats)
+			if(!mappedStats.contains(stat))
+				return false;
+		return true;
+	}
+	
+	public int maxSize() {
+		return Math.min(aGraph.resourceCount, bGraph.resourceCount);
+	}
+	
+	public int[] getAToB() {
+		return aToB;
+	}
+	
+	public int[] getBToA() {
+		return bToA;
+	}
+	
+	public static int[] cut(int[] map, int domainSize, int rangeSize) {
+		int[] newMap = new int[domainSize];
+		for(int i=0;i<domainSize;++i) {
+			int temp = map[i];
+			if(temp >= rangeSize)
+				newMap[i] = -1;
+			else
+				newMap[i] = temp;
+		}
+		return newMap;
+	}
+	
+	public void match() {
+		apply(IdentityMatchingStrategy.INSTANCE);
+		apply(CanonicalizingMatchingStrategy.INSTANCE);
+		while(true) {
+			if(size == maxSize())
+				break;
+			int curSize = size;
+			apply(VotingMatchingStrategy.INSTANCE);
+			if(size == curSize)
+				break;
+		}
+		aToB = cut(aToB, aOriginalSize, bOriginalSize);
+		bToA = cut(bToA, bOriginalSize, aOriginalSize);
+	}
+	
+	private void apply(GraphMatchingStrategy strategy) {
+		if(TIMING) {
+			long begin = System.nanoTime();
+			strategy.applyTo(this);
+			long end = System.nanoTime();		
+			System.out.println(strategy.getClass().getSimpleName() + ": " + 
+					(end - begin)*1e-6 + "ms");
+		}
+		else
+			strategy.applyTo(this);
+	}
+}