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

5 files changed, 51 insertions, 23 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);
                                 }
                         }
                 }