X-Git-Url: https://gerrit.simantics.org/r/gitweb?a=blobdiff_plain;f=bundles%2Forg.simantics.graph%2Fsrc%2Forg%2Fsimantics%2Fgraph%2Fmatching%2FGraphMatching.java;h=4351577290684f153ca93b7337d366f8338bf17d;hb=aab6399f20c07b61a0dbf9614614f44a2e0ea325;hp=e68fa9322463f70ba752dd46f58ea7a1e5341ab3;hpb=969bd23cab98a79ca9101af33334000879fb60c5;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
index e68fa9322..435157729 100644
--- a/bundles/org.simantics.graph/src/org/simantics/graph/matching/GraphMatching.java
+++ b/bundles/org.simantics.graph/src/org/simantics/graph/matching/GraphMatching.java
@@ -1,185 +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);
-	}
-}
+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);
+	}
+}