initial version

10 files changed, 895 insertions, 0 deletions

diff --git a/src/uk/ac/ox/cs/pagoda/endomorph/Clique.java b/src/uk/ac/ox/cs/pagoda/endomorph/Clique.java
new file mode 100644
index 0000000..1c269ea
--- /dev/null
+++ b/src/uk/ac/ox/cs/pagoda/endomorph/Clique.java
@@ -0,0 +1,36 @@
+package uk.ac.ox.cs.pagoda.endomorph;
+
+import java.util.Collection;
+import java.util.HashSet;
+import java.util.Set;
+
+import uk.ac.ox.cs.pagoda.summary.NodeTuple;
+
+public class Clique {
+        NodeTuple representative; 
+        Set<NodeTuple> nodeTuples = null; 
+        
+        public Clique(NodeTuple u) {
+                nodeTuples = new HashSet<NodeTuple>(); 
+                representative = u;
+        }
+
+        public boolean addNodeTuple(NodeTuple nodeTuple) {
+                return nodeTuples.add(nodeTuple); 
+        }
+        
+        public NodeTuple getRepresentative() {
+                return representative; 
+        }
+        
+        @Override
+        public String toString() {
+                return representative.toString(); 
+        }
+
+        public Collection<NodeTuple> getNodeTuples() {
+                return nodeTuples; 
+        }
+        
+}
+
diff --git a/src/uk/ac/ox/cs/pagoda/endomorph/DependencyGraph.java b/src/uk/ac/ox/cs/pagoda/endomorph/DependencyGraph.java
new file mode 100644
index 0000000..307fa33
--- /dev/null
+++ b/src/uk/ac/ox/cs/pagoda/endomorph/DependencyGraph.java
@@ -0,0 +1,295 @@
+ package uk.ac.ox.cs.pagoda.endomorph;
+
+import java.util.Arrays;
+import java.util.Collection;
+import java.util.Comparator;
+import java.util.HashMap;
+import java.util.HashSet;
+import java.util.Iterator;
+import java.util.LinkedList;
+import java.util.Map;
+import java.util.Queue;
+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 uk.ac.ox.cs.pagoda.util.Utility;
+
+public class DependencyGraph {
+
+        Set<Clique> entrances = new HashSet<Clique>();
+
+        public Set<Clique> getEntrances() {
+                return entrances;
+        }
+        
+        Set<Clique> exits = new HashSet<Clique>();  
+        
+        public Set<Clique> getExits() {
+                return exits;
+        }
+        
+        Map<Clique, Collection<Clique>> outGoingEdges = new HashMap<Clique, Collection<Clique>>();
+        
+        public Map<Clique, Collection<Clique>> getOutGoingEdges() {
+                return outGoingEdges;
+        }
+
+        Map<Clique, Collection<Clique>> inComingEdges = new HashMap<Clique, Collection<Clique>>();
+        
+        public Map<Clique, Collection<Clique>> getInComingEdges() {
+                return inComingEdges;
+        }
+
+        Graph graph; 
+        EndomorphChecker homomorphismChecker;
+        Set<Clique> cliques = new HashSet<Clique>(); 
+        
+        public DependencyGraph(Graph graph) {
+                this.graph = graph; 
+                homomorphismChecker = new EndomorphChecker2(graph);
+//              homomorphismChecker = new EndomorphChecker1(graph);
+        }
+        
+        private int compareNodeTuple(NodeTuple t1, NodeTuple t2) {
+                Iterator<Node> iter1 = t1.getNodes().iterator(); 
+                Iterator<Node> iter2 = t2.getNodes().iterator();
+                int ret; 
+                int index = 0;
+                Node u, v; 
+                while (iter1.hasNext()) {
+                        u = iter1.next(); v = iter2.next();
+                        if (u == null && v == null) {
+                                if ((ret = t1.getAnswerTuple().getGroundTerm(index).toString().compareTo(t2.getAnswerTuple().getGroundTerm(index).toString())) != 0)
+                                        return ret;
+                        }
+                        else if (u != null && v != null) { 
+                                if ((ret = compareNode(u, v)) != 0) return ret;
+                        }
+                        else if (u == null)
+                                return 1; 
+                        else if (v == null)
+                                return -1; 
+                                
+                }
+                
+                return 0; 
+        }
+        
+        private int compareNode(Node o1, Node o2) {
+                int result = o1.getConcepts().size() - o2.getConcepts().size();
+                if (result != 0) return dir(result);
+                Edge[] edge1 = graph.getOutGoingEdges(o1), edge2 = graph.getOutGoingEdges(o2);;
+                int len1 = edge1 == null ? 0 : edge1.length, len2 = edge2 == null ? 0 : edge2.length; 
+                result = len1 - len2; 
+                if (result != 0) return dir(result);
+                
+                edge1 = graph.getInComingEdges(o1); edge2 = graph.getInComingEdges(o2); 
+                len1 = edge1 == null ? 0 : edge1.length; len2 = edge2 == null ? 0 : edge2.length; 
+                result = len1 - len2;
+                if (result != 0) return dir(result);
+                
+                else return o1.getLabel().compareTo(o2.getLabel()); 
+        }
+        
+        private int dir(int flag) { return - flag; }
+        
+        public void build(Collection<NodeTuple> nodeTuples) {
+                
+                if (nodeTuples.isEmpty()) return ;
+                
+                Timer t = new Timer(); 
+                
+                NodeTuple[] nodeTupleArray = new NodeTuple[nodeTuples.size()]; 
+                nodeTuples.toArray(nodeTupleArray); 
+                
+                Arrays.sort(nodeTupleArray, new Comparator<NodeTuple>() {
+                        @Override
+                        public int compare(NodeTuple t1, NodeTuple t2) {
+                                return compareNodeTuple(t1, t2); 
+                        }
+                });
+                
+                Utility.logDebug(nodeTupleArray[0].toString(), 
+                                nodeTupleArray[nodeTupleArray.length - 1].toString()); 
+                
+                for (NodeTuple nodeTuple: nodeTupleArray) addNodeTuple(nodeTuple);
+                
+                Utility.logDebug("The number of times to call homomorphism checker: " + homomorphismCheckCounter + "(" + outGoingCheckCounter + "," + inComingCheckCounter + ").", 
+                                "Time to compute endomorphism relation: " + t.duration());
+                
+//              print(); 
+                
+                topolocialOrder = null;
+                Utility.logInfo("link: " + link);
+        }
+        
+        LinkedList<Clique> topolocialOrder = null; 
+
+        public LinkedList<Clique> getTopologicalOrder() {
+                if (topolocialOrder != null) return topolocialOrder;
+                
+                topolocialOrder = new LinkedList<Clique>(); 
+                Queue<Clique> toVisit = new LinkedList<Clique>(entrances); 
+                Map<Clique, Integer> toVisitedInComingDegree = new HashMap<Clique, Integer>();
+                
+                int count; 
+                while (!toVisit.isEmpty()) {
+                        Clique cu = toVisit.remove();
+                        topolocialOrder.add(cu); 
+                        if (outGoingEdges.containsKey(cu))
+                                for (Clique cv: outGoingEdges.get(cu)) {
+                                        if (toVisitedInComingDegree.containsKey(cv)) {
+                                                count = toVisitedInComingDegree.get(cv) - 1; 
+                                                toVisitedInComingDegree.put(cv, count); 
+                                        }
+                                        else 
+                                                toVisitedInComingDegree.put(cv, count = inComingEdges.get(cv).size() - 1); 
+                                        if (count == 0) 
+                                                toVisit.add(cv); 
+                                }
+                }
+                
+                return topolocialOrder; 
+        }
+
+        private void addNodeTuple(NodeTuple u) {
+                Queue<Clique> toCompare = new LinkedList<Clique>(entrances);
+                
+                Map<Clique, Integer> toVisitedDegree = new HashMap<Clique, Integer>();
+                Collection<Clique> directSuccessors = new LinkedList<Clique>(); 
+                
+                int count; 
+                while (!toCompare.isEmpty()) {
+                        Clique cv = toCompare.remove();
+                        ++outGoingCheckCounter; 
+                        if (checkHomomorphism(u, cv.representative)) {
+                                directSuccessors.add(cv); 
+                        }
+                        else {
+                                if (outGoingEdges.containsKey(cv))
+                                        for (Clique c: outGoingEdges.get(cv)) {
+                                                if (toVisitedDegree.containsKey(c)) {
+                                                        count = toVisitedDegree.get(c) - 1; 
+                                                        toVisitedDegree.put(c, count); 
+                                                }
+                                                else 
+                                                        toVisitedDegree.put(c, count = inComingEdges.get(c).size() - 1);
+                                                
+                                                if (count == 0) 
+                                                        toCompare.add(c);
+                                        }
+                        }
+                }
+                
+                if (directSuccessors.size() == 1) {
+                        Clique clique = directSuccessors.iterator().next();
+                        if (checkHomomorphism(clique.representative, u)) {
+                                clique.addNodeTuple(u);
+                                return ;
+                        }
+                }
+                
+                Clique cu = new Clique(u);
+                cliques.add(cu); 
+                
+                toCompare.clear();
+                Set<Clique> visited = new HashSet<Clique>();  
+                
+                if (directSuccessors.size() == 0) 
+                        toCompare.addAll(exits); 
+                else {
+                        for (Clique cv: directSuccessors)
+                                if (inComingEdges.containsKey(cv))
+                                        for (Clique cw: inComingEdges.get(cv)) {
+                                                visited.add(cw); 
+                                                toCompare.add(cw);
+                                        }
+                }
+                
+                
+                
+                Collection<Clique> directPredecessors = new LinkedList<Clique>(); 
+                        
+                while (!toCompare.isEmpty()) {
+                        Clique cv = toCompare.remove();
+                        ++inComingCheckCounter; 
+                        if (checkHomomorphism(cv.representative, u)) 
+                                directPredecessors.add(cv); 
+                        else {
+                                if (inComingEdges.containsKey(cv))
+                                        for (Clique c: inComingEdges.get(cv)) 
+                                                if (!visited.contains(c)) {
+                                                        visited.add(c); 
+                                                        toCompare.add(c);
+                                                }
+                        }
+                }
+                
+                for (Clique cv: directSuccessors) {
+                        if (entrances.contains(cv)) entrances.remove(cv); 
+                        link(cu, cv); 
+                }
+                
+                for (Clique cw: directPredecessors) {
+                        if (exits.contains(cw)) exits.remove(cw); 
+                        link(cw, cu);
+                }
+                
+                if (directPredecessors.size() == 0) entrances.add(cu); 
+                if (directSuccessors.size() == 0) exits.add(cu); 
+        }
+        
+        private int homomorphismCheckCounter = 0; 
+        private int outGoingCheckCounter = 0, inComingCheckCounter = 0; 
+        
+        private boolean checkHomomorphism(NodeTuple u, NodeTuple v) {
+                ++homomorphismCheckCounter; 
+                homomorphismChecker.setMapping(u, v);
+                try {
+                        Node node1, node2; 
+                        for (Iterator<Node> iter1 = u.getNodes().iterator(), iter2 = v.getNodes().iterator(); iter1.hasNext(); ) {
+                                node1 = iter1.next(); node2 = iter2.next(); 
+                                if (node1 != node2 && !homomorphismChecker.check(node1, node2)) {
+//                                      System.out.println(homomorphismChecker.check(node1, node2)); 
+                                        return false; 
+                                }
+                        }
+                        return true;
+                } finally {
+                        homomorphismChecker.clearMappings(); 
+                }
+        }
+
+        private void link(Clique u, Clique v) {
+                ++link; 
+                addToList(outGoingEdges, u, v); 
+                addToList(inComingEdges, v, u); 
+        }
+        
+        private int link = 0; 
+
+        private void addToList(Map<Clique, Collection<Clique>> map, Clique u, Clique v) {
+                Collection<Clique> temp; 
+                if ((temp = map.get(u)) == null) {
+                        temp = new LinkedList<Clique>(); 
+                        map.put(u, temp); 
+                }
+                temp.add(v); 
+        }
+        
+        public void print() {
+                System.out.println("---------- Dependency Graph -------------"); 
+                for (Clique u: cliques)
+                        if (outGoingEdges.containsKey(u))
+                                for (Clique v: outGoingEdges.get(u)) 
+                                        System.out.println(u + " -> " + v);
+                System.out.println("-----------------------------------------"); 
+        }
+        
+
+}
+
diff --git a/src/uk/ac/ox/cs/pagoda/endomorph/Endomorph.java b/src/uk/ac/ox/cs/pagoda/endomorph/Endomorph.java
new file mode 100644
index 0000000..e6b50f9
--- /dev/null
+++ b/src/uk/ac/ox/cs/pagoda/endomorph/Endomorph.java
@@ -0,0 +1,95 @@
+package uk.ac.ox.cs.pagoda.endomorph;
+
+import java.util.Collection;
+import java.util.LinkedList;
+
+import org.semanticweb.owlapi.model.OWLOntology;
+
+import uk.ac.ox.cs.pagoda.endomorph.plan.*;
+import uk.ac.ox.cs.pagoda.query.AnswerTuple;
+import uk.ac.ox.cs.pagoda.query.AnswerTuples;
+import uk.ac.ox.cs.pagoda.query.QueryRecord;
+import uk.ac.ox.cs.pagoda.reasoner.full.Checker;
+import uk.ac.ox.cs.pagoda.summary.Graph;
+import uk.ac.ox.cs.pagoda.summary.NodeTuple;
+import uk.ac.ox.cs.pagoda.util.Timer;
+import uk.ac.ox.cs.pagoda.util.Utility;
+
+public class Endomorph implements Checker {
+        
+        Checker fullReasoner; 
+        DependencyGraph dGraph; 
+        Graph graph; 
+        QueryRecord m_record; 
+
+        /**
+         * constructor using HermiTChecker ...  
+         * @throws Exception 
+         */
+        
+        public Endomorph(QueryRecord record, Checker checker) {
+                this.m_record = record; 
+                fullReasoner = checker; 
+                graph = new Graph(record.getRelevantOntology());
+                dGraph = new DependencyGraph(graph); 
+        }
+        
+        @Override
+        public int check(AnswerTuples answerTuples) {
+                Collection<NodeTuple> nodes = new LinkedList<NodeTuple>(); 
+                int counter = 0; 
+                
+                for (; answerTuples.isValid(); answerTuples.moveNext()) {
+                        ++counter; 
+                        nodes.add(graph.getNodeTuple(answerTuples.getTuple()));
+                }
+                answerTuples.dispose();
+
+                Timer t = new Timer(); 
+                dGraph.build(nodes);
+//              dGraph.print();
+                Utility.logDebug("@TIME to group individuals in the gap: " + t.duration());
+                Utility.logInfo("The number of different groups: " + dGraph.cliques.size()); 
+                
+                Utility.logInfo("The number of individuals to be checked by Homomorphism checker: " + counter);
+//              CheckPlan plan = new PlainPlan(this.checker, dGraph.cliques);
+//              CheckPlan plan = new OpenEndMultiThreadPlan(this.checker, dGraph);              
+                CheckPlan plan = new OpenEndPlan(fullReasoner, dGraph, m_record);               
+                int answerCounter = plan.check(); 
+                
+                Utility.logDebug("The number of correct answers: " + answerCounter);
+                return answerCounter; 
+        }
+
+        public OWLOntology getOntology() {
+                return m_record.getRelevantOntology(); 
+        }
+
+        @Override
+        public boolean check(AnswerTuple answerTuple) {
+                return fullReasoner.check(answerTuple);
+        }
+
+        @Override
+        public boolean isConsistent() {
+                return fullReasoner.isConsistent();
+        }
+
+        @Override
+        public void dispose() {
+                fullReasoner.dispose();
+        }
+        
+        public Graph getGraph() {
+                return graph; 
+        }
+        
+        public Checker getChecker() {
+                return fullReasoner; 
+        }
+
+        public DependencyGraph getDependencyGraph() {
+                return dGraph;
+        }
+        
+}
diff --git a/src/uk/ac/ox/cs/pagoda/endomorph/EndomorphChecker.java b/src/uk/ac/ox/cs/pagoda/endomorph/EndomorphChecker.java
new file mode 100644
index 0000000..8f5ea07
--- /dev/null
+++ b/src/uk/ac/ox/cs/pagoda/endomorph/EndomorphChecker.java
@@ -0,0 +1,14 @@
+package uk.ac.ox.cs.pagoda.endomorph;
+
+import uk.ac.ox.cs.pagoda.summary.Node;
+import uk.ac.ox.cs.pagoda.summary.NodeTuple;
+
+public interface EndomorphChecker {
+
+        void clearMappings();
+
+        void setMapping(NodeTuple u, NodeTuple v);
+
+        boolean check(Node next, Node next2);
+
+}
diff --git a/src/uk/ac/ox/cs/pagoda/endomorph/EndomorphChecker1.java b/src/uk/ac/ox/cs/pagoda/endomorph/EndomorphChecker1.java
new file mode 100644
index 0000000..ca1256c
--- /dev/null
+++ b/src/uk/ac/ox/cs/pagoda/endomorph/EndomorphChecker1.java
@@ -0,0 +1,49 @@
+package uk.ac.ox.cs.pagoda.endomorph;
+
+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;
+
+public class EndomorphChecker1 implements EndomorphChecker {
+        
+        private Graph graph; 
+        
+        public EndomorphChecker1(Graph graph) {
+                this.graph = graph;
+        }
+        
+        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; 
+        }
+
+        private boolean isSubsetOf(Edge[] e1, Edge[] e2, boolean out) {
+                int j = 0; 
+                for (int i = 0; i < e1.length; ++i) {
+                        while (j < e2.length && equals(e1[i], e2[j], out))
+                                ++j; 
+                }
+                return j < e2.length;                   
+        }
+
+        private boolean equals(Edge edge, Edge edge2, boolean out) {
+                if (!edge.getLabel().equals(edge2.getLabel())) return false;   
+                return out ? edge.getToNode().equals(edge2.getToNode()) : edge.getFromNode().equals(edge2.getFromNode()); 
+        }
+
+        @Override
+        public void clearMappings() {
+                // TODO Auto-generated method stub
+                
+        }
+
+        @Override
+        public void setMapping(NodeTuple u, NodeTuple v) {
+                // TODO Auto-generated method stub
+                
+        }
+
+}
diff --git a/src/uk/ac/ox/cs/pagoda/endomorph/EndomorphChecker2.java b/src/uk/ac/ox/cs/pagoda/endomorph/EndomorphChecker2.java
new file mode 100644
index 0000000..7ad271a
--- /dev/null
+++ b/src/uk/ac/ox/cs/pagoda/endomorph/EndomorphChecker2.java
@@ -0,0 +1,125 @@
+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;
+
+public class EndomorphChecker2 implements EndomorphChecker {
+        
+        private Graph graph; 
+//      DependencyGraph dGraph; 
+        
+        public EndomorphChecker2(Graph graph) {
+                this.graph = graph;
+        }
+        
+        private Timer timer = new Timer();
+        private boolean time_out = false; 
+        private static final int TIME_OUT = 60;
+        
+        public boolean check(NodeTuple u, NodeTuple v) {
+                int length = u.getNodes().size(); 
+                Edge[][] ss = new Edge[1][length], tt = new Edge[1][length];
+                int index = 0;
+                Iterator<Node> iter1 = u.getNodes().iterator(); 
+                Iterator<Node> iter2 = v.getNodes().iterator(); 
+                for (; iter1.hasNext(); ) {
+                        ss[0][index] = new Edge(null, iter1.next(), "auxilary" + index);
+                        tt[0][index++] = new Edge(null, iter2.next(), "auxilary" + index); 
+                }
+                return checkSortedEdges(ss, tt, 0, 0); 
+        }
+        
+        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; 
+        }
+
+        Map<Node, Node> mappings = new HashMap<Node, Node>();
+
+        public void clearMappings() {
+                mappings.clear();
+                timer.pause();
+        }
+        
+        public void setMapping(NodeTuple key, NodeTuple value) {
+                timer.resume(); 
+                // FIXME
+                timer.setTimeout(TIME_OUT);
+//              time_out = false;
+                for (Iterator<Node> key_iter = key.getNodes().iterator(), value_iter = value.getNodes().iterator(); key_iter.hasNext(); ) {
+                        mappings.put(key_iter.next(), value_iter.next());
+                }
+        }
+        
+        private boolean checkSortedEdges(Edge[][] ss, Edge[][] st, int dim, int index) {
+                if (time_out || timer.timeOut()) {
+                        time_out = true; 
+                        return false; 
+                }
+                
+                while (ss[dim] == null || index >= ss[dim].length)
+                        if (++dim >= ss.length) return true;
+                        else index = 0;
+                Edge[] s = ss[dim], t = st[dim];
+
+                if (t.length > 10) return false; 
+                
+                Node u = s[index].getDestinationNode(dim == 0), w;
+                Set<Node> candidates = new HashSet<Node>(); 
+                
+                for (int j = findFirstEdge(t, s[index].getLabel()); j < t.length; ++j) {
+                        if (j == -1) break;
+                        if (s[index].getLabel().equals(t[j].getLabel())) { 
+                                w = t[j].getDestinationNode(dim == 0); 
+                                candidates.add(w); 
+                        }
+                        else break; 
+                }
+
+                if ((w = mappings.get(u)) != null) 
+                        if (candidates.contains(w))
+                                return checkSortedEdges(ss, st, dim, index + 1); 
+                        else return false; 
+                
+                if (candidates.contains(u)) {
+                        mappings.put(u, u); 
+                        if (checkSortedEdges(ss, st, dim, index + 1))
+                                return true; 
+                        mappings.remove(u);
+                        return false; 
+                }; 
+        
+                for (Node v: candidates) {
+                        mappings.put(u, v); 
+                        if (check(u, v) && checkSortedEdges(ss, st, dim, index + 1))
+                                return true; 
+                        mappings.remove(u); 
+                }
+                        
+                return false;
+        }
+
+        private int findFirstEdge(Edge[] edges, String label) {
+                int left = 0, right = edges.length - 1, mid; 
+                while (left < right) {
+                        mid = left + (right - left) / 2; 
+                        if (edges[mid].getLabel().compareTo(label) < 0) left = mid + 1; 
+                        else right = mid; 
+                }
+                return right; 
+        }
+        
+}
diff --git a/src/uk/ac/ox/cs/pagoda/endomorph/plan/CheckPlan.java b/src/uk/ac/ox/cs/pagoda/endomorph/plan/CheckPlan.java
new file mode 100644
index 0000000..ab3735f
--- /dev/null
+++ b/src/uk/ac/ox/cs/pagoda/endomorph/plan/CheckPlan.java
@@ -0,0 +1,7 @@
+package uk.ac.ox.cs.pagoda.endomorph.plan;
+
+public interface CheckPlan {
+
+        public int check(); 
+        
+}
diff --git a/src/uk/ac/ox/cs/pagoda/endomorph/plan/OpenEndMultiThreadPlan.java b/src/uk/ac/ox/cs/pagoda/endomorph/plan/OpenEndMultiThreadPlan.java
new file mode 100644
index 0000000..8c7ce6a
--- /dev/null
+++ b/src/uk/ac/ox/cs/pagoda/endomorph/plan/OpenEndMultiThreadPlan.java
@@ -0,0 +1,136 @@
+package uk.ac.ox.cs.pagoda.endomorph.plan;
+
+import java.util.Collection;
+import java.util.Collections;
+import java.util.LinkedList;
+import java.util.Map;
+import java.util.Set;
+import java.util.concurrent.ConcurrentHashMap;
+import java.util.concurrent.ConcurrentLinkedDeque;
+import java.util.concurrent.atomic.AtomicInteger;
+
+import uk.ac.ox.cs.pagoda.endomorph.DependencyGraph;
+import uk.ac.ox.cs.pagoda.endomorph.Clique;
+import uk.ac.ox.cs.pagoda.query.AnswerTuple;
+import uk.ac.ox.cs.pagoda.reasoner.full.Checker;
+import uk.ac.ox.cs.pagoda.reasoner.full.HermitChecker;
+import uk.ac.ox.cs.pagoda.util.Utility;
+
+public class OpenEndMultiThreadPlan implements CheckPlan {
+        
+        Checker checker; 
+        DependencyGraph dGraph; 
+
+        public OpenEndMultiThreadPlan(Checker checker, DependencyGraph dGraph) {
+                this.checker = checker; 
+                this.dGraph = dGraph;
+        }
+        
+//      Clique[] topo;
+//      AtomicInteger open, end; 
+        ConcurrentLinkedDeque<Clique> topo; 
+        
+        Set<Clique> validated, falsified; 
+        
+        @Override
+        public int check() {
+                Collection<Clique> cliques = dGraph.getTopologicalOrder();
+//              topo = new LinkedBlockingDeque<Clique>(cliques);
+                topo = new ConcurrentLinkedDeque<Clique>(cliques); 
+                
+//              topo = new Clique[cliques.size()];
+//              int index = 0; 
+//              for (Clique clique: cliques) topo[index++] = clique;
+//              open = new AtomicInteger(); 
+//              end = new AtomicInteger(cliques.size() - 1); 
+                        
+//              validated = Collections.synchronizedSet(new HashSet<Clique>()); 
+//              falsified = Collections.synchronizedSet(new HashSet<Clique>());
+                validated = Collections.newSetFromMap(new ConcurrentHashMap<Clique, Boolean>()); 
+                falsified = Collections.newSetFromMap(new ConcurrentHashMap<Clique, Boolean>()); 
+
+                int numOfThreads = 10; 
+                Collection<Thread> threads = new LinkedList<Thread>(); 
+                for (int i = 0; i < numOfThreads; ++i) 
+                        threads.add(new Thread(new SubThread(new HermitChecker(checker), i)));
+                
+                for (Thread thread: threads) thread.start();
+                
+                for (Thread thread: threads) {
+                        try {
+                                thread.join();
+                        } catch (InterruptedException e) {
+                                e.printStackTrace();
+                        } 
+                }
+                
+                Utility.logDebug("HermiT was called " + counter.get() + " times."); 
+                
+                int count = 0; 
+                for (Clique c: dGraph.getTopologicalOrder()) {
+                        if (validated.contains(c))
+                                count += c.getNodeTuples().size() + 1; 
+                }
+                return count;           
+        }
+
+        private void setMarkCascadely(Clique clique, Set<Clique> marked, Map<Clique, Collection<Clique>> edges) {
+                marked.add(clique); 
+                if (edges.containsKey(clique))
+                        for (Clique c: edges.get(clique))
+                                if (!marked.contains(c)) 
+                                        setMarkCascadely(c, marked, edges);
+        }
+        
+        AtomicInteger counter = new AtomicInteger(); 
+
+        class SubThread implements Runnable {
+                
+                HermitChecker m_checker; 
+                int m_ID;  
+
+                public SubThread(HermitChecker checker, int ID) {
+                        m_checker = checker; 
+                        m_ID = ID; 
+                }
+
+                @Override
+                public void run() {
+                        boolean flag = ((m_ID & 1) == 0); 
+                        Clique clique;
+                        AnswerTuple answerTuple; 
+                        while (!topo.isEmpty())
+                                if (flag) {
+                                        clique = topo.removeFirst(); 
+                                        if (validated.contains(clique)) continue; 
+                                        if (falsified.contains(clique)) { flag = false; continue; }
+                                        counter.incrementAndGet(); 
+                                        Utility.logDebug("Thread " + m_ID + ": start checking front ... " + (answerTuple = clique.getRepresentative().getAnswerTuple())); 
+                                        if (m_checker.check(answerTuple)) {
+                                                setMarkCascadely(clique, validated, dGraph.getOutGoingEdges()); 
+                                        }
+                                        else {
+                                                falsified.add(clique);
+                                                flag = false; 
+                                        }
+                                }
+                                else {
+                                        clique = topo.removeLast(); 
+                                        if (falsified.contains(clique)) continue; 
+                                        if (validated.contains(clique)) { flag = true; continue; }
+                                        counter.incrementAndGet(); 
+                                        Utility.logDebug("Thread " + m_ID + ": start checking back ... " + (answerTuple = clique.getRepresentative().getAnswerTuple())); 
+                                        if (!m_checker.check(answerTuple)) 
+                                                setMarkCascadely(clique, falsified, dGraph.getInComingEdges()); 
+                                        else {
+                                                validated.add(clique);
+                                                flag = true; 
+                                        }
+                                }
+                        
+                        m_checker.dispose(); 
+                }
+                
+        }
+}
+
diff --git a/src/uk/ac/ox/cs/pagoda/endomorph/plan/OpenEndPlan.java b/src/uk/ac/ox/cs/pagoda/endomorph/plan/OpenEndPlan.java
new file mode 100644
index 0000000..202021d
--- /dev/null
+++ b/src/uk/ac/ox/cs/pagoda/endomorph/plan/OpenEndPlan.java
@@ -0,0 +1,106 @@
+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;
+import java.util.Set;
+
+import uk.ac.ox.cs.pagoda.endomorph.*;
+import uk.ac.ox.cs.pagoda.query.AnswerTuple;
+import uk.ac.ox.cs.pagoda.query.QueryRecord;
+import uk.ac.ox.cs.pagoda.query.QueryRecord.Step;
+import uk.ac.ox.cs.pagoda.reasoner.full.Checker;
+import uk.ac.ox.cs.pagoda.summary.NodeTuple;
+import uk.ac.ox.cs.pagoda.util.Timer;
+import uk.ac.ox.cs.pagoda.util.Utility;
+
+public class OpenEndPlan implements CheckPlan {
+        
+        public static final int TIME_OUT_MIN = 1; 
+        
+        Checker checker; 
+        DependencyGraph dGraph; 
+        QueryRecord m_record; 
+
+        public OpenEndPlan(Checker checker, DependencyGraph dGraph, QueryRecord record) {
+                this.checker = checker; 
+                this.dGraph = dGraph;
+                m_record = record; 
+        }
+        
+        @Override
+        public int check() {
+                Deque<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; 
+                while (!topo.isEmpty()) { 
+                        if (flag) {
+                                clique = topo.removeFirst(); 
+                                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()); 
+                                }
+                                else {
+                                        falsified.add(clique);
+                                        flag = false; 
+                                }
+                        }
+                        else {
+                                clique = topo.removeLast(); 
+                                if (falsified.contains(clique)) continue; 
+                                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()); 
+                                else {
+                                        Utility.logDebug(answerTuple.toString() + " is verified.");
+                                        validated.add(clique);
+                                        flag = true; 
+                                }
+                        }
+                }
+                
+//              Utility.logDebug("HermiT was called " + times + " times."); 
+                
+                int count = 0; 
+                AnswerTuple ans; 
+                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()); 
+                                
+                                for (NodeTuple nodeTuple: c.getNodeTuples()) {
+                                        ans = nodeTuple.getAnswerTuple(); 
+                                        validAnswers.add(ans);
+                                        Utility.logDebug(ans + " is verified."); 
+                                }
+                        }
+                
+                m_record.addLowerBoundAnswers(validAnswers);
+                m_record.addProcessingTime(Step.FullReasoning, t.duration());
+                return count;           
+        }
+
+        private void setMarkCascadely(Clique clique, Set<Clique> marked, Map<Clique, Collection<Clique>> edges) {
+                marked.add(clique); 
+                if (edges.containsKey(clique))
+                        for (Clique c: edges.get(clique))
+                                if (!marked.contains(c)) 
+                                        setMarkCascadely(c, marked, edges);
+        }
+
+}
diff --git a/src/uk/ac/ox/cs/pagoda/endomorph/plan/PlainPlan.java b/src/uk/ac/ox/cs/pagoda/endomorph/plan/PlainPlan.java
new file mode 100644
index 0000000..d6067d0
--- /dev/null
+++ b/src/uk/ac/ox/cs/pagoda/endomorph/plan/PlainPlan.java
@@ -0,0 +1,32 @@
+package uk.ac.ox.cs.pagoda.endomorph.plan;
+
+import java.util.Set;
+
+import uk.ac.ox.cs.pagoda.endomorph.Clique;
+import uk.ac.ox.cs.pagoda.reasoner.full.Checker;
+import uk.ac.ox.cs.pagoda.summary.NodeTuple;
+import uk.ac.ox.cs.pagoda.util.Utility;
+
+public class PlainPlan implements CheckPlan {
+        
+        Checker checker; 
+        Set<Clique> toCheck; 
+
+        public PlainPlan(Checker checker, Set<Clique> toCheck) {
+                this.checker = checker; 
+                this.toCheck = toCheck; 
+        }
+
+        @Override
+        public int check() {
+                int count = 0; 
+                for (Clique clique: toCheck)
+                        if (checker.check(clique.getRepresentative().getAnswerTuple())) {
+                                count += clique.getNodeTuples().size() + 1; 
+                                for (NodeTuple nodeTuple: clique.getNodeTuples()) 
+                                        Utility.logDebug(nodeTuple.getAnswerTuple().toString());
+                        }
+                return count; 
+        }
+        
+}