diff options
author | Kristóf Marussy <kristof@marussy.com> | 2023-08-31 17:36:36 +0200 |
---|---|---|
committer | Kristóf Marussy <kristof@marussy.com> | 2023-08-31 17:41:55 +0200 |
commit | d43046735ec9b1dd2b93aba4182cc8b94ee80f1c (patch) | |
tree | 74493177cc39198e0f0b25a06a3d7b13ebcae48c /subprojects/viatra-runtime-rete | |
parent | chore(deps): bump dependencies (diff) | |
download | refinery-d43046735ec9b1dd2b93aba4182cc8b94ee80f1c.tar.gz refinery-d43046735ec9b1dd2b93aba4182cc8b94ee80f1c.tar.zst refinery-d43046735ec9b1dd2b93aba4182cc8b94ee80f1c.zip |
refactor(viatra): replace Stack with Deque
Diffstat (limited to 'subprojects/viatra-runtime-rete')
2 files changed, 16 insertions, 19 deletions
diff --git a/subprojects/viatra-runtime-rete/src/main/java/tools/refinery/viatra/runtime/rete/itc/alg/misc/scc/SCC.java b/subprojects/viatra-runtime-rete/src/main/java/tools/refinery/viatra/runtime/rete/itc/alg/misc/scc/SCC.java index f6ef9847..de070839 100644 --- a/subprojects/viatra-runtime-rete/src/main/java/tools/refinery/viatra/runtime/rete/itc/alg/misc/scc/SCC.java +++ b/subprojects/viatra-runtime-rete/src/main/java/tools/refinery/viatra/runtime/rete/itc/alg/misc/scc/SCC.java | |||
@@ -9,13 +9,10 @@ | |||
9 | 9 | ||
10 | package tools.refinery.viatra.runtime.rete.itc.alg.misc.scc; | 10 | package tools.refinery.viatra.runtime.rete.itc.alg.misc.scc; |
11 | 11 | ||
12 | import java.util.HashSet; | ||
13 | import java.util.Map; | ||
14 | import java.util.Set; | ||
15 | import java.util.Stack; | ||
16 | |||
17 | import tools.refinery.viatra.runtime.rete.itc.igraph.IGraphDataSource; | ||
18 | import tools.refinery.viatra.runtime.matchers.util.CollectionsFactory; | 12 | import tools.refinery.viatra.runtime.matchers.util.CollectionsFactory; |
13 | import tools.refinery.viatra.runtime.rete.itc.igraph.IGraphDataSource; | ||
14 | |||
15 | import java.util.*; | ||
19 | 16 | ||
20 | /** | 17 | /** |
21 | * Efficient algorithms to compute the Strongly Connected Components in a directed graph. | 18 | * Efficient algorithms to compute the Strongly Connected Components in a directed graph. |
@@ -52,10 +49,10 @@ public class SCC<V> { | |||
52 | Map<V, Set<V>> notVisitedMap = CollectionsFactory.createMap(); | 49 | Map<V, Set<V>> notVisitedMap = CollectionsFactory.createMap(); |
53 | 50 | ||
54 | // stores the nodes during the traversal | 51 | // stores the nodes during the traversal |
55 | Stack<V> nodeStack = new Stack<V>(); | 52 | Deque<V> nodeStack = new ArrayDeque<V>(); |
56 | 53 | ||
57 | // stores the nodes which belong to an scc (there can be many sccs in the stack at the same time) | 54 | // stores the nodes which belong to an scc (there can be many sccs in the stack at the same time) |
58 | Stack<V> sccStack = new Stack<V>(); | 55 | Deque<V> sccStack = new ArrayDeque<V>(); |
59 | 56 | ||
60 | boolean sink = false, finishedTraversal = true; | 57 | boolean sink = false, finishedTraversal = true; |
61 | 58 | ||
@@ -71,14 +68,14 @@ public class SCC<V> { | |||
71 | nodeStack.push(n); | 68 | nodeStack.push(n); |
72 | 69 | ||
73 | while (!nodeStack.isEmpty()) { | 70 | while (!nodeStack.isEmpty()) { |
74 | V currentNode = nodeStack.peek(); | 71 | V currentNode = nodeStack.peekLast(); |
75 | sink = false; | 72 | sink = false; |
76 | finishedTraversal = false; | 73 | finishedTraversal = false; |
77 | SCCProperty prop = nodeMap.get(currentNode); | 74 | SCCProperty prop = nodeMap.get(currentNode); |
78 | 75 | ||
79 | if (nodeMap.get(currentNode).getIndex() == 0) { | 76 | if (nodeMap.get(currentNode).getIndex() == 0) { |
80 | index++; | 77 | index++; |
81 | sccStack.push(currentNode); | 78 | sccStack.addLast(currentNode); |
82 | prop.setIndex(index); | 79 | prop.setIndex(index); |
83 | prop.setLowlink(index); | 80 | prop.setLowlink(index); |
84 | 81 | ||
@@ -97,7 +94,7 @@ public class SCC<V> { | |||
97 | if (targetNodeMap.get(currentNode).size() == 0) { | 94 | if (targetNodeMap.get(currentNode).size() == 0) { |
98 | targetNodeMap.remove(currentNode); | 95 | targetNodeMap.remove(currentNode); |
99 | 96 | ||
100 | nodeStack.pop(); | 97 | nodeStack.removeLast(); |
101 | 98 | ||
102 | for (V targetNode : g.getTargetNodes(currentNode).distinctValues()) { | 99 | for (V targetNode : g.getTargetNodes(currentNode).distinctValues()) { |
103 | if (notVisitedMap.get(currentNode).contains(targetNode)) { | 100 | if (notVisitedMap.get(currentNode).contains(targetNode)) { |
@@ -115,13 +112,13 @@ public class SCC<V> { | |||
115 | // and mark it in the notVisitedMap | 112 | // and mark it in the notVisitedMap |
116 | if (nodeMap.get(targetNode).getIndex() == 0) { | 113 | if (nodeMap.get(targetNode).getIndex() == 0) { |
117 | notVisitedMap.get(currentNode).add(targetNode); | 114 | notVisitedMap.get(currentNode).add(targetNode); |
118 | nodeStack.add(targetNode); | 115 | nodeStack.addLast(targetNode); |
119 | } | 116 | } |
120 | } | 117 | } |
121 | } | 118 | } |
122 | // if currentNode has no target nodes | 119 | // if currentNode has no target nodes |
123 | else { | 120 | else { |
124 | nodeStack.pop(); | 121 | nodeStack.removeLast(); |
125 | sink = true; | 122 | sink = true; |
126 | } | 123 | } |
127 | 124 | ||
@@ -131,7 +128,7 @@ public class SCC<V> { | |||
131 | V targetNode = null; | 128 | V targetNode = null; |
132 | 129 | ||
133 | do { | 130 | do { |
134 | targetNode = sccStack.pop(); | 131 | targetNode = sccStack.removeLast(); |
135 | sc.add(targetNode); | 132 | sc.add(targetNode); |
136 | } while (!targetNode.equals(currentNode)); | 133 | } while (!targetNode.equals(currentNode)); |
137 | 134 | ||
diff --git a/subprojects/viatra-runtime-rete/src/main/java/tools/refinery/viatra/runtime/rete/itc/alg/misc/topsort/TopologicalSorting.java b/subprojects/viatra-runtime-rete/src/main/java/tools/refinery/viatra/runtime/rete/itc/alg/misc/topsort/TopologicalSorting.java index db46d178..89be6804 100644 --- a/subprojects/viatra-runtime-rete/src/main/java/tools/refinery/viatra/runtime/rete/itc/alg/misc/topsort/TopologicalSorting.java +++ b/subprojects/viatra-runtime-rete/src/main/java/tools/refinery/viatra/runtime/rete/itc/alg/misc/topsort/TopologicalSorting.java | |||
@@ -40,15 +40,15 @@ public class TopologicalSorting { | |||
40 | public static <T> List<T> compute(final IGraphDataSource<T> gds) { | 40 | public static <T> List<T> compute(final IGraphDataSource<T> gds) { |
41 | final Set<T> visited = new HashSet<T>(); | 41 | final Set<T> visited = new HashSet<T>(); |
42 | final LinkedList<T> result = new LinkedList<T>(); | 42 | final LinkedList<T> result = new LinkedList<T>(); |
43 | final Stack<Pair<T>> dfsStack = new Stack<Pair<T>>(); | 43 | final Deque<Pair<T>> dfsStack = new ArrayDeque<Pair<T>>(); |
44 | 44 | ||
45 | for (final T node : gds.getAllNodes()) { | 45 | for (final T node : gds.getAllNodes()) { |
46 | if (!visited.contains(node)) { | 46 | if (!visited.contains(node)) { |
47 | dfsStack.push(new Pair<T>(node, false)); | 47 | dfsStack.addLast(new Pair<T>(node, false)); |
48 | } | 48 | } |
49 | 49 | ||
50 | while (!dfsStack.isEmpty()) { | 50 | while (!dfsStack.isEmpty()) { |
51 | final Pair<T> head = dfsStack.pop(); | 51 | final Pair<T> head = dfsStack.removeLast(); |
52 | final T source = head.element; | 52 | final T source = head.element; |
53 | 53 | ||
54 | if (head.isParent) { | 54 | if (head.isParent) { |
@@ -57,11 +57,11 @@ public class TopologicalSorting { | |||
57 | } else { | 57 | } else { |
58 | // first time we see source, continue with its children | 58 | // first time we see source, continue with its children |
59 | visited.add(source); | 59 | visited.add(source); |
60 | dfsStack.push(new Pair<T>(source, true)); | 60 | dfsStack.addLast(new Pair<T>(source, true)); |
61 | 61 | ||
62 | for (final T target : gds.getTargetNodes(source).distinctValues()) { | 62 | for (final T target : gds.getTargetNodes(source).distinctValues()) { |
63 | if (!visited.contains(target)) { | 63 | if (!visited.contains(target)) { |
64 | dfsStack.push(new Pair<T>(target, false)); | 64 | dfsStack.addLast(new Pair<T>(target, false)); |
65 | } | 65 | } |
66 | } | 66 | } |
67 | } | 67 | } |