diff options
Diffstat (limited to 'subprojects/viatra-runtime-rete/src/main/java/tools/refinery/viatra/runtime/rete/itc/alg/incscc')
2 files changed, 645 insertions, 0 deletions
diff --git a/subprojects/viatra-runtime-rete/src/main/java/tools/refinery/viatra/runtime/rete/itc/alg/incscc/CountingListener.java b/subprojects/viatra-runtime-rete/src/main/java/tools/refinery/viatra/runtime/rete/itc/alg/incscc/CountingListener.java new file mode 100644 index 00000000..7d507d82 --- /dev/null +++ b/subprojects/viatra-runtime-rete/src/main/java/tools/refinery/viatra/runtime/rete/itc/alg/incscc/CountingListener.java | |||
@@ -0,0 +1,36 @@ | |||
1 | /******************************************************************************* | ||
2 | * Copyright (c) 2010-2012, Tamas Szabo, Istvan Rath and Daniel Varro | ||
3 | * This program and the accompanying materials are made available under the | ||
4 | * terms of the Eclipse Public License v. 2.0 which is available at | ||
5 | * http://www.eclipse.org/legal/epl-v20.html. | ||
6 | * | ||
7 | * SPDX-License-Identifier: EPL-2.0 | ||
8 | *******************************************************************************/ | ||
9 | package tools.refinery.viatra.runtime.rete.itc.alg.incscc; | ||
10 | |||
11 | import tools.refinery.viatra.runtime.rete.itc.igraph.ITcObserver; | ||
12 | import tools.refinery.viatra.runtime.matchers.util.Direction; | ||
13 | |||
14 | /** | ||
15 | * @author Tamas Szabo | ||
16 | * | ||
17 | */ | ||
18 | public class CountingListener<V> implements ITcObserver<V> { | ||
19 | |||
20 | private IncSCCAlg<V> alg; | ||
21 | |||
22 | public CountingListener(IncSCCAlg<V> alg) { | ||
23 | this.alg = alg; | ||
24 | } | ||
25 | |||
26 | @Override | ||
27 | public void tupleInserted(V source, V target) { | ||
28 | alg.notifyTcObservers(alg.sccs.getPartition(source), alg.sccs.getPartition(target), Direction.INSERT); | ||
29 | } | ||
30 | |||
31 | @Override | ||
32 | public void tupleDeleted(V source, V target) { | ||
33 | alg.notifyTcObservers(alg.sccs.getPartition(source), alg.sccs.getPartition(target), Direction.DELETE); | ||
34 | } | ||
35 | |||
36 | } | ||
diff --git a/subprojects/viatra-runtime-rete/src/main/java/tools/refinery/viatra/runtime/rete/itc/alg/incscc/IncSCCAlg.java b/subprojects/viatra-runtime-rete/src/main/java/tools/refinery/viatra/runtime/rete/itc/alg/incscc/IncSCCAlg.java new file mode 100644 index 00000000..774e55eb --- /dev/null +++ b/subprojects/viatra-runtime-rete/src/main/java/tools/refinery/viatra/runtime/rete/itc/alg/incscc/IncSCCAlg.java | |||
@@ -0,0 +1,609 @@ | |||
1 | /******************************************************************************* | ||
2 | * Copyright (c) 2010-2012, Tamas Szabo, Istvan Rath and Daniel Varro | ||
3 | * This program and the accompanying materials are made available under the | ||
4 | * terms of the Eclipse Public License v. 2.0 which is available at | ||
5 | * http://www.eclipse.org/legal/epl-v20.html. | ||
6 | * | ||
7 | * SPDX-License-Identifier: EPL-2.0 | ||
8 | *******************************************************************************/ | ||
9 | |||
10 | package tools.refinery.viatra.runtime.rete.itc.alg.incscc; | ||
11 | |||
12 | import tools.refinery.viatra.runtime.matchers.algorithms.UnionFind; | ||
13 | import tools.refinery.viatra.runtime.matchers.util.CollectionsFactory; | ||
14 | import tools.refinery.viatra.runtime.matchers.util.Direction; | ||
15 | import tools.refinery.viatra.runtime.matchers.util.IMemoryView; | ||
16 | import tools.refinery.viatra.runtime.rete.itc.alg.counting.CountingAlg; | ||
17 | import tools.refinery.viatra.runtime.rete.itc.alg.misc.DFSPathFinder; | ||
18 | import tools.refinery.viatra.runtime.rete.itc.alg.misc.GraphHelper; | ||
19 | import tools.refinery.viatra.runtime.rete.itc.alg.misc.IGraphPathFinder; | ||
20 | import tools.refinery.viatra.runtime.rete.itc.alg.misc.Tuple; | ||
21 | import tools.refinery.viatra.runtime.rete.itc.alg.misc.bfs.BFS; | ||
22 | import tools.refinery.viatra.runtime.rete.itc.alg.misc.scc.SCC; | ||
23 | import tools.refinery.viatra.runtime.rete.itc.alg.misc.scc.SCCResult; | ||
24 | import tools.refinery.viatra.runtime.rete.itc.alg.util.CollectionHelper; | ||
25 | import tools.refinery.viatra.runtime.rete.itc.graphimpl.Graph; | ||
26 | import tools.refinery.viatra.runtime.rete.itc.igraph.*; | ||
27 | |||
28 | import java.util.*; | ||
29 | import java.util.Map.Entry; | ||
30 | |||
31 | /** | ||
32 | * Incremental SCC maintenance + counting algorithm. | ||
33 | * | ||
34 | * @author Tamas Szabo | ||
35 | * | ||
36 | * @param <V> | ||
37 | * the type parameter of the nodes in the graph data source | ||
38 | */ | ||
39 | public class IncSCCAlg<V> implements IGraphObserver<V>, ITcDataSource<V> { | ||
40 | |||
41 | public UnionFind<V> sccs; | ||
42 | public IBiDirectionalGraphDataSource<V> gds; | ||
43 | private CountingAlg<V> counting; | ||
44 | private Graph<V> reducedGraph; | ||
45 | private IBiDirectionalGraphDataSource<V> reducedGraphIndexer; | ||
46 | private List<ITcObserver<V>> observers; | ||
47 | private CountingListener<V> countingListener; | ||
48 | |||
49 | public IncSCCAlg(IGraphDataSource<V> graphDataSource) { | ||
50 | |||
51 | if (graphDataSource instanceof IBiDirectionalGraphDataSource<?>) { | ||
52 | gds = (IBiDirectionalGraphDataSource<V>) graphDataSource; | ||
53 | } else { | ||
54 | gds = new IBiDirectionalWrapper<V>(graphDataSource); | ||
55 | } | ||
56 | observers = CollectionsFactory.createObserverList(); | ||
57 | sccs = new UnionFind<V>(); | ||
58 | reducedGraph = new Graph<V>(); | ||
59 | reducedGraphIndexer = new IBiDirectionalWrapper<V>(reducedGraph); | ||
60 | countingListener = new CountingListener<V>(this); | ||
61 | initalizeInternalDataStructures(); | ||
62 | gds.attachObserver(this); | ||
63 | } | ||
64 | |||
65 | private void initalizeInternalDataStructures() { | ||
66 | SCCResult<V> _sccres = SCC.computeSCC(gds); | ||
67 | Set<Set<V>> _sccs = _sccres.getSccs(); | ||
68 | |||
69 | for (Set<V> _set : _sccs) { | ||
70 | sccs.makeSet(_set); | ||
71 | } | ||
72 | |||
73 | // Initalization of the reduced graph | ||
74 | for (V n : sccs.getPartitionHeads()) { | ||
75 | reducedGraph.insertNode(n); | ||
76 | } | ||
77 | |||
78 | for (V source : gds.getAllNodes()) { | ||
79 | final IMemoryView<V> targetNodes = gds.getTargetNodes(source); | ||
80 | for (Entry<V, Integer> entry : targetNodes.entriesWithMultiplicities()) { | ||
81 | for (int i = 0; i < entry.getValue(); i++) { | ||
82 | V target = entry.getKey(); | ||
83 | V sourceRoot = sccs.find(source); | ||
84 | V targetRoot = sccs.find(target); | ||
85 | |||
86 | if (!sourceRoot.equals(targetRoot)) { | ||
87 | reducedGraph.insertEdge(sourceRoot, targetRoot); | ||
88 | } | ||
89 | } | ||
90 | } | ||
91 | } | ||
92 | |||
93 | counting = new CountingAlg<V>(reducedGraph); | ||
94 | } | ||
95 | |||
96 | @Override | ||
97 | public void edgeInserted(V source, V target) { | ||
98 | V sourceRoot = sccs.find(source); | ||
99 | V targetRoot = sccs.find(target); | ||
100 | |||
101 | // Different SCC | ||
102 | if (!sourceRoot.equals(targetRoot)) { | ||
103 | |||
104 | // source is reachable from target? | ||
105 | if (counting.isReachable(targetRoot, sourceRoot)) { | ||
106 | |||
107 | Set<V> predecessorRoots = counting.getAllReachableSources(sourceRoot); | ||
108 | Set<V> successorRoots = counting.getAllReachableTargets(targetRoot); | ||
109 | |||
110 | // 1. intersection of source and target roots, these will be in the merged SCC | ||
111 | Set<V> isectRoots = CollectionHelper.intersection(predecessorRoots, successorRoots); | ||
112 | isectRoots.add(sourceRoot); | ||
113 | isectRoots.add(targetRoot); | ||
114 | |||
115 | // notifications must be issued before Union-Find modifications | ||
116 | if (observers.size() > 0) { | ||
117 | Set<V> sourceSCCs = createSetNullTolerant(predecessorRoots); | ||
118 | sourceSCCs.add(sourceRoot); | ||
119 | Set<V> targetSCCs = createSetNullTolerant(successorRoots); | ||
120 | targetSCCs.add(targetRoot); | ||
121 | |||
122 | // tracing back to actual nodes | ||
123 | for (V sourceSCC : sourceSCCs) { | ||
124 | targetLoop: for (V targetSCC : targetSCCs) { | ||
125 | if (counting.isReachable(sourceSCC, targetSCC)) continue targetLoop; | ||
126 | |||
127 | boolean needsNotification = | ||
128 | // Case 1. sourceSCC and targetSCC are the same and it is a one sized scc. | ||
129 | // Issue notifications only if there is no self-loop present at the moment | ||
130 | (sourceSCC.equals(targetSCC) && sccs.getPartition(sourceSCC).size() == 1 && GraphHelper | ||
131 | .getEdgeCount(sccs.getPartition(sourceSCC).iterator().next(), gds) == 0) | ||
132 | || | ||
133 | // Case 2. sourceSCC and targetSCC are different sccs. | ||
134 | (!sourceSCC.equals(targetSCC)); | ||
135 | // if self loop is already present omit the notification | ||
136 | if (needsNotification) { | ||
137 | notifyTcObservers(sccs.getPartition(sourceSCC), sccs.getPartition(targetSCC), | ||
138 | Direction.INSERT); | ||
139 | } | ||
140 | } | ||
141 | } | ||
142 | } | ||
143 | |||
144 | // 2. delete edges, nodes | ||
145 | List<V> sourceSCCs = new ArrayList<V>(); | ||
146 | List<V> targetSCCs = new ArrayList<V>(); | ||
147 | |||
148 | for (V r : isectRoots) { | ||
149 | List<V> sourceSCCsOfSCC = getSourceSCCsOfSCC(r); | ||
150 | List<V> targetSCCsOfSCC = getTargetSCCsOfSCC(r); | ||
151 | |||
152 | for (V sourceSCC : sourceSCCsOfSCC) { | ||
153 | if (!sourceSCC.equals(r)) { | ||
154 | reducedGraph.deleteEdgeIfExists(sourceSCC, r); | ||
155 | } | ||
156 | } | ||
157 | |||
158 | for (V targetSCC : targetSCCsOfSCC) { | ||
159 | if (!isectRoots.contains(targetSCC) && !r.equals(targetSCC)) { | ||
160 | reducedGraph.deleteEdgeIfExists(r, targetSCC); | ||
161 | } | ||
162 | } | ||
163 | |||
164 | sourceSCCs.addAll(sourceSCCsOfSCC); | ||
165 | targetSCCs.addAll(targetSCCsOfSCC); | ||
166 | } | ||
167 | |||
168 | for (V r : isectRoots) { | ||
169 | reducedGraph.deleteNode(r); | ||
170 | } | ||
171 | |||
172 | // 3. union | ||
173 | Iterator<V> iterator = isectRoots.iterator(); | ||
174 | V newRoot = iterator.next(); | ||
175 | while (iterator.hasNext()) { | ||
176 | newRoot = sccs.union(newRoot, iterator.next()); | ||
177 | } | ||
178 | |||
179 | // 4. add new node | ||
180 | reducedGraph.insertNode(newRoot); | ||
181 | |||
182 | // 5. add edges | ||
183 | Set<V> containedNodes = sccs.getPartition(newRoot); | ||
184 | |||
185 | for (V sourceSCC : sourceSCCs) { | ||
186 | if (!containedNodes.contains(sourceSCC) && !sourceSCC.equals(newRoot)) { | ||
187 | reducedGraph.insertEdge(sourceSCC, newRoot); | ||
188 | } | ||
189 | } | ||
190 | for (V targetSCC : targetSCCs) { | ||
191 | if (!containedNodes.contains(targetSCC) && !targetSCC.equals(newRoot)) { | ||
192 | reducedGraph.insertEdge(newRoot, targetSCC); | ||
193 | } | ||
194 | } | ||
195 | } else { | ||
196 | if (observers.size() > 0 && GraphHelper.getEdgeCount(source, target, gds) == 1) { | ||
197 | counting.attachObserver(countingListener); | ||
198 | } | ||
199 | reducedGraph.insertEdge(sourceRoot, targetRoot); | ||
200 | counting.detachObserver(countingListener); | ||
201 | } | ||
202 | } else { | ||
203 | // Notifications about self-loops | ||
204 | if (observers.size() > 0 && sccs.getPartition(sourceRoot).size() == 1 | ||
205 | && GraphHelper.getEdgeCount(source, target, gds) == 1) { | ||
206 | notifyTcObservers(source, source, Direction.INSERT); | ||
207 | } | ||
208 | } | ||
209 | } | ||
210 | |||
211 | @Override | ||
212 | public void edgeDeleted(V source, V target) { | ||
213 | V sourceRoot = sccs.find(source); | ||
214 | V targetRoot = sccs.find(target); | ||
215 | |||
216 | if (!sourceRoot.equals(targetRoot)) { | ||
217 | if (observers.size() > 0 && GraphHelper.getEdgeCount(source, target, gds) == 0) { | ||
218 | counting.attachObserver(countingListener); | ||
219 | } | ||
220 | reducedGraph.deleteEdgeIfExists(sourceRoot, targetRoot); | ||
221 | counting.detachObserver(countingListener); | ||
222 | } else { | ||
223 | // get the graph for the scc whose root is sourceRoot | ||
224 | Graph<V> g = GraphHelper.getSubGraph(sccs.getPartition(sourceRoot), gds); | ||
225 | |||
226 | // if source is not reachable from target anymore | ||
227 | if (!BFS.isReachable(source, target, g)) { | ||
228 | // create copies of the current state before destructive manipulation | ||
229 | Map<V, Integer> reachableSources = CollectionsFactory.createMap(); | ||
230 | for (Entry<V, Integer> entry : reducedGraphIndexer.getSourceNodes(sourceRoot).entriesWithMultiplicities()) { | ||
231 | reachableSources.put(entry.getKey(), entry.getValue()); | ||
232 | } | ||
233 | Map<V, Integer> reachableTargets = CollectionsFactory.createMap(); | ||
234 | for (Entry<V, Integer> entry : reducedGraphIndexer.getTargetNodes(sourceRoot).entriesWithMultiplicities()) { | ||
235 | reachableTargets.put(entry.getKey(), entry.getValue()); | ||
236 | } | ||
237 | |||
238 | SCCResult<V> _newSccs = SCC.computeSCC(g); | ||
239 | |||
240 | // delete scc node (and with its edges too) | ||
241 | for (Entry<V, Integer> entry : reachableSources.entrySet()) { | ||
242 | V s = entry.getKey(); | ||
243 | for (int i = 0; i < entry.getValue(); i++) { | ||
244 | reducedGraph.deleteEdgeIfExists(s, sourceRoot); | ||
245 | } | ||
246 | } | ||
247 | |||
248 | for (Entry<V, Integer> entry : reachableTargets.entrySet()) { | ||
249 | V t = entry.getKey(); | ||
250 | for (int i = 0; i < entry.getValue(); i++) { | ||
251 | reducedGraph.deleteEdgeIfExists(sourceRoot, t); | ||
252 | } | ||
253 | } | ||
254 | |||
255 | sccs.deleteSet(sourceRoot); | ||
256 | reducedGraph.deleteNode(sourceRoot); | ||
257 | |||
258 | Set<Set<V>> newSCCs = _newSccs.getSccs(); | ||
259 | Set<V> newSCCRoots = CollectionsFactory.createSet(); | ||
260 | |||
261 | // add new nodes and edges to the reduced graph | ||
262 | for (Set<V> newSCC : newSCCs) { | ||
263 | V newRoot = sccs.makeSet(newSCC); | ||
264 | reducedGraph.insertNode(newRoot); | ||
265 | newSCCRoots.add(newRoot); | ||
266 | } | ||
267 | for (V newSCCRoot : newSCCRoots) { | ||
268 | List<V> sourceSCCsOfSCC = getSourceSCCsOfSCC(newSCCRoot); | ||
269 | List<V> targetSCCsOfSCC = getTargetSCCsOfSCC(newSCCRoot); | ||
270 | |||
271 | for (V sourceSCC : sourceSCCsOfSCC) { | ||
272 | if (!sourceSCC.equals(newSCCRoot)) { | ||
273 | reducedGraph.insertEdge(sccs.find(sourceSCC), newSCCRoot); | ||
274 | } | ||
275 | } | ||
276 | for (V targetSCC : targetSCCsOfSCC) { | ||
277 | if (!newSCCRoots.contains(targetSCC) && !targetSCC.equals(newSCCRoot)) | ||
278 | reducedGraph.insertEdge(newSCCRoot, targetSCC); | ||
279 | } | ||
280 | } | ||
281 | |||
282 | // Must be after the union-find modifications | ||
283 | if (observers.size() > 0) { | ||
284 | V newSourceRoot = sccs.find(source); | ||
285 | V newTargetRoot = sccs.find(target); | ||
286 | |||
287 | Set<V> sourceSCCs = createSetNullTolerant(counting.getAllReachableSources(newSourceRoot)); | ||
288 | sourceSCCs.add(newSourceRoot); | ||
289 | |||
290 | Set<V> targetSCCs = createSetNullTolerant(counting.getAllReachableTargets(newTargetRoot)); | ||
291 | targetSCCs.add(newTargetRoot); | ||
292 | |||
293 | for (V sourceSCC : sourceSCCs) { | ||
294 | targetLoop: for (V targetSCC : targetSCCs) { | ||
295 | if (counting.isReachable(sourceSCC, targetSCC)) continue targetLoop; | ||
296 | |||
297 | boolean needsNotification = | ||
298 | // Case 1. sourceSCC and targetSCC are the same and it is a one sized scc. | ||
299 | // Issue notifications only if there is no self-loop present at the moment | ||
300 | (sourceSCC.equals(targetSCC) && sccs.getPartition(sourceSCC).size() == 1 && GraphHelper | ||
301 | .getEdgeCount(sccs.getPartition(sourceSCC).iterator().next(), gds) == 0) | ||
302 | || | ||
303 | // Case 2. sourceSCC and targetSCC are different sccs. | ||
304 | (!sourceSCC.equals(targetSCC)); | ||
305 | // if self loop is already present omit the notification | ||
306 | if (needsNotification) { | ||
307 | notifyTcObservers(sccs.getPartition(sourceSCC), sccs.getPartition(targetSCC), | ||
308 | Direction.DELETE); | ||
309 | } | ||
310 | } | ||
311 | } | ||
312 | } | ||
313 | } else { | ||
314 | // only handle self-loop notifications - sourceRoot equals to targetRoot | ||
315 | if (observers.size() > 0 && sccs.getPartition(sourceRoot).size() == 1 | ||
316 | && GraphHelper.getEdgeCount(source, target, gds) == 0) { | ||
317 | notifyTcObservers(source, source, Direction.DELETE); | ||
318 | } | ||
319 | } | ||
320 | } | ||
321 | } | ||
322 | |||
323 | @Override | ||
324 | public void nodeInserted(V n) { | ||
325 | sccs.makeSet(n); | ||
326 | reducedGraph.insertNode(n); | ||
327 | } | ||
328 | |||
329 | @Override | ||
330 | public void nodeDeleted(V n) { | ||
331 | IMemoryView<V> sources = gds.getSourceNodes(n); | ||
332 | IMemoryView<V> targets = gds.getTargetNodes(n); | ||
333 | |||
334 | for (Entry<V, Integer> entry : sources.entriesWithMultiplicities()) { | ||
335 | for (int i = 0; i < entry.getValue(); i++) { | ||
336 | V source = entry.getKey(); | ||
337 | edgeDeleted(source, n); | ||
338 | } | ||
339 | } | ||
340 | |||
341 | for (Entry<V, Integer> entry : targets.entriesWithMultiplicities()) { | ||
342 | for (int i = 0; i < entry.getValue(); i++) { | ||
343 | V target = entry.getKey(); | ||
344 | edgeDeleted(n, target); | ||
345 | } | ||
346 | } | ||
347 | |||
348 | sccs.deleteSet(n); | ||
349 | } | ||
350 | |||
351 | @Override | ||
352 | public void attachObserver(ITcObserver<V> to) { | ||
353 | observers.add(to); | ||
354 | } | ||
355 | |||
356 | @Override | ||
357 | public void detachObserver(ITcObserver<V> to) { | ||
358 | observers.remove(to); | ||
359 | } | ||
360 | |||
361 | @Override | ||
362 | public Set<V> getAllReachableTargets(V source) { | ||
363 | V sourceRoot = sccs.find(source); | ||
364 | Set<V> containedNodes = sccs.getPartition(sourceRoot); | ||
365 | Set<V> targets = CollectionsFactory.createSet(); | ||
366 | |||
367 | if (containedNodes.size() > 1 || GraphHelper.getEdgeCount(source, gds) == 1) { | ||
368 | targets.addAll(containedNodes); | ||
369 | } | ||
370 | |||
371 | Set<V> rootSet = counting.getAllReachableTargets(sourceRoot); | ||
372 | if (rootSet != null) { | ||
373 | for (V _root : rootSet) { | ||
374 | targets.addAll(sccs.getPartition(_root)); | ||
375 | } | ||
376 | } | ||
377 | |||
378 | return targets; | ||
379 | } | ||
380 | |||
381 | @Override | ||
382 | public Set<V> getAllReachableSources(V target) { | ||
383 | V targetRoot = sccs.find(target); | ||
384 | Set<V> containedNodes = sccs.getPartition(targetRoot); | ||
385 | Set<V> sources = CollectionsFactory.createSet(); | ||
386 | |||
387 | if (containedNodes.size() > 1 || GraphHelper.getEdgeCount(target, gds) == 1) { | ||
388 | sources.addAll(containedNodes); | ||
389 | } | ||
390 | |||
391 | Set<V> rootSet = counting.getAllReachableSources(targetRoot); | ||
392 | if (rootSet != null) { | ||
393 | for (V _root : rootSet) { | ||
394 | sources.addAll(sccs.getPartition(_root)); | ||
395 | } | ||
396 | } | ||
397 | return sources; | ||
398 | } | ||
399 | |||
400 | @Override | ||
401 | public boolean isReachable(V source, V target) { | ||
402 | V sourceRoot = sccs.find(source); | ||
403 | V targetRoot = sccs.find(target); | ||
404 | |||
405 | if (sourceRoot.equals(targetRoot)) | ||
406 | return true; | ||
407 | else | ||
408 | return counting.isReachable(sourceRoot, targetRoot); | ||
409 | } | ||
410 | |||
411 | public List<V> getReachabilityPath(V source, V target) { | ||
412 | if (!isReachable(source, target)) { | ||
413 | return null; | ||
414 | } else { | ||
415 | Set<V> sccsInSubGraph = CollectionHelper.intersection(counting.getAllReachableTargets(source), | ||
416 | counting.getAllReachableSources(target)); | ||
417 | sccsInSubGraph.add(sccs.find(source)); | ||
418 | sccsInSubGraph.add(sccs.find(target)); | ||
419 | Set<V> nodesInSubGraph = CollectionsFactory.createSet(); | ||
420 | |||
421 | for (V sccRoot : sccsInSubGraph) { | ||
422 | nodesInSubGraph.addAll(sccs.getPartition(sccRoot)); | ||
423 | } | ||
424 | |||
425 | return GraphHelper.constructPath(source, target, nodesInSubGraph, gds); | ||
426 | } | ||
427 | } | ||
428 | |||
429 | /** | ||
430 | * Return the SCCs from which the SCC represented by the root node is reachable. Note that an SCC can be present | ||
431 | * multiple times in the returned list (multiple edges between the two SCCs). | ||
432 | * | ||
433 | * @param root | ||
434 | * @return the list of reachable target SCCs | ||
435 | */ | ||
436 | private List<V> getSourceSCCsOfSCC(V root) { | ||
437 | List<V> sourceSCCs = new ArrayList<V>(); | ||
438 | |||
439 | for (V containedNode : this.sccs.getPartition(root)) { | ||
440 | IMemoryView<V> sourceNodes = this.gds.getSourceNodes(containedNode); | ||
441 | for (V source : sourceNodes.distinctValues()) { | ||
442 | sourceSCCs.add(this.sccs.find(source)); | ||
443 | } | ||
444 | } | ||
445 | |||
446 | return sourceSCCs; | ||
447 | } | ||
448 | |||
449 | /** | ||
450 | * Returns true if the SCC represented by the given root node has incoming edges in the reduced graph, | ||
451 | * false otherwise (if this SCC is a source in the reduced graph). | ||
452 | * | ||
453 | * @param root the root node of an SCC | ||
454 | * @return true if it has incoming edges, false otherwise | ||
455 | * @since 1.6 | ||
456 | */ | ||
457 | public boolean hasIncomingEdges(final V root) { | ||
458 | for (final V containedNode : this.sccs.getPartition(root)) { | ||
459 | final IMemoryView<V> sourceNodes = this.gds.getSourceNodes(containedNode); | ||
460 | for (final V source : sourceNodes.distinctValues()) { | ||
461 | final V otherRoot = this.sccs.find(source); | ||
462 | if (!Objects.equals(root, otherRoot)) { | ||
463 | return true; | ||
464 | } | ||
465 | } | ||
466 | } | ||
467 | return false; | ||
468 | } | ||
469 | |||
470 | /** | ||
471 | * Return the SCCs which are reachable from the SCC represented by the root node. Note that an SCC can be present | ||
472 | * multiple times in the returned list (multiple edges between the two SCCs). | ||
473 | * | ||
474 | * @param root | ||
475 | * @return the list of reachable target SCCs | ||
476 | */ | ||
477 | private List<V> getTargetSCCsOfSCC(V root) { | ||
478 | List<V> targetSCCs = new ArrayList<V>(); | ||
479 | |||
480 | for (V containedNode : this.sccs.getPartition(root)) { | ||
481 | IMemoryView<V> targetNodes = this.gds.getTargetNodes(containedNode); | ||
482 | for (V target : targetNodes.distinctValues()) { | ||
483 | targetSCCs.add(this.sccs.find(target)); | ||
484 | } | ||
485 | } | ||
486 | |||
487 | return targetSCCs; | ||
488 | } | ||
489 | |||
490 | /** | ||
491 | * Returns true if the SCC represented by the given root node has outgoing edges in the reduced graph, | ||
492 | * false otherwise (if this SCC is a sink in the reduced graph). | ||
493 | * | ||
494 | * @param root the root node of an SCC | ||
495 | * @return true if it has outgoing edges, false otherwise | ||
496 | * @since 1.6 | ||
497 | */ | ||
498 | public boolean hasOutgoingEdges(V root) { | ||
499 | for (final V containedNode : this.sccs.getPartition(root)) { | ||
500 | final IMemoryView<V> targetNodes = this.gds.getTargetNodes(containedNode); | ||
501 | for (final V target : targetNodes.distinctValues()) { | ||
502 | final V otherRoot = this.sccs.find(target); | ||
503 | if (!Objects.equals(root, otherRoot)) { | ||
504 | return true; | ||
505 | } | ||
506 | } | ||
507 | } | ||
508 | return false; | ||
509 | } | ||
510 | |||
511 | @Override | ||
512 | public void dispose() { | ||
513 | gds.detachObserver(this); | ||
514 | counting.dispose(); | ||
515 | } | ||
516 | |||
517 | /** | ||
518 | * Call this method to notify the observers of the transitive closure relation. The tuples used in the notification | ||
519 | * will be the Descartes product of the two sets given. | ||
520 | * | ||
521 | * @param sources | ||
522 | * the source nodes | ||
523 | * @param targets | ||
524 | * the target nodes | ||
525 | * @param direction | ||
526 | */ | ||
527 | protected void notifyTcObservers(Set<V> sources, Set<V> targets, Direction direction) { | ||
528 | for (V s : sources) { | ||
529 | for (V t : targets) { | ||
530 | notifyTcObservers(s, t, direction); | ||
531 | } | ||
532 | } | ||
533 | } | ||
534 | |||
535 | private void notifyTcObservers(V source, V target, Direction direction) { | ||
536 | for (ITcObserver<V> observer : observers) { | ||
537 | if (direction == Direction.INSERT) { | ||
538 | observer.tupleInserted(source, target); | ||
539 | } | ||
540 | if (direction == Direction.DELETE) { | ||
541 | observer.tupleDeleted(source, target); | ||
542 | } | ||
543 | } | ||
544 | } | ||
545 | |||
546 | /** | ||
547 | * Returns the node that is selected as the representative of the SCC containing the argument. | ||
548 | * @since 1.6 | ||
549 | */ | ||
550 | public V getRepresentative(V node) { | ||
551 | return sccs.find(node); | ||
552 | } | ||
553 | |||
554 | public Set<Tuple<V>> getTcRelation() { | ||
555 | Set<Tuple<V>> resultSet = new HashSet<Tuple<V>>(); | ||
556 | |||
557 | for (V sourceRoot : sccs.getPartitionHeads()) { | ||
558 | Set<V> sources = sccs.getPartition(sourceRoot); | ||
559 | if (sources.size() > 1 || GraphHelper.getEdgeCount(sources.iterator().next(), gds) == 1) { | ||
560 | for (V source : sources) { | ||
561 | for (V target : sources) { | ||
562 | resultSet.add(new Tuple<V>(source, target)); | ||
563 | } | ||
564 | } | ||
565 | } | ||
566 | |||
567 | Set<V> reachableTargets = counting.getAllReachableTargets(sourceRoot); | ||
568 | if (reachableTargets != null) { | ||
569 | for (V targetRoot : reachableTargets) { | ||
570 | for (V source : sources) { | ||
571 | for (V target : sccs.getPartition(targetRoot)) { | ||
572 | resultSet.add(new Tuple<V>(source, target)); | ||
573 | } | ||
574 | } | ||
575 | } | ||
576 | } | ||
577 | } | ||
578 | |||
579 | return resultSet; | ||
580 | } | ||
581 | |||
582 | public boolean isIsolated(V node) { | ||
583 | IMemoryView<V> targets = gds.getTargetNodes(node); | ||
584 | IMemoryView<V> sources = gds.getSourceNodes(node); | ||
585 | return targets.isEmpty() && sources.isEmpty(); | ||
586 | } | ||
587 | |||
588 | @Override | ||
589 | public IGraphPathFinder<V> getPathFinder() { | ||
590 | return new DFSPathFinder<V>(gds, this); | ||
591 | } | ||
592 | |||
593 | /** | ||
594 | * The graph of SCCs; each SCC is represented by its representative node (see {@link #getRepresentative(Object)}) | ||
595 | * @since 1.6 | ||
596 | */ | ||
597 | public Graph<V> getReducedGraph() { | ||
598 | return reducedGraph; | ||
599 | } | ||
600 | |||
601 | private static <V> Set<V> createSetNullTolerant(Set<V> initial) { | ||
602 | if (initial != null) | ||
603 | return CollectionsFactory.createSet(initial); | ||
604 | else | ||
605 | return CollectionsFactory.createSet(); | ||
606 | } | ||
607 | |||
608 | |||
609 | } | ||