aboutsummaryrefslogtreecommitdiff
path: root/src/uk/ac/ox/cs/pagoda/endomorph
diff options
context:
space:
mode:
authorFederico Igne <federico.igne@cs.ox.ac.uk>2022-05-10 18:17:06 +0100
committerFederico Igne <federico.igne@cs.ox.ac.uk>2022-05-11 12:34:47 +0100
commit17bd9beaf7f358a44e5bf36a5855fe6727d506dc (patch)
tree47e9310a0cff869d9ec017dcb2c81876407782c8 /src/uk/ac/ox/cs/pagoda/endomorph
parent8651164cd632a5db310b457ce32d4fbc97bdc41c (diff)
downloadACQuA-17bd9beaf7f358a44e5bf36a5855fe6727d506dc.tar.gz
ACQuA-17bd9beaf7f358a44e5bf36a5855fe6727d506dc.zip
[pagoda] Move project to Scala
This commit includes a few changes: - The repository still uses Maven to manage dependency but it is now a Scala project. - The code has been ported from OWLAPI 3.4.10 to 5.1.20 - A proof of concept program using both RSAComb and PAGOdA has been added.
Diffstat (limited to 'src/uk/ac/ox/cs/pagoda/endomorph')
-rw-r--r--src/uk/ac/ox/cs/pagoda/endomorph/Clique.java37
-rw-r--r--src/uk/ac/ox/cs/pagoda/endomorph/DependencyGraph.java290
-rw-r--r--src/uk/ac/ox/cs/pagoda/endomorph/Endomorph.java139
-rw-r--r--src/uk/ac/ox/cs/pagoda/endomorph/EndomorphChecker.java15
-rw-r--r--src/uk/ac/ox/cs/pagoda/endomorph/EndomorphChecker1.java53
-rw-r--r--src/uk/ac/ox/cs/pagoda/endomorph/EndomorphChecker2.java142
-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.java134
-rw-r--r--src/uk/ac/ox/cs/pagoda/endomorph/plan/PlainPlan.java32
10 files changed, 0 insertions, 985 deletions
diff --git a/src/uk/ac/ox/cs/pagoda/endomorph/Clique.java b/src/uk/ac/ox/cs/pagoda/endomorph/Clique.java
deleted file mode 100644
index 9b0d88e..0000000
--- a/src/uk/ac/ox/cs/pagoda/endomorph/Clique.java
+++ /dev/null
@@ -1,37 +0,0 @@
1package uk.ac.ox.cs.pagoda.endomorph;
2
3import uk.ac.ox.cs.pagoda.summary.NodeTuple;
4
5import java.util.Collection;
6import java.util.HashSet;
7import java.util.Set;
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 nodeTuples.add(u);
17 }
18
19 public boolean addNodeTuple(NodeTuple nodeTuple) {
20 return nodeTuples.add(nodeTuple);
21 }
22
23 public NodeTuple getRepresentative() {
24 return representative;
25 }
26
27 @Override
28 public String toString() {
29 return representative.toString();
30 }
31
32 public Collection<NodeTuple> getNodeTuples() {
33 return nodeTuples;
34 }
35
36}
37
diff --git a/src/uk/ac/ox/cs/pagoda/endomorph/DependencyGraph.java b/src/uk/ac/ox/cs/pagoda/endomorph/DependencyGraph.java
deleted file mode 100644
index 0f215ad..0000000
--- a/src/uk/ac/ox/cs/pagoda/endomorph/DependencyGraph.java
+++ /dev/null
@@ -1,290 +0,0 @@
1 package uk.ac.ox.cs.pagoda.endomorph;
2
3 import uk.ac.ox.cs.pagoda.summary.Edge;
4 import uk.ac.ox.cs.pagoda.summary.Graph;
5 import uk.ac.ox.cs.pagoda.summary.Node;
6 import uk.ac.ox.cs.pagoda.summary.NodeTuple;
7 import uk.ac.ox.cs.pagoda.util.Timer;
8 import uk.ac.ox.cs.pagoda.util.Utility;
9
10 import java.util.*;
11
12public class DependencyGraph {
13
14 Set<Clique> entrances = new HashSet<Clique>();
15
16 public Set<Clique> getEntrances() {
17 return entrances;
18 }
19
20 Set<Clique> exits = new HashSet<Clique>();
21
22 public Set<Clique> getExits() {
23 return exits;
24 }
25
26 Map<Clique, Collection<Clique>> outGoingEdges = new HashMap<Clique, Collection<Clique>>();
27
28 public Map<Clique, Collection<Clique>> getOutGoingEdges() {
29 return outGoingEdges;
30 }
31
32 Map<Clique, Collection<Clique>> inComingEdges = new HashMap<Clique, Collection<Clique>>();
33
34 public Map<Clique, Collection<Clique>> getInComingEdges() {
35 return inComingEdges;
36 }
37
38 Graph graph;
39 EndomorphChecker homomorphismChecker;
40 Set<Clique> cliques = new HashSet<Clique>();
41
42 public DependencyGraph(Graph graph) {
43 this.graph = graph;
44 homomorphismChecker = new EndomorphChecker2(graph);
45// homomorphismChecker = new EndomorphChecker1(graph);
46 }
47
48 private int compareNodeTuple(NodeTuple t1, NodeTuple t2) {
49 Iterator<Node> iter1 = t1.getNodes().iterator();
50 Iterator<Node> iter2 = t2.getNodes().iterator();
51 int ret;
52 int index = 0;
53 Node u, v;
54 while (iter1.hasNext()) {
55 u = iter1.next(); v = iter2.next();
56 if (u == null && v == null) {
57 if ((ret = t1.getAnswerTuple().getGroundTerm(index).toString().compareTo(t2.getAnswerTuple().getGroundTerm(index).toString())) != 0)
58 return ret;
59 }
60 else if (u != null && v != null) {
61 if ((ret = compareNode(u, v)) != 0) return ret;
62 }
63 else if (u == null)
64 return 1;
65 else if (v == null)
66 return -1;
67
68 }
69
70 return 0;
71 }
72
73 private int compareNode(Node o1, Node o2) {
74 int result = o1.getConcepts().size() - o2.getConcepts().size();
75 if (result != 0) return dir(result);
76 Edge[] edge1 = graph.getOutGoingEdges(o1), edge2 = graph.getOutGoingEdges(o2);
77 int len1 = edge1 == null ? 0 : edge1.length, len2 = edge2 == null ? 0 : edge2.length;
78 result = len1 - len2;
79 if (result != 0) return dir(result);
80
81 edge1 = graph.getInComingEdges(o1); edge2 = graph.getInComingEdges(o2);
82 len1 = edge1 == null ? 0 : edge1.length; len2 = edge2 == null ? 0 : edge2.length;
83 result = len1 - len2;
84 if (result != 0) return dir(result);
85
86 else return o1.getLabel().compareTo(o2.getLabel());
87 }
88
89 private int dir(int flag) { return - flag; }
90
91 public void build(Collection<NodeTuple> nodeTuples) {
92
93 if (nodeTuples.isEmpty()) return ;
94
95 Timer t = new Timer();
96
97 NodeTuple[] nodeTupleArray = new NodeTuple[nodeTuples.size()];
98 nodeTuples.toArray(nodeTupleArray);
99
100 Arrays.sort(nodeTupleArray, new Comparator<NodeTuple>() {
101 @Override
102 public int compare(NodeTuple t1, NodeTuple t2) {
103 return compareNodeTuple(t1, t2);
104 }
105 });
106
107 Utility.logDebug(nodeTupleArray[0].toString(),
108 nodeTupleArray[nodeTupleArray.length - 1].toString());
109
110 for (NodeTuple nodeTuple: nodeTupleArray) addNodeTuple(nodeTuple);
111
112 Utility.logDebug("The number of times to call homomorphism checker: " + homomorphismCheckCounter + "(" + outGoingCheckCounter + "," + inComingCheckCounter + ").",
113 "Time to compute endomorphism relation: " + t.duration());
114
115// print();
116
117 topologicalOrder = null;
118 Utility.logDebug("link: " + link);
119 }
120
121 LinkedList<Clique> topologicalOrder = null;
122
123 public LinkedList<Clique> getTopologicalOrder() {
124 if (topologicalOrder != null) return topologicalOrder;
125
126 topologicalOrder = new LinkedList<Clique>();
127 Queue<Clique> toVisit = new LinkedList<Clique>(entrances);
128 Map<Clique, Integer> toVisitedInComingDegree = new HashMap<Clique, Integer>();
129
130 int count;
131 while (!toVisit.isEmpty()) {
132 Clique cu = toVisit.remove();
133 topologicalOrder.add(cu);
134 if (outGoingEdges.containsKey(cu))
135 for (Clique cv: outGoingEdges.get(cu)) {
136 if (toVisitedInComingDegree.containsKey(cv)) {
137 count = toVisitedInComingDegree.get(cv) - 1;
138 toVisitedInComingDegree.put(cv, count);
139 }
140 else
141 toVisitedInComingDegree.put(cv, count = inComingEdges.get(cv).size() - 1);
142 if (count == 0)
143 toVisit.add(cv);
144 }
145 }
146
147 return topologicalOrder;
148 }
149
150 private void addNodeTuple(NodeTuple u) {
151 Queue<Clique> toCompare = new LinkedList<Clique>(entrances);
152
153 Map<Clique, Integer> toVisitedDegree = new HashMap<Clique, Integer>();
154 Collection<Clique> directSuccessors = new LinkedList<Clique>();
155
156 int count;
157 while (!toCompare.isEmpty()) {
158 Clique cv = toCompare.remove();
159 ++outGoingCheckCounter;
160 if (checkHomomorphism(u, cv.representative)) {
161 directSuccessors.add(cv);
162 }
163 else {
164 if (outGoingEdges.containsKey(cv))
165 for (Clique c: outGoingEdges.get(cv)) {
166 if (toVisitedDegree.containsKey(c)) {
167 count = toVisitedDegree.get(c) - 1;
168 toVisitedDegree.put(c, count);
169 }
170 else
171 toVisitedDegree.put(c, count = inComingEdges.get(c).size() - 1);
172
173 if (count == 0)
174 toCompare.add(c);
175 }
176 }
177 }
178
179 if (directSuccessors.size() == 1) {
180 Clique clique = directSuccessors.iterator().next();
181 if (checkHomomorphism(clique.representative, u)) {
182 clique.addNodeTuple(u);
183 return ;
184 }
185 }
186
187 Clique cu = new Clique(u);
188 cliques.add(cu);
189
190 toCompare.clear();
191 Set<Clique> visited = new HashSet<Clique>();
192
193 if (directSuccessors.size() == 0)
194 toCompare.addAll(exits);
195 else {
196 for (Clique cv: directSuccessors)
197 if (inComingEdges.containsKey(cv))
198 for (Clique cw: inComingEdges.get(cv)) {
199 visited.add(cw);
200 toCompare.add(cw);
201 }
202 }
203
204
205
206 Collection<Clique> directPredecessors = new LinkedList<Clique>();
207
208 while (!toCompare.isEmpty()) {
209 Clique cv = toCompare.remove();
210 ++inComingCheckCounter;
211 if (checkHomomorphism(cv.representative, u))
212 directPredecessors.add(cv);
213 else {
214 if (inComingEdges.containsKey(cv))
215 for (Clique c: inComingEdges.get(cv))
216 if (!visited.contains(c)) {
217 visited.add(c);
218 toCompare.add(c);
219 }
220 }
221 }
222
223 for (Clique cv: directSuccessors) {
224 if (entrances.contains(cv)) entrances.remove(cv);
225 link(cu, cv);
226 }
227
228 for (Clique cw: directPredecessors) {
229 if (exits.contains(cw)) exits.remove(cw);
230 link(cw, cu);
231 }
232
233 if (directPredecessors.size() == 0) entrances.add(cu);
234 if (directSuccessors.size() == 0) exits.add(cu);
235 }
236
237 private int homomorphismCheckCounter = 0;
238 private int outGoingCheckCounter = 0, inComingCheckCounter = 0;
239
240 private boolean checkHomomorphism(NodeTuple u, NodeTuple v) {
241 ++homomorphismCheckCounter;
242 homomorphismChecker.setMapping(u, v);
243
244 if(!homomorphismChecker.isMappingTo(u, v))
245 return false;
246
247 try {
248 Node node1, node2;
249 for (Iterator<Node> iter1 = u.getNodes().iterator(), iter2 = v.getNodes().iterator(); iter1.hasNext(); ) {
250 node1 = iter1.next(); node2 = iter2.next();
251 if (node1 != node2 && !homomorphismChecker.check(node1, node2)) {
252// System.out.println(homomorphismChecker.check(node1, node2));
253 return false;
254 }
255 }
256 return true;
257 } finally {
258 homomorphismChecker.clearMappings();
259 }
260 }
261
262 private void link(Clique u, Clique v) {
263 ++link;
264 addToList(outGoingEdges, u, v);
265 addToList(inComingEdges, v, u);
266 }
267
268 private int link = 0;
269
270 private void addToList(Map<Clique, Collection<Clique>> map, Clique u, Clique v) {
271 Collection<Clique> temp;
272 if ((temp = map.get(u)) == null) {
273 temp = new LinkedList<Clique>();
274 map.put(u, temp);
275 }
276 temp.add(v);
277 }
278
279 public void print() {
280 System.out.println("---------- Dependency Graph -------------");
281 for (Clique u: cliques)
282 if (outGoingEdges.containsKey(u))
283 for (Clique v: outGoingEdges.get(u))
284 System.out.println(u + " -> " + v);
285 System.out.println("-----------------------------------------");
286 }
287
288
289}
290
diff --git a/src/uk/ac/ox/cs/pagoda/endomorph/Endomorph.java b/src/uk/ac/ox/cs/pagoda/endomorph/Endomorph.java
deleted file mode 100644
index 9ca73a1..0000000
--- a/src/uk/ac/ox/cs/pagoda/endomorph/Endomorph.java
+++ /dev/null
@@ -1,139 +0,0 @@
1package uk.ac.ox.cs.pagoda.endomorph;
2
3import org.semanticweb.owlapi.model.OWLOntology;
4import uk.ac.ox.cs.pagoda.endomorph.plan.CheckPlan;
5import uk.ac.ox.cs.pagoda.endomorph.plan.OpenEndPlan;
6import uk.ac.ox.cs.pagoda.query.AnswerTuple;
7import uk.ac.ox.cs.pagoda.query.AnswerTuples;
8import uk.ac.ox.cs.pagoda.query.QueryRecord;
9import uk.ac.ox.cs.pagoda.reasoner.full.Checker;
10import uk.ac.ox.cs.pagoda.summary.Graph;
11import uk.ac.ox.cs.pagoda.summary.NodeTuple;
12import uk.ac.ox.cs.pagoda.util.Timer;
13import uk.ac.ox.cs.pagoda.util.Utility;
14import uk.ac.ox.cs.pagoda.util.disposable.DisposedException;
15
16import java.util.Collection;
17import java.util.LinkedList;
18
19public class Endomorph extends Checker {
20
21 Checker fullReasoner;
22 DependencyGraph dGraph;
23 Graph graph;
24 QueryRecord m_record;
25
26 /**
27 * constructor using HermiTChecker ...
28 * @throws Exception
29 */
30
31 public Endomorph(QueryRecord record, Checker checker) {
32 this.m_record = record;
33 fullReasoner = checker;
34 graph = new Graph(record.getRelevantOntology());
35 dGraph = new DependencyGraph(graph);
36 }
37
38 /*
39 * FIXME
40 * The result is unsound. The output is not deterministic.
41 * */
42 @Override
43 public int check(AnswerTuples answerTuples) {
44 if(isDisposed()) throw new DisposedException();
45
46 Collection<NodeTuple> nodes = new LinkedList<NodeTuple>();
47 int counter = 0;
48
49 for (; answerTuples.isValid(); answerTuples.moveNext()) {
50 ++counter;
51 nodes.add(graph.getNodeTuple(answerTuples.getTuple()));
52 }
53 answerTuples.dispose();
54
55 Timer t = new Timer();
56 dGraph.build(nodes);
57// dGraph.print();
58 Utility.logDebug("@TIME to group individuals in the gap: " + t.duration());
59 Utility.logInfo("The number of different groups: " + dGraph.cliques.size());
60
61 Utility.logInfo("The number of individuals to be checked by Homomorphism checker: " + counter);
62// CheckPlan plan = new PlainPlan(this.checker, dGraph.cliques);
63// CheckPlan plan = new OpenEndMultiThreadPlan(this.checker, dGraph);
64
65 CheckPlan plan = new OpenEndPlan(fullReasoner, dGraph, m_record);
66 int answerCounter = plan.check();
67
68
69// // BEGIN: debugging code
70// Set<AnswerTuple> validatedAnswers = new HashSet<>();
71// for (answerTuples.reset(); answerTuples.isValid(); answerTuples.moveNext()) {
72// if(fullReasoner.check(answerTuples.getTuple())) {
73// validatedAnswers.add(answerTuples.getTuple());
74// }
75// }
76// m_record.addLowerBoundAnswers(validatedAnswers);
77//
78// Utility.logDebug("The number of correct answers: " + validatedAnswers.size());
79// return validatedAnswers.size();
80//// END: debugging code
81
82 Utility.logDebug("The number of correct answers: " + answerCounter);
83 return answerCounter;
84 }
85
86 public OWLOntology getOntology() {
87 if(isDisposed()) throw new DisposedException();
88
89 return m_record.getRelevantOntology();
90 }
91
92 @Override
93 public boolean check(AnswerTuple answerTuple) {
94 if(isDisposed()) throw new DisposedException();
95
96 return fullReasoner.check(answerTuple);
97 }
98
99 @Override
100 public boolean isConsistent() {
101 if(isDisposed()) throw new DisposedException();
102
103 return fullReasoner.isConsistent();
104 }
105
106 @Override
107 public int getNoOfCalls() {
108 return fullReasoner.getNoOfCalls();
109 }
110
111 @Override
112 public void dispose() {
113 super.dispose();
114
115 if(fullReasoner != null) {
116// Utility.logInfo("Hermit was called " + fullReasoner.getNoOfCalls() + " times");
117 fullReasoner.dispose();
118 }
119 }
120
121 public Graph getGraph() {
122 if(isDisposed()) throw new DisposedException();
123
124 return graph;
125 }
126
127 public Checker getChecker() {
128 if(isDisposed()) throw new DisposedException();
129
130 return fullReasoner;
131 }
132
133 public DependencyGraph getDependencyGraph() {
134 if(isDisposed()) throw new DisposedException();
135
136 return dGraph;
137 }
138
139}
diff --git a/src/uk/ac/ox/cs/pagoda/endomorph/EndomorphChecker.java b/src/uk/ac/ox/cs/pagoda/endomorph/EndomorphChecker.java
deleted file mode 100644
index 46ddbb3..0000000
--- a/src/uk/ac/ox/cs/pagoda/endomorph/EndomorphChecker.java
+++ /dev/null
@@ -1,15 +0,0 @@
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 boolean isMappingTo(NodeTuple u, NodeTuple v);
15}
diff --git a/src/uk/ac/ox/cs/pagoda/endomorph/EndomorphChecker1.java b/src/uk/ac/ox/cs/pagoda/endomorph/EndomorphChecker1.java
deleted file mode 100644
index c2117b6..0000000
--- a/src/uk/ac/ox/cs/pagoda/endomorph/EndomorphChecker1.java
+++ /dev/null
@@ -1,53 +0,0 @@
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 return isSubsetOf(graph.getInComingEdges(u), graph.getInComingEdges(v), false);
20 }
21
22 @Override
23 public boolean isMappingTo(NodeTuple u, NodeTuple v) {
24 throw new UnsupportedOperationException();
25 }
26
27 private boolean isSubsetOf(Edge[] e1, Edge[] e2, boolean out) {
28 int j = 0;
29 for (int i = 0; i < e1.length; ++i) {
30 while (j < e2.length && equals(e1[i], e2[j], out))
31 ++j;
32 }
33 return j < e2.length;
34 }
35
36 private boolean equals(Edge edge, Edge edge2, boolean out) {
37 if (!edge.getLabel().equals(edge2.getLabel())) return false;
38 return out ? edge.getToNode().equals(edge2.getToNode()) : edge.getFromNode().equals(edge2.getFromNode());
39 }
40
41 @Override
42 public void clearMappings() {
43 // TODO Auto-generated method stub
44
45 }
46
47 @Override
48 public void setMapping(NodeTuple u, NodeTuple v) {
49 // TODO Auto-generated method stub
50
51 }
52
53}
diff --git a/src/uk/ac/ox/cs/pagoda/endomorph/EndomorphChecker2.java b/src/uk/ac/ox/cs/pagoda/endomorph/EndomorphChecker2.java
deleted file mode 100644
index aac5f3c..0000000
--- a/src/uk/ac/ox/cs/pagoda/endomorph/EndomorphChecker2.java
+++ /dev/null
@@ -1,142 +0,0 @@
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;
7import uk.ac.ox.cs.pagoda.util.Timer;
8
9import java.util.*;
10
11public class EndomorphChecker2 implements EndomorphChecker {
12
13 private Graph graph;
14// DependencyGraph dGraph;
15
16 public EndomorphChecker2(Graph graph) {
17 this.graph = graph;
18 }
19
20 private Timer timer = new Timer();
21 private boolean time_out = false;
22 private static final int TIME_OUT = 60;
23// private static final int TIME_OUT = 99999999;
24
25 public boolean check(NodeTuple u, NodeTuple v) {
26 int length = u.getNodes().size();
27 Edge[][] ss = new Edge[1][length], tt = new Edge[1][length];
28 int index = 0;
29 Iterator<Node> iter1 = u.getNodes().iterator();
30 Iterator<Node> iter2 = v.getNodes().iterator();
31 for (; iter1.hasNext(); ) {
32 ss[0][index] = new Edge(null, iter1.next(), "auxilary" + index);
33 tt[0][index++] = new Edge(null, iter2.next(), "auxilary" + index);
34 }
35 return checkSortedEdges(ss, tt, 0, 0);
36 }
37
38 public boolean check(Node u, Node v) {
39 if (!u.isSubConceptOf(v)) return false;
40 return checkSortedEdges(new Edge[][]{graph.getOutGoingEdges(u), graph.getInComingEdges(u)},
41 new Edge[][]{graph.getOutGoingEdges(v), graph.getInComingEdges(v)}, 0, 0);
42 }
43
44 /***
45 * Checks whether the found mapping is actually a mapping from tuple u to tuple v.
46 *
47 * @param u
48 * @param v
49 * @return
50 */
51 @Override
52 public boolean isMappingTo(NodeTuple u, NodeTuple v) {
53 Iterator<Node> uIterator = u.getNodes().iterator();
54 Iterator<Node> vIterator = v.getNodes().iterator();
55
56 while(uIterator.hasNext() && vIterator.hasNext()) {
57 Node uNode = uIterator.next();
58 Node vNode = vIterator.next();
59 if(mappings.containsKey(uNode) && !mappings.get(uNode).equals(vNode))
60 return false;
61 else if(!mappings.containsKey(uNode) && !uNode.equals(vNode))
62 return false;
63 }
64 return !uIterator.hasNext() && !vIterator.hasNext();
65 }
66
67 Map<Node, Node> mappings = new HashMap<Node, Node>();
68
69 public void clearMappings() {
70 mappings.clear();
71 timer.pause();
72 }
73
74 public void setMapping(NodeTuple key, NodeTuple value) {
75 timer.resume();
76 // FIXME
77 timer.setTimeout(TIME_OUT);
78// time_out = false;
79 for (Iterator<Node> key_iter = key.getNodes().iterator(), value_iter = value.getNodes().iterator(); key_iter.hasNext(); ) {
80 mappings.put(key_iter.next(), value_iter.next());
81 }
82 }
83
84 private boolean checkSortedEdges(Edge[][] ss, Edge[][] st, int dim, int index) {
85 if (time_out || timer.timeOut()) {
86 time_out = true;
87 return false;
88 }
89
90 while (ss[dim] == null || index >= ss[dim].length)
91 if (++dim >= ss.length) return true;
92 else index = 0;
93 Edge[] s = ss[dim], t = st[dim];
94
95 if (t.length > 10) return false;
96
97 Node u = s[index].getDestinationNode(dim == 0), w;
98 Set<Node> candidates = new HashSet<Node>();
99
100 for (int j = findFirstEdge(t, s[index].getLabel()); j < t.length; ++j) {
101 if (j == -1) break;
102 if (s[index].getLabel().equals(t[j].getLabel())) {
103 w = t[j].getDestinationNode(dim == 0);
104 candidates.add(w);
105 }
106 else break;
107 }
108
109 if ((w = mappings.get(u)) != null)
110 if (candidates.contains(w))
111 return checkSortedEdges(ss, st, dim, index + 1);
112 else return false;
113
114 if (candidates.contains(u)) {
115 mappings.put(u, u);
116 if (checkSortedEdges(ss, st, dim, index + 1))
117 return true;
118 mappings.remove(u);
119 return false;
120 }
121
122 for (Node v: candidates) {
123 mappings.put(u, v);
124 if (check(u, v) && checkSortedEdges(ss, st, dim, index + 1))
125 return true;
126 mappings.remove(u);
127 }
128
129 return false;
130 }
131
132 private int findFirstEdge(Edge[] edges, String label) {
133 int left = 0, right = edges.length - 1, mid;
134 while (left < right) {
135 mid = left + (right - left) / 2;
136 if (edges[mid].getLabel().compareTo(label) < 0) left = mid + 1;
137 else right = mid;
138 }
139 return right;
140 }
141
142}
diff --git a/src/uk/ac/ox/cs/pagoda/endomorph/plan/CheckPlan.java b/src/uk/ac/ox/cs/pagoda/endomorph/plan/CheckPlan.java
deleted file mode 100644
index ab3735f..0000000
--- a/src/uk/ac/ox/cs/pagoda/endomorph/plan/CheckPlan.java
+++ /dev/null
@@ -1,7 +0,0 @@
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
deleted file mode 100644
index 4e2fc5f..0000000
--- a/src/uk/ac/ox/cs/pagoda/endomorph/plan/OpenEndMultiThreadPlan.java
+++ /dev/null
@@ -1,136 +0,0 @@
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();
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
deleted file mode 100644
index 076427e..0000000
--- a/src/uk/ac/ox/cs/pagoda/endomorph/plan/OpenEndPlan.java
+++ /dev/null
@@ -1,134 +0,0 @@
1package uk.ac.ox.cs.pagoda.endomorph.plan;
2
3import uk.ac.ox.cs.pagoda.endomorph.Clique;
4import uk.ac.ox.cs.pagoda.endomorph.DependencyGraph;
5import uk.ac.ox.cs.pagoda.query.AnswerTuple;
6import uk.ac.ox.cs.pagoda.query.QueryRecord;
7import uk.ac.ox.cs.pagoda.query.QueryRecord.Step;
8import uk.ac.ox.cs.pagoda.reasoner.full.Checker;
9import uk.ac.ox.cs.pagoda.summary.NodeTuple;
10import uk.ac.ox.cs.pagoda.util.SimpleProgressBar;
11import uk.ac.ox.cs.pagoda.util.Timer;
12import uk.ac.ox.cs.pagoda.util.Utility;
13
14import java.util.*;
15
16public class OpenEndPlan implements CheckPlan {
17
18 public static final int TIME_OUT_MIN = 1;
19
20 Checker checker;
21 DependencyGraph dGraph;
22 QueryRecord m_record;
23 int m_answerArity;
24 Set<Clique> validated = new HashSet<Clique>();
25 Set<Clique> falsified = new HashSet<Clique>();
26 Set<AnswerTuple> passedAnswers = new HashSet<AnswerTuple>();
27 public OpenEndPlan(Checker checker, DependencyGraph dGraph, QueryRecord record) {
28 this.checker = checker;
29 this.dGraph = dGraph;
30 m_record = record;
31 m_answerArity = record.getAnswerVariables().length;
32 }
33
34 @Override
35 public int check() {
36 LinkedList<Clique> topo = new LinkedList<Clique>(dGraph.getTopologicalOrder());
37 Utility.logInfo("Entrances: " + dGraph.getEntrances().size() + " Exists: " + dGraph.getExits().size());
38
39 boolean flag = true;
40 Clique clique;
41 Timer t = new Timer();
42
43 AnswerTuple answerTuple;
44 int initialTopoSize = topo.size();
45 // TODO test progress bar
46 SimpleProgressBar progressBar = new SimpleProgressBar("Checking", initialTopoSize);
47 while (!topo.isEmpty()) {
48 progressBar.update(initialTopoSize - topo.size());
49 if (flag) {
50 clique = topo.removeFirst();
51 if (redundant(clique)) continue;
52 if (validated.contains(clique)) continue;
53 if (falsified.contains(clique)) { flag = false; continue; }
54 Utility.logDebug("start checking front ... " + (answerTuple = clique.getRepresentative().getAnswerTuple()));
55 if (checker.check(answerTuple)) {
56 Utility.logDebug(answerTuple.toString() + " is verified.");
57 setMarkCascadelyValidated(clique);
58 }
59 else {
60 falsified.add(clique);
61 flag = false;
62 }
63 }
64 else {
65 clique = topo.removeLast();
66 if (falsified.contains(clique)) continue;
67 if (validated.contains(clique)) { flag = true; continue; }
68 Utility.logDebug("start checking back ... " + (answerTuple = clique.getRepresentative().getAnswerTuple()));
69 if (!checker.check(answerTuple))
70 setMarkCascadelyFasified(clique);
71 else {
72 Utility.logDebug(answerTuple.toString() + " is verified.");
73 addProjections(clique);
74 flag = true;
75 validated.add(clique);
76 }
77 }
78 }
79 progressBar.update(initialTopoSize - topo.size());
80 progressBar.dispose();
81
82// Utility.logDebug("HermiT was called " + times + " times.");
83
84 int count = 0;
85 AnswerTuple ans;
86 Collection<AnswerTuple> validAnswers = new LinkedList<AnswerTuple>();
87 for (Clique c: dGraph.getTopologicalOrder())
88 if (validated.contains(c)) {
89 count += c.getNodeTuples().size();
90// validAnswers.add(c.getRepresentative().getAnswerTuple());
91 for (NodeTuple nodeTuple: c.getNodeTuples()) {
92 ans = nodeTuple.getAnswerTuple();
93 validAnswers.add(ans);
94 Utility.logDebug(ans + " is verified.");
95 }
96 }
97
98 m_record.addLowerBoundAnswers(validAnswers);
99 m_record.addProcessingTime(Step.FULL_REASONING, t.duration());
100 return count;
101 }
102
103 private boolean redundant(Clique clique) {
104 for (NodeTuple nodeTuple: clique.getNodeTuples())
105 if(!passedAnswers.contains(AnswerTuple.create(nodeTuple.getAnswerTuple(), m_answerArity)))
106 return false;
107 return true;
108 }
109
110 private void addProjections(Clique clique) {
111 for (NodeTuple nodeTuple: clique.getNodeTuples())
112 passedAnswers.add(AnswerTuple.create(nodeTuple.getAnswerTuple(), m_answerArity));
113 }
114
115 private void setMarkCascadelyValidated(Clique clique) {
116 validated.add(clique);
117 addProjections(clique);
118 Map<Clique, Collection<Clique>> edges = dGraph.getOutGoingEdges();
119 if (edges.containsKey(clique))
120 for (Clique c: edges.get(clique))
121 if (!validated.contains(c))
122 setMarkCascadelyValidated(c);
123 }
124
125 private void setMarkCascadelyFasified(Clique clique) {
126 falsified.add(clique);
127 Map<Clique, Collection<Clique>> edges = dGraph.getInComingEdges();
128 if (edges.containsKey(clique))
129 for (Clique c: edges.get(clique))
130 if (!falsified.contains(c))
131 setMarkCascadelyFasified(c);
132 }
133
134}
diff --git a/src/uk/ac/ox/cs/pagoda/endomorph/plan/PlainPlan.java b/src/uk/ac/ox/cs/pagoda/endomorph/plan/PlainPlan.java
deleted file mode 100644
index 5e1a700..0000000
--- a/src/uk/ac/ox/cs/pagoda/endomorph/plan/PlainPlan.java
+++ /dev/null
@@ -1,32 +0,0 @@
1package uk.ac.ox.cs.pagoda.endomorph.plan;
2
3import uk.ac.ox.cs.pagoda.endomorph.Clique;
4import uk.ac.ox.cs.pagoda.reasoner.full.Checker;
5import uk.ac.ox.cs.pagoda.summary.NodeTuple;
6import uk.ac.ox.cs.pagoda.util.Utility;
7
8import java.util.Set;
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();
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 16:11:23 +0000