From cca3b176cea8df8823094c105f612844b649647e Mon Sep 17 00:00:00 2001 From: Kristóf Marussy Date: Sun, 27 Aug 2023 02:13:15 +0200 Subject: fix: strong represenative election algorithm Make sure to merge all clusters reachable from source and target. --- .../viatra/runtime/rete/itc/alg/misc/bfs/BFS.java | 29 +++++++++--------- .../RepresentativeElectionAlgorithm.java | 34 ++++++++++++++++++++++ .../StronglyConnectedComponentAlgorithm.java | 5 +++- 3 files changed, 51 insertions(+), 17 deletions(-) (limited to 'subprojects/viatra-runtime-rete') 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 { @@ -35,7 +32,7 @@ public class BFS { * @return true if source is reachable from target, false otherwise */ public static boolean isReachable(V source, V target, IGraphDataSource graph) { - List nodeQueue = new ArrayList(); + Deque nodeQueue = new ArrayDeque(); Set visited = new HashSet(); nodeQueue.add(source); @@ -45,17 +42,17 @@ public class BFS { return ret; } - private static boolean _isReachable(V target, IGraphDataSource graph, List nodeQueue, Set visited) { + private static boolean _isReachable(V target, IGraphDataSource graph, Deque nodeQueue, Set 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 { public static Set reachableSources(IBiDirectionalGraphDataSource graph, V target) { Set retSet = new HashSet(); retSet.add(target); - List nodeQueue = new ArrayList(); + Deque nodeQueue = new ArrayDeque(); nodeQueue.add(target); _reachableSources(graph, nodeQueue, retSet); @@ -73,14 +70,14 @@ public class BFS { return retSet; } - private static void _reachableSources(IBiDirectionalGraphDataSource graph, List nodeQueue, + private static void _reachableSources(IBiDirectionalGraphDataSource graph, Deque nodeQueue, Set 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 { public static Set reachableTargets(IGraphDataSource graph, V source) { Set retSet = new HashSet(); retSet.add(source); - List nodeQueue = new ArrayList(); + Deque nodeQueue = new ArrayDeque(); nodeQueue.add(source); _reachableTargets(graph, nodeQueue, retSet); @@ -97,15 +94,15 @@ public class BFS { return retSet; } - private static void _reachableTargets(IGraphDataSource graph, List nodeQueue, Set retSet) { + private static void _reachableTargets(IGraphDataSource graph, Deque nodeQueue, Set 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 toMerge) { + if (toMerge.isEmpty()) { + return; + } + var representativesToMerge = new HashSet<>(); + Object bestRepresentative = null; + Set 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); } } -- cgit v1.2.3-70-g09d2