From 1f360dfa6505e971658bad416214f5f358305fba Mon Sep 17 00:00:00 2001 From: luukkainen Date: Wed, 28 Sep 2011 14:43:34 +0000 Subject: [PATCH] More extensive search for comparable resources git-svn-id: https://www.simantics.org/svn/simantics/interoperability/trunk@22466 ac1ea38d-2e2b-0410-8846-a27921b304fc --- .../interop/test/GraphComparator.java | 213 ++++++++++++++---- .../src/org/simantics/interop/test/Path.java | 99 ++++++++ 2 files changed, 270 insertions(+), 42 deletions(-) create mode 100644 org.simantics.interop/src/org/simantics/interop/test/Path.java 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 152d423..8d43207 100644 --- a/org.simantics.interop/src/org/simantics/interop/test/GraphComparator.java +++ b/org.simantics.interop/src/org/simantics/interop/test/GraphComparator.java @@ -11,6 +11,7 @@ *******************************************************************************/ package org.simantics.interop.test; +import java.math.MathContext; import java.util.ArrayList; import java.util.Arrays; import java.util.Collection; @@ -29,6 +30,7 @@ import org.simantics.db.Statement; import org.simantics.db.common.utils.NameUtils; import org.simantics.db.exception.DatabaseException; import org.simantics.db.exception.DoesNotContainValueException; +import org.simantics.db.exception.ManyObjectsForFunctionalRelationException; import org.simantics.db.exception.ServiceException; import org.simantics.db.exception.ValidationException; import org.simantics.layer0.Layer0; @@ -173,8 +175,7 @@ public class GraphComparator { objectsRight.push(r2); - List ss1 = new ArrayList(); - List ss2 = new ArrayList(); + Set unreliableLeft = new HashSet(); Set unreliableRight = new HashSet(); @@ -183,47 +184,15 @@ public class GraphComparator { if (objectsLeft.isEmpty()) break; - while (!objectsLeft.isEmpty()) { - Resource r1 = objectsLeft.pop(); - Resource r2 = objectsRight.pop(); - - if (comparableResources.contains(r1, r2)) { - //System.out.println("already tested " + NameUtils.getSafeName(g, r1) + " " + NameUtils.getSafeName(g, r2)); - continue; - } - comparableResources.map(r1, r2); - - //System.out.println("test " + NameUtils.getSafeName(g, r1) + " " + NameUtils.getSafeName(g, r2)); - compareProps(r1, r2); - - for (Resource rel : tested) { - ss1.addAll(g.getStatements(r1, rel)); - ss2.addAll(g.getStatements(r2, rel)); - ss1 = filterAsserted(r1, ss1); - ss2 = filterAsserted(r2, ss2); - ss1 = filterTraversed(ss1); - ss2 = filterTraversed(ss2); - ss1 = filterNonTested(ss1); - ss2 = filterNonTested(ss2); - - compareStatements(ss1, ss2, null, null,null,null); - ss1.clear(); - ss2.clear(); - } - - for (Resource rel : traversed) { - ss1.addAll(g.getStatements(r1, rel)); - ss2.addAll(g.getStatements(r2, rel)); - ss1 = filterAsserted(r1, ss1); - ss2 = filterAsserted(r2, ss2); - compareStatements(ss1, ss2, objectsLeft, objectsRight,unreliableLeft,unreliableRight); - ss1.clear(); - ss2.clear(); - - } - } - + // process compares objects that are identified and searches for more resources to process. + process(objectsLeft, objectsRight, 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) { + // comparison is ending, but we have still unprocessed unidentified resources left. + // These cases have longer path than one to identified objects. + processUnreliableDeep(unreliableLeft, unreliableRight, objectsLeft, objectsRight); + } } for (Statement s : unreliableLeft) { @@ -238,6 +207,50 @@ public class GraphComparator { } + private void process(Stack objectsLeft, Stack objectsRight, Set unreliableLeft, Set unreliableRight) throws DatabaseException { + List ss1 = new ArrayList(); + List ss2 = new ArrayList(); + + while (!objectsLeft.isEmpty()) { + Resource r1 = objectsLeft.pop(); + Resource r2 = objectsRight.pop(); + + if (comparableResources.contains(r1, r2)) { + //System.out.println("already tested " + NameUtils.getSafeName(g, r1) + " " + NameUtils.getSafeName(g, r2)); + continue; + } + comparableResources.map(r1, r2); + + //System.out.println("test " + NameUtils.getSafeName(g, r1) + " " + NameUtils.getSafeName(g, r2)); + compareProps(r1, r2); + + for (Resource rel : tested) { + ss1.addAll(g.getStatements(r1, rel)); + ss2.addAll(g.getStatements(r2, rel)); + ss1 = filterAsserted(r1, ss1); + ss2 = filterAsserted(r2, ss2); + ss1 = filterTraversed(ss1); + ss2 = filterTraversed(ss2); + ss1 = filterNonTested(ss1); + ss2 = filterNonTested(ss2); + + compareStatements(ss1, ss2, null, null,null,null); + ss1.clear(); + ss2.clear(); + } + + for (Resource rel : traversed) { + ss1.addAll(g.getStatements(r1, rel)); + ss2.addAll(g.getStatements(r2, rel)); + ss1 = filterAsserted(r1, ss1); + ss2 = filterAsserted(r2, ss2); + compareStatements(ss1, ss2, objectsLeft, objectsRight,unreliableLeft,unreliableRight); + ss1.clear(); + ss2.clear(); + + } + } + } private void processUnreliable(Set unreliableLeft, Set unreliableRight, Stack objectsLeft, Stack objectsRight) { MapList subjectLeft = new MapList(); MapList subjectRight = new MapList(); @@ -350,6 +363,122 @@ public class GraphComparator { } + private void processUnreliableDeep(Set unreliableLeft, Set unreliableRight, Stack objectsLeft, Stack objectsRight) throws ManyObjectsForFunctionalRelationException, ServiceException { + 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()) { + Set pathsLeft = new HashSet(); + for (Resource rel : traversed) { + pathsLeft.addAll(Path.create(g.getStatements(ol, rel))); + } + while (true) { + expand(pathsLeft); + if (pathsLeft.size() == 0) + break; + Collection endPaths = new ArrayList(1); + for (Path p : pathsLeft) { + if (comparableResources.containsLeft(p.getEnd())) { + endPaths.add(p); + } + } + if (endPaths.size() > 0) { + pathsLeft.clear(); + pathsLeft.addAll(endPaths); + break; + } + } + if (pathsLeft.size() > 0) { + Resource sl = objectLeft.getValues(ol).get(0).getSubject(); + Resource sr = comparableResources.getRight(sl); + Collection possibleOR = new ArrayList(); + for (Statement s : subjectRight.getValues(sr)) { + possibleOR.add(s.getObject()); + } + Map> matchingPaths = new HashMap>(); + for (Resource or : possibleOR) { + Set possiblePathsRight = new HashSet(); + for (Path leftPath : pathsLeft) { + possiblePathsRight.addAll(findComparableRight(leftPath, or)); + } + if (possiblePathsRight.size() == pathsLeft.size()) { + matchingPaths.put(or, possiblePathsRight); + } + } + if (matchingPaths.size() > 0) { + if (matchingPaths.size() == 1) { + Resource or = matchingPaths.keySet().iterator().next(); + objectsLeft.add(ol); + objectsRight.add(or); + Collection statementsLeft = objectLeft.getValues(ol); + Collection statementsRight = objectRight.getValues(or); + unreliableLeft.removeAll(statementsLeft); + unreliableRight.removeAll(statementsRight); + System.out.println(); + } else { + System.out.println(); + } + } + } + + } + + } + + private void expand(Set paths) throws ManyObjectsForFunctionalRelationException, ServiceException { + Set stepPathsLeft = new HashSet(); + if (paths.size() == 0) + return; + int length = paths.iterator().next().getLength() + 1; + for (Path p : paths) { + for (Resource rel : traversed) { + stepPathsLeft.addAll(Path.expand(p,g.getStatements(p.getEnd(), rel))); + } + } + paths.clear(); + for (Path p : stepPathsLeft) { + if (p.getLength() == length) + paths.add(p); + } + } + + private Collection findComparableRight(Path leftPath, Resource beginRight) throws ManyObjectsForFunctionalRelationException, ServiceException { + Set rightPaths = new HashSet(); + rightPaths.addAll(Path.create(g.getStatements(beginRight, getRight(leftPath.getStatements().get(0).getPredicate())))); + for (int i = 1; i < leftPath.getLength(); i++) { + if (rightPaths.size() == 0) + return rightPaths; + Set stepPaths = new HashSet(); + for (Path p : rightPaths) { + stepPaths.addAll(Path.expand(p, g.getStatements(p.getEnd(), getRight(leftPath.getStatements().get(i).getPredicate())))); + } + rightPaths.clear(); + for (Path p : stepPaths) + if (p.getLength() == i+1) + rightPaths.add(p); + } + return rightPaths; + + } + + private Resource getRight(Resource r) { + if (comparableResources.containsLeft(r)) + return comparableResources.getRight(r); + return r; + } + + + public BijectionMap getComparableStatements() { return comparableStatements; } diff --git a/org.simantics.interop/src/org/simantics/interop/test/Path.java b/org.simantics.interop/src/org/simantics/interop/test/Path.java new file mode 100644 index 0000000..b772267 --- /dev/null +++ b/org.simantics.interop/src/org/simantics/interop/test/Path.java @@ -0,0 +1,99 @@ +package org.simantics.interop.test; + +import java.util.ArrayList; +import java.util.Collection; +import java.util.List; + +import org.simantics.db.Resource; +import org.simantics.db.Statement; + +public class Path { + private Resource begin; + private Resource end; + private List statements = new ArrayList(2); + + public Path(Statement s) { + begin = s.getSubject(); + end = s.getObject(); + statements.add(s); + } + + public Path(Path p) { + begin = p.begin; + end = p.end; + statements.addAll(p.statements); + } + + public Resource getBegin() { + return begin; + } + + public Resource getEnd() { + return end; + } + + public List getStatements() { + return statements; + } + + public int getLength() { + return statements.size(); + } + + public boolean add(Statement s) { + if (!statements.get(statements.size()-1).getObject().equals(s.getSubject())) + //throw new RuntimeException("Non continuous path. " + s.getSubject() + " does not match " + statements.get(statements.size()-1).getObject()); + return false; + if (s.getObject().equals(begin)) + return false; + for (Statement stm : statements) { + if (stm.getObject().equals(s.getObject())) + return false; + } + end = s.getObject(); + statements.add(s); + return true; + } + + public static Collection expand(Path path, Collection statements) { + Collection result = new ArrayList(statements.size()); + for (Statement s : statements) { + Path p = new Path(path); + p.add(s); + result.add(p); + } + return result; + } + + public static Collection create(Collection statements) { + Collection result = new ArrayList(statements.size()); + for (Statement s : statements) { + Path p = new Path(s); + result.add(p); + } + return result; + } + + @Override + public boolean equals(Object arg0) { + if(!arg0.getClass().equals(getClass())) + return false; + Path other = (Path)arg0; + if (!begin.equals(other.begin)) + return false; + if (!end.equals(other.end)) + return false; + if (statements.size() != other.statements.size()) + return false; + for (int i = 0; i < statements.size(); i++) { + if (!statements.get(i).equals(other.statements.get(i))) + return false; + } + return false; + } + + @Override + public int hashCode() { + return begin.hashCode() + end.hashCode(); + } +} -- 2.46.2