X-Git-Url: https://gerrit.simantics.org/r/gitweb?a=blobdiff_plain;f=bundles%2Forg.simantics.graph%2Fsrc%2Forg%2Fsimantics%2Fgraph%2Fmatching%2FCanonicalizingMatchingStrategy.java;h=5ceb87b6ad0728efa51484a157531b3909e3e4f7;hb=aab6399f20c07b61a0dbf9614614f44a2e0ea325;hp=06ecb3c3e604c2eb43f8befbc1dc840f15ac9317;hpb=969bd23cab98a79ca9101af33334000879fb60c5;p=simantics%2Fplatform.git

diff --git a/bundles/org.simantics.graph/src/org/simantics/graph/matching/CanonicalizingMatchingStrategy.java b/bundles/org.simantics.graph/src/org/simantics/graph/matching/CanonicalizingMatchingStrategy.java
index 06ecb3c3e..5ceb87b6a 100644
--- a/bundles/org.simantics.graph/src/org/simantics/graph/matching/CanonicalizingMatchingStrategy.java
+++ b/bundles/org.simantics.graph/src/org/simantics/graph/matching/CanonicalizingMatchingStrategy.java
@@ -1,412 +1,412 @@
-package org.simantics.graph.matching;
-
-import gnu.trove.list.array.TIntArrayList;
-import gnu.trove.map.hash.TObjectIntHashMap;
-import gnu.trove.set.hash.TIntHashSet;
-
-import java.util.Arrays;
-import java.util.Comparator;
-
-import org.simantics.databoard.binding.mutable.Variant;
-
-public enum CanonicalizingMatchingStrategy implements GraphMatchingStrategy {
-	INSTANCE;
-
-	private static class Vertex {
-		int graph;
-		int original;
-		int pos;
-		Stat[] stats;
-		
-		public Vertex(int graph, int original, int pos, Stat[] stats) {
-			this.graph = graph;
-			this.original = original;
-			this.pos = pos;
-			this.stats = stats;
-		}
-	}
-	
-	private static final Comparator<Vertex> VERTEX_COMPARATOR = new Comparator<Vertex>() {
-		@Override
-		public int compare(Vertex o1, Vertex o2) {
-			int pos1 = o1.pos;
-			int pos2 = o2.pos;
-			if(pos1 < pos2)
-				return -1;
-			if(pos1 > pos2)
-				return 1;
-			Stat[] stats1 = o1.stats;
-			Stat[] stats2 = o2.stats;
-			if(stats1.length < stats2.length)
-				return -1;
-			if(stats1.length > stats2.length)
-				return 1;
-			for(int i=0;i<stats1.length;++i) {
-				int comp = Stat.STAT_COMPARATOR.compare(stats1[i], stats2[i]);
-				if(comp != 0)
-					return comp;
-			}
-			if(o1.graph < o2.graph)
-				return -1;
-			if(o1.graph > o2.graph)
-				return 1;			
-			if(o1.original < o2.original)
-				return -1;
-			if(o1.original > o2.original)
-				return 1;
-			return 0;
-		}
-	};
-	
-	private static int[] generateMapA(int[] aToB) {
-		int[] map = new int[aToB.length];
-		for(int i=0;i<aToB.length;++i) {
-			int c = aToB[i];
-			if(c >= 0)
-				map[i] = -1 - c;
-			else
-				map[i] = 0;
-		}
-		return map;
-	}
-	
-	private static int[] generateMapB(int[] bToA) {
-		int[] map = new int[bToA.length];
-		for(int i=0;i<bToA.length;++i) {
-			int c = bToA[i];
-			if(c >= 0)
-				map[i] = -1 - i;
-			else
-				map[i] = 0;
-		}
-		return map;
-	}
-	
-	private static Vertex[] generateVertices(int graph, int[] map, Stat[][] statements) {
-		int size = 0;
-		for(int s=0;s<map.length;++s)
-			if(map[s] == 0)
-				++size;
-		Vertex[] vertices = new Vertex[size];
-		for(int s=0,i=0;s<map.length;++s)
-			if(map[s] == 0) {
-				Stat[] ns = statements[s];
-				Stat[] stats = new Stat[ns.length];
-				for(int j=0;j<ns.length;++j) {
-					Stat n = ns[j];
-					stats[j] = new Stat(map[n.p], map[n.o]);
-				}
-				Arrays.sort(stats, Stat.STAT_COMPARATOR);
-				vertices[i++] = new Vertex(graph, s, 0, stats);
-			}
-		return vertices;
-	}
-	
-	private static void updateVertices(Vertex[] vertices, int[] map, Stat[][] statements) {
-		for(int i=0;i<vertices.length;++i) {
-			int s = vertices[i].original;
-			Stat[] ns = statements[s];
-			Stat[] stats = vertices[i].stats;
-			for(int j=0;j<ns.length;++j) {
-				Stat n = ns[j];
-				Stat stat = stats[j];
-				stat.p = map[n.p];
-				stat.o = map[n.o];
-			}
-			Arrays.sort(stats, Stat.STAT_COMPARATOR);
-		}
-	}
-	
-	private static Vertex[] concat(Vertex[] as, Vertex[] bs) {
-		Vertex[] result = new Vertex[as.length + bs.length];
-		System.arraycopy(as, 0, result, 0, as.length);
-		System.arraycopy(bs, 0, result, as.length, bs.length);
-		return result;
-	}
-	
-	static boolean equals(Stat[] stats1, Stat[] stats2) {
-		if(stats1.length != stats2.length)
-			return false;
-		for(int i=0;i<stats1.length;++i) {
-			Stat stat1 = stats1[i];
-			Stat stat2 = stats2[i];
-			if(stat1.p != stat2.p || stat1.o != stat2.o)
-				return false;
-		}
-		return true;
-	}
-	
-	private static boolean updatePositions(Vertex[] can) {
-		boolean modified = false;
-		int oldPos = can[0].pos;
-		Vertex oldVertex = can[0];
-		for(int i=1;i<can.length;++i) {
-			Vertex curVertex = can[i];
-			int curPos = curVertex.pos;
-			if(curPos == oldPos) {
-				if(equals(oldVertex.stats, curVertex.stats))
-					curVertex.pos = oldVertex.pos;
-				else {
-					curVertex.pos = i;
-					modified = true;
-				}
-			}
-			else
-				oldPos = curPos;
-			oldVertex = curVertex;
-		}
-		return modified;
-	}
-	
-	private static void updateMap(Vertex[] vertices, int[] map) {
-		for(Vertex vertex : vertices)
-			map[vertex.original] = vertex.pos;
-	}
-
-	private static int[] groupPositions(Vertex[] can) {
-		TIntArrayList result = new TIntArrayList();
-		for(int i=0;i<can.length;++i)
-			if(can[i].pos == i)
-				result.add(i);
-		result.add(can.length);
-		return result.toArray();
-	}	
-		
-	static class TByteArrayIntHashMap extends TObjectIntHashMap<byte[]> {
-		@Override
-		protected boolean equals(Object one, Object two) {
-			return Arrays.equals((byte[])one, (byte[])two);
-		}
-		
-		@Override
-		protected int hash(Object obj) {
-			return Arrays.hashCode((byte[])obj);
-		}
-	}
-	
-	private boolean separateByValues(Vertex[] can, int begin, int end, Variant[] aValues, Variant[] bValues) {		
-		int valueCount = 0;
-		TObjectIntHashMap<Variant> valueIds = new TObjectIntHashMap<Variant>();
-		int[] ids = new int[end-begin];
-		for(int i=begin;i<end;++i) {
-			Vertex v = can[i];
-			Variant value = v.graph==0 ? aValues[v.original] : bValues[v.original];
-			int valueId = valueIds.get(value);
-			if(valueId == 0) {
-				valueIds.put(value, ++valueCount);
-				ids[i-begin] = valueCount-1;
-			}
-			else
-				ids[i-begin] = valueId-1;
-		}
-		if(valueCount > 1) {
-			Vertex[] vs = Arrays.copyOfRange(can, begin, end);
-			int[] temp = new int[valueCount];
-			for(int id : ids)
-				++temp[id];
-			int cur = begin;
-			for(int i=0;i<temp.length;++i) {
-				int count = temp[i];
-				temp[i] = cur;
-				cur += count;
-			}
-			for(int i=0;i<ids.length;++i)
-				vs[i].pos = temp[ids[i]];
-			for(int i=0;i<ids.length;++i)
-				can[temp[ids[i]]++] = vs[i];
-			return true;
-		}
-		else
-			return false;
-	}
-	
-	private boolean separateByValues(Vertex[] can, int[] groupPos, Variant[] aValues, Variant[] bValues) {
-		boolean modified = false;
-		for(int i=0;i<groupPos.length-1;++i) {
-			int begin = groupPos[i];
-			int end = groupPos[i+1];
-			if(end - begin > 2)
-				modified |= separateByValues(can, begin, end, aValues, bValues);					
-		}
-		return modified;
-	}
-	
-	private boolean hasBigGroups(Vertex[] can, int[] groupPos) {
-		for(int i=0;i<groupPos.length-1;++i) {
-			int begin = groupPos[i];
-			int end = groupPos[i+1];
-			if(end - begin > 2 && can[begin].graph == 0 && can[end-1].graph == 1)
-				return true;
-		}
-		return false;
-	}
-	
-	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;
-		}
-	}
-	
-	private static void guessIsomorphism(Vertex[] can, int[] groupPos) {
-		UnionFind uf = new UnionFind(can.length);
-		for(int i=0;i<can.length;++i) {
-			uf.merge(i, can[i].pos);
-			for(Stat stat : can[i].stats) {
-				if(stat.p >= 0)
-					uf.merge(i, stat.p);
-				if(stat.o >= 0)
-					uf.merge(i, stat.o);
-			}
-		}
-		
-		TIntHashSet done = new TIntHashSet();
-		for(int i=0;i<groupPos.length-1;++i) {
-			int begin = groupPos[i];
-			int end = groupPos[i+1];
-			if(end - begin > 2 && can[begin].graph == 0 && can[end-1].graph == 1) {
-				int c = uf.canonical(begin);
-				if(done.add(c)) {
-					int middle = begin+1;
-					while(can[middle].graph==0)
-						++middle;
-					int j;
-					for(j=0;begin+j < middle && middle+j < end;++j) {
-						can[begin+j].pos = begin + j*2;
-						can[middle+j].pos = begin + j*2;
-					}
-					int pos = begin+j*2;					
-					for(;begin+j < middle;++j)
-						can[begin+j].pos = pos;
-					for(;middle+j < end;++j)
-						can[middle+j].pos = pos;
-				}
-			}
-		}
-	}
-	
-	@Override
-	public void applyTo(GraphMatching matching) {
-		if(matching.size == matching.aGraph.resourceCount ||
-				matching.size == matching.bGraph.resourceCount)
-			return;
-		long begin1 = System.nanoTime();
-		int[] aMap = generateMapA(matching.aToB);
-		int[] bMap = generateMapB(matching.bToA);
-		Vertex[] aVertices = generateVertices(0,
-				aMap, matching.aGraph.statements);
-		Vertex[] bVertices = generateVertices(1,
-				bMap, matching.bGraph.statements);
-		Vertex[] can = concat(aVertices, bVertices);
-		if(GraphMatching.TIMING)
-			System.out.println("    Init:    " + (System.nanoTime()-begin1)*1e-6 + "ms");
-		
-		int[] groupPos = null;
-		boolean doneSeparationByValues = false;
-		while(true) {
-			long begin2 = System.nanoTime();
-			Arrays.sort(can, VERTEX_COMPARATOR);
-			if(GraphMatching.TIMING)
-				System.out.println("    Sort:    " + (System.nanoTime()-begin2)*1e-6 + "ms");
-			
-			long begin3 = System.nanoTime();
-			if(!updatePositions(can)) {			
-				groupPos = groupPositions(can);				
-				if(!hasBigGroups(can, groupPos))
-					break;
-				
-				boolean modified = false;
-				if(!doneSeparationByValues) {
-					modified = separateByValues(can, groupPos, matching.aGraph.values, matching.bGraph.values);										
-					doneSeparationByValues = true;
-					if(GraphMatching.TIMING)
-						System.out.println("    - separate by values");
-				}
-				
-				if(!modified) {
-					guessIsomorphism(can, groupPos);
-					if(GraphMatching.TIMING)
-						System.out.println("    - guess isomorphism");
-				}
-			}
-			if(GraphMatching.TIMING)
-				System.out.println("    Update1: " + (System.nanoTime()-begin3)*1e-6 + "ms");
-			
-			long begin4 = System.nanoTime();
-			updateMap(aVertices, aMap);			
-			updateMap(bVertices, bMap);
-			if(GraphMatching.TIMING)
-				System.out.println("    Update2: " + (System.nanoTime()-begin4)*1e-6 + "ms");			
-			long begin5 = System.nanoTime();
-			updateVertices(aVertices, aMap, matching.aGraph.statements);
-			updateVertices(bVertices, bMap, matching.bGraph.statements);
-			if(GraphMatching.TIMING)
-				System.out.println("    Update3: " + (System.nanoTime()-begin5)*1e-6 + "ms");
-		}
-		
-		for(int i=0;i<groupPos.length-1;++i) {
-			int begin = groupPos[i];
-			int end = groupPos[i+1];
-			if(end - begin == 2) {
-				Vertex a = can[begin];
-				Vertex b = can[end-1];
-				if(a.graph == 0 && b.graph == 1)
-					matching.map(a.original, b.original);
-			}
-		}
-		
-		if(GraphMatching.DEBUG)
-			for(int i=0;i<groupPos.length-1;++i) {
-				int begin = groupPos[i];
-				int end = groupPos[i+1];
-				if(end - begin > 2) {				
-					System.out.println("----");
-					for(int j=begin;j<end;++j) {
-						if(can[j].graph == 0) {
-							int org = can[j].original;
-							String name = matching.aGraph.names[org];
-							System.out.println(name + " (A)");
-							for(Stat stat : matching.aGraph.statements[org])
-								System.out.println("    " + stat.toString(matching.aGraph.names));
-							Variant value = matching.aGraph.values[org];
-							if(value != null)
-								System.out.println("    " + value);
-						}
-						else {
-							int org = can[j].original;
-							String name = matching.bGraph.names[org];
-							System.out.println(name + " (B)");
-							for(Stat stat : matching.bGraph.statements[org])
-								System.out.println("    " + stat.toString(matching.bGraph.names));
-							Variant value = matching.bGraph.values[org];
-							if(value != null)
-								System.out.println("    " + value);
-						}
-					}
-				}
-			}
-	}
-}
+package org.simantics.graph.matching;
+
+import gnu.trove.list.array.TIntArrayList;
+import gnu.trove.map.hash.TObjectIntHashMap;
+import gnu.trove.set.hash.TIntHashSet;
+
+import java.util.Arrays;
+import java.util.Comparator;
+
+import org.simantics.databoard.binding.mutable.Variant;
+
+public enum CanonicalizingMatchingStrategy implements GraphMatchingStrategy {
+	INSTANCE;
+
+	private static class Vertex {
+		int graph;
+		int original;
+		int pos;
+		Stat[] stats;
+		
+		public Vertex(int graph, int original, int pos, Stat[] stats) {
+			this.graph = graph;
+			this.original = original;
+			this.pos = pos;
+			this.stats = stats;
+		}
+	}
+	
+	private static final Comparator<Vertex> VERTEX_COMPARATOR = new Comparator<Vertex>() {
+		@Override
+		public int compare(Vertex o1, Vertex o2) {
+			int pos1 = o1.pos;
+			int pos2 = o2.pos;
+			if(pos1 < pos2)
+				return -1;
+			if(pos1 > pos2)
+				return 1;
+			Stat[] stats1 = o1.stats;
+			Stat[] stats2 = o2.stats;
+			if(stats1.length < stats2.length)
+				return -1;
+			if(stats1.length > stats2.length)
+				return 1;
+			for(int i=0;i<stats1.length;++i) {
+				int comp = Stat.STAT_COMPARATOR.compare(stats1[i], stats2[i]);
+				if(comp != 0)
+					return comp;
+			}
+			if(o1.graph < o2.graph)
+				return -1;
+			if(o1.graph > o2.graph)
+				return 1;			
+			if(o1.original < o2.original)
+				return -1;
+			if(o1.original > o2.original)
+				return 1;
+			return 0;
+		}
+	};
+	
+	private static int[] generateMapA(int[] aToB) {
+		int[] map = new int[aToB.length];
+		for(int i=0;i<aToB.length;++i) {
+			int c = aToB[i];
+			if(c >= 0)
+				map[i] = -1 - c;
+			else
+				map[i] = 0;
+		}
+		return map;
+	}
+	
+	private static int[] generateMapB(int[] bToA) {
+		int[] map = new int[bToA.length];
+		for(int i=0;i<bToA.length;++i) {
+			int c = bToA[i];
+			if(c >= 0)
+				map[i] = -1 - i;
+			else
+				map[i] = 0;
+		}
+		return map;
+	}
+	
+	private static Vertex[] generateVertices(int graph, int[] map, Stat[][] statements) {
+		int size = 0;
+		for(int s=0;s<map.length;++s)
+			if(map[s] == 0)
+				++size;
+		Vertex[] vertices = new Vertex[size];
+		for(int s=0,i=0;s<map.length;++s)
+			if(map[s] == 0) {
+				Stat[] ns = statements[s];
+				Stat[] stats = new Stat[ns.length];
+				for(int j=0;j<ns.length;++j) {
+					Stat n = ns[j];
+					stats[j] = new Stat(map[n.p], map[n.o]);
+				}
+				Arrays.sort(stats, Stat.STAT_COMPARATOR);
+				vertices[i++] = new Vertex(graph, s, 0, stats);
+			}
+		return vertices;
+	}
+	
+	private static void updateVertices(Vertex[] vertices, int[] map, Stat[][] statements) {
+		for(int i=0;i<vertices.length;++i) {
+			int s = vertices[i].original;
+			Stat[] ns = statements[s];
+			Stat[] stats = vertices[i].stats;
+			for(int j=0;j<ns.length;++j) {
+				Stat n = ns[j];
+				Stat stat = stats[j];
+				stat.p = map[n.p];
+				stat.o = map[n.o];
+			}
+			Arrays.sort(stats, Stat.STAT_COMPARATOR);
+		}
+	}
+	
+	private static Vertex[] concat(Vertex[] as, Vertex[] bs) {
+		Vertex[] result = new Vertex[as.length + bs.length];
+		System.arraycopy(as, 0, result, 0, as.length);
+		System.arraycopy(bs, 0, result, as.length, bs.length);
+		return result;
+	}
+	
+	static boolean equals(Stat[] stats1, Stat[] stats2) {
+		if(stats1.length != stats2.length)
+			return false;
+		for(int i=0;i<stats1.length;++i) {
+			Stat stat1 = stats1[i];
+			Stat stat2 = stats2[i];
+			if(stat1.p != stat2.p || stat1.o != stat2.o)
+				return false;
+		}
+		return true;
+	}
+	
+	private static boolean updatePositions(Vertex[] can) {
+		boolean modified = false;
+		int oldPos = can[0].pos;
+		Vertex oldVertex = can[0];
+		for(int i=1;i<can.length;++i) {
+			Vertex curVertex = can[i];
+			int curPos = curVertex.pos;
+			if(curPos == oldPos) {
+				if(equals(oldVertex.stats, curVertex.stats))
+					curVertex.pos = oldVertex.pos;
+				else {
+					curVertex.pos = i;
+					modified = true;
+				}
+			}
+			else
+				oldPos = curPos;
+			oldVertex = curVertex;
+		}
+		return modified;
+	}
+	
+	private static void updateMap(Vertex[] vertices, int[] map) {
+		for(Vertex vertex : vertices)
+			map[vertex.original] = vertex.pos;
+	}
+
+	private static int[] groupPositions(Vertex[] can) {
+		TIntArrayList result = new TIntArrayList();
+		for(int i=0;i<can.length;++i)
+			if(can[i].pos == i)
+				result.add(i);
+		result.add(can.length);
+		return result.toArray();
+	}	
+		
+	static class TByteArrayIntHashMap extends TObjectIntHashMap<byte[]> {
+		@Override
+		protected boolean equals(Object one, Object two) {
+			return Arrays.equals((byte[])one, (byte[])two);
+		}
+		
+		@Override
+		protected int hash(Object obj) {
+			return Arrays.hashCode((byte[])obj);
+		}
+	}
+	
+	private boolean separateByValues(Vertex[] can, int begin, int end, Variant[] aValues, Variant[] bValues) {		
+		int valueCount = 0;
+		TObjectIntHashMap<Variant> valueIds = new TObjectIntHashMap<Variant>();
+		int[] ids = new int[end-begin];
+		for(int i=begin;i<end;++i) {
+			Vertex v = can[i];
+			Variant value = v.graph==0 ? aValues[v.original] : bValues[v.original];
+			int valueId = valueIds.get(value);
+			if(valueId == 0) {
+				valueIds.put(value, ++valueCount);
+				ids[i-begin] = valueCount-1;
+			}
+			else
+				ids[i-begin] = valueId-1;
+		}
+		if(valueCount > 1) {
+			Vertex[] vs = Arrays.copyOfRange(can, begin, end);
+			int[] temp = new int[valueCount];
+			for(int id : ids)
+				++temp[id];
+			int cur = begin;
+			for(int i=0;i<temp.length;++i) {
+				int count = temp[i];
+				temp[i] = cur;
+				cur += count;
+			}
+			for(int i=0;i<ids.length;++i)
+				vs[i].pos = temp[ids[i]];
+			for(int i=0;i<ids.length;++i)
+				can[temp[ids[i]]++] = vs[i];
+			return true;
+		}
+		else
+			return false;
+	}
+	
+	private boolean separateByValues(Vertex[] can, int[] groupPos, Variant[] aValues, Variant[] bValues) {
+		boolean modified = false;
+		for(int i=0;i<groupPos.length-1;++i) {
+			int begin = groupPos[i];
+			int end = groupPos[i+1];
+			if(end - begin > 2)
+				modified |= separateByValues(can, begin, end, aValues, bValues);					
+		}
+		return modified;
+	}
+	
+	private boolean hasBigGroups(Vertex[] can, int[] groupPos) {
+		for(int i=0;i<groupPos.length-1;++i) {
+			int begin = groupPos[i];
+			int end = groupPos[i+1];
+			if(end - begin > 2 && can[begin].graph == 0 && can[end-1].graph == 1)
+				return true;
+		}
+		return false;
+	}
+	
+	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;
+		}
+	}
+	
+	private static void guessIsomorphism(Vertex[] can, int[] groupPos) {
+		UnionFind uf = new UnionFind(can.length);
+		for(int i=0;i<can.length;++i) {
+			uf.merge(i, can[i].pos);
+			for(Stat stat : can[i].stats) {
+				if(stat.p >= 0)
+					uf.merge(i, stat.p);
+				if(stat.o >= 0)
+					uf.merge(i, stat.o);
+			}
+		}
+		
+		TIntHashSet done = new TIntHashSet();
+		for(int i=0;i<groupPos.length-1;++i) {
+			int begin = groupPos[i];
+			int end = groupPos[i+1];
+			if(end - begin > 2 && can[begin].graph == 0 && can[end-1].graph == 1) {
+				int c = uf.canonical(begin);
+				if(done.add(c)) {
+					int middle = begin+1;
+					while(can[middle].graph==0)
+						++middle;
+					int j;
+					for(j=0;begin+j < middle && middle+j < end;++j) {
+						can[begin+j].pos = begin + j*2;
+						can[middle+j].pos = begin + j*2;
+					}
+					int pos = begin+j*2;					
+					for(;begin+j < middle;++j)
+						can[begin+j].pos = pos;
+					for(;middle+j < end;++j)
+						can[middle+j].pos = pos;
+				}
+			}
+		}
+	}
+	
+	@Override
+	public void applyTo(GraphMatching matching) {
+		if(matching.size == matching.aGraph.resourceCount ||
+				matching.size == matching.bGraph.resourceCount)
+			return;
+		long begin1 = System.nanoTime();
+		int[] aMap = generateMapA(matching.aToB);
+		int[] bMap = generateMapB(matching.bToA);
+		Vertex[] aVertices = generateVertices(0,
+				aMap, matching.aGraph.statements);
+		Vertex[] bVertices = generateVertices(1,
+				bMap, matching.bGraph.statements);
+		Vertex[] can = concat(aVertices, bVertices);
+		if(GraphMatching.TIMING)
+			System.out.println("    Init:    " + (System.nanoTime()-begin1)*1e-6 + "ms");
+		
+		int[] groupPos = null;
+		boolean doneSeparationByValues = false;
+		while(true) {
+			long begin2 = System.nanoTime();
+			Arrays.sort(can, VERTEX_COMPARATOR);
+			if(GraphMatching.TIMING)
+				System.out.println("    Sort:    " + (System.nanoTime()-begin2)*1e-6 + "ms");
+			
+			long begin3 = System.nanoTime();
+			if(!updatePositions(can)) {			
+				groupPos = groupPositions(can);				
+				if(!hasBigGroups(can, groupPos))
+					break;
+				
+				boolean modified = false;
+				if(!doneSeparationByValues) {
+					modified = separateByValues(can, groupPos, matching.aGraph.values, matching.bGraph.values);										
+					doneSeparationByValues = true;
+					if(GraphMatching.TIMING)
+						System.out.println("    - separate by values");
+				}
+				
+				if(!modified) {
+					guessIsomorphism(can, groupPos);
+					if(GraphMatching.TIMING)
+						System.out.println("    - guess isomorphism");
+				}
+			}
+			if(GraphMatching.TIMING)
+				System.out.println("    Update1: " + (System.nanoTime()-begin3)*1e-6 + "ms");
+			
+			long begin4 = System.nanoTime();
+			updateMap(aVertices, aMap);			
+			updateMap(bVertices, bMap);
+			if(GraphMatching.TIMING)
+				System.out.println("    Update2: " + (System.nanoTime()-begin4)*1e-6 + "ms");			
+			long begin5 = System.nanoTime();
+			updateVertices(aVertices, aMap, matching.aGraph.statements);
+			updateVertices(bVertices, bMap, matching.bGraph.statements);
+			if(GraphMatching.TIMING)
+				System.out.println("    Update3: " + (System.nanoTime()-begin5)*1e-6 + "ms");
+		}
+		
+		for(int i=0;i<groupPos.length-1;++i) {
+			int begin = groupPos[i];
+			int end = groupPos[i+1];
+			if(end - begin == 2) {
+				Vertex a = can[begin];
+				Vertex b = can[end-1];
+				if(a.graph == 0 && b.graph == 1)
+					matching.map(a.original, b.original);
+			}
+		}
+		
+		if(GraphMatching.DEBUG)
+			for(int i=0;i<groupPos.length-1;++i) {
+				int begin = groupPos[i];
+				int end = groupPos[i+1];
+				if(end - begin > 2) {				
+					System.out.println("----");
+					for(int j=begin;j<end;++j) {
+						if(can[j].graph == 0) {
+							int org = can[j].original;
+							String name = matching.aGraph.names[org];
+							System.out.println(name + " (A)");
+							for(Stat stat : matching.aGraph.statements[org])
+								System.out.println("    " + stat.toString(matching.aGraph.names));
+							Variant value = matching.aGraph.values[org];
+							if(value != null)
+								System.out.println("    " + value);
+						}
+						else {
+							int org = can[j].original;
+							String name = matching.bGraph.names[org];
+							System.out.println(name + " (B)");
+							for(Stat stat : matching.bGraph.statements[org])
+								System.out.println("    " + stat.toString(matching.bGraph.names));
+							Variant value = matching.bGraph.values[org];
+							if(value != null)
+								System.out.println("    " + value);
+						}
+					}
+				}
+			}
+	}
+}