diff options
5 files changed, 223 insertions, 17 deletions
diff --git a/subprojects/store-query-viatra/src/test/java/tools/refinery/store/query/viatra/StronglyConnectedComponentsTest.java b/subprojects/store-query-viatra/src/test/java/tools/refinery/store/query/viatra/StronglyConnectedComponentsTest.java index 05ea1bbb..37795ff3 100644 --- a/subprojects/store-query-viatra/src/test/java/tools/refinery/store/query/viatra/StronglyConnectedComponentsTest.java +++ b/subprojects/store-query-viatra/src/test/java/tools/refinery/store/query/viatra/StronglyConnectedComponentsTest.java | |||
@@ -214,4 +214,48 @@ class StronglyConnectedComponentsTest { | |||
214 | assertThat(resultSet.size(), is(2)); | 214 | assertThat(resultSet.size(), is(2)); |
215 | assertThat(resultSet.get(Tuple.of(2)), is(true)); | 215 | assertThat(resultSet.get(Tuple.of(2)), is(true)); |
216 | } | 216 | } |
217 | |||
218 | @Test | ||
219 | void loopTest() { | ||
220 | var query = Query.of("SymbolViewRepresentative", (builder, p1, p2) -> builder | ||
221 | .clause(v1 -> List.of( | ||
222 | new RepresentativeElectionLiteral(Connectivity.STRONG, friendView, p1, v1), | ||
223 | new RepresentativeElectionLiteral(Connectivity.STRONG, friendView, p2, v1) | ||
224 | ))); | ||
225 | |||
226 | var store = ModelStore.builder() | ||
227 | .symbols(friend) | ||
228 | .with(ViatraModelQueryAdapter.builder() | ||
229 | .queries(query)) | ||
230 | .build(); | ||
231 | |||
232 | var model = store.createEmptyModel(); | ||
233 | var friendInterpretation = model.getInterpretation(friend); | ||
234 | var queryEngine = model.getAdapter(ModelQueryAdapter.class); | ||
235 | var resultSet = queryEngine.getResultSet(query); | ||
236 | |||
237 | friendInterpretation.put(Tuple.of(0, 1), true); | ||
238 | friendInterpretation.put(Tuple.of(1, 2), true); | ||
239 | friendInterpretation.put(Tuple.of(2, 3), true); | ||
240 | friendInterpretation.put(Tuple.of(3, 0), true); | ||
241 | friendInterpretation.put(Tuple.of(3, 4), true); | ||
242 | queryEngine.flushChanges(); | ||
243 | |||
244 | assertThat(resultSet.get(Tuple.of(0, 1)), is(true)); | ||
245 | assertThat(resultSet.get(Tuple.of(1, 2)), is(true)); | ||
246 | assertThat(resultSet.get(Tuple.of(2, 3)), is(true)); | ||
247 | assertThat(resultSet.get(Tuple.of(3, 0)), is(true)); | ||
248 | assertThat(resultSet.get(Tuple.of(3, 4)), is(false)); | ||
249 | |||
250 | friendInterpretation.put(Tuple.of(2, 3), false); | ||
251 | queryEngine.flushChanges(); | ||
252 | |||
253 | assertThat(resultSet.get(Tuple.of(0, 1)), is(false)); | ||
254 | assertThat(resultSet.get(Tuple.of(0, 2)), is(false)); | ||
255 | assertThat(resultSet.get(Tuple.of(0, 3)), is(false)); | ||
256 | assertThat(resultSet.get(Tuple.of(1, 2)), is(false)); | ||
257 | assertThat(resultSet.get(Tuple.of(2, 3)), is(false)); | ||
258 | assertThat(resultSet.get(Tuple.of(3, 0)), is(false)); | ||
259 | assertThat(resultSet.get(Tuple.of(3, 4)), is(false)); | ||
260 | } | ||
217 | } | 261 | } |
diff --git a/subprojects/store-reasoning/src/test/java/tools/refinery/store/reasoning/translator/containment/ContainmentHierarchyTranslatorTest.java b/subprojects/store-reasoning/src/test/java/tools/refinery/store/reasoning/translator/containment/ContainmentHierarchyTranslatorTest.java new file mode 100644 index 00000000..bbfaff84 --- /dev/null +++ b/subprojects/store-reasoning/src/test/java/tools/refinery/store/reasoning/translator/containment/ContainmentHierarchyTranslatorTest.java | |||
@@ -0,0 +1,128 @@ | |||
1 | /* | ||
2 | * SPDX-FileCopyrightText: 2023 The Refinery Authors <https://refinery.tools/> | ||
3 | * | ||
4 | * SPDX-License-Identifier: EPL-2.0 | ||
5 | */ | ||
6 | package tools.refinery.store.reasoning.translator.containment; | ||
7 | |||
8 | import org.junit.jupiter.api.BeforeEach; | ||
9 | import org.junit.jupiter.api.Test; | ||
10 | import tools.refinery.store.model.ModelStore; | ||
11 | import tools.refinery.store.query.viatra.ViatraModelQueryAdapter; | ||
12 | import tools.refinery.store.reasoning.ReasoningAdapter; | ||
13 | import tools.refinery.store.reasoning.ReasoningStoreAdapter; | ||
14 | import tools.refinery.store.reasoning.literal.Concreteness; | ||
15 | import tools.refinery.store.reasoning.representation.PartialRelation; | ||
16 | import tools.refinery.store.reasoning.seed.ModelSeed; | ||
17 | import tools.refinery.store.reasoning.translator.multiobject.MultiObjectTranslator; | ||
18 | import tools.refinery.store.reasoning.translator.multiplicity.UnconstrainedMultiplicity; | ||
19 | import tools.refinery.store.reasoning.translator.typehierarchy.TypeHierarchy; | ||
20 | import tools.refinery.store.reasoning.translator.typehierarchy.TypeHierarchyTranslator; | ||
21 | import tools.refinery.store.representation.TruthValue; | ||
22 | import tools.refinery.store.representation.cardinality.CardinalityIntervals; | ||
23 | import tools.refinery.store.tuple.Tuple; | ||
24 | |||
25 | import java.util.Map; | ||
26 | |||
27 | import static org.hamcrest.MatcherAssert.assertThat; | ||
28 | import static org.hamcrest.Matchers.is; | ||
29 | import static tools.refinery.store.reasoning.translator.containment.ContainmentHierarchyTranslator.CONTAINED_SYMBOL; | ||
30 | import static tools.refinery.store.reasoning.translator.containment.ContainmentHierarchyTranslator.CONTAINS_SYMBOL; | ||
31 | import static tools.refinery.store.reasoning.translator.multiobject.MultiObjectTranslator.COUNT_SYMBOL; | ||
32 | |||
33 | class ContainmentHierarchyTranslatorTest { | ||
34 | private final PartialRelation c1 = new PartialRelation("C1", 1); | ||
35 | private final PartialRelation c2 = new PartialRelation("C2", 1); | ||
36 | private final PartialRelation entry = new PartialRelation("entry", 2); | ||
37 | |||
38 | private ModelStore store; | ||
39 | |||
40 | @BeforeEach | ||
41 | void beforeEach() { | ||
42 | |||
43 | var typeHierarchy = TypeHierarchy.builder() | ||
44 | .type(CONTAINED_SYMBOL, true) | ||
45 | .type(c1) | ||
46 | .type(c2, c1, CONTAINED_SYMBOL) | ||
47 | .build(); | ||
48 | |||
49 | var containmentHierarchy = Map.of( | ||
50 | entry, | ||
51 | new ContainmentInfo(c1, UnconstrainedMultiplicity.INSTANCE, c2) | ||
52 | ); | ||
53 | |||
54 | store = ModelStore.builder() | ||
55 | .with(ViatraModelQueryAdapter.builder()) | ||
56 | .with(ReasoningAdapter.builder()) | ||
57 | .with(new MultiObjectTranslator()) | ||
58 | .with(new TypeHierarchyTranslator(typeHierarchy)) | ||
59 | .with(new ContainmentHierarchyTranslator(containmentHierarchy)) | ||
60 | .build(); | ||
61 | } | ||
62 | |||
63 | @Test | ||
64 | void treeTest() { | ||
65 | var modelSeed = ModelSeed.builder(3) | ||
66 | .seed(COUNT_SYMBOL, builder -> builder.reducedValue(CardinalityIntervals.ONE)) | ||
67 | .seed(CONTAINED_SYMBOL, builder -> builder.reducedValue(TruthValue.UNKNOWN)) | ||
68 | .seed(CONTAINS_SYMBOL, builder -> builder.reducedValue(TruthValue.UNKNOWN)) | ||
69 | .seed(c1, builder -> builder | ||
70 | .reducedValue(TruthValue.UNKNOWN) | ||
71 | .put(Tuple.of(0), TruthValue.TRUE)) | ||
72 | .seed(c2, builder -> builder | ||
73 | .put(Tuple.of(1), TruthValue.TRUE) | ||
74 | .put(Tuple.of(2), TruthValue.TRUE)) | ||
75 | .seed(entry, builder -> builder | ||
76 | .reducedValue(TruthValue.UNKNOWN) | ||
77 | .put(Tuple.of(0, 1), TruthValue.TRUE) | ||
78 | .put(Tuple.of(0, 2), TruthValue.TRUE)) | ||
79 | .build(); | ||
80 | |||
81 | var model = store.getAdapter(ReasoningStoreAdapter.class).createInitialModel(modelSeed); | ||
82 | var interpretation = model.getAdapter(ReasoningAdapter.class).getPartialInterpretation(Concreteness.PARTIAL, | ||
83 | entry); | ||
84 | |||
85 | assertThat(interpretation.get(Tuple.of(0, 0)), is(TruthValue.FALSE)); | ||
86 | assertThat(interpretation.get(Tuple.of(0, 1)), is(TruthValue.TRUE)); | ||
87 | assertThat(interpretation.get(Tuple.of(0, 2)), is(TruthValue.TRUE)); | ||
88 | assertThat(interpretation.get(Tuple.of(1, 0)), is(TruthValue.FALSE)); | ||
89 | assertThat(interpretation.get(Tuple.of(1, 1)), is(TruthValue.FALSE)); | ||
90 | assertThat(interpretation.get(Tuple.of(1, 2)), is(TruthValue.FALSE)); | ||
91 | assertThat(interpretation.get(Tuple.of(2, 0)), is(TruthValue.FALSE)); | ||
92 | assertThat(interpretation.get(Tuple.of(2, 1)), is(TruthValue.FALSE)); | ||
93 | assertThat(interpretation.get(Tuple.of(2, 2)), is(TruthValue.FALSE)); | ||
94 | } | ||
95 | |||
96 | @Test | ||
97 | void loopTest() { | ||
98 | var modelSeed = ModelSeed.builder(3) | ||
99 | .seed(COUNT_SYMBOL, builder -> builder.reducedValue(CardinalityIntervals.ONE)) | ||
100 | .seed(CONTAINED_SYMBOL, builder -> builder.reducedValue(TruthValue.UNKNOWN)) | ||
101 | .seed(CONTAINS_SYMBOL, builder -> builder.reducedValue(TruthValue.UNKNOWN)) | ||
102 | .seed(c1, builder -> builder.reducedValue(TruthValue.UNKNOWN)) | ||
103 | .seed(c2, builder -> builder | ||
104 | .put(Tuple.of(0), TruthValue.TRUE) | ||
105 | .put(Tuple.of(1), TruthValue.TRUE) | ||
106 | .put(Tuple.of(2), TruthValue.TRUE)) | ||
107 | .seed(entry, builder -> builder | ||
108 | .reducedValue(TruthValue.UNKNOWN) | ||
109 | .put(Tuple.of(0, 1), TruthValue.TRUE) | ||
110 | .put(Tuple.of(1, 2), TruthValue.TRUE) | ||
111 | .put(Tuple.of(2, 0), TruthValue.TRUE)) | ||
112 | .build(); | ||
113 | |||
114 | var model = store.getAdapter(ReasoningStoreAdapter.class).createInitialModel(modelSeed); | ||
115 | var interpretation = model.getAdapter(ReasoningAdapter.class).getPartialInterpretation(Concreteness.PARTIAL, | ||
116 | entry); | ||
117 | |||
118 | assertThat(interpretation.get(Tuple.of(0, 0)), is(TruthValue.FALSE)); | ||
119 | assertThat(interpretation.get(Tuple.of(0, 1)), is(TruthValue.ERROR)); | ||
120 | assertThat(interpretation.get(Tuple.of(0, 2)), is(TruthValue.FALSE)); | ||
121 | assertThat(interpretation.get(Tuple.of(1, 0)), is(TruthValue.FALSE)); | ||
122 | assertThat(interpretation.get(Tuple.of(1, 1)), is(TruthValue.FALSE)); | ||
123 | assertThat(interpretation.get(Tuple.of(1, 2)), is(TruthValue.ERROR)); | ||
124 | assertThat(interpretation.get(Tuple.of(2, 0)), is(TruthValue.ERROR)); | ||
125 | assertThat(interpretation.get(Tuple.of(2, 1)), is(TruthValue.FALSE)); | ||
126 | assertThat(interpretation.get(Tuple.of(2, 2)), is(TruthValue.FALSE)); | ||
127 | } | ||
128 | } | ||
diff --git a/subprojects/viatra-runtime-rete/src/main/java/tools/refinery/viatra/runtime/rete/itc/alg/misc/bfs/BFS.java b/subprojects/viatra-runtime-rete/src/main/java/tools/refinery/viatra/runtime/rete/itc/alg/misc/bfs/BFS.java index 00b0a96d..22ce8962 100644 --- a/subprojects/viatra-runtime-rete/src/main/java/tools/refinery/viatra/runtime/rete/itc/alg/misc/bfs/BFS.java +++ b/subprojects/viatra-runtime-rete/src/main/java/tools/refinery/viatra/runtime/rete/itc/alg/misc/bfs/BFS.java | |||
@@ -12,10 +12,7 @@ package tools.refinery.viatra.runtime.rete.itc.alg.misc.bfs; | |||
12 | import tools.refinery.viatra.runtime.rete.itc.igraph.IBiDirectionalGraphDataSource; | 12 | import tools.refinery.viatra.runtime.rete.itc.igraph.IBiDirectionalGraphDataSource; |
13 | import tools.refinery.viatra.runtime.rete.itc.igraph.IGraphDataSource; | 13 | import tools.refinery.viatra.runtime.rete.itc.igraph.IGraphDataSource; |
14 | 14 | ||
15 | import java.util.ArrayList; | 15 | import java.util.*; |
16 | import java.util.HashSet; | ||
17 | import java.util.List; | ||
18 | import java.util.Set; | ||
19 | 16 | ||
20 | public class BFS<V> { | 17 | public class BFS<V> { |
21 | 18 | ||
@@ -35,7 +32,7 @@ public class BFS<V> { | |||
35 | * @return true if source is reachable from target, false otherwise | 32 | * @return true if source is reachable from target, false otherwise |
36 | */ | 33 | */ |
37 | public static <V> boolean isReachable(V source, V target, IGraphDataSource<V> graph) { | 34 | public static <V> boolean isReachable(V source, V target, IGraphDataSource<V> graph) { |
38 | List<V> nodeQueue = new ArrayList<V>(); | 35 | Deque<V> nodeQueue = new ArrayDeque<V>(); |
39 | Set<V> visited = new HashSet<V>(); | 36 | Set<V> visited = new HashSet<V>(); |
40 | 37 | ||
41 | nodeQueue.add(source); | 38 | nodeQueue.add(source); |
@@ -45,17 +42,17 @@ public class BFS<V> { | |||
45 | return ret; | 42 | return ret; |
46 | } | 43 | } |
47 | 44 | ||
48 | private static <V> boolean _isReachable(V target, IGraphDataSource<V> graph, List<V> nodeQueue, Set<V> visited) { | 45 | private static <V> boolean _isReachable(V target, IGraphDataSource<V> graph, Deque<V> nodeQueue, Set<V> visited) { |
49 | 46 | ||
50 | while (!nodeQueue.isEmpty()) { | 47 | while (!nodeQueue.isEmpty()) { |
51 | V node = nodeQueue.remove(0); | 48 | V node = nodeQueue.removeFirst(); |
52 | for (V t : graph.getTargetNodes(node).distinctValues()){ | 49 | for (V t : graph.getTargetNodes(node).distinctValues()){ |
53 | if (t.equals(target)) { | 50 | if (t.equals(target)) { |
54 | return true; | 51 | return true; |
55 | } | 52 | } |
56 | if (!visited.contains(t)) { | 53 | if (!visited.contains(t)) { |
57 | visited.add(t); | 54 | visited.add(t); |
58 | nodeQueue.add(t); | 55 | nodeQueue.addLast(t); |
59 | } | 56 | } |
60 | } | 57 | } |
61 | } | 58 | } |
@@ -65,7 +62,7 @@ public class BFS<V> { | |||
65 | public static <V> Set<V> reachableSources(IBiDirectionalGraphDataSource<V> graph, V target) { | 62 | public static <V> Set<V> reachableSources(IBiDirectionalGraphDataSource<V> graph, V target) { |
66 | Set<V> retSet = new HashSet<V>(); | 63 | Set<V> retSet = new HashSet<V>(); |
67 | retSet.add(target); | 64 | retSet.add(target); |
68 | List<V> nodeQueue = new ArrayList<V>(); | 65 | Deque<V> nodeQueue = new ArrayDeque<V>(); |
69 | nodeQueue.add(target); | 66 | nodeQueue.add(target); |
70 | 67 | ||
71 | _reachableSources(graph, nodeQueue, retSet); | 68 | _reachableSources(graph, nodeQueue, retSet); |
@@ -73,14 +70,14 @@ public class BFS<V> { | |||
73 | return retSet; | 70 | return retSet; |
74 | } | 71 | } |
75 | 72 | ||
76 | private static <V> void _reachableSources(IBiDirectionalGraphDataSource<V> graph, List<V> nodeQueue, | 73 | private static <V> void _reachableSources(IBiDirectionalGraphDataSource<V> graph, Deque<V> nodeQueue, |
77 | Set<V> retSet) { | 74 | Set<V> retSet) { |
78 | while (!nodeQueue.isEmpty()) { | 75 | while (!nodeQueue.isEmpty()) { |
79 | V node = nodeQueue.remove(0); | 76 | V node = nodeQueue.removeFirst(); |
80 | for (V _node : graph.getSourceNodes(node).distinctValues()) { | 77 | for (V _node : graph.getSourceNodes(node).distinctValues()) { |
81 | if (!retSet.contains(_node)) { | 78 | if (!retSet.contains(_node)) { |
82 | retSet.add(_node); | 79 | retSet.add(_node); |
83 | nodeQueue.add(_node); | 80 | nodeQueue.addLast(_node); |
84 | } | 81 | } |
85 | } | 82 | } |
86 | } | 83 | } |
@@ -89,7 +86,7 @@ public class BFS<V> { | |||
89 | public static <V> Set<V> reachableTargets(IGraphDataSource<V> graph, V source) { | 86 | public static <V> Set<V> reachableTargets(IGraphDataSource<V> graph, V source) { |
90 | Set<V> retSet = new HashSet<V>(); | 87 | Set<V> retSet = new HashSet<V>(); |
91 | retSet.add(source); | 88 | retSet.add(source); |
92 | List<V> nodeQueue = new ArrayList<V>(); | 89 | Deque<V> nodeQueue = new ArrayDeque<V>(); |
93 | nodeQueue.add(source); | 90 | nodeQueue.add(source); |
94 | 91 | ||
95 | _reachableTargets(graph, nodeQueue, retSet); | 92 | _reachableTargets(graph, nodeQueue, retSet); |
@@ -97,15 +94,15 @@ public class BFS<V> { | |||
97 | return retSet; | 94 | return retSet; |
98 | } | 95 | } |
99 | 96 | ||
100 | private static <V> void _reachableTargets(IGraphDataSource<V> graph, List<V> nodeQueue, Set<V> retSet) { | 97 | private static <V> void _reachableTargets(IGraphDataSource<V> graph, Deque<V> nodeQueue, Set<V> retSet) { |
101 | while (!nodeQueue.isEmpty()) { | 98 | while (!nodeQueue.isEmpty()) { |
102 | V node = nodeQueue.remove(0); | 99 | V node = nodeQueue.removeFirst(); |
103 | 100 | ||
104 | for (V _node : graph.getTargetNodes(node).distinctValues()) { | 101 | for (V _node : graph.getTargetNodes(node).distinctValues()) { |
105 | 102 | ||
106 | if (!retSet.contains(_node)) { | 103 | if (!retSet.contains(_node)) { |
107 | retSet.add(_node); | 104 | retSet.add(_node); |
108 | nodeQueue.add(_node); | 105 | nodeQueue.addLast(_node); |
109 | } | 106 | } |
110 | } | 107 | } |
111 | } | 108 | } |
diff --git a/subprojects/viatra-runtime-rete/src/main/java/tools/refinery/viatra/runtime/rete/itc/alg/representative/RepresentativeElectionAlgorithm.java b/subprojects/viatra-runtime-rete/src/main/java/tools/refinery/viatra/runtime/rete/itc/alg/representative/RepresentativeElectionAlgorithm.java index 5343f956..794dabc0 100644 --- a/subprojects/viatra-runtime-rete/src/main/java/tools/refinery/viatra/runtime/rete/itc/alg/representative/RepresentativeElectionAlgorithm.java +++ b/subprojects/viatra-runtime-rete/src/main/java/tools/refinery/viatra/runtime/rete/itc/alg/representative/RepresentativeElectionAlgorithm.java | |||
@@ -45,6 +45,40 @@ public abstract class RepresentativeElectionAlgorithm implements IGraphObserver< | |||
45 | components.put(representative, set); | 45 | components.put(representative, set); |
46 | } | 46 | } |
47 | 47 | ||
48 | protected void merge(Set<Object> toMerge) { | ||
49 | if (toMerge.isEmpty()) { | ||
50 | return; | ||
51 | } | ||
52 | var representativesToMerge = new HashSet<>(); | ||
53 | Object bestRepresentative = null; | ||
54 | Set<Object> bestSet = null; | ||
55 | for (var object : toMerge) { | ||
56 | var representative = getRepresentative(object); | ||
57 | if (representativesToMerge.add(representative)) { | ||
58 | var component = getComponent(representative); | ||
59 | if (bestSet == null || bestSet.size() < component.size()) { | ||
60 | bestRepresentative = representative; | ||
61 | bestSet = component; | ||
62 | } | ||
63 | } | ||
64 | } | ||
65 | if (bestRepresentative == null) { | ||
66 | throw new AssertionError("Could not determine best representative"); | ||
67 | } | ||
68 | for (var representative : representativesToMerge) { | ||
69 | if (!bestRepresentative.equals(representative)) { | ||
70 | components.remove(representative); | ||
71 | } | ||
72 | } | ||
73 | components.put(bestRepresentative, toMerge); | ||
74 | for (var object : toMerge) { | ||
75 | var previousRepresentative = representatives.put(object, bestRepresentative); | ||
76 | if (!bestSet.contains(object)) { | ||
77 | notifyToObservers(object, previousRepresentative, bestRepresentative); | ||
78 | } | ||
79 | } | ||
80 | } | ||
81 | |||
48 | protected void merge(Object leftRepresentative, Object rightRepresentative) { | 82 | protected void merge(Object leftRepresentative, Object rightRepresentative) { |
49 | if (leftRepresentative.equals(rightRepresentative)) { | 83 | if (leftRepresentative.equals(rightRepresentative)) { |
50 | return; | 84 | return; |
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 index 4acb2b77..0463301b 100644 --- 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 | |||
@@ -35,7 +35,10 @@ public class StronglyConnectedComponentAlgorithm extends RepresentativeElectionA | |||
35 | return; | 35 | return; |
36 | } | 36 | } |
37 | if (BFS.isReachable(target, source, graph)) { | 37 | if (BFS.isReachable(target, source, graph)) { |
38 | merge(sourceRoot, targetRoot); | 38 | var sources = BFS.reachableSources(graph, target); |
39 | var targets = BFS.reachableTargets(graph, source); | ||
40 | sources.retainAll(targets); | ||
41 | merge(sources); | ||
39 | } | 42 | } |
40 | } | 43 | } |
41 | 44 | ||