From 9ce65c5a963b03ee97fe9cb6c5aa65a3c04a80a8 Mon Sep 17 00:00:00 2001 From: yzhou Date: Tue, 21 Apr 2015 10:34:27 +0100 Subject: initial version --- src/uk/ac/ox/cs/pagoda/endomorph/Clique.java | 36 +++ .../ac/ox/cs/pagoda/endomorph/DependencyGraph.java | 295 +++++++++++++++++++++ src/uk/ac/ox/cs/pagoda/endomorph/Endomorph.java | 95 +++++++ .../ox/cs/pagoda/endomorph/EndomorphChecker.java | 14 + .../ox/cs/pagoda/endomorph/EndomorphChecker1.java | 49 ++++ .../ox/cs/pagoda/endomorph/EndomorphChecker2.java | 125 +++++++++ .../ac/ox/cs/pagoda/endomorph/plan/CheckPlan.java | 7 + .../endomorph/plan/OpenEndMultiThreadPlan.java | 136 ++++++++++ .../ox/cs/pagoda/endomorph/plan/OpenEndPlan.java | 106 ++++++++ .../ac/ox/cs/pagoda/endomorph/plan/PlainPlan.java | 32 +++ 10 files changed, 895 insertions(+) create mode 100644 src/uk/ac/ox/cs/pagoda/endomorph/Clique.java create mode 100644 src/uk/ac/ox/cs/pagoda/endomorph/DependencyGraph.java create mode 100644 src/uk/ac/ox/cs/pagoda/endomorph/Endomorph.java create mode 100644 src/uk/ac/ox/cs/pagoda/endomorph/EndomorphChecker.java create mode 100644 src/uk/ac/ox/cs/pagoda/endomorph/EndomorphChecker1.java create mode 100644 src/uk/ac/ox/cs/pagoda/endomorph/EndomorphChecker2.java create mode 100644 src/uk/ac/ox/cs/pagoda/endomorph/plan/CheckPlan.java create mode 100644 src/uk/ac/ox/cs/pagoda/endomorph/plan/OpenEndMultiThreadPlan.java create mode 100644 src/uk/ac/ox/cs/pagoda/endomorph/plan/OpenEndPlan.java create mode 100644 src/uk/ac/ox/cs/pagoda/endomorph/plan/PlainPlan.java (limited to 'src/uk/ac/ox/cs/pagoda/endomorph') 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 nodeTuples = null; + + public Clique(NodeTuple u) { + nodeTuples = new HashSet(); + 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 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 entrances = new HashSet(); + + public Set getEntrances() { + return entrances; + } + + Set exits = new HashSet(); + + public Set getExits() { + return exits; + } + + Map> outGoingEdges = new HashMap>(); + + public Map> getOutGoingEdges() { + return outGoingEdges; + } + + Map> inComingEdges = new HashMap>(); + + public Map> getInComingEdges() { + return inComingEdges; + } + + Graph graph; + EndomorphChecker homomorphismChecker; + Set cliques = new HashSet(); + + public DependencyGraph(Graph graph) { + this.graph = graph; + homomorphismChecker = new EndomorphChecker2(graph); +// homomorphismChecker = new EndomorphChecker1(graph); + } + + private int compareNodeTuple(NodeTuple t1, NodeTuple t2) { + Iterator iter1 = t1.getNodes().iterator(); + Iterator 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 nodeTuples) { + + if (nodeTuples.isEmpty()) return ; + + Timer t = new Timer(); + + NodeTuple[] nodeTupleArray = new NodeTuple[nodeTuples.size()]; + nodeTuples.toArray(nodeTupleArray); + + Arrays.sort(nodeTupleArray, new Comparator() { + @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 topolocialOrder = null; + + public LinkedList getTopologicalOrder() { + if (topolocialOrder != null) return topolocialOrder; + + topolocialOrder = new LinkedList(); + Queue toVisit = new LinkedList(entrances); + Map toVisitedInComingDegree = new HashMap(); + + 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 toCompare = new LinkedList(entrances); + + Map toVisitedDegree = new HashMap(); + Collection directSuccessors = new LinkedList(); + + 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 visited = new HashSet(); + + 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 directPredecessors = new LinkedList(); + + 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 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> map, Clique u, Clique v) { + Collection temp; + if ((temp = map.get(u)) == null) { + temp = new LinkedList(); + 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 nodes = new LinkedList(); + 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 iter1 = u.getNodes().iterator(); + Iterator 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 mappings = new HashMap(); + + 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 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 candidates = new HashSet(); + + 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 topo; + + Set validated, falsified; + + @Override + public int check() { + Collection cliques = dGraph.getTopologicalOrder(); +// topo = new LinkedBlockingDeque(cliques); + topo = new ConcurrentLinkedDeque(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()); +// falsified = Collections.synchronizedSet(new HashSet()); + validated = Collections.newSetFromMap(new ConcurrentHashMap()); + falsified = Collections.newSetFromMap(new ConcurrentHashMap()); + + int numOfThreads = 10; + Collection threads = new LinkedList(); + 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 marked, Map> 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 topo = new LinkedList(dGraph.getTopologicalOrder()); + Utility.logInfo("Entrances: " + dGraph.getEntrances().size() + " Exists: " + dGraph.getExits().size()); + Set validated = new HashSet(); + Set falsified = new HashSet(); + + 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 validAnswers = new LinkedList(); + 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 marked, Map> 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 toCheck; + + public PlainPlan(Checker checker, Set 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; + } + +} -- cgit v1.2.3