blob: 6b6c19ed3aca21876efddbd223f4ab0ede0d2aed (
plain) (
blame)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
|
/*
* SPDX-FileCopyrightText: 2023 The Refinery Authors <https://refinery.tools/>
*
* SPDX-License-Identifier: EPL-2.0
*/
package tools.refinery.interpreter.rete.itc.alg.representative;
import tools.refinery.interpreter.rete.itc.graphimpl.Graph;
import java.util.ArrayDeque;
import java.util.HashSet;
import java.util.Set;
public class WeaklyConnectedComponentAlgorithm<T> extends RepresentativeElectionAlgorithm<T> {
public WeaklyConnectedComponentAlgorithm(Graph<T> graph) {
super(graph);
}
@Override
protected void initializeComponents() {
for (var node : graph.getAllNodes()) {
if (representatives.containsKey(node)) {
continue;
}
var reachable = getReachableNodes(node);
initializeSet(reachable);
}
}
@Override
public void edgeInserted(T source, T target) {
var sourceRoot = getRepresentative(source);
var targetRoot = getRepresentative(target);
merge(sourceRoot, targetRoot);
}
@Override
public void edgeDeleted(T source, T target) {
var sourceRoot = getRepresentative(source);
var targetRoot = getRepresentative(target);
if (!sourceRoot.equals(targetRoot)) {
throw new IllegalArgumentException("Trying to remove edge not in graph");
}
var targetReachable = getReachableNodes(target);
if (!targetReachable.contains(source)) {
split(sourceRoot, targetReachable);
}
}
private void split(T sourceRepresentative, Set<T> targetReachable) {
var sourceComponent = getComponent(sourceRepresentative);
sourceComponent.removeAll(targetReachable);
if (targetReachable.contains(sourceRepresentative)) {
components.put(sourceRepresentative, targetReachable);
assignNewRepresentative(sourceRepresentative, sourceComponent);
} else {
assignNewRepresentative(sourceRepresentative, targetReachable);
}
}
private Set<T> getReachableNodes(T source) {
var retSet = new HashSet<T>();
retSet.add(source);
var nodeQueue = new ArrayDeque<T>();
nodeQueue.addLast(source);
while (!nodeQueue.isEmpty()) {
var node = nodeQueue.removeFirst();
for (var neighbor : graph.getTargetNodes(node).distinctValues()) {
if (!retSet.contains(neighbor)) {
retSet.add(neighbor);
nodeQueue.addLast(neighbor);
}
}
for (var neighbor : graph.getSourceNodes(node).distinctValues()) {
if (!retSet.contains(neighbor)) {
retSet.add(neighbor);
nodeQueue.addLast(neighbor);
}
}
}
return retSet;
}
}
|
