diff options
Diffstat (limited to 'subprojects/viatra-runtime-matchers/src/main/java/tools/refinery/viatra/runtime/matchers/algorithms/UnionFind.java')
-rw-r--r-- | subprojects/viatra-runtime-matchers/src/main/java/tools/refinery/viatra/runtime/matchers/algorithms/UnionFind.java | 214 |
1 files changed, 214 insertions, 0 deletions
diff --git a/subprojects/viatra-runtime-matchers/src/main/java/tools/refinery/viatra/runtime/matchers/algorithms/UnionFind.java b/subprojects/viatra-runtime-matchers/src/main/java/tools/refinery/viatra/runtime/matchers/algorithms/UnionFind.java new file mode 100644 index 00000000..c69f08e5 --- /dev/null +++ b/subprojects/viatra-runtime-matchers/src/main/java/tools/refinery/viatra/runtime/matchers/algorithms/UnionFind.java | |||
@@ -0,0 +1,214 @@ | |||
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.matchers.algorithms; | ||
11 | |||
12 | import java.util.Collection; | ||
13 | import java.util.HashSet; | ||
14 | import java.util.Iterator; | ||
15 | import java.util.Map; | ||
16 | import java.util.Set; | ||
17 | |||
18 | import tools.refinery.viatra.runtime.matchers.util.CollectionsFactory; | ||
19 | |||
20 | /** | ||
21 | * Union-find data structure implementation. Note that the implementation relies on the correct implementation of the | ||
22 | * equals method of the type parameter's class. | ||
23 | * | ||
24 | * @author Tamas Szabo | ||
25 | * | ||
26 | * @param <V> | ||
27 | * the type parameter of the element's stored in the union-find data structure | ||
28 | */ | ||
29 | public class UnionFind<V> { | ||
30 | |||
31 | private final Map<V, UnionFindNodeProperty<V>> nodeMap; | ||
32 | final Map<V, Set<V>> setMap; | ||
33 | |||
34 | /** | ||
35 | * Instantiate a new union-find data structure. | ||
36 | */ | ||
37 | public UnionFind() { | ||
38 | nodeMap = CollectionsFactory.createMap(); | ||
39 | setMap = CollectionsFactory.createMap(); | ||
40 | } | ||
41 | |||
42 | /** | ||
43 | * Instantiate a new union-find data structure with the given elements as separate sets. | ||
44 | */ | ||
45 | public UnionFind(Iterable<V> elements) { | ||
46 | this(); | ||
47 | for (V element : elements) { | ||
48 | makeSet(element); | ||
49 | } | ||
50 | } | ||
51 | |||
52 | /** | ||
53 | * Creates a new union set from a collection of elements. | ||
54 | * | ||
55 | * @param nodes | ||
56 | * the collection of elements | ||
57 | * @return the root element | ||
58 | */ | ||
59 | public V makeSet(Collection<V> nodes) { | ||
60 | if (!nodes.isEmpty()) { | ||
61 | Iterator<V> iterator = nodes.iterator(); | ||
62 | V root = makeSet(iterator.next()); | ||
63 | while (iterator.hasNext()) { | ||
64 | root = union(root, iterator.next()); | ||
65 | } | ||
66 | return root; | ||
67 | } else { | ||
68 | return null; | ||
69 | } | ||
70 | } | ||
71 | |||
72 | /** | ||
73 | * This method creates a single set containing the given node. | ||
74 | * | ||
75 | * @param node | ||
76 | * the root node of the set | ||
77 | * @return the root element | ||
78 | */ | ||
79 | public V makeSet(V node) { | ||
80 | if (!nodeMap.containsKey(node)) { | ||
81 | UnionFindNodeProperty<V> prop = new UnionFindNodeProperty<V>(0, node); | ||
82 | nodeMap.put(node, prop); | ||
83 | Set<V> set = new HashSet<V>(); | ||
84 | set.add(node); | ||
85 | setMap.put(node, set); | ||
86 | } | ||
87 | return node; | ||
88 | } | ||
89 | |||
90 | /** | ||
91 | * Find method with path compression. | ||
92 | * | ||
93 | * @param node | ||
94 | * the node to find | ||
95 | * @return the root node of the set in which the given node can be found | ||
96 | */ | ||
97 | public V find(V node) { | ||
98 | UnionFindNodeProperty<V> prop = nodeMap.get(node); | ||
99 | |||
100 | if (prop != null) { | ||
101 | if (prop.parent.equals(node)) { | ||
102 | return node; | ||
103 | } else { | ||
104 | prop.parent = find(prop.parent); | ||
105 | return prop.parent; | ||
106 | } | ||
107 | } | ||
108 | return null; | ||
109 | } | ||
110 | |||
111 | /** | ||
112 | * Union by rank implementation of the two sets which contain x and y; x and/or y can be a single element from the | ||
113 | * universe. | ||
114 | * | ||
115 | * @param x | ||
116 | * set or single element of the universe | ||
117 | * @param y | ||
118 | * set or single element of the universe | ||
119 | * @return the new root of the two sets | ||
120 | */ | ||
121 | public V union(V x, V y) { | ||
122 | V xRoot = find(x); | ||
123 | V yRoot = find(y); | ||
124 | |||
125 | if ((xRoot == null) || (yRoot == null)) { | ||
126 | return union( (xRoot == null) ? makeSet(x) : xRoot, (yRoot == null) ? makeSet(y) : yRoot); | ||
127 | } | ||
128 | else if (!xRoot.equals(yRoot)) { | ||
129 | UnionFindNodeProperty<V> xRootProp = nodeMap.get(xRoot); | ||
130 | UnionFindNodeProperty<V> yRootProp = nodeMap.get(yRoot); | ||
131 | |||
132 | if (xRootProp.rank < yRootProp.rank) { | ||
133 | xRootProp.parent = yRoot; | ||
134 | setMap.get(yRoot).addAll(setMap.get(xRoot)); | ||
135 | setMap.remove(xRoot); | ||
136 | return yRoot; | ||
137 | } else {// (xRootProp.rank >= yRootProp.rank) | ||
138 | yRootProp.parent = xRoot; | ||
139 | yRootProp.rank = (xRootProp.rank == yRootProp.rank) ? yRootProp.rank + 1 : yRootProp.rank; | ||
140 | setMap.get(xRoot).addAll(setMap.get(yRoot)); | ||
141 | setMap.remove(yRoot); | ||
142 | return xRoot; | ||
143 | } | ||
144 | } else { | ||
145 | return xRoot; | ||
146 | } | ||
147 | } | ||
148 | |||
149 | /** | ||
150 | * Places the given elements in to the same partition. | ||
151 | */ | ||
152 | public void unite(Set<V> elements) { | ||
153 | if (elements.size() > 1) { | ||
154 | V current = null; | ||
155 | for (V element : elements) { | ||
156 | if (current != null) { | ||
157 | if (getPartition(element) != null) { | ||
158 | union(current, element); | ||
159 | } | ||
160 | } else { | ||
161 | if (getPartition(element) != null) { | ||
162 | current = element; | ||
163 | } | ||
164 | } | ||
165 | } | ||
166 | } | ||
167 | } | ||
168 | |||
169 | /** | ||
170 | * Delete the set whose root is the given node. | ||
171 | * | ||
172 | * @param root | ||
173 | * the root node | ||
174 | */ | ||
175 | public void deleteSet(V root) { | ||
176 | // if (setMap.containsKey(root)) | ||
177 | for (V n : setMap.get(root)) { | ||
178 | nodeMap.remove(n); | ||
179 | } | ||
180 | setMap.remove(root); | ||
181 | } | ||
182 | |||
183 | /** | ||
184 | * Returns if all given elements are in the same partition. | ||
185 | */ | ||
186 | public boolean isSameUnion(Set<V> elements) { | ||
187 | for (Set<V> partition : setMap.values()) { | ||
188 | if (partition.containsAll(elements)) { | ||
189 | return true; | ||
190 | } | ||
191 | } | ||
192 | return false; | ||
193 | } | ||
194 | |||
195 | |||
196 | /** | ||
197 | * Returns the partition in which the given element can be found, or null otherwise. | ||
198 | */ | ||
199 | public Set<V> getPartition(V element) { | ||
200 | V root = find(element); | ||
201 | return setMap.get(root); | ||
202 | } | ||
203 | |||
204 | /** | ||
205 | * Returns all partitions. | ||
206 | */ | ||
207 | public Collection<Set<V>> getPartitions() { | ||
208 | return setMap.values(); | ||
209 | } | ||
210 | |||
211 | public Set<V> getPartitionHeads() { | ||
212 | return setMap.keySet(); | ||
213 | } | ||
214 | } | ||