aboutsummaryrefslogtreecommitdiff
path: root/src/uk/ac/ox/cs/pagoda/endomorph
diff options
context:
space:
mode:
Diffstat (limited to 'src/uk/ac/ox/cs/pagoda/endomorph')
-rw-r--r--src/uk/ac/ox/cs/pagoda/endomorph/Clique.java36
-rw-r--r--src/uk/ac/ox/cs/pagoda/endomorph/DependencyGraph.java295
-rw-r--r--src/uk/ac/ox/cs/pagoda/endomorph/Endomorph.java95
-rw-r--r--src/uk/ac/ox/cs/pagoda/endomorph/EndomorphChecker.java14
-rw-r--r--src/uk/ac/ox/cs/pagoda/endomorph/EndomorphChecker1.java49
-rw-r--r--src/uk/ac/ox/cs/pagoda/endomorph/EndomorphChecker2.java125
-rw-r--r--src/uk/ac/ox/cs/pagoda/endomorph/plan/CheckPlan.java7
-rw-r--r--src/uk/ac/ox/cs/pagoda/endomorph/plan/OpenEndMultiThreadPlan.java136
-rw-r--r--src/uk/ac/ox/cs/pagoda/endomorph/plan/OpenEndPlan.java106
-rw-r--r--src/uk/ac/ox/cs/pagoda/endomorph/plan/PlainPlan.java32
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 @@
1package uk.ac.ox.cs.pagoda.endomorph;
2
3import java.util.Collection;
4import java.util.HashSet;
5import java.util.Set;
6
7import uk.ac.ox.cs.pagoda.summary.NodeTuple;
8
9public class Clique {
10 NodeTuple representative;
11 Set<NodeTuple> nodeTuples = null;
12
13 public Clique(NodeTuple u) {
14 nodeTuples = new HashSet<NodeTuple>();
15 representative = u;
16 }
17
18 public boolean addNodeTuple(NodeTuple nodeTuple) {
19 return nodeTuples.add(nodeTuple);
20 }
21
22 public NodeTuple getRepresentative() {
23 return representative;
24 }
25
26 @Override
27 public String toString() {
28 return representative.toString();
29 }
30
31 public Collection<NodeTuple> getNodeTuples() {
32 return nodeTuples;
33 }
34
35}
36
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 @@
1 package uk.ac.ox.cs.pagoda.endomorph;
2
3import java.util.Arrays;
4import java.util.Collection;
5import java.util.Comparator;
6import java.util.HashMap;
7import java.util.HashSet;
8import java.util.Iterator;
9import java.util.LinkedList;
10import java.util.Map;
11import java.util.Queue;
12import java.util.Set;
13
14import uk.ac.ox.cs.pagoda.summary.Edge;
15import uk.ac.ox.cs.pagoda.summary.Graph;
16import uk.ac.ox.cs.pagoda.summary.Node;
17import uk.ac.ox.cs.pagoda.summary.NodeTuple;
18import uk.ac.ox.cs.pagoda.util.Timer;
19import uk.ac.ox.cs.pagoda.util.Utility;
20
21public class DependencyGraph {
22
23 Set<Clique> entrances = new HashSet<Clique>();
24
25 public Set<Clique> getEntrances() {
26 return entrances;
27 }
28
29 Set<Clique> exits = new HashSet<Clique>();
30
31 public Set<Clique> getExits() {
32 return exits;
33 }
34
35 Map<Clique, Collection<Clique>> outGoingEdges = new HashMap<Clique, Collection<Clique>>();
36
37 public Map<Clique, Collection<Clique>> getOutGoingEdges() {
38 return outGoingEdges;
39 }
40
41 Map<Clique, Collection<Clique>> inComingEdges = new HashMap<Clique, Collection<Clique>>();
42
43 public Map<Clique, Collection<Clique>> getInComingEdges() {
44 return inComingEdges;
45 }
46
47 Graph graph;
48 EndomorphChecker homomorphismChecker;
49 Set<Clique> cliques = new HashSet<Clique>();
50
51 public DependencyGraph(Graph graph) {
52 this.graph = graph;
53 homomorphismChecker = new EndomorphChecker2(graph);
54// homomorphismChecker = new EndomorphChecker1(graph);
55 }
56
57 private int compareNodeTuple(NodeTuple t1, NodeTuple t2) {
58 Iterator<Node> iter1 = t1.getNodes().iterator();
59 Iterator<Node> iter2 = t2.getNodes().iterator();
60 int ret;
61 int index = 0;
62 Node u, v;
63 while (iter1.hasNext()) {
64 u = iter1.next(); v = iter2.next();
65 if (u == null && v == null) {
66 if ((ret = t1.getAnswerTuple().getGroundTerm(index).toString().compareTo(t2.getAnswerTuple().getGroundTerm(index).toString())) != 0)
67 return ret;
68 }
69 else if (u != null && v != null) {
70 if ((ret = compareNode(u, v)) != 0) return ret;
71 }
72 else if (u == null)
73 return 1;
74 else if (v == null)
75 return -1;
76
77 }
78
79 return 0;
80 }
81
82 private int compareNode(Node o1, Node o2) {
83 int result = o1.getConcepts().size() - o2.getConcepts().size();
84 if (result != 0) return dir(result);
85 Edge[] edge1 = graph.getOutGoingEdges(o1), edge2 = graph.getOutGoingEdges(o2);;
86 int len1 = edge1 == null ? 0 : edge1.length, len2 = edge2 == null ? 0 : edge2.length;
87 result = len1 - len2;
88 if (result != 0) return dir(result);
89
90 edge1 = graph.getInComingEdges(o1); edge2 = graph.getInComingEdges(o2);
91 len1 = edge1 == null ? 0 : edge1.length; len2 = edge2 == null ? 0 : edge2.length;
92 result = len1 - len2;
93 if (result != 0) return dir(result);
94
95 else return o1.getLabel().compareTo(o2.getLabel());
96 }
97
98 private int dir(int flag) { return - flag; }
99
100 public void build(Collection<NodeTuple> nodeTuples) {
101
102 if (nodeTuples.isEmpty()) return ;
103
104 Timer t = new Timer();
105
106 NodeTuple[] nodeTupleArray = new NodeTuple[nodeTuples.size()];
107 nodeTuples.toArray(nodeTupleArray);
108
109 Arrays.sort(nodeTupleArray, new Comparator<NodeTuple>() {
110 @Override
111 public int compare(NodeTuple t1, NodeTuple t2) {
112 return compareNodeTuple(t1, t2);
113 }
114 });
115
116 Utility.logDebug(nodeTupleArray[0].toString(),
117 nodeTupleArray[nodeTupleArray.length - 1].toString());
118
119 for (NodeTuple nodeTuple: nodeTupleArray) addNodeTuple(nodeTuple);
120
121 Utility.logDebug("The number of times to call homomorphism checker: " + homomorphismCheckCounter + "(" + outGoingCheckCounter + "," + inComingCheckCounter + ").",
122 "Time to compute endomorphism relation: " + t.duration());
123
124// print();
125
126 topolocialOrder = null;
127 Utility.logInfo("link: " + link);
128 }
129
130 LinkedList<Clique> topolocialOrder = null;
131
132 public LinkedList<Clique> getTopologicalOrder() {
133 if (topolocialOrder != null) return topolocialOrder;
134
135 topolocialOrder = new LinkedList<Clique>();
136 Queue<Clique> toVisit = new LinkedList<Clique>(entrances);
137 Map<Clique, Integer> toVisitedInComingDegree = new HashMap<Clique, Integer>();
138
139 int count;
140 while (!toVisit.isEmpty()) {
141 Clique cu = toVisit.remove();
142 topolocialOrder.add(cu);
143 if (outGoingEdges.containsKey(cu))
144 for (Clique cv: outGoingEdges.get(cu)) {
145 if (toVisitedInComingDegree.containsKey(cv)) {
146 count = toVisitedInComingDegree.get(cv) - 1;
147 toVisitedInComingDegree.put(cv, count);
148 }
149 else
150 toVisitedInComingDegree.put(cv, count = inComingEdges.get(cv).size() - 1);
151 if (count == 0)
152 toVisit.add(cv);
153 }
154 }
155
156 return topolocialOrder;
157 }
158
159 private void addNodeTuple(NodeTuple u) {
160 Queue<Clique> toCompare = new LinkedList<Clique>(entrances);
161
162 Map<Clique, Integer> toVisitedDegree = new HashMap<Clique, Integer>();
163 Collection<Clique> directSuccessors = new LinkedList<Clique>();
164
165 int count;
166 while (!toCompare.isEmpty()) {
167 Clique cv = toCompare.remove();
168 ++outGoingCheckCounter;
169 if (checkHomomorphism(u, cv.representative)) {
170 directSuccessors.add(cv);
171 }
172 else {
173 if (outGoingEdges.containsKey(cv))
174 for (Clique c: outGoingEdges.get(cv)) {
175 if (toVisitedDegree.containsKey(c)) {
176 count = toVisitedDegree.get(c) - 1;
177 toVisitedDegree.put(c, count);
178 }
179 else
180 toVisitedDegree.put(c, count = inComingEdges.get(c).size() - 1);
181
182 if (count == 0)
183 toCompare.add(c);
184 }
185 }
186 }
187
188 if (directSuccessors.size() == 1) {
189 Clique clique = directSuccessors.iterator().next();
190 if (checkHomomorphism(clique.representative, u)) {
191 clique.addNodeTuple(u);
192 return ;
193 }
194 }
195
196 Clique cu = new Clique(u);
197 cliques.add(cu);
198
199 toCompare.clear();
200 Set<Clique> visited = new HashSet<Clique>();
201
202 if (directSuccessors.size() == 0)
203 toCompare.addAll(exits);
204 else {
205 for (Clique cv: directSuccessors)
206 if (inComingEdges.containsKey(cv))
207 for (Clique cw: inComingEdges.get(cv)) {
208 visited.add(cw);
209 toCompare.add(cw);
210 }
211 }
212
213
214
215 Collection<Clique> directPredecessors = new LinkedList<Clique>();
216
217 while (!toCompare.isEmpty()) {
218 Clique cv = toCompare.remove();
219 ++inComingCheckCounter;
220 if (checkHomomorphism(cv.representative, u))
221 directPredecessors.add(cv);
222 else {
223 if (inComingEdges.containsKey(cv))
224 for (Clique c: inComingEdges.get(cv))
225 if (!visited.contains(c)) {
226 visited.add(c);
227 toCompare.add(c);
228 }
229 }
230 }
231
232 for (Clique cv: directSuccessors) {
233 if (entrances.contains(cv)) entrances.remove(cv);
234 link(cu, cv);
235 }
236
237 for (Clique cw: directPredecessors) {
238 if (exits.contains(cw)) exits.remove(cw);
239 link(cw, cu);
240 }
241
242 if (directPredecessors.size() == 0) entrances.add(cu);
243 if (directSuccessors.size() == 0) exits.add(cu);
244 }
245
246 private int homomorphismCheckCounter = 0;
247 private int outGoingCheckCounter = 0, inComingCheckCounter = 0;
248
249 private boolean checkHomomorphism(NodeTuple u, NodeTuple v) {
250 ++homomorphismCheckCounter;
251 homomorphismChecker.setMapping(u, v);
252 try {
253 Node node1, node2;
254 for (Iterator<Node> iter1 = u.getNodes().iterator(), iter2 = v.getNodes().iterator(); iter1.hasNext(); ) {
255 node1 = iter1.next(); node2 = iter2.next();
256 if (node1 != node2 && !homomorphismChecker.check(node1, node2)) {
257// System.out.println(homomorphismChecker.check(node1, node2));
258 return false;
259 }
260 }
261 return true;
262 } finally {
263 homomorphismChecker.clearMappings();
264 }
265 }
266
267 private void link(Clique u, Clique v) {
268 ++link;
269 addToList(outGoingEdges, u, v);
270 addToList(inComingEdges, v, u);
271 }
272
273 private int link = 0;
274
275 private void addToList(Map<Clique, Collection<Clique>> map, Clique u, Clique v) {
276 Collection<Clique> temp;
277 if ((temp = map.get(u)) == null) {
278 temp = new LinkedList<Clique>();
279 map.put(u, temp);
280 }
281 temp.add(v);
282 }
283
284 public void print() {
285 System.out.println("---------- Dependency Graph -------------");
286 for (Clique u: cliques)
287 if (outGoingEdges.containsKey(u))
288 for (Clique v: outGoingEdges.get(u))
289 System.out.println(u + " -> " + v);
290 System.out.println("-----------------------------------------");
291 }
292
293
294}
295
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 @@
1package uk.ac.ox.cs.pagoda.endomorph;
2
3import java.util.Collection;
4import java.util.LinkedList;
5
6import org.semanticweb.owlapi.model.OWLOntology;
7
8import uk.ac.ox.cs.pagoda.endomorph.plan.*;
9import uk.ac.ox.cs.pagoda.query.AnswerTuple;
10import uk.ac.ox.cs.pagoda.query.AnswerTuples;
11import uk.ac.ox.cs.pagoda.query.QueryRecord;
12import uk.ac.ox.cs.pagoda.reasoner.full.Checker;
13import uk.ac.ox.cs.pagoda.summary.Graph;
14import uk.ac.ox.cs.pagoda.summary.NodeTuple;
15import uk.ac.ox.cs.pagoda.util.Timer;
16import uk.ac.ox.cs.pagoda.util.Utility;
17
18public class Endomorph implements Checker {
19
20 Checker fullReasoner;
21 DependencyGraph dGraph;
22 Graph graph;
23 QueryRecord m_record;
24
25 /**
26 * constructor using HermiTChecker ...
27 * @throws Exception
28 */
29
30 public Endomorph(QueryRecord record, Checker checker) {
31 this.m_record = record;
32 fullReasoner = checker;
33 graph = new Graph(record.getRelevantOntology());
34 dGraph = new DependencyGraph(graph);
35 }
36
37 @Override
38 public int check(AnswerTuples answerTuples) {
39 Collection<NodeTuple> nodes = new LinkedList<NodeTuple>();
40 int counter = 0;
41
42 for (; answerTuples.isValid(); answerTuples.moveNext()) {
43 ++counter;
44 nodes.add(graph.getNodeTuple(answerTuples.getTuple()));
45 }
46 answerTuples.dispose();
47
48 Timer t = new Timer();
49 dGraph.build(nodes);
50// dGraph.print();
51 Utility.logDebug("@TIME to group individuals in the gap: " + t.duration());
52 Utility.logInfo("The number of different groups: " + dGraph.cliques.size());
53
54 Utility.logInfo("The number of individuals to be checked by Homomorphism checker: " + counter);
55// CheckPlan plan = new PlainPlan(this.checker, dGraph.cliques);
56// CheckPlan plan = new OpenEndMultiThreadPlan(this.checker, dGraph);
57 CheckPlan plan = new OpenEndPlan(fullReasoner, dGraph, m_record);
58 int answerCounter = plan.check();
59
60 Utility.logDebug("The number of correct answers: " + answerCounter);
61 return answerCounter;
62 }
63
64 public OWLOntology getOntology() {
65 return m_record.getRelevantOntology();
66 }
67
68 @Override
69 public boolean check(AnswerTuple answerTuple) {
70 return fullReasoner.check(answerTuple);
71 }
72
73 @Override
74 public boolean isConsistent() {
75 return fullReasoner.isConsistent();
76 }
77
78 @Override
79 public void dispose() {
80 fullReasoner.dispose();
81 }
82
83 public Graph getGraph() {
84 return graph;
85 }
86
87 public Checker getChecker() {
88 return fullReasoner;
89 }
90
91 public DependencyGraph getDependencyGraph() {
92 return dGraph;
93 }
94
95}
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 @@
1package uk.ac.ox.cs.pagoda.endomorph;
2
3import uk.ac.ox.cs.pagoda.summary.Node;
4import uk.ac.ox.cs.pagoda.summary.NodeTuple;
5
6public interface EndomorphChecker {
7
8 void clearMappings();
9
10 void setMapping(NodeTuple u, NodeTuple v);
11
12 boolean check(Node next, Node next2);
13
14}
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 @@
1package uk.ac.ox.cs.pagoda.endomorph;
2
3import uk.ac.ox.cs.pagoda.summary.Edge;
4import uk.ac.ox.cs.pagoda.summary.Graph;
5import uk.ac.ox.cs.pagoda.summary.Node;
6import uk.ac.ox.cs.pagoda.summary.NodeTuple;
7
8public class EndomorphChecker1 implements EndomorphChecker {
9
10 private Graph graph;
11
12 public EndomorphChecker1(Graph graph) {
13 this.graph = graph;
14 }
15
16 public boolean check(Node u, Node v) {
17 if (!u.isSubConceptOf(v)) return false;
18 if (!isSubsetOf(graph.getOutGoingEdges(u), graph.getOutGoingEdges(v), true)) return false;
19 if (!isSubsetOf(graph.getInComingEdges(u), graph.getInComingEdges(v), false)) return false;
20 return true;
21 }
22
23 private boolean isSubsetOf(Edge[] e1, Edge[] e2, boolean out) {
24 int j = 0;
25 for (int i = 0; i < e1.length; ++i) {
26 while (j < e2.length && equals(e1[i], e2[j], out))
27 ++j;
28 }
29 return j < e2.length;
30 }
31
32 private boolean equals(Edge edge, Edge edge2, boolean out) {
33 if (!edge.getLabel().equals(edge2.getLabel())) return false;
34 return out ? edge.getToNode().equals(edge2.getToNode()) : edge.getFromNode().equals(edge2.getFromNode());
35 }
36
37 @Override
38 public void clearMappings() {
39 // TODO Auto-generated method stub
40
41 }
42
43 @Override
44 public void setMapping(NodeTuple u, NodeTuple v) {
45 // TODO Auto-generated method stub
46
47 }
48
49}
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 @@
1package uk.ac.ox.cs.pagoda.endomorph;
2
3import java.util.HashMap;
4import java.util.HashSet;
5import java.util.Iterator;
6import java.util.Map;
7import java.util.Set;
8
9import uk.ac.ox.cs.pagoda.summary.Edge;
10import uk.ac.ox.cs.pagoda.summary.Graph;
11import uk.ac.ox.cs.pagoda.summary.Node;
12import uk.ac.ox.cs.pagoda.summary.NodeTuple;
13import uk.ac.ox.cs.pagoda.util.Timer;
14
15public class EndomorphChecker2 implements EndomorphChecker {
16
17 private Graph graph;
18// DependencyGraph dGraph;
19
20 public EndomorphChecker2(Graph graph) {
21 this.graph = graph;
22 }
23
24 private Timer timer = new Timer();
25 private boolean time_out = false;
26 private static final int TIME_OUT = 60;
27
28 public boolean check(NodeTuple u, NodeTuple v) {
29 int length = u.getNodes().size();
30 Edge[][] ss = new Edge[1][length], tt = new Edge[1][length];
31 int index = 0;
32 Iterator<Node> iter1 = u.getNodes().iterator();
33 Iterator<Node> iter2 = v.getNodes().iterator();
34 for (; iter1.hasNext(); ) {
35 ss[0][index] = new Edge(null, iter1.next(), "auxilary" + index);
36 tt[0][index++] = new Edge(null, iter2.next(), "auxilary" + index);
37 }
38 return checkSortedEdges(ss, tt, 0, 0);
39 }
40
41 public boolean check(Node u, Node v) {
42 if (!u.isSubConceptOf(v)) return false;
43 if (!checkSortedEdges(new Edge[][] {graph.getOutGoingEdges(u), graph.getInComingEdges(u) },
44 new Edge[][] {graph.getOutGoingEdges(v), graph.getInComingEdges(v)}, 0, 0)) {
45 return false;
46 }
47 return true;
48 }
49
50 Map<Node, Node> mappings = new HashMap<Node, Node>();
51
52 public void clearMappings() {
53 mappings.clear();
54 timer.pause();
55 }
56
57 public void setMapping(NodeTuple key, NodeTuple value) {
58 timer.resume();
59 // FIXME
60 timer.setTimeout(TIME_OUT);
61// time_out = false;
62 for (Iterator<Node> key_iter = key.getNodes().iterator(), value_iter = value.getNodes().iterator(); key_iter.hasNext(); ) {
63 mappings.put(key_iter.next(), value_iter.next());
64 }
65 }
66
67 private boolean checkSortedEdges(Edge[][] ss, Edge[][] st, int dim, int index) {
68 if (time_out || timer.timeOut()) {
69 time_out = true;
70 return false;
71 }
72
73 while (ss[dim] == null || index >= ss[dim].length)
74 if (++dim >= ss.length) return true;
75 else index = 0;
76 Edge[] s = ss[dim], t = st[dim];
77
78 if (t.length > 10) return false;
79
80 Node u = s[index].getDestinationNode(dim == 0), w;
81 Set<Node> candidates = new HashSet<Node>();
82
83 for (int j = findFirstEdge(t, s[index].getLabel()); j < t.length; ++j) {
84 if (j == -1) break;
85 if (s[index].getLabel().equals(t[j].getLabel())) {
86 w = t[j].getDestinationNode(dim == 0);
87 candidates.add(w);
88 }
89 else break;
90 }
91
92 if ((w = mappings.get(u)) != null)
93 if (candidates.contains(w))
94 return checkSortedEdges(ss, st, dim, index + 1);
95 else return false;
96
97 if (candidates.contains(u)) {
98 mappings.put(u, u);
99 if (checkSortedEdges(ss, st, dim, index + 1))
100 return true;
101 mappings.remove(u);
102 return false;
103 };
104
105 for (Node v: candidates) {
106 mappings.put(u, v);
107 if (check(u, v) && checkSortedEdges(ss, st, dim, index + 1))
108 return true;
109 mappings.remove(u);
110 }
111
112 return false;
113 }
114
115 private int findFirstEdge(Edge[] edges, String label) {
116 int left = 0, right = edges.length - 1, mid;
117 while (left < right) {
118 mid = left + (right - left) / 2;
119 if (edges[mid].getLabel().compareTo(label) < 0) left = mid + 1;
120 else right = mid;
121 }
122 return right;
123 }
124
125}
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 @@
1package uk.ac.ox.cs.pagoda.endomorph.plan;
2
3public interface CheckPlan {
4
5 public int check();
6
7}
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 @@
1package uk.ac.ox.cs.pagoda.endomorph.plan;
2
3import java.util.Collection;
4import java.util.Collections;
5import java.util.LinkedList;
6import java.util.Map;
7import java.util.Set;
8import java.util.concurrent.ConcurrentHashMap;
9import java.util.concurrent.ConcurrentLinkedDeque;
10import java.util.concurrent.atomic.AtomicInteger;
11
12import uk.ac.ox.cs.pagoda.endomorph.DependencyGraph;
13import uk.ac.ox.cs.pagoda.endomorph.Clique;
14import uk.ac.ox.cs.pagoda.query.AnswerTuple;
15import uk.ac.ox.cs.pagoda.reasoner.full.Checker;
16import uk.ac.ox.cs.pagoda.reasoner.full.HermitChecker;
17import uk.ac.ox.cs.pagoda.util.Utility;
18
19public class OpenEndMultiThreadPlan implements CheckPlan {
20
21 Checker checker;
22 DependencyGraph dGraph;
23
24 public OpenEndMultiThreadPlan(Checker checker, DependencyGraph dGraph) {
25 this.checker = checker;
26 this.dGraph = dGraph;
27 }
28
29// Clique[] topo;
30// AtomicInteger open, end;
31 ConcurrentLinkedDeque<Clique> topo;
32
33 Set<Clique> validated, falsified;
34
35 @Override
36 public int check() {
37 Collection<Clique> cliques = dGraph.getTopologicalOrder();
38// topo = new LinkedBlockingDeque<Clique>(cliques);
39 topo = new ConcurrentLinkedDeque<Clique>(cliques);
40
41// topo = new Clique[cliques.size()];
42// int index = 0;
43// for (Clique clique: cliques) topo[index++] = clique;
44// open = new AtomicInteger();
45// end = new AtomicInteger(cliques.size() - 1);
46
47// validated = Collections.synchronizedSet(new HashSet<Clique>());
48// falsified = Collections.synchronizedSet(new HashSet<Clique>());
49 validated = Collections.newSetFromMap(new ConcurrentHashMap<Clique, Boolean>());
50 falsified = Collections.newSetFromMap(new ConcurrentHashMap<Clique, Boolean>());
51
52 int numOfThreads = 10;
53 Collection<Thread> threads = new LinkedList<Thread>();
54 for (int i = 0; i < numOfThreads; ++i)
55 threads.add(new Thread(new SubThread(new HermitChecker(checker), i)));
56
57 for (Thread thread: threads) thread.start();
58
59 for (Thread thread: threads) {
60 try {
61 thread.join();
62 } catch (InterruptedException e) {
63 e.printStackTrace();
64 }
65 }
66
67 Utility.logDebug("HermiT was called " + counter.get() + " times.");
68
69 int count = 0;
70 for (Clique c: dGraph.getTopologicalOrder()) {
71 if (validated.contains(c))
72 count += c.getNodeTuples().size() + 1;
73 }
74 return count;
75 }
76
77 private void setMarkCascadely(Clique clique, Set<Clique> marked, Map<Clique, Collection<Clique>> edges) {
78 marked.add(clique);
79 if (edges.containsKey(clique))
80 for (Clique c: edges.get(clique))
81 if (!marked.contains(c))
82 setMarkCascadely(c, marked, edges);
83 }
84
85 AtomicInteger counter = new AtomicInteger();
86
87 class SubThread implements Runnable {
88
89 HermitChecker m_checker;
90 int m_ID;
91
92 public SubThread(HermitChecker checker, int ID) {
93 m_checker = checker;
94 m_ID = ID;
95 }
96
97 @Override
98 public void run() {
99 boolean flag = ((m_ID & 1) == 0);
100 Clique clique;
101 AnswerTuple answerTuple;
102 while (!topo.isEmpty())
103 if (flag) {
104 clique = topo.removeFirst();
105 if (validated.contains(clique)) continue;
106 if (falsified.contains(clique)) { flag = false; continue; }
107 counter.incrementAndGet();
108 Utility.logDebug("Thread " + m_ID + ": start checking front ... " + (answerTuple = clique.getRepresentative().getAnswerTuple()));
109 if (m_checker.check(answerTuple)) {
110 setMarkCascadely(clique, validated, dGraph.getOutGoingEdges());
111 }
112 else {
113 falsified.add(clique);
114 flag = false;
115 }
116 }
117 else {
118 clique = topo.removeLast();
119 if (falsified.contains(clique)) continue;
120 if (validated.contains(clique)) { flag = true; continue; }
121 counter.incrementAndGet();
122 Utility.logDebug("Thread " + m_ID + ": start checking back ... " + (answerTuple = clique.getRepresentative().getAnswerTuple()));
123 if (!m_checker.check(answerTuple))
124 setMarkCascadely(clique, falsified, dGraph.getInComingEdges());
125 else {
126 validated.add(clique);
127 flag = true;
128 }
129 }
130
131 m_checker.dispose();
132 }
133
134 }
135}
136
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 @@
1package uk.ac.ox.cs.pagoda.endomorph.plan;
2
3import java.util.Collection;
4import java.util.Deque;
5import java.util.HashSet;
6import java.util.LinkedList;
7import java.util.Map;
8import java.util.Set;
9
10import uk.ac.ox.cs.pagoda.endomorph.*;
11import uk.ac.ox.cs.pagoda.query.AnswerTuple;
12import uk.ac.ox.cs.pagoda.query.QueryRecord;
13import uk.ac.ox.cs.pagoda.query.QueryRecord.Step;
14import uk.ac.ox.cs.pagoda.reasoner.full.Checker;
15import uk.ac.ox.cs.pagoda.summary.NodeTuple;
16import uk.ac.ox.cs.pagoda.util.Timer;
17import uk.ac.ox.cs.pagoda.util.Utility;
18
19public class OpenEndPlan implements CheckPlan {
20
21 public static final int TIME_OUT_MIN = 1;
22
23 Checker checker;
24 DependencyGraph dGraph;
25 QueryRecord m_record;
26
27 public OpenEndPlan(Checker checker, DependencyGraph dGraph, QueryRecord record) {
28 this.checker = checker;
29 this.dGraph = dGraph;
30 m_record = record;
31 }
32
33 @Override
34 public int check() {
35 Deque<Clique> topo = new LinkedList<Clique>(dGraph.getTopologicalOrder());
36 Utility.logInfo("Entrances: " + dGraph.getEntrances().size() + " Exists: " + dGraph.getExits().size());
37 Set<Clique> validated = new HashSet<Clique>();
38 Set<Clique> falsified = new HashSet<Clique>();
39
40 boolean flag = true;
41 Clique clique;
42 Timer t = new Timer();
43
44
45 AnswerTuple answerTuple;
46 while (!topo.isEmpty()) {
47 if (flag) {
48 clique = topo.removeFirst();
49 if (validated.contains(clique)) continue;
50 if (falsified.contains(clique)) { flag = false; continue; }
51 Utility.logDebug("start checking front ... " + (answerTuple = clique.getRepresentative().getAnswerTuple()));
52 if (checker.check(answerTuple)) {
53 Utility.logDebug(answerTuple.toString() + " is verified.");
54 setMarkCascadely(clique, validated, dGraph.getOutGoingEdges());
55 }
56 else {
57 falsified.add(clique);
58 flag = false;
59 }
60 }
61 else {
62 clique = topo.removeLast();
63 if (falsified.contains(clique)) continue;
64 if (validated.contains(clique)) { flag = true; continue; }
65 Utility.logDebug("start checking back ... " + (answerTuple = clique.getRepresentative().getAnswerTuple()));
66 if (!checker.check(answerTuple))
67 setMarkCascadely(clique, falsified, dGraph.getInComingEdges());
68 else {
69 Utility.logDebug(answerTuple.toString() + " is verified.");
70 validated.add(clique);
71 flag = true;
72 }
73 }
74 }
75
76// Utility.logDebug("HermiT was called " + times + " times.");
77
78 int count = 0;
79 AnswerTuple ans;
80 Collection<AnswerTuple> validAnswers = new LinkedList<AnswerTuple>();
81 for (Clique c: dGraph.getTopologicalOrder())
82 if (validated.contains(c)) {
83 count += c.getNodeTuples().size() + 1;
84 validAnswers.add(c.getRepresentative().getAnswerTuple());
85
86 for (NodeTuple nodeTuple: c.getNodeTuples()) {
87 ans = nodeTuple.getAnswerTuple();
88 validAnswers.add(ans);
89 Utility.logDebug(ans + " is verified.");
90 }
91 }
92
93 m_record.addLowerBoundAnswers(validAnswers);
94 m_record.addProcessingTime(Step.FullReasoning, t.duration());
95 return count;
96 }
97
98 private void setMarkCascadely(Clique clique, Set<Clique> marked, Map<Clique, Collection<Clique>> edges) {
99 marked.add(clique);
100 if (edges.containsKey(clique))
101 for (Clique c: edges.get(clique))
102 if (!marked.contains(c))
103 setMarkCascadely(c, marked, edges);
104 }
105
106}
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 @@
1package uk.ac.ox.cs.pagoda.endomorph.plan;
2
3import java.util.Set;
4
5import uk.ac.ox.cs.pagoda.endomorph.Clique;
6import uk.ac.ox.cs.pagoda.reasoner.full.Checker;
7import uk.ac.ox.cs.pagoda.summary.NodeTuple;
8import uk.ac.ox.cs.pagoda.util.Utility;
9
10public class PlainPlan implements CheckPlan {
11
12 Checker checker;
13 Set<Clique> toCheck;
14
15 public PlainPlan(Checker checker, Set<Clique> toCheck) {
16 this.checker = checker;
17 this.toCheck = toCheck;
18 }
19
20 @Override
21 public int check() {
22 int count = 0;
23 for (Clique clique: toCheck)
24 if (checker.check(clique.getRepresentative().getAnswerTuple())) {
25 count += clique.getNodeTuples().size() + 1;
26 for (NodeTuple nodeTuple: clique.getNodeTuples())
27 Utility.logDebug(nodeTuple.getAnswerTuple().toString());
28 }
29 return count;
30 }
31
32}
generated by cgit v1.2.3 (git 2.25.1) at 2025-11-05 19:17:51 +0000