diff options
Diffstat (limited to 'subprojects/viatra-runtime-rete/src/main/java/tools/refinery/viatra/runtime/rete/itc/alg/representative/StronglyConnectedComponentAlgorithm.java')
-rw-r--r-- | subprojects/viatra-runtime-rete/src/main/java/tools/refinery/viatra/runtime/rete/itc/alg/representative/StronglyConnectedComponentAlgorithm.java | 69 |
1 files changed, 69 insertions, 0 deletions
diff --git a/subprojects/viatra-runtime-rete/src/main/java/tools/refinery/viatra/runtime/rete/itc/alg/representative/StronglyConnectedComponentAlgorithm.java b/subprojects/viatra-runtime-rete/src/main/java/tools/refinery/viatra/runtime/rete/itc/alg/representative/StronglyConnectedComponentAlgorithm.java new file mode 100644 index 00000000..0463301b --- /dev/null +++ b/subprojects/viatra-runtime-rete/src/main/java/tools/refinery/viatra/runtime/rete/itc/alg/representative/StronglyConnectedComponentAlgorithm.java | |||
@@ -0,0 +1,69 @@ | |||
1 | /* | ||
2 | * SPDX-FileCopyrightText: 2023 The Refinery Authors <https://refinery.tools/> | ||
3 | * | ||
4 | * SPDX-License-Identifier: EPL-2.0 | ||
5 | */ | ||
6 | package tools.refinery.viatra.runtime.rete.itc.alg.representative; | ||
7 | |||
8 | import tools.refinery.viatra.runtime.rete.itc.alg.misc.GraphHelper; | ||
9 | import tools.refinery.viatra.runtime.rete.itc.alg.misc.bfs.BFS; | ||
10 | import tools.refinery.viatra.runtime.rete.itc.alg.misc.scc.SCC; | ||
11 | import tools.refinery.viatra.runtime.rete.itc.graphimpl.Graph; | ||
12 | |||
13 | import java.util.Collection; | ||
14 | import java.util.Set; | ||
15 | |||
16 | public class StronglyConnectedComponentAlgorithm extends RepresentativeElectionAlgorithm { | ||
17 | public StronglyConnectedComponentAlgorithm(Graph<Object> graph) { | ||
18 | super(graph); | ||
19 | } | ||
20 | |||
21 | @Override | ||
22 | protected void initializeComponents() { | ||
23 | var computedSCCs = SCC.computeSCC(graph).getSccs(); | ||
24 | for (var computedSCC : computedSCCs) { | ||
25 | initializeSet(computedSCC); | ||
26 | } | ||
27 | } | ||
28 | |||
29 | @Override | ||
30 | public void edgeInserted(Object source, Object target) { | ||
31 | var sourceRoot = getRepresentative(source); | ||
32 | var targetRoot = getRepresentative(target); | ||
33 | if (sourceRoot.equals(targetRoot)) { | ||
34 | // New edge does not change strongly connected components. | ||
35 | return; | ||
36 | } | ||
37 | if (BFS.isReachable(target, source, graph)) { | ||
38 | var sources = BFS.reachableSources(graph, target); | ||
39 | var targets = BFS.reachableTargets(graph, source); | ||
40 | sources.retainAll(targets); | ||
41 | merge(sources); | ||
42 | } | ||
43 | } | ||
44 | |||
45 | @Override | ||
46 | public void edgeDeleted(Object source, Object target) { | ||
47 | var sourceRoot = getRepresentative(source); | ||
48 | var targetRoot = getRepresentative(target); | ||
49 | if (!sourceRoot.equals(targetRoot)) { | ||
50 | // New edge does not change strongly connected components. | ||
51 | return; | ||
52 | } | ||
53 | var component = GraphHelper.getSubGraph(getComponent(sourceRoot), graph); | ||
54 | if (!BFS.isReachable(source, target, component)) { | ||
55 | var newSCCs = SCC.computeSCC(component).getSccs(); | ||
56 | split(sourceRoot, newSCCs); | ||
57 | } | ||
58 | } | ||
59 | |||
60 | private void split(Object preservedRepresentative, Collection<? extends Set<Object>> sets) { | ||
61 | for (var set : sets) { | ||
62 | if (set.contains(preservedRepresentative)) { | ||
63 | components.put(preservedRepresentative, set); | ||
64 | } else { | ||
65 | assignNewRepresentative(preservedRepresentative, set); | ||
66 | } | ||
67 | } | ||
68 | } | ||
69 | } | ||