From cbc22e9a30434bca2d197a3b6cbbdbced19aed4e Mon Sep 17 00:00:00 2001 From: Marko Luukkainen Date: Thu, 13 Apr 2017 10:34:54 +0300 Subject: [PATCH] Improve graph comparison logic Added additional processing step for Resources that cannot be identified when they are encountered the first time refs #7045 Change-Id: I4cdefb7ae765f2f8efe5ab7d2cf444d8e98d7185 --- .../interop/test/GraphComparator.java | 118 ++++++++++++++---- .../interop/test/ResourceComparator.java | 92 ++++++++------ 2 files changed, 146 insertions(+), 64 deletions(-) diff --git a/org.simantics.interop/src/org/simantics/interop/test/GraphComparator.java b/org.simantics.interop/src/org/simantics/interop/test/GraphComparator.java index aa2ddee..11b3d1a 100644 --- a/org.simantics.interop/src/org/simantics/interop/test/GraphComparator.java +++ b/org.simantics.interop/src/org/simantics/interop/test/GraphComparator.java @@ -20,6 +20,7 @@ import java.util.HashMap; import java.util.HashSet; import java.util.List; import java.util.Map; +import java.util.Map.Entry; import java.util.Set; import java.util.Stack; @@ -196,6 +197,9 @@ public class GraphComparator { processUnreliable(unreliableLeft, unreliableRight); // process unreliable handles cases where unidentified resources have path of length one to identified resource processUnreliable(unreliableLeft, unreliableRight,objectsLeft,objectsRight); + if (objectsLeft.isEmpty() && unreliableLeft.size() > 0 && unreliableRight.size() > 0) { + processUnreliable2(unreliableLeft, unreliableRight,objectsLeft,objectsRight); + } if (objectsLeft.isEmpty() && unreliableLeft.size() > 0 && unreliableRight.size() > 0) { // comparison is ending, but we have still unprocessed unidentified resources left. // These cases have longer path than one to identified objects. @@ -211,8 +215,6 @@ public class GraphComparator { if (!comparableStatements.containsRight(s)) addAddition(s); } - - } public void test(Session session) throws DatabaseException { @@ -223,7 +225,7 @@ public class GraphComparator { comparator.setComparator(this); - addComparable(r1, r2, false); + addComparable(r1, r2); final Stack objectsLeft = new Stack(); final Stack objectsRight = new Stack(); @@ -248,6 +250,9 @@ public class GraphComparator { processUnreliable(unreliableLeft, unreliableRight); // process unreliable handles cases where unidentified resources have path of length one to identified resource processUnreliable(unreliableLeft, unreliableRight,objectsLeft,objectsRight); + if (objectsLeft.isEmpty() && unreliableLeft.size() > 0 && unreliableRight.size() > 0) { + processUnreliable2(unreliableLeft, unreliableRight,objectsLeft,objectsRight); + } if (objectsLeft.isEmpty() && unreliableLeft.size() > 0 && unreliableRight.size() > 0) { // comparison is ending, but we have still unprocessed unidentified resources left. // These cases have longer path than one to identified objects. @@ -261,6 +266,8 @@ public class GraphComparator { } for (Statement s : unreliableLeft) { if (!comparableStatements.containsLeft(s)) + if (s.getObject().getResourceId() == 303248) + System.out.println(); addDeletion(s); } for (Statement s : unreliableRight) { @@ -290,7 +297,7 @@ public class GraphComparator { if((comparableResources.containsLeft(r1)||comparableResources.containsRight(r2)) && !comparableResources.contains(r1, r2)) { throw new DatabaseException("Comparator error: Trying to map " + r1 + " to " + r2 + " while mappings " + r1 + " to " + comparableResources.getRight(r1) + " and " + comparableResources.getLeft(r2) + " to " + r2 + " exist."); } - addComparable(r1, r2, false); + addComparable(r1, r2); //System.out.println("test " + NameUtils.getSafeName(g, r1) + " " + NameUtils.getSafeName(g, r2)); compareProps(r1, r2); @@ -342,16 +349,16 @@ public class GraphComparator { } for (Resource left : subjectLeft.getKeys()) { - if (!comparableResources.containsLeft(left)) - continue; Resource right = comparableResources.getRight(left); + if (right == null) + continue; for (Statement leftS : subjectLeft.getValues(left)) { Resource leftO = leftS.getObject(); - if (!comparableResources.containsLeft(leftO)) - continue; if (!unreliableLeft.contains(leftS)) continue; Resource rightO = comparableResources.getRight(leftO); + if (rightO == null) + continue; for (Statement rightS : subjectRight.getValues(right)) { if (!rightS.getObject().equals(rightO)) continue; @@ -361,7 +368,7 @@ public class GraphComparator { comparableResources.contains(leftS.getPredicate(), rightS.getPredicate())) { unreliableLeft.remove(leftS); unreliableRight.remove(rightS); - addComparable(leftS, rightS, false); + addComparable(leftS, rightS); } } } @@ -407,6 +414,8 @@ public class GraphComparator { } } + compareStatements(ss1, ss2, objectsLeft, objectsRight,unreliableLeft,unreliableRight); + for (Resource similarOl : comparableOLeft.getKeys()) { List similarLeft = comparableOLeft.getValues(similarOl); if (similarLeft.size() == left.size()) { @@ -420,12 +429,18 @@ public class GraphComparator { for (int j = 0; j < left.size(); j++) { if (useSL[j]) continue; + // compare predicates Resource pl = left.get(i).getPredicate(); Resource psl = similarLeft.get(j).getPredicate(); if (pl.equals(psl)) { - useL[i] = true; - useSL[j] = true; - break; + // compare objects (unreliable result is interpreted as positive match) + + int comp = comparator.compare(g, left.get(i).getObject(), similarLeft.get(j).getObject(), true); + if (comp >= 0 && comp < Integer.MAX_VALUE) { + useL[i] = true; + useSL[j] = true; + break; + } } } } @@ -483,8 +498,13 @@ public class GraphComparator { if (!comparableResources.contains(ls.getSubject(), rs.getSubject())) continue; if (rcomp.compare(ls.getPredicate(),rs.getPredicate()) == 0) { - iLeft[l] = r; - iRight[r] = l; + // compare objects (unreliable result is not accepted) + int comp = comparator.compare(g, ls.getObject(), rs.getObject()); + if (comp > 0 && comp < Integer.MAX_VALUE) { + iLeft[l] = r; + iRight[r] = l; + break; + } break; } } @@ -516,16 +536,18 @@ public class GraphComparator { objectsLeft.add(ol); objectsRight.add(or); - addComparable(ol, or, false); + addComparable(ol, or); for (int l = 0; l < left.size(); l++) { int r = indices.first[l]; Statement sl = left.get(l); Statement sr = right.get(r); - addComparable(sl, sr, true); + addComparable(sl, sr); unreliableLeft.remove(sl); unreliableRight.remove(sr); } + } else { + } } @@ -533,6 +555,49 @@ public class GraphComparator { } + private void processUnreliable2(Set unreliableLeft, Set unreliableRight, Stack objectsLeft, Stack objectsRight) throws DatabaseException { + MapList subjectLeft = new MapList(); + MapList subjectRight = new MapList(); + MapList objectLeft = new MapList(); + MapList objectRight = new MapList(); + + for (Statement s : unreliableLeft) { + subjectLeft.add(s.getSubject(),s); + objectLeft.add(s.getObject(),s); + } + for (Statement s : unreliableRight) { + subjectRight.add(s.getSubject(),s); + objectRight.add(s.getObject(),s); + } + + for (Resource ol : objectLeft.getKeys()) { + // all statements to the left side object + List left = objectLeft.getValues(ol); + // all subjects that have statements to the left side object (ol) + Set sLeft = new HashSet(); + // all matching subjects on the right side + Set sRight = new HashSet(); + for (Statement s : left) { + sLeft.add(s.getSubject()); + sRight.add(comparableResources.getRight(s.getSubject())); + } + + if (sLeft.size() == 1 && sRight.size() == 1) { + List ss1 = new ArrayList(subjectLeft.getValues(sLeft.iterator().next())); + List ss2 = new ArrayList(subjectRight.getValues(sRight.iterator().next())); + + int count = comparableStatements.size(); + compareStatements(ss1, ss2, objectsLeft, objectsRight,unreliableLeft,unreliableRight); + if (comparableStatements.size() > count) { + for (Entry entry : comparableStatements.getEntries()) { + unreliableLeft.remove(entry.getKey()); + unreliableRight.remove(entry.getValue()); + } + } + } + } + } + private void processUnreliableDeep(Set unreliableLeft, Set unreliableRight, Stack objectsLeft, Stack objectsRight) throws DatabaseException { MapList subjectLeft = new MapList(); MapList subjectRight = new MapList(); @@ -591,7 +656,7 @@ public class GraphComparator { objectsLeft.add(ol); objectsRight.add(or); - addComparable(ol, or, false); + addComparable(ol, or); Collection statementsLeft = objectLeft.getValues(ol); Collection statementsRight = objectRight.getValues(or); unreliableLeft.removeAll(statementsLeft); @@ -600,7 +665,7 @@ public class GraphComparator { for (Path left : map.getLeftSet()) { Path right = map.getRight(left); for (int i = 0; i < left.getLength(); i++) { - addComparable(left.getStatements().get(i),right.getStatements().get(i),false); + addComparable(left.getStatements().get(i),right.getStatements().get(i)); } } } @@ -691,19 +756,22 @@ public class GraphComparator { return new GraphChanges(r1,r2,changes1,changes2,modifications,comparableResources); } - private void addComparable(Statement left, Statement right, boolean process) throws DatabaseException { - addComparable(left.getObject(), right.getObject(), process); + private void addComparable(Statement left, Statement right) throws DatabaseException { + addComparable(left.getObject(), right.getObject()); comparableStatements.map(left, right); //comparableResources.map(left.getObject(), right.getObject()); } - private void addComparable(Resource left, Resource right, boolean process) throws DatabaseException { + private void addComparable(Resource left, Resource right) throws DatabaseException { if(!comparableResources.contains(left, right)) { if (comparableResources.containsLeft(left)||comparableResources.containsRight(right)) { throw new DatabaseException("Comparator error: Trying to map " + left + " to " + right + " while mappings " + left + " to " + comparableResources.getRight(left) + " and " + comparableResources.getLeft(right) + " to " + right + " exist."); } else { if (DEBUG) System.out.println(left + " = " + right); - comparableResources.map(left, right); + comparableResources.map(left, right); + //if (left.getResourceId() == 313071 && right.getResourceId() == 325324) + if (left.getResourceId() == 313231 && right.getResourceId() == 337775) + System.out.println(); } } @@ -1009,7 +1077,7 @@ public class GraphComparator { objectsLeft.add(s1.getObject()); objectsRight.add(s2.getObject()); } - addComparable(s1, s2, true); + addComparable(s1, s2); break; } } @@ -1128,7 +1196,7 @@ public class GraphComparator { boolean eq = compareValue(v1, v2); if (!eq) { addModification(s1, s2); - addComparable(s1, s2, false); + addComparable(s1, s2); } } else { if (!s1.getObject().equals(s1.getSubject()) && !s2.getObject().equals(s2.getSubject())) @@ -1136,7 +1204,7 @@ public class GraphComparator { } } else { addModification(s1, s2); - addComparable(s1, s2, false); + addComparable(s1, s2); } i1++; i2++; diff --git a/org.simantics.interop/src/org/simantics/interop/test/ResourceComparator.java b/org.simantics.interop/src/org/simantics/interop/test/ResourceComparator.java index 0b0a7c1..f65617c 100644 --- a/org.simantics.interop/src/org/simantics/interop/test/ResourceComparator.java +++ b/org.simantics.interop/src/org/simantics/interop/test/ResourceComparator.java @@ -1,39 +1,53 @@ -package org.simantics.interop.test; - -import org.simantics.db.ReadGraph; -import org.simantics.db.Resource; -import org.simantics.db.exception.DatabaseException; - -/** - * - * @author Marko Luukkainen - * - */ -public abstract class ResourceComparator { - - private GraphComparator comparator; - - void setComparator(GraphComparator comparator) { - this.comparator = comparator; - } - - public GraphComparator getComparator() { - return comparator; - } - - /** - * Compares two resources and returns numeric value of differences, minimum value is 1. - * - * Special values: - * Integer.MAX_VALUE: Objects are not comparable. - * 0 (zero): Object comparison is not reliable. - * - * @param g - * @param o1 - * @param o2 - * @return - * @throws DatabaseException - */ - public abstract int compare(ReadGraph g, Resource o1, Resource o2) throws DatabaseException; - -} +package org.simantics.interop.test; + +import org.simantics.db.ReadGraph; +import org.simantics.db.Resource; +import org.simantics.db.exception.DatabaseException; + +/** + * + * @author Marko Luukkainen + * + */ +public abstract class ResourceComparator { + + private GraphComparator comparator; + + void setComparator(GraphComparator comparator) { + this.comparator = comparator; + } + + public GraphComparator getComparator() { + return comparator; + } + + + /** + * Compares two resources and returns numeric value of differences, minimum value is 1. + * + * Special values: + * Integer.MAX_VALUE: Objects are not comparable. + * 0 (zero): Object comparison is not reliable. + * + * Result is same as compare(g, o1, o2, true); + * + */ + public abstract int compare(ReadGraph g, Resource o1, Resource o2) throws DatabaseException; + + /** + * Compares two resources and returns numeric value of differences, minimum value is 1. + * + * Special values: + * Integer.MAX_VALUE: Objects are not comparable. + * 0 (zero): Object comparison is not reliable. + * + * @param g + * @param o1 + * @param o2 + * @param local: if true, comparison must not utilise information stored into comparator. + * @return + * @throws DatabaseException + */ + public abstract int compare(ReadGraph g, Resource o1, Resource o2, boolean local) throws DatabaseException; + +} -- 2.47.1