X-Git-Url: https://gerrit.simantics.org/r/gitweb?a=blobdiff_plain;f=bundles%2Forg.simantics.graph%2Fsrc%2Forg%2Fsimantics%2Fgraph%2Fmatching%2FComponentMatchingStrategy.java;h=dabd2e8df1e3e0a61c3cba5d940929caaca57c1a;hb=ff1337ff96700fb157ec789cbef88b8f40e03798;hp=ef354a1c3867d15cf23e71fb40d2ea4371302b35;hpb=969bd23cab98a79ca9101af33334000879fb60c5;p=simantics%2Fplatform.git

diff --git a/bundles/org.simantics.graph/src/org/simantics/graph/matching/ComponentMatchingStrategy.java b/bundles/org.simantics.graph/src/org/simantics/graph/matching/ComponentMatchingStrategy.java
index ef354a1c3..dabd2e8df 100644
--- a/bundles/org.simantics.graph/src/org/simantics/graph/matching/ComponentMatchingStrategy.java
+++ b/bundles/org.simantics.graph/src/org/simantics/graph/matching/ComponentMatchingStrategy.java
@@ -1,309 +1,309 @@
-package org.simantics.graph.matching;
-
-import gnu.trove.list.array.TIntArrayList;
-import gnu.trove.map.hash.THashMap;
-import gnu.trove.map.hash.TIntIntHashMap;
-import gnu.trove.map.hash.TIntObjectHashMap;
-import gnu.trove.procedure.TObjectProcedure;
-
-import java.util.ArrayList;
-import java.util.Arrays;
-import java.util.Comparator;
-
-/**
- * Matches isomorphic components of the not yet matched graphs together.
- * 
- * @author Hannu Niemistö
- */
-public enum ComponentMatchingStrategy implements GraphMatchingStrategy {
-	INSTANCE;
-
-	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;
-		}
-	}
-	
-	public static int[][] findComponents(int[] map, Stat[][] statements, TIntIntHashMap inverses) {
-		int resourceCount = map.length;
-		
-		UnionFind uf = new UnionFind(resourceCount);
-		for(int s=0;s<resourceCount;++s)
-			if(map[s] < 0) {
-				for(Stat stat : statements[s]) {
-					int o = stat.o;
-					if(s < o && map[o] < 0)
-						uf.merge(s, o);
-				}
-				/*if(inverses.containsKey(s))
-					uf.merge(s, inverses.get(s));
-					*/
-			}
-		
-		TIntObjectHashMap<TIntArrayList> components = new TIntObjectHashMap<TIntArrayList>();
-		for(int i=0;i<resourceCount;++i)
-			if(map[i] < 0) {
-				int c = uf.canonical(i);
-				TIntArrayList els = components.get(c);
-				if(els == null) {
-					els = new TIntArrayList(2);
-					components.put(c, els);
-				}
-				els.add(i);
-			}
-		
-		final int[][] result = new int[components.size()][];
-		components.forEachValue(new TObjectProcedure<TIntArrayList>() {
-			int i = 0;
-			@Override
-			public boolean execute(TIntArrayList els) {
-				result[i++] = els.toArray();
-				return true;
-			}
-		});
-		return result;
-	}	
-	
-	public static Stat[][] neighbors(int[] map, Stat[][] statements) {
-		int resourceCount = map.length;
-		Stat[][] neighbors = new Stat[resourceCount][];
-		
-		ArrayList<Stat> stats = new ArrayList<Stat>();
-		for(int s=0;s<resourceCount;++s) {
-			if(map[s] >= 0) {
-				neighbors[s] = Stat.NO_STATS;
-				continue;
-			}
-			
-			for(Stat stat : statements[s]) {
-				int pp = map[stat.p] >= 0 ? stat.p : -1;
-				int oo = map[stat.o] >= 0 ? stat.o : -1;				
-				stats.add(new Stat(pp, oo));
-			}
-			
-			if(stats.isEmpty())
-				neighbors[s] = Stat.NO_STATS;
-			else {
-				neighbors[s] = stats.toArray(new Stat[stats.size()]);
-				stats.clear();
-			}
-		}
-		
-		return neighbors;
-	}
-	
-	static class Component {
-		int[] elements;
-		Stat[][] neighbors;
-		
-		public Component(int[] elements, Stat[][] neighbors) {
-			this.elements = elements;
-			this.neighbors = new Stat[elements.length][];
-			for(int i=0;i<elements.length;++i)
-				this.neighbors[i] = neighbors[elements[i]];
-		}
-		
-		public void map(int[] map) {
-			for(Stat[] stats : neighbors)
-				for(Stat stat : stats)
-					stat.map(map);
-		}
-		
-		static class PP {
-			int element;
-			Stat[] stats;
-			
-			public PP(int element, Stat[] stats) {
-				this.element = element;
-				Arrays.sort(stats, Stat.STAT_COMPARATOR);
-				this.stats = stats;
-			}
-		}
-		
-		static final Comparator<PP> PP_COMPARATOR = new Comparator<PP>() {
-			@Override
-			public int compare(PP o1, PP o2) {
-				Stat[] stats1 = o1.stats;
-				Stat[] stats2 = o2.stats;
-				int l1 = stats1.length;
-				int l2 = stats2.length;
-				if(l1 < l2)
-					return -1;
-				else if(l1 > l2)
-					return 1;
-				for(int i=0;i<l1;++i) {
-					Stat s1 = stats1[i];
-					Stat s2 = stats2[i];
-					if(s1.p < s2.p)
-						return -1;
-					else if(s1.p > s2.p)
-						return 1;
-					else if(s1.o < s2.o)
-						return -1;
-					else if(s1.o > s2.o)
-						return 1;
-				}
-				return 0;
-			}			
-		};
-		
-		public void canonicalize(String[] elNames, String[] statNames) {
-			PP[] pps = new PP[elements.length];
-			for(int i=0;i<elements.length;++i)
-				pps[i] = new PP(elements[i], neighbors[i]);
-			Arrays.sort(pps, PP_COMPARATOR);
-			for(int i=0;i<pps.length-1;++i)
-				if(PP_COMPARATOR.compare(pps[i], pps[i+1]) == 0) {
-					System.out.println("AMB " + pps.length + " " + (elNames==statNames));
-					for(i=0;i<pps.length-1;++i) {
-						if(PP_COMPARATOR.compare(pps[i], pps[i+1]) == 0)
-							System.out.print(">   ");
-						else
-							System.out.print("    ");
-						System.out.println(elNames[pps[i].element]);
-						for(Stat stat : pps[i].stats)
-							System.out.println("        " + stat.toString(statNames));
-					}
-					break;
-				}
-			for(int i=0;i<elements.length;++i) {
-				PP pp = pps[i];
-				elements[i] = pp.element;
-				neighbors[i] = pp.stats;
-			}
-		}
-
-		public boolean isIsolated() {
-			for(Stat[] stats : neighbors)
-				if(stats.length > 0)
-					return false;
-			return true;
-		}
-	}
-	
-	static class TNeighbourObjectHashMap<T> extends THashMap<Stat[][], T> {
-		@Override
-		protected boolean equals(Object one, Object two) {
-			Stat[][] o1 = (Stat[][])one;
-			Stat[][] o2 = (Stat[][])two;
-			if(o1.length != o2.length)
-				return false;
-			for(int i=0;i<o1.length;++i) {
-				Stat[] ss1 = o1[i];
-				Stat[] ss2 = o2[i];
-				if(ss1.length != ss2.length)
-					return false;
-				for(int j=0;j<ss1.length;++j) {
-					Stat s1 = ss1[j];
-					Stat s2 = ss2[j];
-					if(s1.p != s2.p || s1.o != s2.o)
-						return false;
-				}
-			}
-			return true;
-		}
-		
-		@Override
-		protected int hash(Object obj) {
-			int result = 152433;
-			for(Stat[] stats : (Stat[][])obj)
-				for(Stat stat : stats)
-					result = (result*31 + stat.p)*31 + stat.o;
-			return result;
-		}
-	}
-	
-	@Override
-	public void applyTo(GraphMatching matching) {
-		System.out.println("ComponentMatchingStrategy");
-		TNeighbourObjectHashMap<ArrayList<int[]>> aComponents = new TNeighbourObjectHashMap<ArrayList<int[]>>(); 
-		{			
-			Stat[][] neighbors = neighbors(matching.aToB, matching.aGraph.statements);
-			//TIntIntHashMap componentSizes = new TIntIntHashMap();
-			for(int[] els : findComponents(matching.aToB, matching.aGraph.statements, matching.aGraph.inverses)) {
-				/*for(int el : els)
-					System.out.print(matching.aGraph.names[el] + " ");
-				System.out.println();
-				componentSizes.adjustOrPutValue(els.length, 1, 1);*/
-				Component component = new Component(els, neighbors);
-				if(component.isIsolated())
-					continue;
-				component.map(matching.aToB);
-				component.canonicalize(matching.aGraph.names, matching.bGraph.names);
-				ArrayList<int[]> values = aComponents.get(component.neighbors);
-				if(values == null) {
-					values = new ArrayList<int[]>(1);
-					aComponents.put(component.neighbors, values);
-				}
-				values.add(component.elements);
-			}
-			/*componentSizes.forEachEntry(new TIntIntProcedure() {				
-				@Override
-				public boolean execute(int a, int b) {
-					System.out.println("Components of size " + a + ": " + b);
-					return true;
-				}
-			});*/
-		}
-		
-		ArrayList<Component> bComponents = new ArrayList<Component>(); 
-		{
-			Stat[][] neighbors = neighbors(matching.bToA, matching.bGraph.statements);
-			for(int[] els : findComponents(matching.bToA, matching.bGraph.statements, matching.bGraph.inverses)) {
-				Component component = new Component(els, neighbors);
-				if(component.isIsolated())
-					continue;
-				component.canonicalize(matching.bGraph.names, matching.bGraph.names);
-				bComponents.add(component);
-			}
-		}
-		
-		for(Component c : bComponents) {
-			ArrayList<int[]> candidates = aComponents.get(c.neighbors);
-			if(candidates != null)
-				for(int i=0;i<candidates.size();++i) {
-					int[] els = candidates.get(i);
-					if(els != null) {
-						matching.map(els, c.elements);
-						if(matching.checkMatch(els, c.elements)) {
-							if(candidates.size() == 1)
-								aComponents.remove(c.neighbors);
-							else {
-								int last = candidates.size()-1;
-								int[] temp = candidates.remove(last);
-								if(i < last)
-									candidates.set(i, temp);
-							}
-						    break;
-						}
-						else
-							matching.unmap(els, c.elements);
-					}	
-				}			
-		}
-	}
-}
+package org.simantics.graph.matching;
+
+import gnu.trove.list.array.TIntArrayList;
+import gnu.trove.map.hash.THashMap;
+import gnu.trove.map.hash.TIntIntHashMap;
+import gnu.trove.map.hash.TIntObjectHashMap;
+import gnu.trove.procedure.TObjectProcedure;
+
+import java.util.ArrayList;
+import java.util.Arrays;
+import java.util.Comparator;
+
+/**
+ * Matches isomorphic components of the not yet matched graphs together.
+ * 
+ * @author Hannu Niemistö
+ */
+public enum ComponentMatchingStrategy implements GraphMatchingStrategy {
+	INSTANCE;
+
+	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;
+		}
+	}
+	
+	public static int[][] findComponents(int[] map, Stat[][] statements, TIntIntHashMap inverses) {
+		int resourceCount = map.length;
+		
+		UnionFind uf = new UnionFind(resourceCount);
+		for(int s=0;s<resourceCount;++s)
+			if(map[s] < 0) {
+				for(Stat stat : statements[s]) {
+					int o = stat.o;
+					if(s < o && map[o] < 0)
+						uf.merge(s, o);
+				}
+				/*if(inverses.containsKey(s))
+					uf.merge(s, inverses.get(s));
+					*/
+			}
+		
+		TIntObjectHashMap<TIntArrayList> components = new TIntObjectHashMap<TIntArrayList>();
+		for(int i=0;i<resourceCount;++i)
+			if(map[i] < 0) {
+				int c = uf.canonical(i);
+				TIntArrayList els = components.get(c);
+				if(els == null) {
+					els = new TIntArrayList(2);
+					components.put(c, els);
+				}
+				els.add(i);
+			}
+		
+		final int[][] result = new int[components.size()][];
+		components.forEachValue(new TObjectProcedure<TIntArrayList>() {
+			int i = 0;
+			@Override
+			public boolean execute(TIntArrayList els) {
+				result[i++] = els.toArray();
+				return true;
+			}
+		});
+		return result;
+	}	
+	
+	public static Stat[][] neighbors(int[] map, Stat[][] statements) {
+		int resourceCount = map.length;
+		Stat[][] neighbors = new Stat[resourceCount][];
+		
+		ArrayList<Stat> stats = new ArrayList<Stat>();
+		for(int s=0;s<resourceCount;++s) {
+			if(map[s] >= 0) {
+				neighbors[s] = Stat.NO_STATS;
+				continue;
+			}
+			
+			for(Stat stat : statements[s]) {
+				int pp = map[stat.p] >= 0 ? stat.p : -1;
+				int oo = map[stat.o] >= 0 ? stat.o : -1;				
+				stats.add(new Stat(pp, oo));
+			}
+			
+			if(stats.isEmpty())
+				neighbors[s] = Stat.NO_STATS;
+			else {
+				neighbors[s] = stats.toArray(new Stat[stats.size()]);
+				stats.clear();
+			}
+		}
+		
+		return neighbors;
+	}
+	
+	static class Component {
+		int[] elements;
+		Stat[][] neighbors;
+		
+		public Component(int[] elements, Stat[][] neighbors) {
+			this.elements = elements;
+			this.neighbors = new Stat[elements.length][];
+			for(int i=0;i<elements.length;++i)
+				this.neighbors[i] = neighbors[elements[i]];
+		}
+		
+		public void map(int[] map) {
+			for(Stat[] stats : neighbors)
+				for(Stat stat : stats)
+					stat.map(map);
+		}
+		
+		static class PP {
+			int element;
+			Stat[] stats;
+			
+			public PP(int element, Stat[] stats) {
+				this.element = element;
+				Arrays.sort(stats, Stat.STAT_COMPARATOR);
+				this.stats = stats;
+			}
+		}
+		
+		static final Comparator<PP> PP_COMPARATOR = new Comparator<PP>() {
+			@Override
+			public int compare(PP o1, PP o2) {
+				Stat[] stats1 = o1.stats;
+				Stat[] stats2 = o2.stats;
+				int l1 = stats1.length;
+				int l2 = stats2.length;
+				if(l1 < l2)
+					return -1;
+				else if(l1 > l2)
+					return 1;
+				for(int i=0;i<l1;++i) {
+					Stat s1 = stats1[i];
+					Stat s2 = stats2[i];
+					if(s1.p < s2.p)
+						return -1;
+					else if(s1.p > s2.p)
+						return 1;
+					else if(s1.o < s2.o)
+						return -1;
+					else if(s1.o > s2.o)
+						return 1;
+				}
+				return 0;
+			}			
+		};
+		
+		public void canonicalize(String[] elNames, String[] statNames) {
+			PP[] pps = new PP[elements.length];
+			for(int i=0;i<elements.length;++i)
+				pps[i] = new PP(elements[i], neighbors[i]);
+			Arrays.sort(pps, PP_COMPARATOR);
+			for(int i=0;i<pps.length-1;++i)
+				if(PP_COMPARATOR.compare(pps[i], pps[i+1]) == 0) {
+					System.out.println("AMB " + pps.length + " " + (elNames==statNames));
+					for(i=0;i<pps.length-1;++i) {
+						if(PP_COMPARATOR.compare(pps[i], pps[i+1]) == 0)
+							System.out.print(">   ");
+						else
+							System.out.print("    ");
+						System.out.println(elNames[pps[i].element]);
+						for(Stat stat : pps[i].stats)
+							System.out.println("        " + stat.toString(statNames));
+					}
+					break;
+				}
+			for(int i=0;i<elements.length;++i) {
+				PP pp = pps[i];
+				elements[i] = pp.element;
+				neighbors[i] = pp.stats;
+			}
+		}
+
+		public boolean isIsolated() {
+			for(Stat[] stats : neighbors)
+				if(stats.length > 0)
+					return false;
+			return true;
+		}
+	}
+	
+	static class TNeighbourObjectHashMap<T> extends THashMap<Stat[][], T> {
+		@Override
+		protected boolean equals(Object one, Object two) {
+			Stat[][] o1 = (Stat[][])one;
+			Stat[][] o2 = (Stat[][])two;
+			if(o1.length != o2.length)
+				return false;
+			for(int i=0;i<o1.length;++i) {
+				Stat[] ss1 = o1[i];
+				Stat[] ss2 = o2[i];
+				if(ss1.length != ss2.length)
+					return false;
+				for(int j=0;j<ss1.length;++j) {
+					Stat s1 = ss1[j];
+					Stat s2 = ss2[j];
+					if(s1.p != s2.p || s1.o != s2.o)
+						return false;
+				}
+			}
+			return true;
+		}
+		
+		@Override
+		protected int hash(Object obj) {
+			int result = 152433;
+			for(Stat[] stats : (Stat[][])obj)
+				for(Stat stat : stats)
+					result = (result*31 + stat.p)*31 + stat.o;
+			return result;
+		}
+	}
+	
+	@Override
+	public void applyTo(GraphMatching matching) {
+		System.out.println("ComponentMatchingStrategy");
+		TNeighbourObjectHashMap<ArrayList<int[]>> aComponents = new TNeighbourObjectHashMap<ArrayList<int[]>>(); 
+		{			
+			Stat[][] neighbors = neighbors(matching.aToB, matching.aGraph.statements);
+			//TIntIntHashMap componentSizes = new TIntIntHashMap();
+			for(int[] els : findComponents(matching.aToB, matching.aGraph.statements, matching.aGraph.inverses)) {
+				/*for(int el : els)
+					System.out.print(matching.aGraph.names[el] + " ");
+				System.out.println();
+				componentSizes.adjustOrPutValue(els.length, 1, 1);*/
+				Component component = new Component(els, neighbors);
+				if(component.isIsolated())
+					continue;
+				component.map(matching.aToB);
+				component.canonicalize(matching.aGraph.names, matching.bGraph.names);
+				ArrayList<int[]> values = aComponents.get(component.neighbors);
+				if(values == null) {
+					values = new ArrayList<int[]>(1);
+					aComponents.put(component.neighbors, values);
+				}
+				values.add(component.elements);
+			}
+			/*componentSizes.forEachEntry(new TIntIntProcedure() {				
+				@Override
+				public boolean execute(int a, int b) {
+					System.out.println("Components of size " + a + ": " + b);
+					return true;
+				}
+			});*/
+		}
+		
+		ArrayList<Component> bComponents = new ArrayList<Component>(); 
+		{
+			Stat[][] neighbors = neighbors(matching.bToA, matching.bGraph.statements);
+			for(int[] els : findComponents(matching.bToA, matching.bGraph.statements, matching.bGraph.inverses)) {
+				Component component = new Component(els, neighbors);
+				if(component.isIsolated())
+					continue;
+				component.canonicalize(matching.bGraph.names, matching.bGraph.names);
+				bComponents.add(component);
+			}
+		}
+		
+		for(Component c : bComponents) {
+			ArrayList<int[]> candidates = aComponents.get(c.neighbors);
+			if(candidates != null)
+				for(int i=0;i<candidates.size();++i) {
+					int[] els = candidates.get(i);
+					if(els != null) {
+						matching.map(els, c.elements);
+						if(matching.checkMatch(els, c.elements)) {
+							if(candidates.size() == 1)
+								aComponents.remove(c.neighbors);
+							else {
+								int last = candidates.size()-1;
+								int[] temp = candidates.remove(last);
+								if(i < last)
+									candidates.set(i, temp);
+							}
+						    break;
+						}
+						else
+							matching.unmap(els, c.elements);
+					}	
+				}			
+		}
+	}
+}