From de3749532d060f26c966a81c03f9a5d846c33d06 Mon Sep 17 00:00:00 2001 From: RncLsn Date: Thu, 28 May 2015 17:11:35 +0100 Subject: Merged updates from upstream. --- .../endomorph/plan/OpenEndMultiThreadPlan.java | 85 ++++++++++------------ .../ox/cs/pagoda/endomorph/plan/OpenEndPlan.java | 74 ++++++++++++------- .../ac/ox/cs/pagoda/endomorph/plan/PlainPlan.java | 6 +- 3 files changed, 91 insertions(+), 74 deletions(-) (limited to 'src/uk/ac/ox/cs/pagoda/endomorph/plan') 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..862fdc8 100644 --- a/src/uk/ac/ox/cs/pagoda/endomorph/plan/OpenEndMultiThreadPlan.java +++ b/src/uk/ac/ox/cs/pagoda/endomorph/plan/OpenEndMultiThreadPlan.java @@ -1,88 +1,81 @@ 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.endomorph.DependencyGraph; 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; +import java.util.*; +import java.util.concurrent.ConcurrentHashMap; +import java.util.concurrent.ConcurrentLinkedDeque; +import java.util.concurrent.atomic.AtomicInteger; + public class OpenEndMultiThreadPlan implements CheckPlan { - Checker checker; - DependencyGraph dGraph; - + Checker checker; + DependencyGraph dGraph; + // Clique[] topo; +// AtomicInteger open, end; + ConcurrentLinkedDeque topo; + Set validated, falsified; + AtomicInteger counter = new AtomicInteger(); + public OpenEndMultiThreadPlan(Checker checker, DependencyGraph dGraph) { - this.checker = checker; + 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 ConcurrentLinkedDeque(cliques); + // topo = new Clique[cliques.size()]; -// int index = 0; +// int index = 0; // for (Clique clique: cliques) topo[index++] = clique; -// open = new AtomicInteger(); -// end = new AtomicInteger(cliques.size() - 1); - -// validated = Collections.synchronizedSet(new HashSet()); +// 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()); + validated = Collections.newSetFromMap(new ConcurrentHashMap()); + falsified = Collections.newSetFromMap(new ConcurrentHashMap()); - int numOfThreads = 10; - Collection threads = new LinkedList(); - for (int i = 0; i < numOfThreads; ++i) + 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; + + 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; + count += c.getNodeTuples().size(); } - return count; + return count; } private void setMarkCascadely(Clique clique, Set marked, Map> edges) { - marked.add(clique); + marked.add(clique); if (edges.containsKey(clique)) for (Clique c: edges.get(clique)) - if (!marked.contains(c)) + if(!marked.contains(c)) setMarkCascadely(c, marked, edges); } - - AtomicInteger counter = new AtomicInteger(); class SubThread implements Runnable { 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 19d567a..3294c31 100644 --- a/src/uk/ac/ox/cs/pagoda/endomorph/plan/OpenEndPlan.java +++ b/src/uk/ac/ox/cs/pagoda/endomorph/plan/OpenEndPlan.java @@ -17,37 +17,39 @@ public class OpenEndPlan implements CheckPlan { public static final int TIME_OUT_MIN = 1; Checker checker; - DependencyGraph dGraph; - QueryRecord m_record; - + DependencyGraph dGraph; + QueryRecord m_record; + int m_answerArity; + Set validated = new HashSet(); + Set falsified = new HashSet(); + Set passedAnswers = new HashSet(); public OpenEndPlan(Checker checker, DependencyGraph dGraph, QueryRecord record) { - this.checker = checker; + this.checker = checker; this.dGraph = dGraph; - m_record = record; + m_record = record; + m_answerArity = record.getAnswerVariables().length; } @Override public int check() { - Deque topo = new LinkedList(dGraph.getTopologicalOrder()); + LinkedList 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(); - + 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); @@ -58,12 +60,12 @@ public class OpenEndPlan implements CheckPlan { 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()); + Utility.logDebug("start checking back ... " + (answerTuple = clique.getRepresentative().getAnswerTuple())); + if(!checker.check(answerTuple)) + setMarkCascadelyFasified(clique); else { Utility.logDebug(answerTuple.toString() + " is verified."); - validated.add(clique); + addProjections(clique); flag = true; } } @@ -76,9 +78,8 @@ public class OpenEndPlan implements CheckPlan { Collection validAnswers = new LinkedList(); 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); @@ -91,12 +92,35 @@ public class OpenEndPlan implements CheckPlan { return count; } - private void setMarkCascadely(Clique clique, Set marked, Map> edges) { - marked.add(clique); + private boolean redundant(Clique clique) { + for(NodeTuple nodeTuple : clique.getNodeTuples()) + if(!passedAnswers.contains(AnswerTuple.getInstance(nodeTuple.getAnswerTuple(), m_answerArity))) + return false; + return true; + } + + private void addProjections(Clique clique) { + for(NodeTuple nodeTuple : clique.getNodeTuples()) + passedAnswers.add(AnswerTuple.getInstance(nodeTuple.getAnswerTuple(), m_answerArity)); + } + + private void setMarkCascadelyValidated(Clique clique) { + validated.add(clique); + addProjections(clique); + Map> edges = dGraph.getOutGoingEdges(); if (edges.containsKey(clique)) for (Clique c: edges.get(clique)) - if (!marked.contains(c)) - setMarkCascadely(c, marked, edges); + if(!validated.contains(c)) + setMarkCascadelyValidated(c); + } + + private void setMarkCascadelyFasified(Clique clique) { + falsified.add(clique); + Map> edges = dGraph.getInComingEdges(); + if(edges.containsKey(clique)) + for(Clique c : edges.get(clique)) + 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..5e1a700 100644 --- a/src/uk/ac/ox/cs/pagoda/endomorph/plan/PlainPlan.java +++ b/src/uk/ac/ox/cs/pagoda/endomorph/plan/PlainPlan.java @@ -1,12 +1,12 @@ 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; +import java.util.Set; + public class PlainPlan implements CheckPlan { Checker checker; @@ -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()); } -- cgit v1.2.3