From 3d44aee6069175038266c65f945147569e6343f6 Mon Sep 17 00:00:00 2001 From: RncLsn Date: Thu, 9 Jul 2015 16:01:01 +0100 Subject: Bug-fix for answer dependencies analysis: now it checks whether the endomorphism makes the first tuple identical to the second one. --- .../ac/ox/cs/pagoda/endomorph/DependencyGraph.java | 7 ++- .../ox/cs/pagoda/endomorph/EndomorphChecker.java | 1 + .../ox/cs/pagoda/endomorph/EndomorphChecker1.java | 10 ++-- .../ox/cs/pagoda/endomorph/EndomorphChecker2.java | 53 ++++++++++++------- .../ox/cs/pagoda/endomorph/plan/OpenEndPlan.java | 3 +- test/resources/BugTests.xml | 1 + test/resources/MainTests.xml | 8 +-- .../cs/pagoda/endomorph/DependencyGraphTest.java | 59 ++++++++++++++++++++++ test/uk/ac/ox/cs/pagoda/global_tests/BugTests.java | 14 +++-- test/uk/ac/ox/cs/pagoda/util/TestUtil.java | 7 +++ 10 files changed, 128 insertions(+), 35 deletions(-) create mode 100644 test/uk/ac/ox/cs/pagoda/endomorph/DependencyGraphTest.java diff --git a/src/uk/ac/ox/cs/pagoda/endomorph/DependencyGraph.java b/src/uk/ac/ox/cs/pagoda/endomorph/DependencyGraph.java index 8514808..320af09 100644 --- a/src/uk/ac/ox/cs/pagoda/endomorph/DependencyGraph.java +++ b/src/uk/ac/ox/cs/pagoda/endomorph/DependencyGraph.java @@ -240,6 +240,11 @@ public class DependencyGraph { private boolean checkHomomorphism(NodeTuple u, NodeTuple v) { ++homomorphismCheckCounter; homomorphismChecker.setMapping(u, v); + + // TODO recently added, test it + if(!homomorphismChecker.isMappingTo(u, v)) + return false; + try { Node node1, node2; for (Iterator iter1 = u.getNodes().iterator(), iter2 = v.getNodes().iterator(); iter1.hasNext(); ) { @@ -251,7 +256,7 @@ public class DependencyGraph { } return true; } finally { - homomorphismChecker.clearMappings(); + homomorphismChecker.clearMappings(); } } diff --git a/src/uk/ac/ox/cs/pagoda/endomorph/EndomorphChecker.java b/src/uk/ac/ox/cs/pagoda/endomorph/EndomorphChecker.java index 8f5ea07..46ddbb3 100644 --- a/src/uk/ac/ox/cs/pagoda/endomorph/EndomorphChecker.java +++ b/src/uk/ac/ox/cs/pagoda/endomorph/EndomorphChecker.java @@ -11,4 +11,5 @@ public interface EndomorphChecker { boolean check(Node next, Node next2); + boolean isMappingTo(NodeTuple u, NodeTuple v); } diff --git a/src/uk/ac/ox/cs/pagoda/endomorph/EndomorphChecker1.java b/src/uk/ac/ox/cs/pagoda/endomorph/EndomorphChecker1.java index ca1256c..c2117b6 100644 --- a/src/uk/ac/ox/cs/pagoda/endomorph/EndomorphChecker1.java +++ b/src/uk/ac/ox/cs/pagoda/endomorph/EndomorphChecker1.java @@ -15,9 +15,13 @@ public class EndomorphChecker1 implements EndomorphChecker { public boolean check(Node u, Node v) { if (!u.isSubConceptOf(v)) return false; - if (!isSubsetOf(graph.getOutGoingEdges(u), graph.getOutGoingEdges(v), true)) return false; - if (!isSubsetOf(graph.getInComingEdges(u), graph.getInComingEdges(v), false)) return false; - return true; + if (!isSubsetOf(graph.getOutGoingEdges(u), graph.getOutGoingEdges(v), true)) return false; + return isSubsetOf(graph.getInComingEdges(u), graph.getInComingEdges(v), false); + } + + @Override + public boolean isMappingTo(NodeTuple u, NodeTuple v) { + throw new UnsupportedOperationException(); } private boolean isSubsetOf(Edge[] e1, Edge[] e2, boolean out) { diff --git a/src/uk/ac/ox/cs/pagoda/endomorph/EndomorphChecker2.java b/src/uk/ac/ox/cs/pagoda/endomorph/EndomorphChecker2.java index 7ad271a..aac5f3c 100644 --- a/src/uk/ac/ox/cs/pagoda/endomorph/EndomorphChecker2.java +++ b/src/uk/ac/ox/cs/pagoda/endomorph/EndomorphChecker2.java @@ -1,17 +1,13 @@ package uk.ac.ox.cs.pagoda.endomorph; -import java.util.HashMap; -import java.util.HashSet; -import java.util.Iterator; -import java.util.Map; -import java.util.Set; - import uk.ac.ox.cs.pagoda.summary.Edge; import uk.ac.ox.cs.pagoda.summary.Graph; import uk.ac.ox.cs.pagoda.summary.Node; import uk.ac.ox.cs.pagoda.summary.NodeTuple; import uk.ac.ox.cs.pagoda.util.Timer; +import java.util.*; + public class EndomorphChecker2 implements EndomorphChecker { private Graph graph; @@ -24,7 +20,8 @@ public class EndomorphChecker2 implements EndomorphChecker { private Timer timer = new Timer(); private boolean time_out = false; private static final int TIME_OUT = 60; - +// private static final int TIME_OUT = 99999999; + public boolean check(NodeTuple u, NodeTuple v) { int length = u.getNodes().size(); Edge[][] ss = new Edge[1][length], tt = new Edge[1][length]; @@ -39,15 +36,35 @@ public class EndomorphChecker2 implements EndomorphChecker { } public boolean check(Node u, Node v) { - if (!u.isSubConceptOf(v)) return false; - if (!checkSortedEdges(new Edge[][] {graph.getOutGoingEdges(u), graph.getInComingEdges(u) }, - new Edge[][] {graph.getOutGoingEdges(v), graph.getInComingEdges(v)}, 0, 0)) { - return false; - } - return true; - } + if (!u.isSubConceptOf(v)) return false; + return checkSortedEdges(new Edge[][]{graph.getOutGoingEdges(u), graph.getInComingEdges(u)}, + new Edge[][]{graph.getOutGoingEdges(v), graph.getInComingEdges(v)}, 0, 0); + } + + /*** + * Checks whether the found mapping is actually a mapping from tuple u to tuple v. + * + * @param u + * @param v + * @return + */ + @Override + public boolean isMappingTo(NodeTuple u, NodeTuple v) { + Iterator uIterator = u.getNodes().iterator(); + Iterator vIterator = v.getNodes().iterator(); + + while(uIterator.hasNext() && vIterator.hasNext()) { + Node uNode = uIterator.next(); + Node vNode = vIterator.next(); + if(mappings.containsKey(uNode) && !mappings.get(uNode).equals(vNode)) + return false; + else if(!mappings.containsKey(uNode) && !uNode.equals(vNode)) + return false; + } + return !uIterator.hasNext() && !vIterator.hasNext(); + } - Map mappings = new HashMap(); + Map mappings = new HashMap(); public void clearMappings() { mappings.clear(); @@ -100,9 +117,9 @@ public class EndomorphChecker2 implements EndomorphChecker { return true; mappings.remove(u); return false; - }; - - for (Node v: candidates) { + } + + for (Node v: candidates) { mappings.put(u, v); if (check(u, v) && checkSortedEdges(ss, st, dim, index + 1)) return true; diff --git a/src/uk/ac/ox/cs/pagoda/endomorph/plan/OpenEndPlan.java b/src/uk/ac/ox/cs/pagoda/endomorph/plan/OpenEndPlan.java index a46da85..076427e 100644 --- a/src/uk/ac/ox/cs/pagoda/endomorph/plan/OpenEndPlan.java +++ b/src/uk/ac/ox/cs/pagoda/endomorph/plan/OpenEndPlan.java @@ -71,7 +71,8 @@ public class OpenEndPlan implements CheckPlan { else { Utility.logDebug(answerTuple.toString() + " is verified."); addProjections(clique); - flag = true; + flag = true; + validated.add(clique); } } } diff --git a/test/resources/BugTests.xml b/test/resources/BugTests.xml index c7a80ba..1413b5b 100644 --- a/test/resources/BugTests.xml +++ b/test/resources/BugTests.xml @@ -6,6 +6,7 @@ + diff --git a/test/resources/MainTests.xml b/test/resources/MainTests.xml index db8d977..255b68e 100644 --- a/test/resources/MainTests.xml +++ b/test/resources/MainTests.xml @@ -5,19 +5,19 @@ - + - + - + - + diff --git a/test/uk/ac/ox/cs/pagoda/endomorph/DependencyGraphTest.java b/test/uk/ac/ox/cs/pagoda/endomorph/DependencyGraphTest.java new file mode 100644 index 0000000..eec1e8f --- /dev/null +++ b/test/uk/ac/ox/cs/pagoda/endomorph/DependencyGraphTest.java @@ -0,0 +1,59 @@ +package uk.ac.ox.cs.pagoda.endomorph; + +import org.semanticweb.owlapi.apibinding.OWLManager; +import org.semanticweb.owlapi.model.*; +import org.testng.annotations.Test; +import uk.ac.ox.cs.JRDFox.model.GroundTerm; +import uk.ac.ox.cs.JRDFox.model.Individual; +import uk.ac.ox.cs.pagoda.query.AnswerTuple; +import uk.ac.ox.cs.pagoda.summary.Graph; +import uk.ac.ox.cs.pagoda.summary.NodeTuple; +import uk.ac.ox.cs.pagoda.util.TestUtil; + +import java.util.HashSet; + +import static uk.ac.ox.cs.pagoda.util.TestUtil.getEntityIRI; + +public class DependencyGraphTest { + + private OWLOntology getOntology() throws OWLOntologyCreationException { + OWLOntologyManager manager = OWLManager.createOWLOntologyManager(); + OWLDataFactory factory = manager.getOWLDataFactory(); + OWLOntology ontology = manager.createOntology(); + + OWLClass hardWorkingStudent = factory.getOWLClass(getEntityIRI("HardWorkingStudent")); + manager.addAxiom(ontology, factory.getOWLDeclarationAxiom(hardWorkingStudent)); + OWLNamedIndividual a = factory.getOWLNamedIndividual(getEntityIRI("a")); + OWLNamedIndividual b = factory.getOWLNamedIndividual(getEntityIRI("b")); + OWLObjectProperty takesCourse = factory.getOWLObjectProperty(IRI.create(String.format(TestUtil.NS, "takesCourse"))); + manager.addAxiom(ontology, factory.getOWLDeclarationAxiom(takesCourse)); + + // Class assertions + manager.addAxiom(ontology, factory.getOWLClassAssertionAxiom(hardWorkingStudent, a)); // HardWorkingStudent(a) + manager.addAxiom(ontology, factory.getOWLClassAssertionAxiom(hardWorkingStudent, b)); // HardWorkingStudent(b) + + // Minimum cardinality axiom + manager.addAxiom(ontology, + factory.getOWLEquivalentClassesAxiom(hardWorkingStudent, + factory.getOWLObjectMinCardinality(3, + takesCourse))); + return ontology; + } + + @Test + public void test() throws OWLOntologyCreationException { + OWLOntology ontology = getOntology(); + Graph graph = new Graph(ontology); + DependencyGraph dependencyGraph = new DependencyGraph(graph); + + HashSet tuples = new HashSet<>(); + tuples.add(graph.getNodeTuple(new AnswerTuple(new GroundTerm[]{Individual.create(String.format(TestUtil.NS, "a")), Individual.create(String.format(TestUtil.NS, "a"))}))); + tuples.add(graph.getNodeTuple(new AnswerTuple(new GroundTerm[]{Individual.create(String.format(TestUtil.NS, "a")), Individual.create(String.format(TestUtil.NS, "b"))}))); + tuples.add(graph.getNodeTuple(new AnswerTuple(new GroundTerm[]{Individual.create(String.format(TestUtil.NS, "b")), Individual.create(String.format(TestUtil.NS, "a"))}))); + tuples.add(graph.getNodeTuple(new AnswerTuple(new GroundTerm[]{Individual.create(String.format(TestUtil.NS, "b")), Individual.create(String.format(TestUtil.NS, "b"))}))); + + dependencyGraph.build(tuples); + + System.out.println(dependencyGraph.getTopologicalOrder()); + } +} diff --git a/test/uk/ac/ox/cs/pagoda/global_tests/BugTests.java b/test/uk/ac/ox/cs/pagoda/global_tests/BugTests.java index 6e60e24..3f14ec7 100644 --- a/test/uk/ac/ox/cs/pagoda/global_tests/BugTests.java +++ b/test/uk/ac/ox/cs/pagoda/global_tests/BugTests.java @@ -14,13 +14,11 @@ import java.io.IOException; import java.nio.file.Files; import java.nio.file.Paths; +import static uk.ac.ox.cs.pagoda.util.TestUtil.getEntityIRI; + public class BugTests { - public static final String NS = "http://example.org/test#%s"; - private IRI getEntityIRI(String name) { - return IRI.create(String.format(NS, name)); - } @Test public void minimumCardinalityAxiom2() throws OWLOntologyCreationException, IOException, OWLOntologyStorageException { @@ -41,7 +39,7 @@ public class BugTests { manager.addAxiom(ontology, factory.getOWLDeclarationAxiom(hardWorkingStudent)); OWLNamedIndividual a = factory.getOWLNamedIndividual(getEntityIRI("a")); OWLNamedIndividual b = factory.getOWLNamedIndividual(getEntityIRI("b")); - OWLObjectProperty takesCourse = factory.getOWLObjectProperty(IRI.create(String.format(NS, "takesCourse"))); + OWLObjectProperty takesCourse = factory.getOWLObjectProperty(IRI.create(String.format(TestUtil.NS, "takesCourse"))); manager.addAxiom(ontology, factory.getOWLDeclarationAxiom(takesCourse)); // Class assertions @@ -105,7 +103,7 @@ public class BugTests { OWLNamedIndividual d1 = factory.getOWLNamedIndividual(getEntityIRI("d1")); OWLNamedIndividual d2 = factory.getOWLNamedIndividual(getEntityIRI("d2")); OWLNamedIndividual d3 = factory.getOWLNamedIndividual(getEntityIRI("d3")); - OWLObjectProperty takesCourse = factory.getOWLObjectProperty(IRI.create(String.format(NS, "takesCourse"))); + OWLObjectProperty takesCourse = factory.getOWLObjectProperty(IRI.create(String.format(TestUtil.NS, "takesCourse"))); manager.addAxiom(ontology, factory.getOWLDeclarationAxiom(takesCourse)); // Class assertions @@ -183,9 +181,9 @@ public class BugTests { OWLNamedIndividual a = factory.getOWLNamedIndividual(getEntityIRI("a")); OWLNamedIndividual b = factory.getOWLNamedIndividual(getEntityIRI("b")); OWLNamedIndividual c = factory.getOWLNamedIndividual(getEntityIRI("c")); - OWLObjectProperty roleR = factory.getOWLObjectProperty(IRI.create(String.format(NS, "R"))); + OWLObjectProperty roleR = factory.getOWLObjectProperty(IRI.create(String.format(TestUtil.NS, "R"))); manager.addAxiom(ontology, factory.getOWLDeclarationAxiom(roleR)); - OWLObjectProperty roleP = factory.getOWLObjectProperty(IRI.create(String.format(NS, "P"))); + OWLObjectProperty roleP = factory.getOWLObjectProperty(IRI.create(String.format(TestUtil.NS, "P"))); manager.addAxiom(ontology, factory.getOWLDeclarationAxiom(roleP)); // Class assertions diff --git a/test/uk/ac/ox/cs/pagoda/util/TestUtil.java b/test/uk/ac/ox/cs/pagoda/util/TestUtil.java index fdd242a..c7f024a 100644 --- a/test/uk/ac/ox/cs/pagoda/util/TestUtil.java +++ b/test/uk/ac/ox/cs/pagoda/util/TestUtil.java @@ -3,6 +3,7 @@ package uk.ac.ox.cs.pagoda.util; import org.apache.log4j.Appender; import org.apache.log4j.FileAppender; import org.apache.log4j.Logger; +import org.semanticweb.owlapi.model.IRI; import java.io.File; import java.io.IOException; @@ -87,4 +88,10 @@ public class TestUtil { LOGGER.error(msg, t); } + public static final String NS = "http://example.org/test#%s"; + + public static IRI getEntityIRI(String name) { + return IRI.create(String.format(NS, name)); + } + } -- cgit v1.2.3