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 {
                 assertThat(resultSet.size(), is(2));
                 assertThat(resultSet.get(Tuple.of(2)), is(true));
         }
+
+        @Test
+        void loopTest() {
+                var query = Query.of("SymbolViewRepresentative", (builder, p1, p2) -> builder
+                                .clause(v1 -> List.of(
+                                                new RepresentativeElectionLiteral(Connectivity.STRONG, friendView, p1, v1),
+                                                new RepresentativeElectionLiteral(Connectivity.STRONG, friendView, p2, v1)
+                                )));
+
+                var store = ModelStore.builder()
+                                .symbols(friend)
+                                .with(ViatraModelQueryAdapter.builder()
+                                                .queries(query))
+                                .build();
+
+                var model = store.createEmptyModel();
+                var friendInterpretation = model.getInterpretation(friend);
+                var queryEngine = model.getAdapter(ModelQueryAdapter.class);
+                var resultSet = queryEngine.getResultSet(query);
+
+                friendInterpretation.put(Tuple.of(0, 1), true);
+                friendInterpretation.put(Tuple.of(1, 2), true);
+                friendInterpretation.put(Tuple.of(2, 3), true);
+                friendInterpretation.put(Tuple.of(3, 0), true);
+                friendInterpretation.put(Tuple.of(3, 4), true);
+                queryEngine.flushChanges();
+
+                assertThat(resultSet.get(Tuple.of(0, 1)), is(true));
+                assertThat(resultSet.get(Tuple.of(1, 2)), is(true));
+                assertThat(resultSet.get(Tuple.of(2, 3)), is(true));
+                assertThat(resultSet.get(Tuple.of(3, 0)), is(true));
+                assertThat(resultSet.get(Tuple.of(3, 4)), is(false));
+
+                friendInterpretation.put(Tuple.of(2, 3), false);
+                queryEngine.flushChanges();
+
+                assertThat(resultSet.get(Tuple.of(0, 1)), is(false));
+                assertThat(resultSet.get(Tuple.of(0, 2)), is(false));
+                assertThat(resultSet.get(Tuple.of(0, 3)), is(false));
+                assertThat(resultSet.get(Tuple.of(1, 2)), is(false));
+                assertThat(resultSet.get(Tuple.of(2, 3)), is(false));
+                assertThat(resultSet.get(Tuple.of(3, 0)), is(false));
+                assertThat(resultSet.get(Tuple.of(3, 4)), is(false));
+        }
 }
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 @@
+/*
+ * SPDX-FileCopyrightText: 2023 The Refinery Authors <https://refinery.tools/>
+ *
+ * SPDX-License-Identifier: EPL-2.0
+ */
+package tools.refinery.store.reasoning.translator.containment;
+
+import org.junit.jupiter.api.BeforeEach;
+import org.junit.jupiter.api.Test;
+import tools.refinery.store.model.ModelStore;
+import tools.refinery.store.query.viatra.ViatraModelQueryAdapter;
+import tools.refinery.store.reasoning.ReasoningAdapter;
+import tools.refinery.store.reasoning.ReasoningStoreAdapter;
+import tools.refinery.store.reasoning.literal.Concreteness;
+import tools.refinery.store.reasoning.representation.PartialRelation;
+import tools.refinery.store.reasoning.seed.ModelSeed;
+import tools.refinery.store.reasoning.translator.multiobject.MultiObjectTranslator;
+import tools.refinery.store.reasoning.translator.multiplicity.UnconstrainedMultiplicity;
+import tools.refinery.store.reasoning.translator.typehierarchy.TypeHierarchy;
+import tools.refinery.store.reasoning.translator.typehierarchy.TypeHierarchyTranslator;
+import tools.refinery.store.representation.TruthValue;
+import tools.refinery.store.representation.cardinality.CardinalityIntervals;
+import tools.refinery.store.tuple.Tuple;
+
+import java.util.Map;
+
+import static org.hamcrest.MatcherAssert.assertThat;
+import static org.hamcrest.Matchers.is;
+import static tools.refinery.store.reasoning.translator.containment.ContainmentHierarchyTranslator.CONTAINED_SYMBOL;
+import static tools.refinery.store.reasoning.translator.containment.ContainmentHierarchyTranslator.CONTAINS_SYMBOL;
+import static tools.refinery.store.reasoning.translator.multiobject.MultiObjectTranslator.COUNT_SYMBOL;
+
+class ContainmentHierarchyTranslatorTest {
+        private final PartialRelation c1 = new PartialRelation("C1", 1);
+        private final PartialRelation c2 = new PartialRelation("C2", 1);
+        private final PartialRelation entry = new PartialRelation("entry", 2);
+
+        private ModelStore store;
+
+        @BeforeEach
+        void beforeEach() {
+
+                var typeHierarchy = TypeHierarchy.builder()
+                                .type(CONTAINED_SYMBOL, true)
+                                .type(c1)
+                                .type(c2, c1, CONTAINED_SYMBOL)
+                                .build();
+
+                var containmentHierarchy = Map.of(
+                                entry,
+                                new ContainmentInfo(c1, UnconstrainedMultiplicity.INSTANCE, c2)
+                );
+
+                store = ModelStore.builder()
+                                .with(ViatraModelQueryAdapter.builder())
+                                .with(ReasoningAdapter.builder())
+                                .with(new MultiObjectTranslator())
+                                .with(new TypeHierarchyTranslator(typeHierarchy))
+                                .with(new ContainmentHierarchyTranslator(containmentHierarchy))
+                                .build();
+        }
+
+        @Test
+        void treeTest() {
+                var modelSeed = ModelSeed.builder(3)
+                                .seed(COUNT_SYMBOL, builder -> builder.reducedValue(CardinalityIntervals.ONE))
+                                .seed(CONTAINED_SYMBOL, builder -> builder.reducedValue(TruthValue.UNKNOWN))
+                                .seed(CONTAINS_SYMBOL, builder -> builder.reducedValue(TruthValue.UNKNOWN))
+                                .seed(c1, builder -> builder
+                                                .reducedValue(TruthValue.UNKNOWN)
+                                                .put(Tuple.of(0), TruthValue.TRUE))
+                                .seed(c2, builder -> builder
+                                                .put(Tuple.of(1), TruthValue.TRUE)
+                                                .put(Tuple.of(2), TruthValue.TRUE))
+                                .seed(entry, builder -> builder
+                                                .reducedValue(TruthValue.UNKNOWN)
+                                                .put(Tuple.of(0, 1), TruthValue.TRUE)
+                                                .put(Tuple.of(0, 2), TruthValue.TRUE))
+                                .build();
+
+                var model = store.getAdapter(ReasoningStoreAdapter.class).createInitialModel(modelSeed);
+                var interpretation = model.getAdapter(ReasoningAdapter.class).getPartialInterpretation(Concreteness.PARTIAL,
+                                entry);
+
+                assertThat(interpretation.get(Tuple.of(0, 0)), is(TruthValue.FALSE));
+                assertThat(interpretation.get(Tuple.of(0, 1)), is(TruthValue.TRUE));
+                assertThat(interpretation.get(Tuple.of(0, 2)), is(TruthValue.TRUE));
+                assertThat(interpretation.get(Tuple.of(1, 0)), is(TruthValue.FALSE));
+                assertThat(interpretation.get(Tuple.of(1, 1)), is(TruthValue.FALSE));
+                assertThat(interpretation.get(Tuple.of(1, 2)), is(TruthValue.FALSE));
+                assertThat(interpretation.get(Tuple.of(2, 0)), is(TruthValue.FALSE));
+                assertThat(interpretation.get(Tuple.of(2, 1)), is(TruthValue.FALSE));
+                assertThat(interpretation.get(Tuple.of(2, 2)), is(TruthValue.FALSE));
+        }
+
+        @Test
+        void loopTest() {
+                var modelSeed = ModelSeed.builder(3)
+                                .seed(COUNT_SYMBOL, builder -> builder.reducedValue(CardinalityIntervals.ONE))
+                                .seed(CONTAINED_SYMBOL, builder -> builder.reducedValue(TruthValue.UNKNOWN))
+                                .seed(CONTAINS_SYMBOL, builder -> builder.reducedValue(TruthValue.UNKNOWN))
+                                .seed(c1, builder -> builder.reducedValue(TruthValue.UNKNOWN))
+                                .seed(c2, builder -> builder
+                                                .put(Tuple.of(0), TruthValue.TRUE)
+                                                .put(Tuple.of(1), TruthValue.TRUE)
+                                                .put(Tuple.of(2), TruthValue.TRUE))
+                                .seed(entry, builder -> builder
+                                                .reducedValue(TruthValue.UNKNOWN)
+                                                .put(Tuple.of(0, 1), TruthValue.TRUE)
+                                                .put(Tuple.of(1, 2), TruthValue.TRUE)
+                                                .put(Tuple.of(2, 0), TruthValue.TRUE))
+                                .build();
+
+                var model = store.getAdapter(ReasoningStoreAdapter.class).createInitialModel(modelSeed);
+                var interpretation = model.getAdapter(ReasoningAdapter.class).getPartialInterpretation(Concreteness.PARTIAL,
+                                entry);
+
+                assertThat(interpretation.get(Tuple.of(0, 0)), is(TruthValue.FALSE));
+                assertThat(interpretation.get(Tuple.of(0, 1)), is(TruthValue.ERROR));
+                assertThat(interpretation.get(Tuple.of(0, 2)), is(TruthValue.FALSE));
+                assertThat(interpretation.get(Tuple.of(1, 0)), is(TruthValue.FALSE));
+                assertThat(interpretation.get(Tuple.of(1, 1)), is(TruthValue.FALSE));
+                assertThat(interpretation.get(Tuple.of(1, 2)), is(TruthValue.ERROR));
+                assertThat(interpretation.get(Tuple.of(2, 0)), is(TruthValue.ERROR));
+                assertThat(interpretation.get(Tuple.of(2, 1)), is(TruthValue.FALSE));
+                assertThat(interpretation.get(Tuple.of(2, 2)), is(TruthValue.FALSE));
+        }
+}
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;
 import tools.refinery.viatra.runtime.rete.itc.igraph.IBiDirectionalGraphDataSource;
 import tools.refinery.viatra.runtime.rete.itc.igraph.IGraphDataSource;
 
-import java.util.ArrayList;
-import java.util.HashSet;
-import java.util.List;
-import java.util.Set;
+import java.util.*;
 
 public class BFS<V> {
 
@@ -35,7 +32,7 @@ public class BFS<V> {
      * @return true if source is reachable from target, false otherwise
      */
     public static <V> boolean isReachable(V source, V target, IGraphDataSource<V> graph) {
-        List<V> nodeQueue = new ArrayList<V>();
+        Deque<V> nodeQueue = new ArrayDeque<V>();
         Set<V> visited = new HashSet<V>();
 
         nodeQueue.add(source);
@@ -45,17 +42,17 @@ public class BFS<V> {
         return ret;
     }
 
-    private static <V> boolean _isReachable(V target, IGraphDataSource<V> graph, List<V> nodeQueue, Set<V> visited) {
+    private static <V> boolean _isReachable(V target, IGraphDataSource<V> graph, Deque<V> nodeQueue, Set<V> visited) {
 
         while (!nodeQueue.isEmpty()) {
-            V node = nodeQueue.remove(0);
+            V node = nodeQueue.removeFirst();
             for (V t : graph.getTargetNodes(node).distinctValues()){
                 if (t.equals(target)) {
                     return true;
                 }
                 if (!visited.contains(t)) {
                     visited.add(t);
-                    nodeQueue.add(t);
+                    nodeQueue.addLast(t);
                 }
             }
         }
@@ -65,7 +62,7 @@ public class BFS<V> {
     public static <V> Set<V> reachableSources(IBiDirectionalGraphDataSource<V> graph, V target) {
         Set<V> retSet = new HashSet<V>();
         retSet.add(target);
-        List<V> nodeQueue = new ArrayList<V>();
+        Deque<V> nodeQueue = new ArrayDeque<V>();
         nodeQueue.add(target);
 
         _reachableSources(graph, nodeQueue, retSet);
@@ -73,14 +70,14 @@ public class BFS<V> {
         return retSet;
     }
 
-    private static <V> void _reachableSources(IBiDirectionalGraphDataSource<V> graph, List<V> nodeQueue,
+    private static <V> void _reachableSources(IBiDirectionalGraphDataSource<V> graph, Deque<V> nodeQueue,
             Set<V> retSet) {
         while (!nodeQueue.isEmpty()) {
-            V node = nodeQueue.remove(0);
+            V node = nodeQueue.removeFirst();
             for (V _node : graph.getSourceNodes(node).distinctValues()) {
                 if (!retSet.contains(_node)) {
                     retSet.add(_node);
-                    nodeQueue.add(_node);
+                    nodeQueue.addLast(_node);
                 }
             }
         }
@@ -89,7 +86,7 @@ public class BFS<V> {
     public static <V> Set<V> reachableTargets(IGraphDataSource<V> graph, V source) {
         Set<V> retSet = new HashSet<V>();
         retSet.add(source);
-        List<V> nodeQueue = new ArrayList<V>();
+        Deque<V> nodeQueue = new ArrayDeque<V>();
         nodeQueue.add(source);
 
         _reachableTargets(graph, nodeQueue, retSet);
@@ -97,15 +94,15 @@ public class BFS<V> {
         return retSet;
     }
 
-    private static <V> void _reachableTargets(IGraphDataSource<V> graph, List<V> nodeQueue, Set<V> retSet) {
+    private static <V> void _reachableTargets(IGraphDataSource<V> graph, Deque<V> nodeQueue, Set<V> retSet) {
         while (!nodeQueue.isEmpty()) {
-            V node = nodeQueue.remove(0);
+            V node = nodeQueue.removeFirst();
 
             for (V _node : graph.getTargetNodes(node).distinctValues()) {
 
                 if (!retSet.contains(_node)) {
                     retSet.add(_node);
-                    nodeQueue.add(_node);
+                    nodeQueue.addLast(_node);
                 }
             }
         }
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<
                 components.put(representative, set);
         }
 
+        protected void merge(Set<Object> toMerge) {
+                if (toMerge.isEmpty()) {
+                        return;
+                }
+                var representativesToMerge = new HashSet<>();
+                Object bestRepresentative = null;
+                Set<Object> bestSet = null;
+                for (var object : toMerge) {
+                        var representative = getRepresentative(object);
+                        if (representativesToMerge.add(representative)) {
+                                var component = getComponent(representative);
+                                if (bestSet == null || bestSet.size() < component.size()) {
+                                        bestRepresentative = representative;
+                                        bestSet = component;
+                                }
+                        }
+                }
+                if (bestRepresentative == null) {
+                        throw new AssertionError("Could not determine best representative");
+                }
+                for (var representative : representativesToMerge) {
+                        if (!bestRepresentative.equals(representative)) {
+                                components.remove(representative);
+                        }
+                }
+                components.put(bestRepresentative, toMerge);
+                for (var object : toMerge) {
+                        var previousRepresentative = representatives.put(object, bestRepresentative);
+                        if (!bestSet.contains(object)) {
+                                notifyToObservers(object, previousRepresentative, bestRepresentative);
+                        }
+                }
+        }
+
         protected void merge(Object leftRepresentative, Object rightRepresentative) {
                 if (leftRepresentative.equals(rightRepresentative)) {
                         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
                         return;
                 }
                 if (BFS.isReachable(target, source, graph)) {
-                        merge(sourceRoot, targetRoot);
+                        var sources = BFS.reachableSources(graph, target);
+                        var targets = BFS.reachableTargets(graph, source);
+                        sources.retainAll(targets);
+                        merge(sources);
                 }
         }