aboutsummaryrefslogtreecommitdiff
path: root/src/uk/ac/ox/cs/pagoda/endomorph/DependencyGraph.java
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/DependencyGraph.java
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/DependencyGraph.java')
-rw-r--r--src/uk/ac/ox/cs/pagoda/endomorph/DependencyGraph.java290
1 files changed, 0 insertions, 290 deletions
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
generated by cgit v1.2.3 (git 2.25.1) at 2025-11-05 17:06:45 +0000