diff options
Diffstat (limited to 'subprojects/viatra-runtime-base-itc/src/main/java/tools/refinery/viatra/runtime/base/itc/alg/representative/RepresentativeElectionAlgorithm.java')
-rw-r--r-- | subprojects/viatra-runtime-base-itc/src/main/java/tools/refinery/viatra/runtime/base/itc/alg/representative/RepresentativeElectionAlgorithm.java | 140 |
1 files changed, 140 insertions, 0 deletions
diff --git a/subprojects/viatra-runtime-base-itc/src/main/java/tools/refinery/viatra/runtime/base/itc/alg/representative/RepresentativeElectionAlgorithm.java b/subprojects/viatra-runtime-base-itc/src/main/java/tools/refinery/viatra/runtime/base/itc/alg/representative/RepresentativeElectionAlgorithm.java new file mode 100644 index 00000000..51015404 --- /dev/null +++ b/subprojects/viatra-runtime-base-itc/src/main/java/tools/refinery/viatra/runtime/base/itc/alg/representative/RepresentativeElectionAlgorithm.java | |||
@@ -0,0 +1,140 @@ | |||
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.base.itc.alg.representative; | ||
7 | |||
8 | import tools.refinery.viatra.runtime.base.itc.graphimpl.Graph; | ||
9 | import tools.refinery.viatra.runtime.base.itc.igraph.IGraphObserver; | ||
10 | import tools.refinery.viatra.runtime.matchers.util.Direction; | ||
11 | |||
12 | import java.util.HashMap; | ||
13 | import java.util.HashSet; | ||
14 | import java.util.Map; | ||
15 | import java.util.Set; | ||
16 | |||
17 | public abstract class RepresentativeElectionAlgorithm implements IGraphObserver<Object> { | ||
18 | protected final Graph<Object> graph; | ||
19 | protected final Map<Object, Object> representatives = new HashMap<>(); | ||
20 | protected final Map<Object, Set<Object>> components = new HashMap<>(); | ||
21 | private RepresentativeObserver observer; | ||
22 | |||
23 | protected RepresentativeElectionAlgorithm(Graph<Object> graph) { | ||
24 | this.graph = graph; | ||
25 | initializeComponents(); | ||
26 | graph.attachObserver(this); | ||
27 | } | ||
28 | |||
29 | protected abstract void initializeComponents(); | ||
30 | |||
31 | protected void initializeSet(Set<Object> set) { | ||
32 | var iterator = set.iterator(); | ||
33 | if (!iterator.hasNext()) { | ||
34 | // Set is empty. | ||
35 | return; | ||
36 | } | ||
37 | var representative = iterator.next(); | ||
38 | for (var node : set) { | ||
39 | var oldRepresentative = representatives.put(node, representative); | ||
40 | if (oldRepresentative != null && !representative.equals(oldRepresentative)) { | ||
41 | throw new IllegalStateException("Node %s is already in a set represented by %s, cannot add it to %s" | ||
42 | .formatted(node, oldRepresentative, set)); | ||
43 | } | ||
44 | } | ||
45 | components.put(representative, set); | ||
46 | } | ||
47 | |||
48 | protected void merge(Object leftRepresentative, Object rightRepresentative) { | ||
49 | if (leftRepresentative.equals(rightRepresentative)) { | ||
50 | return; | ||
51 | } | ||
52 | var leftSet = getComponent(leftRepresentative); | ||
53 | var rightSet = getComponent(rightRepresentative); | ||
54 | if (leftSet.size() < rightSet.size()) { | ||
55 | merge(rightRepresentative, rightSet, leftRepresentative, leftSet); | ||
56 | } else { | ||
57 | merge(leftRepresentative, leftSet, rightRepresentative, rightSet); | ||
58 | } | ||
59 | } | ||
60 | |||
61 | private void merge(Object preservedRepresentative, Set<Object> preservedSet, Object removedRepresentative, | ||
62 | Set<Object> removedSet) { | ||
63 | components.remove(removedRepresentative); | ||
64 | for (var node : removedSet) { | ||
65 | representatives.put(node, preservedRepresentative); | ||
66 | preservedSet.add(node); | ||
67 | notifyToObservers(node, removedRepresentative, preservedRepresentative); | ||
68 | } | ||
69 | } | ||
70 | |||
71 | protected void assignNewRepresentative(Object oldRepresentative, Set<Object> set) { | ||
72 | var iterator = set.iterator(); | ||
73 | if (!iterator.hasNext()) { | ||
74 | return; | ||
75 | } | ||
76 | var newRepresentative = iterator.next(); | ||
77 | components.put(newRepresentative, set); | ||
78 | for (var node : set) { | ||
79 | var oldRepresentativeOfNode = representatives.put(node, newRepresentative); | ||
80 | if (!oldRepresentative.equals(oldRepresentativeOfNode)) { | ||
81 | throw new IllegalArgumentException("Node %s was not represented by %s but by %s" | ||
82 | .formatted(node, oldRepresentative, oldRepresentativeOfNode)); | ||
83 | } | ||
84 | notifyToObservers(node, oldRepresentative, newRepresentative); | ||
85 | } | ||
86 | } | ||
87 | |||
88 | public void setObserver(RepresentativeObserver observer) { | ||
89 | this.observer = observer; | ||
90 | } | ||
91 | |||
92 | public Map<Object, Set<Object>> getComponents() { | ||
93 | return components; | ||
94 | } | ||
95 | |||
96 | public Object getRepresentative(Object node) { | ||
97 | return representatives.get(node); | ||
98 | } | ||
99 | |||
100 | public Set<Object> getComponent(Object representative) { | ||
101 | return components.get(representative); | ||
102 | } | ||
103 | |||
104 | public void dispose() { | ||
105 | graph.detachObserver(this); | ||
106 | } | ||
107 | |||
108 | @Override | ||
109 | public void nodeInserted(Object n) { | ||
110 | var component = new HashSet<>(1); | ||
111 | component.add(n); | ||
112 | initializeSet(component); | ||
113 | notifyToObservers(n, n, Direction.INSERT); | ||
114 | } | ||
115 | |||
116 | @Override | ||
117 | public void nodeDeleted(Object n) { | ||
118 | var representative = representatives.remove(n); | ||
119 | if (!representative.equals(n)) { | ||
120 | throw new IllegalStateException("Trying to delete node with dangling edges"); | ||
121 | } | ||
122 | components.remove(representative); | ||
123 | notifyToObservers(n, representative, Direction.DELETE); | ||
124 | } | ||
125 | |||
126 | protected void notifyToObservers(Object node, Object oldRepresentative, Object newRepresentative) { | ||
127 | notifyToObservers(node, oldRepresentative, Direction.DELETE); | ||
128 | notifyToObservers(node, newRepresentative, Direction.INSERT); | ||
129 | } | ||
130 | |||
131 | protected void notifyToObservers(Object node, Object representative, Direction direction) { | ||
132 | if (observer != null) { | ||
133 | observer.tupleChanged(node, representative, direction); | ||
134 | } | ||
135 | } | ||
136 | |||
137 | public interface Factory { | ||
138 | RepresentativeElectionAlgorithm create(Graph<Object> graph); | ||
139 | } | ||
140 | } | ||