Bug-fix for answer dependencies analysis: now it checks whether the endomorphism makes the first tuple identical to the second one.

10 files changed, 128 insertions, 35 deletions

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<Node> 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<Node> uIterator = u.getNodes().iterator();
+        Iterator<Node> 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<Node, Node> mappings = new HashMap<Node, Node>();
+    Map<Node, Node> mappings = new HashMap<Node, Node>();
 
         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 @@
     <test name="BugTest">
         <classes>
             <class name="uk.ac.ox.cs.pagoda.global_tests.BugTests"/>
+            <!--<class name="uk.ac.ox.cs.pagoda.endomorph.DependencyGraphTest"/>-->
         </classes>
     </test>
 
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 @@
     <test name="main">
         <groups>
             <run>
-                <include name="correctness"/>
+                <!--<include name="correctness"/>-->
                 <!--<include name="light"/>-->
                 <!--<include name="justExecute"/>-->
                 <!--&lt;!&ndash;<include name="heavy"/>&ndash;&gt;-->
-                <!--<include name="nonOriginal"/>-->
+                <include name="nonOriginal"/>
             </run>
         </groups>
         <classes>
             <!--<class name="uk.ac.ox.cs.pagoda.global_tests.TestPagodaReactome"/>-->
             <!--<class name="uk.ac.ox.cs.pagoda.global_tests.TestPagodaUOBM"/>-->
-            <class name="uk.ac.ox.cs.pagoda.global_tests.TestPagodaLUBM"/>
+            <!--<class name="uk.ac.ox.cs.pagoda.global_tests.TestPagodaLUBM"/>-->
             <!--Fly does not terminate: query-5 looks really hard-->
-            <!--<class name="uk.ac.ox.cs.pagoda.global_tests.TestPagodaFLY"/>-->
+            <class name="uk.ac.ox.cs.pagoda.global_tests.TestPagodaFLY"/>
             <!--<class name="uk.ac.ox.cs.pagoda.global_tests.SkolemisationTests"/>-->
             <!--<class name="uk.ac.ox.cs.pagoda.util.SimpleProgressBarTester" />-->
         </classes>
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<NodeTuple> 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));
+    }
+
 }