fixed a bug in the process of generating gap tuples, see test in

TestGapMappedToLower.java

4 files changed, 46 insertions, 20 deletions

diff --git a/src/uk/ac/ox/cs/pagoda/endomorph/Clique.java b/src/uk/ac/ox/cs/pagoda/endomorph/Clique.java
index 1c269ea..9daea7e 100644
--- a/src/uk/ac/ox/cs/pagoda/endomorph/Clique.java
+++ b/src/uk/ac/ox/cs/pagoda/endomorph/Clique.java
@@ -13,6 +13,7 @@ public class Clique {
         public Clique(NodeTuple u) {
                 nodeTuples = new HashSet<NodeTuple>(); 
                 representative = u;
+                nodeTuples.add(u);
         }
 
         public boolean addNodeTuple(NodeTuple nodeTuple) {
diff --git a/src/uk/ac/ox/cs/pagoda/endomorph/plan/OpenEndMultiThreadPlan.java b/src/uk/ac/ox/cs/pagoda/endomorph/plan/OpenEndMultiThreadPlan.java
index 8c7ce6a..4e2fc5f 100644
--- a/src/uk/ac/ox/cs/pagoda/endomorph/plan/OpenEndMultiThreadPlan.java
+++ b/src/uk/ac/ox/cs/pagoda/endomorph/plan/OpenEndMultiThreadPlan.java
@@ -69,7 +69,7 @@ public class OpenEndMultiThreadPlan implements CheckPlan {
                 int count = 0; 
                 for (Clique c: dGraph.getTopologicalOrder()) {
                         if (validated.contains(c))
-                                count += c.getNodeTuples().size() + 1; 
+                                count += c.getNodeTuples().size(); 
                 }
                 return count;           
         }
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 202021d..a740833 100644
--- a/src/uk/ac/ox/cs/pagoda/endomorph/plan/OpenEndPlan.java
+++ b/src/uk/ac/ox/cs/pagoda/endomorph/plan/OpenEndPlan.java
@@ -1,7 +1,6 @@
 package uk.ac.ox.cs.pagoda.endomorph.plan;
 
 import java.util.Collection;
-import java.util.Deque;
 import java.util.HashSet;
 import java.util.LinkedList;
 import java.util.Map;
@@ -23,35 +22,39 @@ public class OpenEndPlan implements CheckPlan {
         Checker checker; 
         DependencyGraph dGraph; 
         QueryRecord m_record; 
+        int m_answerArity; 
 
         public OpenEndPlan(Checker checker, DependencyGraph dGraph, QueryRecord record) {
                 this.checker = checker; 
                 this.dGraph = dGraph;
-                m_record = record; 
+                m_record = record;
+                m_answerArity = record.getAnswerVariables().length;
         }
         
+        Set<Clique> validated = new HashSet<Clique>(); 
+        Set<Clique> falsified = new HashSet<Clique>(); 
+        Set<AnswerTuple> passedAnswers = new HashSet<AnswerTuple>();
+        
         @Override
         public int check() {
-                Deque<Clique> topo = new LinkedList<Clique>(dGraph.getTopologicalOrder());
+                LinkedList<Clique> topo = new LinkedList<Clique>(dGraph.getTopologicalOrder());
                 Utility.logInfo("Entrances: " + dGraph.getEntrances().size() + " Exists: " + dGraph.getExits().size()); 
-                Set<Clique> validated = new HashSet<Clique>(); 
-                Set<Clique> falsified = new HashSet<Clique>(); 
 
                 boolean flag = true;
                 Clique clique; 
                 Timer t = new Timer(); 
                 
-
-                AnswerTuple answerTuple; 
+                AnswerTuple answerTuple;
                 while (!topo.isEmpty()) { 
                         if (flag) {
-                                clique = topo.removeFirst(); 
+                                clique = topo.removeFirst();
+                                if (redundant(clique)) continue; 
                                 if (validated.contains(clique)) continue; 
                                 if (falsified.contains(clique)) { flag = false; continue; }
                                 Utility.logDebug("start checking front ... " + (answerTuple = clique.getRepresentative().getAnswerTuple())); 
                                 if (checker.check(answerTuple)) {
                                         Utility.logDebug(answerTuple.toString() + " is verified.");
-                                        setMarkCascadely(clique, validated, dGraph.getOutGoingEdges()); 
+                                        setMarkCascadelyValidated(clique); 
                                 }
                                 else {
                                         falsified.add(clique);
@@ -64,10 +67,10 @@ public class OpenEndPlan implements CheckPlan {
                                 if (validated.contains(clique)) { flag = true; continue; }
                                 Utility.logDebug("start checking back ... " + (answerTuple = clique.getRepresentative().getAnswerTuple())); 
                                 if (!checker.check(answerTuple)) 
-                                        setMarkCascadely(clique, falsified, dGraph.getInComingEdges()); 
+                                        setMarkCascadelyFasified(clique); 
                                 else {
                                         Utility.logDebug(answerTuple.toString() + " is verified.");
-                                        validated.add(clique);
+                                        addProjections(clique); 
                                         flag = true; 
                                 }
                         }
@@ -80,9 +83,8 @@ public class OpenEndPlan implements CheckPlan {
                 Collection<AnswerTuple> validAnswers = new LinkedList<AnswerTuple>(); 
                 for (Clique c: dGraph.getTopologicalOrder()) 
                         if (validated.contains(c)) {
-                                count += c.getNodeTuples().size() + 1;
-                                validAnswers.add(c.getRepresentative().getAnswerTuple()); 
-                                
+                                count += c.getNodeTuples().size();
+//                              validAnswers.add(c.getRepresentative().getAnswerTuple()); 
                                 for (NodeTuple nodeTuple: c.getNodeTuples()) {
                                         ans = nodeTuple.getAnswerTuple(); 
                                         validAnswers.add(ans);
@@ -95,12 +97,35 @@ public class OpenEndPlan implements CheckPlan {
                 return count;           
         }
 
-        private void setMarkCascadely(Clique clique, Set<Clique> marked, Map<Clique, Collection<Clique>> edges) {
-                marked.add(clique); 
+        private boolean redundant(Clique clique) {
+                for (NodeTuple nodeTuple: clique.getNodeTuples())
+                        if (!passedAnswers.contains(AnswerTuple.create(nodeTuple.getAnswerTuple(), m_answerArity))) 
+                                return false; 
+                return true;
+        }
+
+        private void addProjections(Clique clique) {
+                for (NodeTuple nodeTuple: clique.getNodeTuples()) 
+                        passedAnswers.add(AnswerTuple.create(nodeTuple.getAnswerTuple(), m_answerArity)); 
+        }
+
+        private void setMarkCascadelyValidated(Clique clique) { 
+                validated.add(clique);
+                addProjections(clique);
+                Map<Clique, Collection<Clique>> edges = dGraph.getOutGoingEdges(); 
+                if (edges.containsKey(clique))
+                        for (Clique c: edges.get(clique))
+                                if (!validated.contains(c)) 
+                                        setMarkCascadelyValidated(c);
+        }
+
+        private void setMarkCascadelyFasified(Clique clique) { 
+                        falsified.add(clique);
+                Map<Clique, Collection<Clique>> edges = dGraph.getInComingEdges(); 
                 if (edges.containsKey(clique))
                         for (Clique c: edges.get(clique))
-                                if (!marked.contains(c)) 
-                                        setMarkCascadely(c, marked, edges);
+                                if (!falsified.contains(c)) 
+                                        setMarkCascadelyFasified(c);
         }
 
 }
diff --git a/src/uk/ac/ox/cs/pagoda/endomorph/plan/PlainPlan.java b/src/uk/ac/ox/cs/pagoda/endomorph/plan/PlainPlan.java
index d6067d0..6931ccc 100644
--- a/src/uk/ac/ox/cs/pagoda/endomorph/plan/PlainPlan.java
+++ b/src/uk/ac/ox/cs/pagoda/endomorph/plan/PlainPlan.java
@@ -22,7 +22,7 @@ public class PlainPlan implements CheckPlan {
                 int count = 0; 
                 for (Clique clique: toCheck)
                         if (checker.check(clique.getRepresentative().getAnswerTuple())) {
-                                count += clique.getNodeTuples().size() + 1; 
+                                count += clique.getNodeTuples().size(); 
                                 for (NodeTuple nodeTuple: clique.getNodeTuples()) 
                                         Utility.logDebug(nodeTuple.getAnswerTuple().toString());
                         }