diff options
author | 2023-08-19 03:56:39 +0200 | |
---|---|---|
committer | 2023-08-19 03:56:39 +0200 | |
commit | 6e11ebab0aa0dca1de5475761978073dd849aa36 (patch) | |
tree | a96f4caa74a10e799506fceae848b667de2e2d19 /subprojects | |
parent | refactor: apply local search fixes to VIATRA (diff) | |
download | refinery-6e11ebab0aa0dca1de5475761978073dd849aa36.tar.gz refinery-6e11ebab0aa0dca1de5475761978073dd849aa36.tar.zst refinery-6e11ebab0aa0dca1de5475761978073dd849aa36.zip |
refactor: move ITC algorithms
Since only RETE uses ITC, we may move ITC into the RETE project.
Also removes unused ITC algorithms.
Diffstat (limited to 'subprojects')
39 files changed, 226 insertions, 1004 deletions
diff --git a/subprojects/viatra-runtime-rete/src/main/java/tools/refinery/viatra/runtime/rete/index/TransitiveClosureNodeIndexer.java b/subprojects/viatra-runtime-rete/src/main/java/tools/refinery/viatra/runtime/rete/index/TransitiveClosureNodeIndexer.java index b0bea8cb..77202004 100644 --- a/subprojects/viatra-runtime-rete/src/main/java/tools/refinery/viatra/runtime/rete/index/TransitiveClosureNodeIndexer.java +++ b/subprojects/viatra-runtime-rete/src/main/java/tools/refinery/viatra/runtime/rete/index/TransitiveClosureNodeIndexer.java | |||
@@ -3,7 +3,7 @@ | |||
3 | * This program and the accompanying materials are made available under the | 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 | 4 | * terms of the Eclipse Public License v. 2.0 which is available at |
5 | * http://www.eclipse.org/legal/epl-v20.html. | 5 | * http://www.eclipse.org/legal/epl-v20.html. |
6 | * | 6 | * |
7 | * SPDX-License-Identifier: EPL-2.0 | 7 | * SPDX-License-Identifier: EPL-2.0 |
8 | *******************************************************************************/ | 8 | *******************************************************************************/ |
9 | package tools.refinery.viatra.runtime.rete.index; | 9 | package tools.refinery.viatra.runtime.rete.index; |
@@ -13,7 +13,7 @@ import java.util.Collections; | |||
13 | import java.util.Iterator; | 13 | import java.util.Iterator; |
14 | import java.util.Set; | 14 | import java.util.Set; |
15 | 15 | ||
16 | import tools.refinery.viatra.runtime.base.itc.alg.incscc.IncSCCAlg; | 16 | import tools.refinery.viatra.runtime.rete.itc.alg.incscc.IncSCCAlg; |
17 | import tools.refinery.viatra.runtime.matchers.tuple.MaskedTuple; | 17 | import tools.refinery.viatra.runtime.matchers.tuple.MaskedTuple; |
18 | import tools.refinery.viatra.runtime.matchers.tuple.Tuple; | 18 | import tools.refinery.viatra.runtime.matchers.tuple.Tuple; |
19 | import tools.refinery.viatra.runtime.matchers.tuple.TupleMask; | 19 | import tools.refinery.viatra.runtime.matchers.tuple.TupleMask; |
@@ -86,21 +86,21 @@ public class TransitiveClosureNodeIndexer extends StandardIndexer implements Ite | |||
86 | public int getBucketCount() { | 86 | public int getBucketCount() { |
87 | throw new UnsupportedOperationException(); | 87 | throw new UnsupportedOperationException(); |
88 | } | 88 | } |
89 | 89 | ||
90 | @Override | 90 | @Override |
91 | public Collection<Tuple> getSignatures() { | 91 | public Collection<Tuple> getSignatures() { |
92 | return asTupleCollection(tcAlg.getTcRelation()); | 92 | return asTupleCollection(tcAlg.getTcRelation()); |
93 | } | 93 | } |
94 | 94 | ||
95 | @Override | 95 | @Override |
96 | public Iterator<Tuple> iterator() { | 96 | public Iterator<Tuple> iterator() { |
97 | return asTupleCollection(tcAlg.getTcRelation()).iterator(); | 97 | return asTupleCollection(tcAlg.getTcRelation()).iterator(); |
98 | } | 98 | } |
99 | 99 | ||
100 | private Collection<Tuple> asTupleCollection( | 100 | private Collection<Tuple> asTupleCollection( |
101 | Collection<tools.refinery.viatra.runtime.base.itc.alg.misc.Tuple<Object>> tuples) { | 101 | Collection<tools.refinery.viatra.runtime.rete.itc.alg.misc.Tuple<Object>> tuples) { |
102 | Set<Tuple> retSet = CollectionsFactory.createSet(); | 102 | Set<Tuple> retSet = CollectionsFactory.createSet(); |
103 | for (tools.refinery.viatra.runtime.base.itc.alg.misc.Tuple<Object> tuple : tuples) { | 103 | for (tools.refinery.viatra.runtime.rete.itc.alg.misc.Tuple<Object> tuple : tuples) { |
104 | retSet.add(Tuples.staticArityFlatTupleOf(tuple.getSource(), tuple.getTarget())); | 104 | retSet.add(Tuples.staticArityFlatTupleOf(tuple.getSource(), tuple.getTarget())); |
105 | } | 105 | } |
106 | return retSet; | 106 | return retSet; |
@@ -117,5 +117,5 @@ public class TransitiveClosureNodeIndexer extends StandardIndexer implements Ite | |||
117 | public Receiver getActiveNode() { | 117 | public Receiver getActiveNode() { |
118 | return tcNode; | 118 | return tcNode; |
119 | } | 119 | } |
120 | 120 | ||
121 | } | 121 | } |
diff --git a/subprojects/viatra-runtime/src/main/java/tools/refinery/viatra/runtime/base/itc/alg/counting/CountingAlg.java b/subprojects/viatra-runtime-rete/src/main/java/tools/refinery/viatra/runtime/rete/itc/alg/counting/CountingAlg.java index d0367cde..199b44b1 100644 --- a/subprojects/viatra-runtime/src/main/java/tools/refinery/viatra/runtime/base/itc/alg/counting/CountingAlg.java +++ b/subprojects/viatra-runtime-rete/src/main/java/tools/refinery/viatra/runtime/rete/itc/alg/counting/CountingAlg.java | |||
@@ -3,32 +3,32 @@ | |||
3 | * This program and the accompanying materials are made available under the | 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 | 4 | * terms of the Eclipse Public License v. 2.0 which is available at |
5 | * http://www.eclipse.org/legal/epl-v20.html. | 5 | * http://www.eclipse.org/legal/epl-v20.html. |
6 | * | 6 | * |
7 | * SPDX-License-Identifier: EPL-2.0 | 7 | * SPDX-License-Identifier: EPL-2.0 |
8 | *******************************************************************************/ | 8 | *******************************************************************************/ |
9 | 9 | ||
10 | package tools.refinery.viatra.runtime.base.itc.alg.counting; | 10 | package tools.refinery.viatra.runtime.rete.itc.alg.counting; |
11 | 11 | ||
12 | import java.util.List; | 12 | import java.util.List; |
13 | import java.util.Set; | 13 | import java.util.Set; |
14 | 14 | ||
15 | import tools.refinery.viatra.runtime.base.itc.alg.misc.DFSPathFinder; | 15 | import tools.refinery.viatra.runtime.rete.itc.alg.misc.DFSPathFinder; |
16 | import tools.refinery.viatra.runtime.base.itc.alg.misc.IGraphPathFinder; | 16 | import tools.refinery.viatra.runtime.rete.itc.alg.misc.IGraphPathFinder; |
17 | import tools.refinery.viatra.runtime.base.itc.alg.misc.ITcRelation; | 17 | import tools.refinery.viatra.runtime.rete.itc.alg.misc.ITcRelation; |
18 | import tools.refinery.viatra.runtime.base.itc.igraph.IBiDirectionalGraphDataSource; | 18 | import tools.refinery.viatra.runtime.rete.itc.igraph.IBiDirectionalGraphDataSource; |
19 | import tools.refinery.viatra.runtime.base.itc.igraph.IBiDirectionalWrapper; | 19 | import tools.refinery.viatra.runtime.rete.itc.igraph.IBiDirectionalWrapper; |
20 | import tools.refinery.viatra.runtime.base.itc.igraph.IGraphDataSource; | 20 | import tools.refinery.viatra.runtime.rete.itc.igraph.IGraphDataSource; |
21 | import tools.refinery.viatra.runtime.base.itc.igraph.IGraphObserver; | 21 | import tools.refinery.viatra.runtime.rete.itc.igraph.IGraphObserver; |
22 | import tools.refinery.viatra.runtime.base.itc.igraph.ITcDataSource; | 22 | import tools.refinery.viatra.runtime.rete.itc.igraph.ITcDataSource; |
23 | import tools.refinery.viatra.runtime.base.itc.igraph.ITcObserver; | 23 | import tools.refinery.viatra.runtime.rete.itc.igraph.ITcObserver; |
24 | import tools.refinery.viatra.runtime.matchers.util.CollectionsFactory; | 24 | import tools.refinery.viatra.runtime.matchers.util.CollectionsFactory; |
25 | import tools.refinery.viatra.runtime.matchers.util.IMemoryView; | 25 | import tools.refinery.viatra.runtime.matchers.util.IMemoryView; |
26 | 26 | ||
27 | /** | 27 | /** |
28 | * This class is the optimized implementation of the Counting algorithm. | 28 | * This class is the optimized implementation of the Counting algorithm. |
29 | * | 29 | * |
30 | * @author Tamas Szabo | 30 | * @author Tamas Szabo |
31 | * | 31 | * |
32 | * @param <V> | 32 | * @param <V> |
33 | * the type parameter of the nodes in the graph data source | 33 | * the type parameter of the nodes in the graph data source |
34 | */ | 34 | */ |
@@ -41,7 +41,7 @@ public class CountingAlg<V> implements IGraphObserver<V>, ITcDataSource<V> { | |||
41 | /** | 41 | /** |
42 | * Constructs a new Counting algorithm and initializes the transitive closure relation with the given graph data | 42 | * Constructs a new Counting algorithm and initializes the transitive closure relation with the given graph data |
43 | * source. Attach itself on the graph data source as an observer. | 43 | * source. Attach itself on the graph data source as an observer. |
44 | * | 44 | * |
45 | * @param gds | 45 | * @param gds |
46 | * the graph data source instance | 46 | * the graph data source instance |
47 | */ | 47 | */ |
@@ -93,7 +93,7 @@ public class CountingAlg<V> implements IGraphObserver<V>, ITcDataSource<V> { | |||
93 | 93 | ||
94 | /** | 94 | /** |
95 | * Derives the transitive closure relation when an edge is inserted or deleted. | 95 | * Derives the transitive closure relation when an edge is inserted or deleted. |
96 | * | 96 | * |
97 | * @param source | 97 | * @param source |
98 | * the source of the edge | 98 | * the source of the edge |
99 | * @param target | 99 | * @param target |
@@ -133,7 +133,7 @@ public class CountingAlg<V> implements IGraphObserver<V>, ITcDataSource<V> { | |||
133 | CountingTcRelation<V> newTuples = dtc; | 133 | CountingTcRelation<V> newTuples = dtc; |
134 | CountingTcRelation<V> tmp = null; | 134 | CountingTcRelation<V> tmp = null; |
135 | dtc = new CountingTcRelation<V>(false); | 135 | dtc = new CountingTcRelation<V>(false); |
136 | 136 | ||
137 | IMemoryView<V> nodes = null; | 137 | IMemoryView<V> nodes = null; |
138 | 138 | ||
139 | while (!newTuples.isEmpty()) { | 139 | while (!newTuples.isEmpty()) { |
@@ -223,4 +223,4 @@ public class CountingAlg<V> implements IGraphObserver<V>, ITcDataSource<V> { | |||
223 | public IGraphPathFinder<V> getPathFinder() { | 223 | public IGraphPathFinder<V> getPathFinder() { |
224 | return new DFSPathFinder<V>(gds, this); | 224 | return new DFSPathFinder<V>(gds, this); |
225 | } | 225 | } |
226 | } \ No newline at end of file | 226 | } |
diff --git a/subprojects/viatra-runtime/src/main/java/tools/refinery/viatra/runtime/base/itc/alg/counting/CountingTcRelation.java b/subprojects/viatra-runtime-rete/src/main/java/tools/refinery/viatra/runtime/rete/itc/alg/counting/CountingTcRelation.java index 44abbc3d..474c7461 100644 --- a/subprojects/viatra-runtime/src/main/java/tools/refinery/viatra/runtime/base/itc/alg/counting/CountingTcRelation.java +++ b/subprojects/viatra-runtime-rete/src/main/java/tools/refinery/viatra/runtime/rete/itc/alg/counting/CountingTcRelation.java | |||
@@ -7,15 +7,15 @@ | |||
7 | * SPDX-License-Identifier: EPL-2.0 | 7 | * SPDX-License-Identifier: EPL-2.0 |
8 | *******************************************************************************/ | 8 | *******************************************************************************/ |
9 | 9 | ||
10 | package tools.refinery.viatra.runtime.base.itc.alg.counting; | 10 | package tools.refinery.viatra.runtime.rete.itc.alg.counting; |
11 | 11 | ||
12 | import java.util.Collections; | 12 | import java.util.Collections; |
13 | import java.util.List; | 13 | import java.util.List; |
14 | import java.util.Set; | 14 | import java.util.Set; |
15 | 15 | ||
16 | import tools.refinery.viatra.runtime.base.itc.alg.misc.topsort.TopologicalSorting; | 16 | import tools.refinery.viatra.runtime.rete.itc.alg.misc.topsort.TopologicalSorting; |
17 | import tools.refinery.viatra.runtime.base.itc.alg.misc.ITcRelation; | 17 | import tools.refinery.viatra.runtime.rete.itc.alg.misc.ITcRelation; |
18 | import tools.refinery.viatra.runtime.base.itc.igraph.IBiDirectionalGraphDataSource; | 18 | import tools.refinery.viatra.runtime.rete.itc.igraph.IBiDirectionalGraphDataSource; |
19 | import tools.refinery.viatra.runtime.matchers.util.CollectionsFactory; | 19 | import tools.refinery.viatra.runtime.matchers.util.CollectionsFactory; |
20 | import tools.refinery.viatra.runtime.matchers.util.CollectionsFactory.MemoryType; | 20 | import tools.refinery.viatra.runtime.matchers.util.CollectionsFactory.MemoryType; |
21 | import tools.refinery.viatra.runtime.matchers.util.IMemoryView; | 21 | import tools.refinery.viatra.runtime.matchers.util.IMemoryView; |
diff --git a/subprojects/viatra-runtime/src/main/java/tools/refinery/viatra/runtime/base/itc/alg/incscc/CountingListener.java b/subprojects/viatra-runtime-rete/src/main/java/tools/refinery/viatra/runtime/rete/itc/alg/incscc/CountingListener.java index fdf64f77..7d507d82 100644 --- a/subprojects/viatra-runtime/src/main/java/tools/refinery/viatra/runtime/base/itc/alg/incscc/CountingListener.java +++ b/subprojects/viatra-runtime-rete/src/main/java/tools/refinery/viatra/runtime/rete/itc/alg/incscc/CountingListener.java | |||
@@ -3,17 +3,17 @@ | |||
3 | * This program and the accompanying materials are made available under the | 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 | 4 | * terms of the Eclipse Public License v. 2.0 which is available at |
5 | * http://www.eclipse.org/legal/epl-v20.html. | 5 | * http://www.eclipse.org/legal/epl-v20.html. |
6 | * | 6 | * |
7 | * SPDX-License-Identifier: EPL-2.0 | 7 | * SPDX-License-Identifier: EPL-2.0 |
8 | *******************************************************************************/ | 8 | *******************************************************************************/ |
9 | package tools.refinery.viatra.runtime.base.itc.alg.incscc; | 9 | package tools.refinery.viatra.runtime.rete.itc.alg.incscc; |
10 | 10 | ||
11 | import tools.refinery.viatra.runtime.base.itc.igraph.ITcObserver; | 11 | import tools.refinery.viatra.runtime.rete.itc.igraph.ITcObserver; |
12 | import tools.refinery.viatra.runtime.matchers.util.Direction; | 12 | import tools.refinery.viatra.runtime.matchers.util.Direction; |
13 | 13 | ||
14 | /** | 14 | /** |
15 | * @author Tamas Szabo | 15 | * @author Tamas Szabo |
16 | * | 16 | * |
17 | */ | 17 | */ |
18 | public class CountingListener<V> implements ITcObserver<V> { | 18 | public class CountingListener<V> implements ITcObserver<V> { |
19 | 19 | ||
@@ -33,4 +33,4 @@ public class CountingListener<V> implements ITcObserver<V> { | |||
33 | alg.notifyTcObservers(alg.sccs.getPartition(source), alg.sccs.getPartition(target), Direction.DELETE); | 33 | alg.notifyTcObservers(alg.sccs.getPartition(source), alg.sccs.getPartition(target), Direction.DELETE); |
34 | } | 34 | } |
35 | 35 | ||
36 | } \ No newline at end of file | 36 | } |
diff --git a/subprojects/viatra-runtime/src/main/java/tools/refinery/viatra/runtime/base/itc/alg/incscc/IncSCCAlg.java b/subprojects/viatra-runtime-rete/src/main/java/tools/refinery/viatra/runtime/rete/itc/alg/incscc/IncSCCAlg.java index 5d720e75..774e55eb 100644 --- a/subprojects/viatra-runtime/src/main/java/tools/refinery/viatra/runtime/base/itc/alg/incscc/IncSCCAlg.java +++ b/subprojects/viatra-runtime-rete/src/main/java/tools/refinery/viatra/runtime/rete/itc/alg/incscc/IncSCCAlg.java | |||
@@ -7,38 +7,26 @@ | |||
7 | * SPDX-License-Identifier: EPL-2.0 | 7 | * SPDX-License-Identifier: EPL-2.0 |
8 | *******************************************************************************/ | 8 | *******************************************************************************/ |
9 | 9 | ||
10 | package tools.refinery.viatra.runtime.base.itc.alg.incscc; | 10 | package tools.refinery.viatra.runtime.rete.itc.alg.incscc; |
11 | 11 | ||
12 | import java.util.ArrayList; | ||
13 | import java.util.HashSet; | ||
14 | import java.util.Iterator; | ||
15 | import java.util.List; | ||
16 | import java.util.Map; | ||
17 | import java.util.Map.Entry; | ||
18 | import java.util.Objects; | ||
19 | import java.util.Set; | ||
20 | |||
21 | import tools.refinery.viatra.runtime.base.itc.alg.counting.CountingAlg; | ||
22 | import tools.refinery.viatra.runtime.base.itc.alg.misc.bfs.BFS; | ||
23 | import tools.refinery.viatra.runtime.base.itc.alg.misc.scc.SCC; | ||
24 | import tools.refinery.viatra.runtime.base.itc.alg.misc.scc.SCCResult; | ||
25 | import tools.refinery.viatra.runtime.base.itc.alg.util.CollectionHelper; | ||
26 | import tools.refinery.viatra.runtime.base.itc.alg.dred.DRedTcRelation; | ||
27 | import tools.refinery.viatra.runtime.base.itc.alg.misc.DFSPathFinder; | ||
28 | import tools.refinery.viatra.runtime.base.itc.alg.misc.GraphHelper; | ||
29 | import tools.refinery.viatra.runtime.base.itc.alg.misc.IGraphPathFinder; | ||
30 | import tools.refinery.viatra.runtime.base.itc.alg.misc.Tuple; | ||
31 | import tools.refinery.viatra.runtime.base.itc.graphimpl.Graph; | ||
32 | import tools.refinery.viatra.runtime.base.itc.igraph.IBiDirectionalGraphDataSource; | ||
33 | import tools.refinery.viatra.runtime.base.itc.igraph.IBiDirectionalWrapper; | ||
34 | import tools.refinery.viatra.runtime.base.itc.igraph.IGraphDataSource; | ||
35 | import tools.refinery.viatra.runtime.base.itc.igraph.IGraphObserver; | ||
36 | import tools.refinery.viatra.runtime.base.itc.igraph.ITcDataSource; | ||
37 | import tools.refinery.viatra.runtime.base.itc.igraph.ITcObserver; | ||
38 | import tools.refinery.viatra.runtime.matchers.algorithms.UnionFind; | 12 | import tools.refinery.viatra.runtime.matchers.algorithms.UnionFind; |
39 | import tools.refinery.viatra.runtime.matchers.util.CollectionsFactory; | 13 | import tools.refinery.viatra.runtime.matchers.util.CollectionsFactory; |
40 | import tools.refinery.viatra.runtime.matchers.util.Direction; | 14 | import tools.refinery.viatra.runtime.matchers.util.Direction; |
41 | import tools.refinery.viatra.runtime.matchers.util.IMemoryView; | 15 | import tools.refinery.viatra.runtime.matchers.util.IMemoryView; |
16 | import tools.refinery.viatra.runtime.rete.itc.alg.counting.CountingAlg; | ||
17 | import tools.refinery.viatra.runtime.rete.itc.alg.misc.DFSPathFinder; | ||
18 | import tools.refinery.viatra.runtime.rete.itc.alg.misc.GraphHelper; | ||
19 | import tools.refinery.viatra.runtime.rete.itc.alg.misc.IGraphPathFinder; | ||
20 | import tools.refinery.viatra.runtime.rete.itc.alg.misc.Tuple; | ||
21 | import tools.refinery.viatra.runtime.rete.itc.alg.misc.bfs.BFS; | ||
22 | import tools.refinery.viatra.runtime.rete.itc.alg.misc.scc.SCC; | ||
23 | import tools.refinery.viatra.runtime.rete.itc.alg.misc.scc.SCCResult; | ||
24 | import tools.refinery.viatra.runtime.rete.itc.alg.util.CollectionHelper; | ||
25 | import tools.refinery.viatra.runtime.rete.itc.graphimpl.Graph; | ||
26 | import tools.refinery.viatra.runtime.rete.itc.igraph.*; | ||
27 | |||
28 | import java.util.*; | ||
29 | import java.util.Map.Entry; | ||
42 | 30 | ||
43 | /** | 31 | /** |
44 | * Incremental SCC maintenance + counting algorithm. | 32 | * Incremental SCC maintenance + counting algorithm. |
@@ -438,30 +426,6 @@ public class IncSCCAlg<V> implements IGraphObserver<V>, ITcDataSource<V> { | |||
438 | } | 426 | } |
439 | } | 427 | } |
440 | 428 | ||
441 | // for JUnit | ||
442 | public boolean checkTcRelation(DRedTcRelation<V> tc) { | ||
443 | |||
444 | for (V s : tc.getTupleStarts()) { | ||
445 | for (V t : tc.getTupleEnds(s)) { | ||
446 | if (!isReachable(s, t)) | ||
447 | return false; | ||
448 | } | ||
449 | } | ||
450 | |||
451 | for (V root : counting.getTcRelation().getTupleStarts()) { | ||
452 | for (V end : counting.getTcRelation().getTupleEnds(root)) { | ||
453 | for (V s : sccs.getPartition(root)) { | ||
454 | for (V t : sccs.getPartition(end)) { | ||
455 | if (!tc.containsTuple(s, t)) | ||
456 | return false; | ||
457 | } | ||
458 | } | ||
459 | } | ||
460 | } | ||
461 | |||
462 | return true; | ||
463 | } | ||
464 | |||
465 | /** | 429 | /** |
466 | * Return the SCCs from which the SCC represented by the root node is reachable. Note that an SCC can be present | 430 | * Return the SCCs from which the SCC represented by the root node is reachable. Note that an SCC can be present |
467 | * multiple times in the returned list (multiple edges between the two SCCs). | 431 | * multiple times in the returned list (multiple edges between the two SCCs). |
diff --git a/subprojects/viatra-runtime/src/main/java/tools/refinery/viatra/runtime/base/itc/alg/misc/DFSPathFinder.java b/subprojects/viatra-runtime-rete/src/main/java/tools/refinery/viatra/runtime/rete/itc/alg/misc/DFSPathFinder.java index 51017b1a..2cec33a2 100644 --- a/subprojects/viatra-runtime/src/main/java/tools/refinery/viatra/runtime/base/itc/alg/misc/DFSPathFinder.java +++ b/subprojects/viatra-runtime-rete/src/main/java/tools/refinery/viatra/runtime/rete/itc/alg/misc/DFSPathFinder.java | |||
@@ -3,10 +3,10 @@ | |||
3 | * This program and the accompanying materials are made available under the | 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 | 4 | * terms of the Eclipse Public License v. 2.0 which is available at |
5 | * http://www.eclipse.org/legal/epl-v20.html. | 5 | * http://www.eclipse.org/legal/epl-v20.html. |
6 | * | 6 | * |
7 | * SPDX-License-Identifier: EPL-2.0 | 7 | * SPDX-License-Identifier: EPL-2.0 |
8 | *******************************************************************************/ | 8 | *******************************************************************************/ |
9 | package tools.refinery.viatra.runtime.base.itc.alg.misc; | 9 | package tools.refinery.viatra.runtime.rete.itc.alg.misc; |
10 | 10 | ||
11 | import java.util.ArrayList; | 11 | import java.util.ArrayList; |
12 | import java.util.Deque; | 12 | import java.util.Deque; |
@@ -16,17 +16,17 @@ import java.util.LinkedList; | |||
16 | import java.util.List; | 16 | import java.util.List; |
17 | import java.util.Set; | 17 | import java.util.Set; |
18 | 18 | ||
19 | import tools.refinery.viatra.runtime.base.itc.igraph.IGraphDataSource; | 19 | import tools.refinery.viatra.runtime.rete.itc.igraph.IGraphDataSource; |
20 | import tools.refinery.viatra.runtime.base.itc.igraph.ITcDataSource; | 20 | import tools.refinery.viatra.runtime.rete.itc.igraph.ITcDataSource; |
21 | import tools.refinery.viatra.runtime.matchers.util.IMemoryView; | 21 | import tools.refinery.viatra.runtime.matchers.util.IMemoryView; |
22 | 22 | ||
23 | /** | 23 | /** |
24 | * A depth-first search implementation of the {@link IGraphPathFinder}. | 24 | * A depth-first search implementation of the {@link IGraphPathFinder}. |
25 | * | 25 | * |
26 | * TODO use ITC to filter nodes that must be traversed, instead of checks | 26 | * TODO use ITC to filter nodes that must be traversed, instead of checks |
27 | * | 27 | * |
28 | * @author Abel Hegedus | 28 | * @author Abel Hegedus |
29 | * | 29 | * |
30 | * @param <V> | 30 | * @param <V> |
31 | * the node type of the graph | 31 | * the node type of the graph |
32 | */ | 32 | */ |
diff --git a/subprojects/viatra-runtime/src/main/java/tools/refinery/viatra/runtime/base/itc/alg/misc/Edge.java b/subprojects/viatra-runtime-rete/src/main/java/tools/refinery/viatra/runtime/rete/itc/alg/misc/Edge.java index cf68d36a..862c99b3 100644 --- a/subprojects/viatra-runtime/src/main/java/tools/refinery/viatra/runtime/base/itc/alg/misc/Edge.java +++ b/subprojects/viatra-runtime-rete/src/main/java/tools/refinery/viatra/runtime/rete/itc/alg/misc/Edge.java | |||
@@ -3,11 +3,11 @@ | |||
3 | * This program and the accompanying materials are made available under the | 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 | 4 | * terms of the Eclipse Public License v. 2.0 which is available at |
5 | * http://www.eclipse.org/legal/epl-v20.html. | 5 | * http://www.eclipse.org/legal/epl-v20.html. |
6 | * | 6 | * |
7 | * SPDX-License-Identifier: EPL-2.0 | 7 | * SPDX-License-Identifier: EPL-2.0 |
8 | *******************************************************************************/ | 8 | *******************************************************************************/ |
9 | 9 | ||
10 | package tools.refinery.viatra.runtime.base.itc.alg.misc; | 10 | package tools.refinery.viatra.runtime.rete.itc.alg.misc; |
11 | 11 | ||
12 | public class Edge<V> { | 12 | public class Edge<V> { |
13 | private V source; | 13 | private V source; |
diff --git a/subprojects/viatra-runtime/src/main/java/tools/refinery/viatra/runtime/base/itc/alg/misc/GraphHelper.java b/subprojects/viatra-runtime-rete/src/main/java/tools/refinery/viatra/runtime/rete/itc/alg/misc/GraphHelper.java index 194e979b..b79e4d45 100644 --- a/subprojects/viatra-runtime/src/main/java/tools/refinery/viatra/runtime/base/itc/alg/misc/GraphHelper.java +++ b/subprojects/viatra-runtime-rete/src/main/java/tools/refinery/viatra/runtime/rete/itc/alg/misc/GraphHelper.java | |||
@@ -3,35 +3,31 @@ | |||
3 | * This program and the accompanying materials are made available under the | 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 | 4 | * terms of the Eclipse Public License v. 2.0 which is available at |
5 | * http://www.eclipse.org/legal/epl-v20.html. | 5 | * http://www.eclipse.org/legal/epl-v20.html. |
6 | * | 6 | * |
7 | * SPDX-License-Identifier: EPL-2.0 | 7 | * SPDX-License-Identifier: EPL-2.0 |
8 | *******************************************************************************/ | 8 | *******************************************************************************/ |
9 | package tools.refinery.viatra.runtime.base.itc.alg.misc; | 9 | package tools.refinery.viatra.runtime.rete.itc.alg.misc; |
10 | 10 | ||
11 | import java.util.ArrayList; | ||
12 | import java.util.Collection; | ||
13 | import java.util.HashSet; | ||
14 | import java.util.List; | ||
15 | import java.util.Map.Entry; | ||
16 | import java.util.Set; | ||
17 | |||
18 | import tools.refinery.viatra.runtime.base.itc.graphimpl.Graph; | ||
19 | import tools.refinery.viatra.runtime.base.itc.igraph.IBiDirectionalGraphDataSource; | ||
20 | import tools.refinery.viatra.runtime.base.itc.igraph.IGraphDataSource; | ||
21 | import tools.refinery.viatra.runtime.matchers.util.IMemoryView; | 11 | import tools.refinery.viatra.runtime.matchers.util.IMemoryView; |
12 | import tools.refinery.viatra.runtime.rete.itc.graphimpl.Graph; | ||
13 | import tools.refinery.viatra.runtime.rete.itc.igraph.IBiDirectionalGraphDataSource; | ||
14 | import tools.refinery.viatra.runtime.rete.itc.igraph.IGraphDataSource; | ||
15 | |||
16 | import java.util.*; | ||
17 | import java.util.Map.Entry; | ||
22 | 18 | ||
23 | /** | 19 | /** |
24 | * Utility class for graph related operations. | 20 | * Utility class for graph related operations. |
25 | * | 21 | * |
26 | * @author Tamas Szabo | 22 | * @author Tamas Szabo |
27 | */ | 23 | */ |
28 | public class GraphHelper { | 24 | public class GraphHelper { |
29 | 25 | ||
30 | private GraphHelper() {/*Utility class constructor*/} | 26 | private GraphHelper() {/*Utility class constructor*/} |
31 | 27 | ||
32 | /** | 28 | /** |
33 | * Returns the subgraph from the given {@link IBiDirectionalGraphDataSource} which contains the given set of nodes. | 29 | * Returns the subgraph from the given {@link IBiDirectionalGraphDataSource} which contains the given set of nodes. |
34 | * | 30 | * |
35 | * @param nodesInSubGraph | 31 | * @param nodesInSubGraph |
36 | * the nodes that are present in the subgraph | 32 | * the nodes that are present in the subgraph |
37 | * @param graphDataSource | 33 | * @param graphDataSource |
@@ -65,11 +61,11 @@ public class GraphHelper { | |||
65 | /** | 61 | /** |
66 | * Constructs a path between source and target in the given graph. Both the {@link IGraphDataSource} and the set of | 62 | * Constructs a path between source and target in the given graph. Both the {@link IGraphDataSource} and the set of |
67 | * nodes are used, this way it is possible to construct a path in a given subgraph. | 63 | * nodes are used, this way it is possible to construct a path in a given subgraph. |
68 | * | 64 | * |
69 | * The returned {@link List} contains the nodes along the path (this means that there is an edge in the graph | 65 | * The returned {@link List} contains the nodes along the path (this means that there is an edge in the graph |
70 | * between two consecutive nodes). A self loop (one edge) is indicated with the source node being present two times | 66 | * between two consecutive nodes). A self loop (one edge) is indicated with the source node being present two times |
71 | * in the returned {@link List}. | 67 | * in the returned {@link List}. |
72 | * | 68 | * |
73 | * @param source | 69 | * @param source |
74 | * the source node | 70 | * the source node |
75 | * @param target | 71 | * @param target |
@@ -140,7 +136,7 @@ public class GraphHelper { | |||
140 | 136 | ||
141 | /** | 137 | /** |
142 | * Returns the number of self-loop edges for the given node. | 138 | * Returns the number of self-loop edges for the given node. |
143 | * | 139 | * |
144 | * @param node | 140 | * @param node |
145 | * the node | 141 | * the node |
146 | * @param graphDataSource | 142 | * @param graphDataSource |
@@ -153,7 +149,7 @@ public class GraphHelper { | |||
153 | 149 | ||
154 | /** | 150 | /** |
155 | * Returns the number of edges between the given source and target nodes. | 151 | * Returns the number of edges between the given source and target nodes. |
156 | * | 152 | * |
157 | * @param source | 153 | * @param source |
158 | * the source node | 154 | * the source node |
159 | * @param target | 155 | * @param target |
diff --git a/subprojects/viatra-runtime/src/main/java/tools/refinery/viatra/runtime/base/itc/alg/misc/IGraphPathFinder.java b/subprojects/viatra-runtime-rete/src/main/java/tools/refinery/viatra/runtime/rete/itc/alg/misc/IGraphPathFinder.java index cebb09c8..624f9f7d 100644 --- a/subprojects/viatra-runtime/src/main/java/tools/refinery/viatra/runtime/base/itc/alg/misc/IGraphPathFinder.java +++ b/subprojects/viatra-runtime-rete/src/main/java/tools/refinery/viatra/runtime/rete/itc/alg/misc/IGraphPathFinder.java | |||
@@ -3,20 +3,20 @@ | |||
3 | * This program and the accompanying materials are made available under the | 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 | 4 | * terms of the Eclipse Public License v. 2.0 which is available at |
5 | * http://www.eclipse.org/legal/epl-v20.html. | 5 | * http://www.eclipse.org/legal/epl-v20.html. |
6 | * | 6 | * |
7 | * SPDX-License-Identifier: EPL-2.0 | 7 | * SPDX-License-Identifier: EPL-2.0 |
8 | *******************************************************************************/ | 8 | *******************************************************************************/ |
9 | package tools.refinery.viatra.runtime.base.itc.alg.misc; | 9 | package tools.refinery.viatra.runtime.rete.itc.alg.misc; |
10 | 10 | ||
11 | import java.util.Deque; | 11 | import java.util.Deque; |
12 | import java.util.Set; | 12 | import java.util.Set; |
13 | 13 | ||
14 | import tools.refinery.viatra.runtime.base.itc.igraph.ITcDataSource; | 14 | import tools.refinery.viatra.runtime.rete.itc.igraph.ITcDataSource; |
15 | 15 | ||
16 | /** | 16 | /** |
17 | * The path finder provides methods for retrieving paths in a graph between a source node and one or more target nodes. | 17 | * The path finder provides methods for retrieving paths in a graph between a source node and one or more target nodes. |
18 | * Use {@link ITcDataSource#getPathFinder()} for instantiating. | 18 | * Use {@link ITcDataSource#getPathFinder()} for instantiating. |
19 | * | 19 | * |
20 | * @author Abel Hegedus | 20 | * @author Abel Hegedus |
21 | * | 21 | * |
22 | * @param <V> the node type of the graph | 22 | * @param <V> the node type of the graph |
@@ -26,7 +26,7 @@ public interface IGraphPathFinder<V> { | |||
26 | /** | 26 | /** |
27 | * Returns an arbitrary path from the source node to the target node (if such exists). If there is no path | 27 | * Returns an arbitrary path from the source node to the target node (if such exists). If there is no path |
28 | * between them, an empty collection is returned. | 28 | * between them, an empty collection is returned. |
29 | * | 29 | * |
30 | * @param sourceNode the source node of the path | 30 | * @param sourceNode the source node of the path |
31 | * @param targetNode the target node of the path | 31 | * @param targetNode the target node of the path |
32 | * @return the path from the source to the target, or empty collection if target is not reachable from source. | 32 | * @return the path from the source to the target, or empty collection if target is not reachable from source. |
@@ -36,17 +36,17 @@ public interface IGraphPathFinder<V> { | |||
36 | /** | 36 | /** |
37 | * Returns the collection of shortest paths from the source node to the target node (if such exists). If there is no path | 37 | * Returns the collection of shortest paths from the source node to the target node (if such exists). If there is no path |
38 | * between them, an empty collection is returned. | 38 | * between them, an empty collection is returned. |
39 | * | 39 | * |
40 | * @param sourceNode the source node of the path | 40 | * @param sourceNode the source node of the path |
41 | * @param targetNode the target node of the path | 41 | * @param targetNode the target node of the path |
42 | * @return the collection of shortest paths from the source to the target, or empty collection if target is not reachable from source. | 42 | * @return the collection of shortest paths from the source to the target, or empty collection if target is not reachable from source. |
43 | */ | 43 | */ |
44 | Iterable<Deque<V>> getShortestPaths(V sourceNode, V targetNode); | 44 | Iterable<Deque<V>> getShortestPaths(V sourceNode, V targetNode); |
45 | 45 | ||
46 | /** | 46 | /** |
47 | * Returns the collection of paths from the source node to the target node (if such exists). If there is no path | 47 | * Returns the collection of paths from the source node to the target node (if such exists). If there is no path |
48 | * between them, an empty collection is returned. | 48 | * between them, an empty collection is returned. |
49 | * | 49 | * |
50 | * @param sourceNode the source node of the path | 50 | * @param sourceNode the source node of the path |
51 | * @param targetNode the target node of the path | 51 | * @param targetNode the target node of the path |
52 | * @return the collection of paths from the source to the target, or empty collection if target is not reachable from source. | 52 | * @return the collection of paths from the source to the target, or empty collection if target is not reachable from source. |
@@ -56,12 +56,12 @@ public interface IGraphPathFinder<V> { | |||
56 | /** | 56 | /** |
57 | * Returns the collection of paths from the source node to any of the target nodes (if such exists). If there is no path | 57 | * Returns the collection of paths from the source node to any of the target nodes (if such exists). If there is no path |
58 | * between them, an empty collection is returned. | 58 | * between them, an empty collection is returned. |
59 | * | 59 | * |
60 | * @param sourceNode the source node of the path | 60 | * @param sourceNode the source node of the path |
61 | * @param targetNodes the set of target nodes of the paths | 61 | * @param targetNodes the set of target nodes of the paths |
62 | * @return the collection of paths from the source to any of the targets, or empty collection if neither target is reachable from source. | 62 | * @return the collection of paths from the source to any of the targets, or empty collection if neither target is reachable from source. |
63 | */ | 63 | */ |
64 | Iterable<Deque<V>> getAllPathsToTargets(V sourceNode, Set<V> targetNodes); | 64 | Iterable<Deque<V>> getAllPathsToTargets(V sourceNode, Set<V> targetNodes); |
65 | 65 | ||
66 | 66 | ||
67 | } \ No newline at end of file | 67 | } |
diff --git a/subprojects/viatra-runtime/src/main/java/tools/refinery/viatra/runtime/base/itc/alg/misc/ITcRelation.java b/subprojects/viatra-runtime-rete/src/main/java/tools/refinery/viatra/runtime/rete/itc/alg/misc/ITcRelation.java index a41ff6c7..9fd85ae1 100644 --- a/subprojects/viatra-runtime/src/main/java/tools/refinery/viatra/runtime/base/itc/alg/misc/ITcRelation.java +++ b/subprojects/viatra-runtime-rete/src/main/java/tools/refinery/viatra/runtime/rete/itc/alg/misc/ITcRelation.java | |||
@@ -3,11 +3,11 @@ | |||
3 | * This program and the accompanying materials are made available under the | 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 | 4 | * terms of the Eclipse Public License v. 2.0 which is available at |
5 | * http://www.eclipse.org/legal/epl-v20.html. | 5 | * http://www.eclipse.org/legal/epl-v20.html. |
6 | * | 6 | * |
7 | * SPDX-License-Identifier: EPL-2.0 | 7 | * SPDX-License-Identifier: EPL-2.0 |
8 | *******************************************************************************/ | 8 | *******************************************************************************/ |
9 | 9 | ||
10 | package tools.refinery.viatra.runtime.base.itc.alg.misc; | 10 | package tools.refinery.viatra.runtime.rete.itc.alg.misc; |
11 | 11 | ||
12 | import java.util.Set; | 12 | import java.util.Set; |
13 | 13 | ||
@@ -15,14 +15,14 @@ public interface ITcRelation<V> { | |||
15 | 15 | ||
16 | /** | 16 | /** |
17 | * Returns the starting nodes from a transitive closure relation. | 17 | * Returns the starting nodes from a transitive closure relation. |
18 | * | 18 | * |
19 | * @return the set of starting nodes | 19 | * @return the set of starting nodes |
20 | */ | 20 | */ |
21 | public Set<V> getTupleStarts(); | 21 | public Set<V> getTupleStarts(); |
22 | 22 | ||
23 | /** | 23 | /** |
24 | * Returns the set of nodes that are reachable from the given node. | 24 | * Returns the set of nodes that are reachable from the given node. |
25 | * | 25 | * |
26 | * @param start | 26 | * @param start |
27 | * the starting node | 27 | * the starting node |
28 | * @return the set of reachable nodes | 28 | * @return the set of reachable nodes |
diff --git a/subprojects/viatra-runtime/src/main/java/tools/refinery/viatra/runtime/base/itc/alg/misc/Tuple.java b/subprojects/viatra-runtime-rete/src/main/java/tools/refinery/viatra/runtime/rete/itc/alg/misc/Tuple.java index a2d54a59..84c79dcf 100644 --- a/subprojects/viatra-runtime/src/main/java/tools/refinery/viatra/runtime/base/itc/alg/misc/Tuple.java +++ b/subprojects/viatra-runtime-rete/src/main/java/tools/refinery/viatra/runtime/rete/itc/alg/misc/Tuple.java | |||
@@ -3,11 +3,11 @@ | |||
3 | * This program and the accompanying materials are made available under the | 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 | 4 | * terms of the Eclipse Public License v. 2.0 which is available at |
5 | * http://www.eclipse.org/legal/epl-v20.html. | 5 | * http://www.eclipse.org/legal/epl-v20.html. |
6 | * | 6 | * |
7 | * SPDX-License-Identifier: EPL-2.0 | 7 | * SPDX-License-Identifier: EPL-2.0 |
8 | *******************************************************************************/ | 8 | *******************************************************************************/ |
9 | 9 | ||
10 | package tools.refinery.viatra.runtime.base.itc.alg.misc; | 10 | package tools.refinery.viatra.runtime.rete.itc.alg.misc; |
11 | 11 | ||
12 | public class Tuple<V> { | 12 | public class Tuple<V> { |
13 | 13 | ||
diff --git a/subprojects/viatra-runtime/src/main/java/tools/refinery/viatra/runtime/base/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 798f31d2..00b0a96d 100644 --- a/subprojects/viatra-runtime/src/main/java/tools/refinery/viatra/runtime/base/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 | |||
@@ -3,27 +3,27 @@ | |||
3 | * This program and the accompanying materials are made available under the | 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 | 4 | * terms of the Eclipse Public License v. 2.0 which is available at |
5 | * http://www.eclipse.org/legal/epl-v20.html. | 5 | * http://www.eclipse.org/legal/epl-v20.html. |
6 | * | 6 | * |
7 | * SPDX-License-Identifier: EPL-2.0 | 7 | * SPDX-License-Identifier: EPL-2.0 |
8 | *******************************************************************************/ | 8 | *******************************************************************************/ |
9 | 9 | ||
10 | package tools.refinery.viatra.runtime.base.itc.alg.misc.bfs; | 10 | package tools.refinery.viatra.runtime.rete.itc.alg.misc.bfs; |
11 | |||
12 | import tools.refinery.viatra.runtime.rete.itc.igraph.IBiDirectionalGraphDataSource; | ||
13 | import tools.refinery.viatra.runtime.rete.itc.igraph.IGraphDataSource; | ||
11 | 14 | ||
12 | import java.util.ArrayList; | 15 | import java.util.ArrayList; |
13 | import java.util.HashSet; | 16 | import java.util.HashSet; |
14 | import java.util.List; | 17 | import java.util.List; |
15 | import java.util.Set; | 18 | import java.util.Set; |
16 | 19 | ||
17 | import tools.refinery.viatra.runtime.base.itc.igraph.IBiDirectionalGraphDataSource; | ||
18 | import tools.refinery.viatra.runtime.base.itc.igraph.IGraphDataSource; | ||
19 | |||
20 | public class BFS<V> { | 20 | public class BFS<V> { |
21 | 21 | ||
22 | private BFS() {/*Utility class constructor*/} | 22 | private BFS() {/*Utility class constructor*/} |
23 | 23 | ||
24 | /** | 24 | /** |
25 | * Performs a breadth first search on the given graph to determine whether source is reachable from target. | 25 | * Performs a breadth first search on the given graph to determine whether source is reachable from target. |
26 | * | 26 | * |
27 | * @param <V> | 27 | * @param <V> |
28 | * the type parameter of the nodes in the graph | 28 | * the type parameter of the nodes in the graph |
29 | * @param source | 29 | * @param source |
@@ -114,7 +114,7 @@ public class BFS<V> { | |||
114 | /** | 114 | /** |
115 | * Performs a breadth first search on the given graph and collects all the nodes along the path from source to | 115 | * Performs a breadth first search on the given graph and collects all the nodes along the path from source to |
116 | * target if such path exists. | 116 | * target if such path exists. |
117 | * | 117 | * |
118 | * @param <V> | 118 | * @param <V> |
119 | * the type parameter of the nodes in the graph | 119 | * the type parameter of the nodes in the graph |
120 | * @param source | 120 | * @param source |
diff --git a/subprojects/viatra-runtime/src/main/java/tools/refinery/viatra/runtime/base/itc/alg/misc/scc/PKAlg.java b/subprojects/viatra-runtime-rete/src/main/java/tools/refinery/viatra/runtime/rete/itc/alg/misc/scc/PKAlg.java index c99a48ab..892d048e 100644 --- a/subprojects/viatra-runtime/src/main/java/tools/refinery/viatra/runtime/base/itc/alg/misc/scc/PKAlg.java +++ b/subprojects/viatra-runtime-rete/src/main/java/tools/refinery/viatra/runtime/rete/itc/alg/misc/scc/PKAlg.java | |||
@@ -3,11 +3,11 @@ | |||
3 | * This program and the accompanying materials are made available under the | 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 | 4 | * terms of the Eclipse Public License v. 2.0 which is available at |
5 | * http://www.eclipse.org/legal/epl-v20.html. | 5 | * http://www.eclipse.org/legal/epl-v20.html. |
6 | * | 6 | * |
7 | * SPDX-License-Identifier: EPL-2.0 | 7 | * SPDX-License-Identifier: EPL-2.0 |
8 | *******************************************************************************/ | 8 | *******************************************************************************/ |
9 | 9 | ||
10 | package tools.refinery.viatra.runtime.base.itc.alg.misc.scc; | 10 | package tools.refinery.viatra.runtime.rete.itc.alg.misc.scc; |
11 | 11 | ||
12 | import java.util.ArrayList; | 12 | import java.util.ArrayList; |
13 | import java.util.Collections; | 13 | import java.util.Collections; |
@@ -15,10 +15,10 @@ import java.util.HashMap; | |||
15 | import java.util.List; | 15 | import java.util.List; |
16 | import java.util.Map; | 16 | import java.util.Map; |
17 | 17 | ||
18 | import tools.refinery.viatra.runtime.base.itc.igraph.IBiDirectionalGraphDataSource; | 18 | import tools.refinery.viatra.runtime.rete.itc.igraph.IBiDirectionalGraphDataSource; |
19 | import tools.refinery.viatra.runtime.base.itc.igraph.IBiDirectionalWrapper; | 19 | import tools.refinery.viatra.runtime.rete.itc.igraph.IBiDirectionalWrapper; |
20 | import tools.refinery.viatra.runtime.base.itc.igraph.IGraphDataSource; | 20 | import tools.refinery.viatra.runtime.rete.itc.igraph.IGraphDataSource; |
21 | import tools.refinery.viatra.runtime.base.itc.igraph.IGraphObserver; | 21 | import tools.refinery.viatra.runtime.rete.itc.igraph.IGraphObserver; |
22 | 22 | ||
23 | public class PKAlg<V> implements IGraphObserver<V> { | 23 | public class PKAlg<V> implements IGraphObserver<V> { |
24 | 24 | ||
diff --git a/subprojects/viatra-runtime/src/main/java/tools/refinery/viatra/runtime/base/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 8915998b..f6ef9847 100644 --- a/subprojects/viatra-runtime/src/main/java/tools/refinery/viatra/runtime/base/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 | |||
@@ -3,37 +3,37 @@ | |||
3 | * This program and the accompanying materials are made available under the | 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 | 4 | * terms of the Eclipse Public License v. 2.0 which is available at |
5 | * http://www.eclipse.org/legal/epl-v20.html. | 5 | * http://www.eclipse.org/legal/epl-v20.html. |
6 | * | 6 | * |
7 | * SPDX-License-Identifier: EPL-2.0 | 7 | * SPDX-License-Identifier: EPL-2.0 |
8 | *******************************************************************************/ | 8 | *******************************************************************************/ |
9 | 9 | ||
10 | package tools.refinery.viatra.runtime.base.itc.alg.misc.scc; | 10 | package tools.refinery.viatra.runtime.rete.itc.alg.misc.scc; |
11 | 11 | ||
12 | import java.util.HashSet; | 12 | import java.util.HashSet; |
13 | import java.util.Map; | 13 | import java.util.Map; |
14 | import java.util.Set; | 14 | import java.util.Set; |
15 | import java.util.Stack; | 15 | import java.util.Stack; |
16 | 16 | ||
17 | import tools.refinery.viatra.runtime.base.itc.igraph.IGraphDataSource; | 17 | import tools.refinery.viatra.runtime.rete.itc.igraph.IGraphDataSource; |
18 | import tools.refinery.viatra.runtime.matchers.util.CollectionsFactory; | 18 | import tools.refinery.viatra.runtime.matchers.util.CollectionsFactory; |
19 | 19 | ||
20 | /** | 20 | /** |
21 | * Efficient algorithms to compute the Strongly Connected Components in a directed graph. | 21 | * Efficient algorithms to compute the Strongly Connected Components in a directed graph. |
22 | * | 22 | * |
23 | * @author Tamas Szabo | 23 | * @author Tamas Szabo |
24 | * | 24 | * |
25 | * @param <V> | 25 | * @param <V> |
26 | * the type parameter of the nodes in the graph | 26 | * the type parameter of the nodes in the graph |
27 | */ | 27 | */ |
28 | public class SCC<V> { | 28 | public class SCC<V> { |
29 | 29 | ||
30 | private SCC() {/*Utility class constructor*/} | 30 | private SCC() {/*Utility class constructor*/} |
31 | 31 | ||
32 | public static long sccId = 0; | 32 | public static long sccId = 0; |
33 | 33 | ||
34 | /** | 34 | /** |
35 | * Computes the SCCs for the given graph and returns them as a multiset. (Iterative version of Tarjan's algorithm) | 35 | * Computes the SCCs for the given graph and returns them as a multiset. (Iterative version of Tarjan's algorithm) |
36 | * | 36 | * |
37 | * @param g | 37 | * @param g |
38 | * the directed graph data source | 38 | * the directed graph data source |
39 | * @return the set of SCCs | 39 | * @return the set of SCCs |
diff --git a/subprojects/viatra-runtime/src/main/java/tools/refinery/viatra/runtime/base/itc/alg/misc/scc/SCCProperty.java b/subprojects/viatra-runtime-rete/src/main/java/tools/refinery/viatra/runtime/rete/itc/alg/misc/scc/SCCProperty.java index b26e3d37..51ee834e 100644 --- a/subprojects/viatra-runtime/src/main/java/tools/refinery/viatra/runtime/base/itc/alg/misc/scc/SCCProperty.java +++ b/subprojects/viatra-runtime-rete/src/main/java/tools/refinery/viatra/runtime/rete/itc/alg/misc/scc/SCCProperty.java | |||
@@ -3,11 +3,11 @@ | |||
3 | * This program and the accompanying materials are made available under the | 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 | 4 | * terms of the Eclipse Public License v. 2.0 which is available at |
5 | * http://www.eclipse.org/legal/epl-v20.html. | 5 | * http://www.eclipse.org/legal/epl-v20.html. |
6 | * | 6 | * |
7 | * SPDX-License-Identifier: EPL-2.0 | 7 | * SPDX-License-Identifier: EPL-2.0 |
8 | *******************************************************************************/ | 8 | *******************************************************************************/ |
9 | 9 | ||
10 | package tools.refinery.viatra.runtime.base.itc.alg.misc.scc; | 10 | package tools.refinery.viatra.runtime.rete.itc.alg.misc.scc; |
11 | 11 | ||
12 | public class SCCProperty { | 12 | public class SCCProperty { |
13 | private int index; | 13 | private int index; |
diff --git a/subprojects/viatra-runtime/src/main/java/tools/refinery/viatra/runtime/base/itc/alg/misc/scc/SCCResult.java b/subprojects/viatra-runtime-rete/src/main/java/tools/refinery/viatra/runtime/rete/itc/alg/misc/scc/SCCResult.java index fde59d3b..2e511fd6 100644 --- a/subprojects/viatra-runtime/src/main/java/tools/refinery/viatra/runtime/base/itc/alg/misc/scc/SCCResult.java +++ b/subprojects/viatra-runtime-rete/src/main/java/tools/refinery/viatra/runtime/rete/itc/alg/misc/scc/SCCResult.java | |||
@@ -3,16 +3,16 @@ | |||
3 | * This program and the accompanying materials are made available under the | 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 | 4 | * terms of the Eclipse Public License v. 2.0 which is available at |
5 | * http://www.eclipse.org/legal/epl-v20.html. | 5 | * http://www.eclipse.org/legal/epl-v20.html. |
6 | * | 6 | * |
7 | * SPDX-License-Identifier: EPL-2.0 | 7 | * SPDX-License-Identifier: EPL-2.0 |
8 | *******************************************************************************/ | 8 | *******************************************************************************/ |
9 | 9 | ||
10 | package tools.refinery.viatra.runtime.base.itc.alg.misc.scc; | 10 | package tools.refinery.viatra.runtime.rete.itc.alg.misc.scc; |
11 | 11 | ||
12 | import java.util.Map.Entry; | 12 | import java.util.Map.Entry; |
13 | import java.util.Set; | 13 | import java.util.Set; |
14 | 14 | ||
15 | import tools.refinery.viatra.runtime.base.itc.igraph.IGraphDataSource; | 15 | import tools.refinery.viatra.runtime.rete.itc.igraph.IGraphDataSource; |
16 | 16 | ||
17 | public class SCCResult<V> { | 17 | public class SCCResult<V> { |
18 | 18 | ||
diff --git a/subprojects/viatra-runtime/src/main/java/tools/refinery/viatra/runtime/base/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 dd18e6c8..db46d178 100644 --- a/subprojects/viatra-runtime/src/main/java/tools/refinery/viatra/runtime/base/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 | |||
@@ -3,19 +3,15 @@ | |||
3 | * This program and the accompanying materials are made available under the | 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 | 4 | * terms of the Eclipse Public License v. 2.0 which is available at |
5 | * http://www.eclipse.org/legal/epl-v20.html. | 5 | * http://www.eclipse.org/legal/epl-v20.html. |
6 | * | 6 | * |
7 | * SPDX-License-Identifier: EPL-2.0 | 7 | * SPDX-License-Identifier: EPL-2.0 |
8 | *******************************************************************************/ | 8 | *******************************************************************************/ |
9 | 9 | ||
10 | package tools.refinery.viatra.runtime.base.itc.alg.misc.topsort; | 10 | package tools.refinery.viatra.runtime.rete.itc.alg.misc.topsort; |
11 | 11 | ||
12 | import java.util.HashSet; | 12 | import tools.refinery.viatra.runtime.rete.itc.igraph.IGraphDataSource; |
13 | import java.util.LinkedList; | ||
14 | import java.util.List; | ||
15 | import java.util.Set; | ||
16 | import java.util.Stack; | ||
17 | 13 | ||
18 | import tools.refinery.viatra.runtime.base.itc.igraph.IGraphDataSource; | 14 | import java.util.*; |
19 | 15 | ||
20 | /** | 16 | /** |
21 | * @since 1.6 | 17 | * @since 1.6 |
@@ -23,7 +19,7 @@ import tools.refinery.viatra.runtime.base.itc.igraph.IGraphDataSource; | |||
23 | public class TopologicalSorting { | 19 | public class TopologicalSorting { |
24 | 20 | ||
25 | private TopologicalSorting() {/*Utility class constructor*/} | 21 | private TopologicalSorting() {/*Utility class constructor*/} |
26 | 22 | ||
27 | private static final class Pair<T> { | 23 | private static final class Pair<T> { |
28 | public T element; | 24 | public T element; |
29 | public boolean isParent; | 25 | public boolean isParent; |
@@ -35,9 +31,9 @@ public class TopologicalSorting { | |||
35 | } | 31 | } |
36 | 32 | ||
37 | /** | 33 | /** |
38 | * Returns a topological ordering for the given graph data source. | 34 | * Returns a topological ordering for the given graph data source. |
39 | * Output format: if there is an a -> b (transitive) reachability, then node <code>a</code> will come before node <code>b</code> in the resulting list. | 35 | * Output format: if there is an a -> b (transitive) reachability, then node <code>a</code> will come before node <code>b</code> in the resulting list. |
40 | * | 36 | * |
41 | * @param gds the graph data source | 37 | * @param gds the graph data source |
42 | * @return a topological ordering | 38 | * @return a topological ordering |
43 | */ | 39 | */ |
@@ -48,13 +44,13 @@ public class TopologicalSorting { | |||
48 | 44 | ||
49 | for (final T node : gds.getAllNodes()) { | 45 | for (final T node : gds.getAllNodes()) { |
50 | if (!visited.contains(node)) { | 46 | if (!visited.contains(node)) { |
51 | dfsStack.push(new Pair<T>(node, false)); | 47 | dfsStack.push(new Pair<T>(node, false)); |
52 | } | 48 | } |
53 | 49 | ||
54 | while (!dfsStack.isEmpty()) { | 50 | while (!dfsStack.isEmpty()) { |
55 | final Pair<T> head = dfsStack.pop(); | 51 | final Pair<T> head = dfsStack.pop(); |
56 | final T source = head.element; | 52 | final T source = head.element; |
57 | 53 | ||
58 | if (head.isParent) { | 54 | if (head.isParent) { |
59 | // we have already seen source, push it to the resulting stack | 55 | // we have already seen source, push it to the resulting stack |
60 | result.addFirst(source); | 56 | result.addFirst(source); |
@@ -62,7 +58,7 @@ public class TopologicalSorting { | |||
62 | // first time we see source, continue with its children | 58 | // first time we see source, continue with its children |
63 | visited.add(source); | 59 | visited.add(source); |
64 | dfsStack.push(new Pair<T>(source, true)); | 60 | dfsStack.push(new Pair<T>(source, true)); |
65 | 61 | ||
66 | for (final T target : gds.getTargetNodes(source).distinctValues()) { | 62 | for (final T target : gds.getTargetNodes(source).distinctValues()) { |
67 | if (!visited.contains(target)) { | 63 | if (!visited.contains(target)) { |
68 | dfsStack.push(new Pair<T>(target, false)); | 64 | dfsStack.push(new Pair<T>(target, false)); |
diff --git a/subprojects/viatra-runtime/src/main/java/tools/refinery/viatra/runtime/base/itc/alg/representative/RepresentativeElectionAlgorithm.java b/subprojects/viatra-runtime-rete/src/main/java/tools/refinery/viatra/runtime/rete/itc/alg/representative/RepresentativeElectionAlgorithm.java index 51015404..5343f956 100644 --- a/subprojects/viatra-runtime/src/main/java/tools/refinery/viatra/runtime/base/itc/alg/representative/RepresentativeElectionAlgorithm.java +++ b/subprojects/viatra-runtime-rete/src/main/java/tools/refinery/viatra/runtime/rete/itc/alg/representative/RepresentativeElectionAlgorithm.java | |||
@@ -3,10 +3,10 @@ | |||
3 | * | 3 | * |
4 | * SPDX-License-Identifier: EPL-2.0 | 4 | * SPDX-License-Identifier: EPL-2.0 |
5 | */ | 5 | */ |
6 | package tools.refinery.viatra.runtime.base.itc.alg.representative; | 6 | package tools.refinery.viatra.runtime.rete.itc.alg.representative; |
7 | 7 | ||
8 | import tools.refinery.viatra.runtime.base.itc.graphimpl.Graph; | 8 | import tools.refinery.viatra.runtime.rete.itc.graphimpl.Graph; |
9 | import tools.refinery.viatra.runtime.base.itc.igraph.IGraphObserver; | 9 | import tools.refinery.viatra.runtime.rete.itc.igraph.IGraphObserver; |
10 | import tools.refinery.viatra.runtime.matchers.util.Direction; | 10 | import tools.refinery.viatra.runtime.matchers.util.Direction; |
11 | 11 | ||
12 | import java.util.HashMap; | 12 | import java.util.HashMap; |
diff --git a/subprojects/viatra-runtime/src/main/java/tools/refinery/viatra/runtime/base/itc/alg/representative/RepresentativeObserver.java b/subprojects/viatra-runtime-rete/src/main/java/tools/refinery/viatra/runtime/rete/itc/alg/representative/RepresentativeObserver.java index 93cce1ea..6b772fa8 100644 --- a/subprojects/viatra-runtime/src/main/java/tools/refinery/viatra/runtime/base/itc/alg/representative/RepresentativeObserver.java +++ b/subprojects/viatra-runtime-rete/src/main/java/tools/refinery/viatra/runtime/rete/itc/alg/representative/RepresentativeObserver.java | |||
@@ -3,7 +3,7 @@ | |||
3 | * | 3 | * |
4 | * SPDX-License-Identifier: EPL-2.0 | 4 | * SPDX-License-Identifier: EPL-2.0 |
5 | */ | 5 | */ |
6 | package tools.refinery.viatra.runtime.base.itc.alg.representative; | 6 | package tools.refinery.viatra.runtime.rete.itc.alg.representative; |
7 | 7 | ||
8 | import tools.refinery.viatra.runtime.matchers.util.Direction; | 8 | import tools.refinery.viatra.runtime.matchers.util.Direction; |
9 | 9 | ||
diff --git a/subprojects/viatra-runtime/src/main/java/tools/refinery/viatra/runtime/base/itc/alg/representative/StronglyConnectedComponentAlgorithm.java b/subprojects/viatra-runtime-rete/src/main/java/tools/refinery/viatra/runtime/rete/itc/alg/representative/StronglyConnectedComponentAlgorithm.java index ba42bb13..4acb2b77 100644 --- a/subprojects/viatra-runtime/src/main/java/tools/refinery/viatra/runtime/base/itc/alg/representative/StronglyConnectedComponentAlgorithm.java +++ b/subprojects/viatra-runtime-rete/src/main/java/tools/refinery/viatra/runtime/rete/itc/alg/representative/StronglyConnectedComponentAlgorithm.java | |||
@@ -3,12 +3,12 @@ | |||
3 | * | 3 | * |
4 | * SPDX-License-Identifier: EPL-2.0 | 4 | * SPDX-License-Identifier: EPL-2.0 |
5 | */ | 5 | */ |
6 | package tools.refinery.viatra.runtime.base.itc.alg.representative; | 6 | package tools.refinery.viatra.runtime.rete.itc.alg.representative; |
7 | 7 | ||
8 | import tools.refinery.viatra.runtime.base.itc.alg.misc.GraphHelper; | 8 | import tools.refinery.viatra.runtime.rete.itc.alg.misc.GraphHelper; |
9 | import tools.refinery.viatra.runtime.base.itc.alg.misc.bfs.BFS; | 9 | import tools.refinery.viatra.runtime.rete.itc.alg.misc.bfs.BFS; |
10 | import tools.refinery.viatra.runtime.base.itc.alg.misc.scc.SCC; | 10 | import tools.refinery.viatra.runtime.rete.itc.alg.misc.scc.SCC; |
11 | import tools.refinery.viatra.runtime.base.itc.graphimpl.Graph; | 11 | import tools.refinery.viatra.runtime.rete.itc.graphimpl.Graph; |
12 | 12 | ||
13 | import java.util.Collection; | 13 | import java.util.Collection; |
14 | import java.util.Set; | 14 | import java.util.Set; |
diff --git a/subprojects/viatra-runtime/src/main/java/tools/refinery/viatra/runtime/base/itc/alg/representative/WeaklyConnectedComponentAlgorithm.java b/subprojects/viatra-runtime-rete/src/main/java/tools/refinery/viatra/runtime/rete/itc/alg/representative/WeaklyConnectedComponentAlgorithm.java index 22159499..704f0235 100644 --- a/subprojects/viatra-runtime/src/main/java/tools/refinery/viatra/runtime/base/itc/alg/representative/WeaklyConnectedComponentAlgorithm.java +++ b/subprojects/viatra-runtime-rete/src/main/java/tools/refinery/viatra/runtime/rete/itc/alg/representative/WeaklyConnectedComponentAlgorithm.java | |||
@@ -3,9 +3,9 @@ | |||
3 | * | 3 | * |
4 | * SPDX-License-Identifier: EPL-2.0 | 4 | * SPDX-License-Identifier: EPL-2.0 |
5 | */ | 5 | */ |
6 | package tools.refinery.viatra.runtime.base.itc.alg.representative; | 6 | package tools.refinery.viatra.runtime.rete.itc.alg.representative; |
7 | 7 | ||
8 | import tools.refinery.viatra.runtime.base.itc.graphimpl.Graph; | 8 | import tools.refinery.viatra.runtime.rete.itc.graphimpl.Graph; |
9 | 9 | ||
10 | import java.util.ArrayDeque; | 10 | import java.util.ArrayDeque; |
11 | import java.util.HashSet; | 11 | import java.util.HashSet; |
diff --git a/subprojects/viatra-runtime/src/main/java/tools/refinery/viatra/runtime/base/itc/alg/util/CollectionHelper.java b/subprojects/viatra-runtime-rete/src/main/java/tools/refinery/viatra/runtime/rete/itc/alg/util/CollectionHelper.java index c9b3cafa..6655be6d 100644 --- a/subprojects/viatra-runtime/src/main/java/tools/refinery/viatra/runtime/base/itc/alg/util/CollectionHelper.java +++ b/subprojects/viatra-runtime-rete/src/main/java/tools/refinery/viatra/runtime/rete/itc/alg/util/CollectionHelper.java | |||
@@ -3,27 +3,27 @@ | |||
3 | * This program and the accompanying materials are made available under the | 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 | 4 | * terms of the Eclipse Public License v. 2.0 which is available at |
5 | * http://www.eclipse.org/legal/epl-v20.html. | 5 | * http://www.eclipse.org/legal/epl-v20.html. |
6 | * | 6 | * |
7 | * SPDX-License-Identifier: EPL-2.0 | 7 | * SPDX-License-Identifier: EPL-2.0 |
8 | *******************************************************************************/ | 8 | *******************************************************************************/ |
9 | package tools.refinery.viatra.runtime.base.itc.alg.util; | 9 | package tools.refinery.viatra.runtime.rete.itc.alg.util; |
10 | |||
11 | import java.util.Set; | ||
12 | 10 | ||
13 | import tools.refinery.viatra.runtime.matchers.util.CollectionsFactory; | 11 | import tools.refinery.viatra.runtime.matchers.util.CollectionsFactory; |
14 | 12 | ||
13 | import java.util.Set; | ||
14 | |||
15 | /** | 15 | /** |
16 | * @author Tamas Szabo | 16 | * @author Tamas Szabo |
17 | * | 17 | * |
18 | */ | 18 | */ |
19 | public class CollectionHelper { | 19 | public class CollectionHelper { |
20 | 20 | ||
21 | private CollectionHelper() {/*Utility class constructor*/} | 21 | private CollectionHelper() {/*Utility class constructor*/} |
22 | 22 | ||
23 | /** | 23 | /** |
24 | * Returns the intersection of two sets. It calls {@link Set#retainAll(java.util.Collection)} but returns a new set | 24 | * Returns the intersection of two sets. It calls {@link Set#retainAll(java.util.Collection)} but returns a new set |
25 | * containing the elements of the intersection. | 25 | * containing the elements of the intersection. |
26 | * | 26 | * |
27 | * @param set1 | 27 | * @param set1 |
28 | * the first set (can be null, interpreted as empty) | 28 | * the first set (can be null, interpreted as empty) |
29 | * @param set2 | 29 | * @param set2 |
@@ -32,19 +32,19 @@ public class CollectionHelper { | |||
32 | * @since 1.7 | 32 | * @since 1.7 |
33 | */ | 33 | */ |
34 | public static <V> Set<V> intersection(Set<V> set1, Set<V> set2) { | 34 | public static <V> Set<V> intersection(Set<V> set1, Set<V> set2) { |
35 | if (set1 == null || set2 == null) | 35 | if (set1 == null || set2 == null) |
36 | return CollectionsFactory.createSet(); | 36 | return CollectionsFactory.createSet(); |
37 | 37 | ||
38 | Set<V> intersection = CollectionsFactory.createSet(set1); | 38 | Set<V> intersection = CollectionsFactory.createSet(set1); |
39 | intersection.retainAll(set2); | 39 | intersection.retainAll(set2); |
40 | return intersection; | 40 | return intersection; |
41 | } | 41 | } |
42 | 42 | ||
43 | 43 | ||
44 | /** | 44 | /** |
45 | * Returns the difference of two sets (S1\S2). It calls {@link Set#removeAll(java.util.Collection)} but returns a | 45 | * Returns the difference of two sets (S1\S2). It calls {@link Set#removeAll(java.util.Collection)} but returns a |
46 | * new set containing the elements of the difference. | 46 | * new set containing the elements of the difference. |
47 | * | 47 | * |
48 | * @param set1 | 48 | * @param set1 |
49 | * the first set (can be null, interpreted as empty) | 49 | * the first set (can be null, interpreted as empty) |
50 | * @param set2 | 50 | * @param set2 |
@@ -55,10 +55,10 @@ public class CollectionHelper { | |||
55 | public static <V> Set<V> difference(Set<V> set1, Set<V> set2) { | 55 | public static <V> Set<V> difference(Set<V> set1, Set<V> set2) { |
56 | if (set1 == null) | 56 | if (set1 == null) |
57 | return CollectionsFactory.createSet(); | 57 | return CollectionsFactory.createSet(); |
58 | 58 | ||
59 | Set<V> difference = CollectionsFactory.createSet(set1); | 59 | Set<V> difference = CollectionsFactory.createSet(set1); |
60 | if (set2 != null) difference.removeAll(set2); | 60 | if (set2 != null) difference.removeAll(set2); |
61 | return difference; | 61 | return difference; |
62 | } | 62 | } |
63 | 63 | ||
64 | } | 64 | } |
diff --git a/subprojects/viatra-runtime/src/main/java/tools/refinery/viatra/runtime/base/itc/graphimpl/DotGenerator.java b/subprojects/viatra-runtime-rete/src/main/java/tools/refinery/viatra/runtime/rete/itc/graphimpl/DotGenerator.java index 0e21f323..f7f6b5ed 100644 --- a/subprojects/viatra-runtime/src/main/java/tools/refinery/viatra/runtime/base/itc/graphimpl/DotGenerator.java +++ b/subprojects/viatra-runtime-rete/src/main/java/tools/refinery/viatra/runtime/rete/itc/graphimpl/DotGenerator.java | |||
@@ -6,10 +6,10 @@ | |||
6 | * | 6 | * |
7 | * SPDX-License-Identifier: EPL-2.0 | 7 | * SPDX-License-Identifier: EPL-2.0 |
8 | *******************************************************************************/ | 8 | *******************************************************************************/ |
9 | package tools.refinery.viatra.runtime.base.itc.graphimpl; | 9 | package tools.refinery.viatra.runtime.rete.itc.graphimpl; |
10 | 10 | ||
11 | import tools.refinery.viatra.runtime.base.itc.alg.misc.scc.SCC; | 11 | import tools.refinery.viatra.runtime.rete.itc.alg.misc.scc.SCC; |
12 | import tools.refinery.viatra.runtime.base.itc.alg.misc.scc.SCCResult; | 12 | import tools.refinery.viatra.runtime.rete.itc.alg.misc.scc.SCCResult; |
13 | import tools.refinery.viatra.runtime.matchers.util.IMemoryView; | 13 | import tools.refinery.viatra.runtime.matchers.util.IMemoryView; |
14 | 14 | ||
15 | import java.util.HashMap; | 15 | import java.util.HashMap; |
diff --git a/subprojects/viatra-runtime/src/main/java/tools/refinery/viatra/runtime/base/itc/graphimpl/Graph.java b/subprojects/viatra-runtime-rete/src/main/java/tools/refinery/viatra/runtime/rete/itc/graphimpl/Graph.java index 4267579c..91604cb2 100644 --- a/subprojects/viatra-runtime/src/main/java/tools/refinery/viatra/runtime/base/itc/graphimpl/Graph.java +++ b/subprojects/viatra-runtime-rete/src/main/java/tools/refinery/viatra/runtime/rete/itc/graphimpl/Graph.java | |||
@@ -7,11 +7,11 @@ | |||
7 | * SPDX-License-Identifier: EPL-2.0 | 7 | * SPDX-License-Identifier: EPL-2.0 |
8 | *******************************************************************************/ | 8 | *******************************************************************************/ |
9 | 9 | ||
10 | package tools.refinery.viatra.runtime.base.itc.graphimpl; | 10 | package tools.refinery.viatra.runtime.rete.itc.graphimpl; |
11 | 11 | ||
12 | import tools.refinery.viatra.runtime.base.itc.igraph.IGraphDataSource; | 12 | import tools.refinery.viatra.runtime.rete.itc.igraph.IGraphDataSource; |
13 | import tools.refinery.viatra.runtime.base.itc.igraph.IGraphObserver; | 13 | import tools.refinery.viatra.runtime.rete.itc.igraph.IGraphObserver; |
14 | import tools.refinery.viatra.runtime.base.itc.igraph.IBiDirectionalGraphDataSource; | 14 | import tools.refinery.viatra.runtime.rete.itc.igraph.IBiDirectionalGraphDataSource; |
15 | import tools.refinery.viatra.runtime.matchers.util.CollectionsFactory; | 15 | import tools.refinery.viatra.runtime.matchers.util.CollectionsFactory; |
16 | import tools.refinery.viatra.runtime.matchers.util.CollectionsFactory.MemoryType; | 16 | import tools.refinery.viatra.runtime.matchers.util.CollectionsFactory.MemoryType; |
17 | import tools.refinery.viatra.runtime.matchers.util.IMemoryView; | 17 | import tools.refinery.viatra.runtime.matchers.util.IMemoryView; |
diff --git a/subprojects/viatra-runtime/src/main/java/tools/refinery/viatra/runtime/base/itc/igraph/IBiDirectionalGraphDataSource.java b/subprojects/viatra-runtime-rete/src/main/java/tools/refinery/viatra/runtime/rete/itc/igraph/IBiDirectionalGraphDataSource.java index 64659447..4fcaa71f 100644 --- a/subprojects/viatra-runtime/src/main/java/tools/refinery/viatra/runtime/base/itc/igraph/IBiDirectionalGraphDataSource.java +++ b/subprojects/viatra-runtime-rete/src/main/java/tools/refinery/viatra/runtime/rete/itc/igraph/IBiDirectionalGraphDataSource.java | |||
@@ -3,35 +3,35 @@ | |||
3 | * This program and the accompanying materials are made available under the | 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 | 4 | * terms of the Eclipse Public License v. 2.0 which is available at |
5 | * http://www.eclipse.org/legal/epl-v20.html. | 5 | * http://www.eclipse.org/legal/epl-v20.html. |
6 | * | 6 | * |
7 | * SPDX-License-Identifier: EPL-2.0 | 7 | * SPDX-License-Identifier: EPL-2.0 |
8 | *******************************************************************************/ | 8 | *******************************************************************************/ |
9 | 9 | ||
10 | package tools.refinery.viatra.runtime.base.itc.igraph; | 10 | package tools.refinery.viatra.runtime.rete.itc.igraph; |
11 | 11 | ||
12 | import tools.refinery.viatra.runtime.matchers.util.IMemoryView; | 12 | import tools.refinery.viatra.runtime.matchers.util.IMemoryView; |
13 | import tools.refinery.viatra.runtime.matchers.util.IMultiset; | 13 | import tools.refinery.viatra.runtime.matchers.util.IMultiset; |
14 | 14 | ||
15 | /** | 15 | /** |
16 | * A bi-directional graph data source supports all operations that an {@link IGraphDataSource} does, but it | 16 | * A bi-directional graph data source supports all operations that an {@link IGraphDataSource} does, but it |
17 | * also makes it possible to query the incoming edges of nodes, not only the outgoing edges. | 17 | * also makes it possible to query the incoming edges of nodes, not only the outgoing edges. |
18 | * | 18 | * |
19 | * @author Tamas Szabo | 19 | * @author Tamas Szabo |
20 | * | 20 | * |
21 | * @param <V> the type of the nodes in the graph | 21 | * @param <V> the type of the nodes in the graph |
22 | */ | 22 | */ |
23 | public interface IBiDirectionalGraphDataSource<V> extends IGraphDataSource<V> { | 23 | public interface IBiDirectionalGraphDataSource<V> extends IGraphDataSource<V> { |
24 | 24 | ||
25 | /** | 25 | /** |
26 | * Returns the source nodes for the given target node. | 26 | * Returns the source nodes for the given target node. |
27 | * The returned data structure is an {@link IMultiset} because of potential parallel edges in the graph data source. | 27 | * The returned data structure is an {@link IMultiset} because of potential parallel edges in the graph data source. |
28 | * | 28 | * |
29 | * The method must not return null. | 29 | * The method must not return null. |
30 | * | 30 | * |
31 | * @param target the target node | 31 | * @param target the target node |
32 | * @return the multiset of source nodes | 32 | * @return the multiset of source nodes |
33 | * @since 2.0 | 33 | * @since 2.0 |
34 | */ | 34 | */ |
35 | public IMemoryView<V> getSourceNodes(V target); | 35 | public IMemoryView<V> getSourceNodes(V target); |
36 | 36 | ||
37 | } | 37 | } |
diff --git a/subprojects/viatra-runtime/src/main/java/tools/refinery/viatra/runtime/base/itc/igraph/IBiDirectionalWrapper.java b/subprojects/viatra-runtime-rete/src/main/java/tools/refinery/viatra/runtime/rete/itc/igraph/IBiDirectionalWrapper.java index becab0eb..c4315ca2 100644 --- a/subprojects/viatra-runtime/src/main/java/tools/refinery/viatra/runtime/base/itc/igraph/IBiDirectionalWrapper.java +++ b/subprojects/viatra-runtime-rete/src/main/java/tools/refinery/viatra/runtime/rete/itc/igraph/IBiDirectionalWrapper.java | |||
@@ -3,11 +3,11 @@ | |||
3 | * This program and the accompanying materials are made available under the | 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 | 4 | * terms of the Eclipse Public License v. 2.0 which is available at |
5 | * http://www.eclipse.org/legal/epl-v20.html. | 5 | * http://www.eclipse.org/legal/epl-v20.html. |
6 | * | 6 | * |
7 | * SPDX-License-Identifier: EPL-2.0 | 7 | * SPDX-License-Identifier: EPL-2.0 |
8 | *******************************************************************************/ | 8 | *******************************************************************************/ |
9 | 9 | ||
10 | package tools.refinery.viatra.runtime.base.itc.igraph; | 10 | package tools.refinery.viatra.runtime.rete.itc.igraph; |
11 | 11 | ||
12 | import java.util.Set; | 12 | import java.util.Set; |
13 | 13 | ||
@@ -20,7 +20,7 @@ import tools.refinery.viatra.runtime.matchers.util.IMultiLookup; | |||
20 | * This class can be used to wrap an {@link IGraphDataSource} into an {@link IBiDirectionalGraphDataSource}. This class | 20 | * This class can be used to wrap an {@link IGraphDataSource} into an {@link IBiDirectionalGraphDataSource}. This class |
21 | * provides support for the retrieval of source nodes for a given target which is not supported by standard | 21 | * provides support for the retrieval of source nodes for a given target which is not supported by standard |
22 | * {@link IGraphDataSource} implementations. | 22 | * {@link IGraphDataSource} implementations. |
23 | * | 23 | * |
24 | * @author Tamas Szabo | 24 | * @author Tamas Szabo |
25 | * | 25 | * |
26 | * @param <V> | 26 | * @param <V> |
diff --git a/subprojects/viatra-runtime/src/main/java/tools/refinery/viatra/runtime/base/itc/igraph/IGraphDataSource.java b/subprojects/viatra-runtime-rete/src/main/java/tools/refinery/viatra/runtime/rete/itc/igraph/IGraphDataSource.java index 3fa65936..9159a692 100644 --- a/subprojects/viatra-runtime/src/main/java/tools/refinery/viatra/runtime/base/itc/igraph/IGraphDataSource.java +++ b/subprojects/viatra-runtime-rete/src/main/java/tools/refinery/viatra/runtime/rete/itc/igraph/IGraphDataSource.java | |||
@@ -7,7 +7,7 @@ | |||
7 | * SPDX-License-Identifier: EPL-2.0 | 7 | * SPDX-License-Identifier: EPL-2.0 |
8 | *******************************************************************************/ | 8 | *******************************************************************************/ |
9 | 9 | ||
10 | package tools.refinery.viatra.runtime.base.itc.igraph; | 10 | package tools.refinery.viatra.runtime.rete.itc.igraph; |
11 | 11 | ||
12 | import tools.refinery.viatra.runtime.matchers.util.IMemoryView; | 12 | import tools.refinery.viatra.runtime.matchers.util.IMemoryView; |
13 | import tools.refinery.viatra.runtime.matchers.util.IMultiset; | 13 | import tools.refinery.viatra.runtime.matchers.util.IMultiset; |
diff --git a/subprojects/viatra-runtime/src/main/java/tools/refinery/viatra/runtime/base/itc/igraph/IGraphObserver.java b/subprojects/viatra-runtime-rete/src/main/java/tools/refinery/viatra/runtime/rete/itc/igraph/IGraphObserver.java index 5cb2d9fa..a282216d 100644 --- a/subprojects/viatra-runtime/src/main/java/tools/refinery/viatra/runtime/base/itc/igraph/IGraphObserver.java +++ b/subprojects/viatra-runtime-rete/src/main/java/tools/refinery/viatra/runtime/rete/itc/igraph/IGraphObserver.java | |||
@@ -3,23 +3,23 @@ | |||
3 | * This program and the accompanying materials are made available under the | 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 | 4 | * terms of the Eclipse Public License v. 2.0 which is available at |
5 | * http://www.eclipse.org/legal/epl-v20.html. | 5 | * http://www.eclipse.org/legal/epl-v20.html. |
6 | * | 6 | * |
7 | * SPDX-License-Identifier: EPL-2.0 | 7 | * SPDX-License-Identifier: EPL-2.0 |
8 | *******************************************************************************/ | 8 | *******************************************************************************/ |
9 | 9 | ||
10 | package tools.refinery.viatra.runtime.base.itc.igraph; | 10 | package tools.refinery.viatra.runtime.rete.itc.igraph; |
11 | 11 | ||
12 | /** | 12 | /** |
13 | * Interface GraphObserver is used to observ the changes in a graph; edge and node insertion/deleteion. | 13 | * Interface GraphObserver is used to observ the changes in a graph; edge and node insertion/deleteion. |
14 | * | 14 | * |
15 | * @author Tamas Szabo | 15 | * @author Tamas Szabo |
16 | * | 16 | * |
17 | */ | 17 | */ |
18 | public interface IGraphObserver<V> { | 18 | public interface IGraphObserver<V> { |
19 | 19 | ||
20 | /** | 20 | /** |
21 | * Used to notify when an edge is inserted into the graph. | 21 | * Used to notify when an edge is inserted into the graph. |
22 | * | 22 | * |
23 | * @param source | 23 | * @param source |
24 | * the source of the edge | 24 | * the source of the edge |
25 | * @param target | 25 | * @param target |
@@ -29,7 +29,7 @@ public interface IGraphObserver<V> { | |||
29 | 29 | ||
30 | /** | 30 | /** |
31 | * Used to notify when an edge is deleted from the graph. | 31 | * Used to notify when an edge is deleted from the graph. |
32 | * | 32 | * |
33 | * @param source | 33 | * @param source |
34 | * the source of the edge | 34 | * the source of the edge |
35 | * @param target | 35 | * @param target |
@@ -39,7 +39,7 @@ public interface IGraphObserver<V> { | |||
39 | 39 | ||
40 | /** | 40 | /** |
41 | * Used to notify when a node is inserted into the graph. | 41 | * Used to notify when a node is inserted into the graph. |
42 | * | 42 | * |
43 | * @param n | 43 | * @param n |
44 | * the node | 44 | * the node |
45 | */ | 45 | */ |
@@ -47,7 +47,7 @@ public interface IGraphObserver<V> { | |||
47 | 47 | ||
48 | /** | 48 | /** |
49 | * Used to notify when a node is deleted from the graph. | 49 | * Used to notify when a node is deleted from the graph. |
50 | * | 50 | * |
51 | * @param n | 51 | * @param n |
52 | * the node | 52 | * the node |
53 | */ | 53 | */ |
diff --git a/subprojects/viatra-runtime/src/main/java/tools/refinery/viatra/runtime/base/itc/igraph/ITcDataSource.java b/subprojects/viatra-runtime-rete/src/main/java/tools/refinery/viatra/runtime/rete/itc/igraph/ITcDataSource.java index 5924b723..5ede600f 100644 --- a/subprojects/viatra-runtime/src/main/java/tools/refinery/viatra/runtime/base/itc/igraph/ITcDataSource.java +++ b/subprojects/viatra-runtime-rete/src/main/java/tools/refinery/viatra/runtime/rete/itc/igraph/ITcDataSource.java | |||
@@ -3,21 +3,21 @@ | |||
3 | * This program and the accompanying materials are made available under the | 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 | 4 | * terms of the Eclipse Public License v. 2.0 which is available at |
5 | * http://www.eclipse.org/legal/epl-v20.html. | 5 | * http://www.eclipse.org/legal/epl-v20.html. |
6 | * | 6 | * |
7 | * SPDX-License-Identifier: EPL-2.0 | 7 | * SPDX-License-Identifier: EPL-2.0 |
8 | *******************************************************************************/ | 8 | *******************************************************************************/ |
9 | 9 | ||
10 | package tools.refinery.viatra.runtime.base.itc.igraph; | 10 | package tools.refinery.viatra.runtime.rete.itc.igraph; |
11 | 11 | ||
12 | import java.util.Set; | 12 | import java.util.Set; |
13 | 13 | ||
14 | import tools.refinery.viatra.runtime.base.itc.alg.misc.IGraphPathFinder; | 14 | import tools.refinery.viatra.runtime.rete.itc.alg.misc.IGraphPathFinder; |
15 | 15 | ||
16 | /** | 16 | /** |
17 | * This interface defines those methods that a transitive reachability data source should provide. | 17 | * This interface defines those methods that a transitive reachability data source should provide. |
18 | * | 18 | * |
19 | * @author Tamas Szabo | 19 | * @author Tamas Szabo |
20 | * | 20 | * |
21 | * @param <V> | 21 | * @param <V> |
22 | * the type parameter of the node | 22 | * the type parameter of the node |
23 | */ | 23 | */ |
@@ -25,7 +25,7 @@ public interface ITcDataSource<V> { | |||
25 | 25 | ||
26 | /** | 26 | /** |
27 | * Attach a transitive closure relation observer. | 27 | * Attach a transitive closure relation observer. |
28 | * | 28 | * |
29 | * @param to | 29 | * @param to |
30 | * the observer object | 30 | * the observer object |
31 | */ | 31 | */ |
@@ -33,7 +33,7 @@ public interface ITcDataSource<V> { | |||
33 | 33 | ||
34 | /** | 34 | /** |
35 | * Detach a transitive closure relation observer. | 35 | * Detach a transitive closure relation observer. |
36 | * | 36 | * |
37 | * @param to | 37 | * @param to |
38 | * the observer object | 38 | * the observer object |
39 | */ | 39 | */ |
@@ -41,7 +41,7 @@ public interface ITcDataSource<V> { | |||
41 | 41 | ||
42 | /** | 42 | /** |
43 | * Returns all nodes which are reachable from the source node. | 43 | * Returns all nodes which are reachable from the source node. |
44 | * | 44 | * |
45 | * @param source | 45 | * @param source |
46 | * the source node | 46 | * the source node |
47 | * @return the set of target nodes | 47 | * @return the set of target nodes |
@@ -50,7 +50,7 @@ public interface ITcDataSource<V> { | |||
50 | 50 | ||
51 | /** | 51 | /** |
52 | * Returns all nodes from which the target node is reachable. | 52 | * Returns all nodes from which the target node is reachable. |
53 | * | 53 | * |
54 | * @param target | 54 | * @param target |
55 | * the target node | 55 | * the target node |
56 | * @return the set of source nodes | 56 | * @return the set of source nodes |
@@ -59,7 +59,7 @@ public interface ITcDataSource<V> { | |||
59 | 59 | ||
60 | /** | 60 | /** |
61 | * Returns true if the target node is reachable from the source node. | 61 | * Returns true if the target node is reachable from the source node. |
62 | * | 62 | * |
63 | * @param source | 63 | * @param source |
64 | * the source node | 64 | * the source node |
65 | * @param target | 65 | * @param target |
@@ -67,14 +67,14 @@ public interface ITcDataSource<V> { | |||
67 | * @return true if target is reachable from source, false otherwise | 67 | * @return true if target is reachable from source, false otherwise |
68 | */ | 68 | */ |
69 | public boolean isReachable(V source, V target); | 69 | public boolean isReachable(V source, V target); |
70 | 70 | ||
71 | /** | 71 | /** |
72 | * The returned {@link IGraphPathFinder} can be used to retrieve paths between nodes using transitive reachability. | 72 | * The returned {@link IGraphPathFinder} can be used to retrieve paths between nodes using transitive reachability. |
73 | * | 73 | * |
74 | * @return a path finder for the graph. | 74 | * @return a path finder for the graph. |
75 | */ | 75 | */ |
76 | public IGraphPathFinder<V> getPathFinder(); | 76 | public IGraphPathFinder<V> getPathFinder(); |
77 | 77 | ||
78 | /** | 78 | /** |
79 | * Call this method to properly dispose the data structures of a transitive closure algorithm. | 79 | * Call this method to properly dispose the data structures of a transitive closure algorithm. |
80 | */ | 80 | */ |
diff --git a/subprojects/viatra-runtime/src/main/java/tools/refinery/viatra/runtime/base/itc/igraph/ITcObserver.java b/subprojects/viatra-runtime-rete/src/main/java/tools/refinery/viatra/runtime/rete/itc/igraph/ITcObserver.java index fded53f1..74e0cb75 100644 --- a/subprojects/viatra-runtime/src/main/java/tools/refinery/viatra/runtime/base/itc/igraph/ITcObserver.java +++ b/subprojects/viatra-runtime-rete/src/main/java/tools/refinery/viatra/runtime/rete/itc/igraph/ITcObserver.java | |||
@@ -3,23 +3,23 @@ | |||
3 | * This program and the accompanying materials are made available under the | 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 | 4 | * terms of the Eclipse Public License v. 2.0 which is available at |
5 | * http://www.eclipse.org/legal/epl-v20.html. | 5 | * http://www.eclipse.org/legal/epl-v20.html. |
6 | * | 6 | * |
7 | * SPDX-License-Identifier: EPL-2.0 | 7 | * SPDX-License-Identifier: EPL-2.0 |
8 | *******************************************************************************/ | 8 | *******************************************************************************/ |
9 | 9 | ||
10 | package tools.refinery.viatra.runtime.base.itc.igraph; | 10 | package tools.refinery.viatra.runtime.rete.itc.igraph; |
11 | 11 | ||
12 | /** | 12 | /** |
13 | * Interface ITcObserver is used to observe the changes in a transitive closure relation; tuple insertion/deletion. | 13 | * Interface ITcObserver is used to observe the changes in a transitive closure relation; tuple insertion/deletion. |
14 | * | 14 | * |
15 | * @author Szabo Tamas | 15 | * @author Szabo Tamas |
16 | * | 16 | * |
17 | */ | 17 | */ |
18 | public interface ITcObserver<V> { | 18 | public interface ITcObserver<V> { |
19 | 19 | ||
20 | /** | 20 | /** |
21 | * Used to notify when a tuple is inserted into the transitive closure relation. | 21 | * Used to notify when a tuple is inserted into the transitive closure relation. |
22 | * | 22 | * |
23 | * @param source | 23 | * @param source |
24 | * the source of the tuple | 24 | * the source of the tuple |
25 | * @param target | 25 | * @param target |
@@ -29,7 +29,7 @@ public interface ITcObserver<V> { | |||
29 | 29 | ||
30 | /** | 30 | /** |
31 | * Used to notify when a tuple is deleted from the transitive closure relation. | 31 | * Used to notify when a tuple is deleted from the transitive closure relation. |
32 | * | 32 | * |
33 | * @param source | 33 | * @param source |
34 | * the source of the tuple | 34 | * the source of the tuple |
35 | * @param target | 35 | * @param target |
diff --git a/subprojects/viatra-runtime-rete/src/main/java/tools/refinery/viatra/runtime/rete/network/NodeFactory.java b/subprojects/viatra-runtime-rete/src/main/java/tools/refinery/viatra/runtime/rete/network/NodeFactory.java index 231bdfe5..3e4ea4e0 100644 --- a/subprojects/viatra-runtime-rete/src/main/java/tools/refinery/viatra/runtime/rete/network/NodeFactory.java +++ b/subprojects/viatra-runtime-rete/src/main/java/tools/refinery/viatra/runtime/rete/network/NodeFactory.java | |||
@@ -11,9 +11,9 @@ package tools.refinery.viatra.runtime.rete.network; | |||
11 | 11 | ||
12 | import org.apache.log4j.Logger; | 12 | import org.apache.log4j.Logger; |
13 | import org.eclipse.emf.common.util.EMap; | 13 | import org.eclipse.emf.common.util.EMap; |
14 | import tools.refinery.viatra.runtime.base.itc.alg.representative.RepresentativeElectionAlgorithm; | 14 | import tools.refinery.viatra.runtime.rete.itc.alg.representative.RepresentativeElectionAlgorithm; |
15 | import tools.refinery.viatra.runtime.base.itc.alg.representative.StronglyConnectedComponentAlgorithm; | 15 | import tools.refinery.viatra.runtime.rete.itc.alg.representative.StronglyConnectedComponentAlgorithm; |
16 | import tools.refinery.viatra.runtime.base.itc.alg.representative.WeaklyConnectedComponentAlgorithm; | 16 | import tools.refinery.viatra.runtime.rete.itc.alg.representative.WeaklyConnectedComponentAlgorithm; |
17 | import tools.refinery.viatra.runtime.matchers.context.IPosetComparator; | 17 | import tools.refinery.viatra.runtime.matchers.context.IPosetComparator; |
18 | import tools.refinery.viatra.runtime.matchers.psystem.IExpressionEvaluator; | 18 | import tools.refinery.viatra.runtime.matchers.psystem.IExpressionEvaluator; |
19 | import tools.refinery.viatra.runtime.matchers.psystem.IRelationEvaluator; | 19 | import tools.refinery.viatra.runtime.matchers.psystem.IRelationEvaluator; |
diff --git a/subprojects/viatra-runtime-rete/src/main/java/tools/refinery/viatra/runtime/rete/network/communication/CommunicationTracker.java b/subprojects/viatra-runtime-rete/src/main/java/tools/refinery/viatra/runtime/rete/network/communication/CommunicationTracker.java index 8435a547..d244e644 100644 --- a/subprojects/viatra-runtime-rete/src/main/java/tools/refinery/viatra/runtime/rete/network/communication/CommunicationTracker.java +++ b/subprojects/viatra-runtime-rete/src/main/java/tools/refinery/viatra/runtime/rete/network/communication/CommunicationTracker.java | |||
@@ -3,7 +3,7 @@ | |||
3 | * This program and the accompanying materials are made available under the | 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 | 4 | * terms of the Eclipse Public License v. 2.0 which is available at |
5 | * http://www.eclipse.org/legal/epl-v20.html. | 5 | * http://www.eclipse.org/legal/epl-v20.html. |
6 | * | 6 | * |
7 | * SPDX-License-Identifier: EPL-2.0 | 7 | * SPDX-License-Identifier: EPL-2.0 |
8 | *******************************************************************************/ | 8 | *******************************************************************************/ |
9 | package tools.refinery.viatra.runtime.rete.network.communication; | 9 | package tools.refinery.viatra.runtime.rete.network.communication; |
@@ -16,9 +16,9 @@ import java.util.PriorityQueue; | |||
16 | import java.util.Queue; | 16 | import java.util.Queue; |
17 | import java.util.Set; | 17 | import java.util.Set; |
18 | 18 | ||
19 | import tools.refinery.viatra.runtime.base.itc.alg.incscc.IncSCCAlg; | 19 | import tools.refinery.viatra.runtime.rete.itc.alg.incscc.IncSCCAlg; |
20 | import tools.refinery.viatra.runtime.base.itc.alg.misc.topsort.TopologicalSorting; | 20 | import tools.refinery.viatra.runtime.rete.itc.alg.misc.topsort.TopologicalSorting; |
21 | import tools.refinery.viatra.runtime.base.itc.graphimpl.Graph; | 21 | import tools.refinery.viatra.runtime.rete.itc.graphimpl.Graph; |
22 | import tools.refinery.viatra.runtime.matchers.tuple.TupleMask; | 22 | import tools.refinery.viatra.runtime.matchers.tuple.TupleMask; |
23 | import tools.refinery.viatra.runtime.rete.aggregation.IAggregatorNode; | 23 | import tools.refinery.viatra.runtime.rete.aggregation.IAggregatorNode; |
24 | import tools.refinery.viatra.runtime.rete.boundary.ExternalInputEnumeratorNode; | 24 | import tools.refinery.viatra.runtime.rete.boundary.ExternalInputEnumeratorNode; |
@@ -52,7 +52,7 @@ import tools.refinery.viatra.runtime.rete.single.TrimmerNode; | |||
52 | * precisely, the mailboxes that contain the messages) for the associated {@link ReteContainer}. The ordering is | 52 | * precisely, the mailboxes that contain the messages) for the associated {@link ReteContainer}. The ordering is |
53 | * governed by the strongly connected components in the dependency network and follows a topological sorting scheme; | 53 | * governed by the strongly connected components in the dependency network and follows a topological sorting scheme; |
54 | * those mailboxes will be emptied first whose owner nodes do not depend on other undelivered messages. | 54 | * those mailboxes will be emptied first whose owner nodes do not depend on other undelivered messages. |
55 | * | 55 | * |
56 | * @author Tamas Szabo | 56 | * @author Tamas Szabo |
57 | * @since 1.6 | 57 | * @since 1.6 |
58 | * | 58 | * |
@@ -186,7 +186,7 @@ public abstract class CommunicationTracker { | |||
186 | // or true trimming in its sole parent | 186 | // or true trimming in its sole parent |
187 | directParents.size() == 1 && trueTrimming(directParents.iterator().next())))) && | 187 | directParents.size() == 1 && trueTrimming(directParents.iterator().next())))) && |
188 | // disallow fallthrough: external updates should be stored (if updates are delayed) | 188 | // disallow fallthrough: external updates should be stored (if updates are delayed) |
189 | (!(node instanceof ExternalInputEnumeratorNode)) && | 189 | (!(node instanceof ExternalInputEnumeratorNode)) && |
190 | // disallow fallthrough: RelationEvaluatorNode needs to be notified in batch-style, and the batching is done by the mailbox | 190 | // disallow fallthrough: RelationEvaluatorNode needs to be notified in batch-style, and the batching is done by the mailbox |
191 | // however, it is not the RelationEvaluatorNode itself that is interesting here, as that indirectly uses the BatchingReceiver | 191 | // however, it is not the RelationEvaluatorNode itself that is interesting here, as that indirectly uses the BatchingReceiver |
192 | // so we need to disable fall-through for the BatchingReceiver | 192 | // so we need to disable fall-through for the BatchingReceiver |
@@ -375,7 +375,7 @@ public abstract class CommunicationTracker { | |||
375 | 375 | ||
376 | /** | 376 | /** |
377 | * Unregisters a dependency between source and target. | 377 | * Unregisters a dependency between source and target. |
378 | * | 378 | * |
379 | * @param source | 379 | * @param source |
380 | * the source node | 380 | * the source node |
381 | * @param target | 381 | * @param target |
@@ -416,10 +416,10 @@ public abstract class CommunicationTracker { | |||
416 | } | 416 | } |
417 | 417 | ||
418 | /** | 418 | /** |
419 | * Returns true if the given source-target edge in the communication network acts as a recursion cut point. | 419 | * Returns true if the given source-target edge in the communication network acts as a recursion cut point. |
420 | * The current implementation considers edges leading into {@link ProductionNode}s as cut point iff | 420 | * The current implementation considers edges leading into {@link ProductionNode}s as cut point iff |
421 | * both source and target belong to the same group. | 421 | * both source and target belong to the same group. |
422 | * | 422 | * |
423 | * @param source the source node | 423 | * @param source the source node |
424 | * @param target the target node | 424 | * @param target the target node |
425 | * @return true if the edge is a cut point, false otherwise | 425 | * @return true if the edge is a cut point, false otherwise |
diff --git a/subprojects/viatra-runtime-rete/src/main/java/tools/refinery/viatra/runtime/rete/network/communication/timely/TimelyCommunicationTracker.java b/subprojects/viatra-runtime-rete/src/main/java/tools/refinery/viatra/runtime/rete/network/communication/timely/TimelyCommunicationTracker.java index 1ff69882..79179880 100644 --- a/subprojects/viatra-runtime-rete/src/main/java/tools/refinery/viatra/runtime/rete/network/communication/timely/TimelyCommunicationTracker.java +++ b/subprojects/viatra-runtime-rete/src/main/java/tools/refinery/viatra/runtime/rete/network/communication/timely/TimelyCommunicationTracker.java | |||
@@ -3,7 +3,7 @@ | |||
3 | * This program and the accompanying materials are made available under the | 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 | 4 | * terms of the Eclipse Public License v. 2.0 which is available at |
5 | * http://www.eclipse.org/legal/epl-v20.html. | 5 | * http://www.eclipse.org/legal/epl-v20.html. |
6 | * | 6 | * |
7 | * SPDX-License-Identifier: EPL-2.0 | 7 | * SPDX-License-Identifier: EPL-2.0 |
8 | *******************************************************************************/ | 8 | *******************************************************************************/ |
9 | package tools.refinery.viatra.runtime.rete.network.communication.timely; | 9 | package tools.refinery.viatra.runtime.rete.network.communication.timely; |
@@ -15,8 +15,8 @@ import java.util.Map.Entry; | |||
15 | import java.util.Set; | 15 | import java.util.Set; |
16 | import java.util.function.Function; | 16 | import java.util.function.Function; |
17 | 17 | ||
18 | import tools.refinery.viatra.runtime.base.itc.alg.misc.topsort.TopologicalSorting; | 18 | import tools.refinery.viatra.runtime.rete.itc.alg.misc.topsort.TopologicalSorting; |
19 | import tools.refinery.viatra.runtime.base.itc.graphimpl.Graph; | 19 | import tools.refinery.viatra.runtime.rete.itc.graphimpl.Graph; |
20 | import tools.refinery.viatra.runtime.matchers.util.CollectionsFactory; | 20 | import tools.refinery.viatra.runtime.matchers.util.CollectionsFactory; |
21 | import tools.refinery.viatra.runtime.rete.index.IndexerListener; | 21 | import tools.refinery.viatra.runtime.rete.index.IndexerListener; |
22 | import tools.refinery.viatra.runtime.rete.index.SpecializedProjectionIndexer; | 22 | import tools.refinery.viatra.runtime.rete.index.SpecializedProjectionIndexer; |
@@ -37,7 +37,7 @@ import tools.refinery.viatra.runtime.rete.single.DiscriminatorDispatcherNode; | |||
37 | 37 | ||
38 | /** | 38 | /** |
39 | * Timely (DDF) implementation of the {@link CommunicationTracker}. | 39 | * Timely (DDF) implementation of the {@link CommunicationTracker}. |
40 | * | 40 | * |
41 | * @author Tamas Szabo | 41 | * @author Tamas Szabo |
42 | * @since 2.3 | 42 | * @since 2.3 |
43 | */ | 43 | */ |
diff --git a/subprojects/viatra-runtime-rete/src/main/java/tools/refinery/viatra/runtime/rete/single/RepresentativeElectionNode.java b/subprojects/viatra-runtime-rete/src/main/java/tools/refinery/viatra/runtime/rete/single/RepresentativeElectionNode.java index 6a1e305c..95018c4f 100644 --- a/subprojects/viatra-runtime-rete/src/main/java/tools/refinery/viatra/runtime/rete/single/RepresentativeElectionNode.java +++ b/subprojects/viatra-runtime-rete/src/main/java/tools/refinery/viatra/runtime/rete/single/RepresentativeElectionNode.java | |||
@@ -8,9 +8,9 @@ | |||
8 | *******************************************************************************/ | 8 | *******************************************************************************/ |
9 | package tools.refinery.viatra.runtime.rete.single; | 9 | package tools.refinery.viatra.runtime.rete.single; |
10 | 10 | ||
11 | import tools.refinery.viatra.runtime.base.itc.alg.representative.RepresentativeElectionAlgorithm; | 11 | import tools.refinery.viatra.runtime.rete.itc.alg.representative.RepresentativeElectionAlgorithm; |
12 | import tools.refinery.viatra.runtime.base.itc.alg.representative.RepresentativeObserver; | 12 | import tools.refinery.viatra.runtime.rete.itc.alg.representative.RepresentativeObserver; |
13 | import tools.refinery.viatra.runtime.base.itc.graphimpl.Graph; | 13 | import tools.refinery.viatra.runtime.rete.itc.graphimpl.Graph; |
14 | import tools.refinery.viatra.runtime.matchers.tuple.Tuple; | 14 | import tools.refinery.viatra.runtime.matchers.tuple.Tuple; |
15 | import tools.refinery.viatra.runtime.matchers.tuple.Tuples; | 15 | import tools.refinery.viatra.runtime.matchers.tuple.Tuples; |
16 | import tools.refinery.viatra.runtime.matchers.util.Clearable; | 16 | import tools.refinery.viatra.runtime.matchers.util.Clearable; |
diff --git a/subprojects/viatra-runtime-rete/src/main/java/tools/refinery/viatra/runtime/rete/single/TransitiveClosureNode.java b/subprojects/viatra-runtime-rete/src/main/java/tools/refinery/viatra/runtime/rete/single/TransitiveClosureNode.java index eeead31b..fdda4ef4 100644 --- a/subprojects/viatra-runtime-rete/src/main/java/tools/refinery/viatra/runtime/rete/single/TransitiveClosureNode.java +++ b/subprojects/viatra-runtime-rete/src/main/java/tools/refinery/viatra/runtime/rete/single/TransitiveClosureNode.java | |||
@@ -8,11 +8,11 @@ | |||
8 | *******************************************************************************/ | 8 | *******************************************************************************/ |
9 | package tools.refinery.viatra.runtime.rete.single; | 9 | package tools.refinery.viatra.runtime.rete.single; |
10 | 10 | ||
11 | import tools.refinery.viatra.runtime.base.itc.alg.incscc.IncSCCAlg; | 11 | import tools.refinery.viatra.runtime.rete.itc.alg.incscc.IncSCCAlg; |
12 | import tools.refinery.viatra.runtime.base.itc.alg.misc.Tuple; | 12 | import tools.refinery.viatra.runtime.rete.itc.alg.misc.Tuple; |
13 | import tools.refinery.viatra.runtime.base.itc.graphimpl.Graph; | 13 | import tools.refinery.viatra.runtime.rete.itc.graphimpl.Graph; |
14 | import tools.refinery.viatra.runtime.base.itc.igraph.ITcDataSource; | 14 | import tools.refinery.viatra.runtime.rete.itc.igraph.ITcDataSource; |
15 | import tools.refinery.viatra.runtime.base.itc.igraph.ITcObserver; | 15 | import tools.refinery.viatra.runtime.rete.itc.igraph.ITcObserver; |
16 | import tools.refinery.viatra.runtime.matchers.tuple.Tuples; | 16 | import tools.refinery.viatra.runtime.matchers.tuple.Tuples; |
17 | import tools.refinery.viatra.runtime.matchers.util.Clearable; | 17 | import tools.refinery.viatra.runtime.matchers.util.Clearable; |
18 | import tools.refinery.viatra.runtime.matchers.util.Direction; | 18 | import tools.refinery.viatra.runtime.matchers.util.Direction; |
diff --git a/subprojects/viatra-runtime/src/main/java/tools/refinery/viatra/runtime/base/itc/alg/dred/DRedAlg.java b/subprojects/viatra-runtime/src/main/java/tools/refinery/viatra/runtime/base/itc/alg/dred/DRedAlg.java deleted file mode 100644 index b92d08bf..00000000 --- a/subprojects/viatra-runtime/src/main/java/tools/refinery/viatra/runtime/base/itc/alg/dred/DRedAlg.java +++ /dev/null | |||
@@ -1,308 +0,0 @@ | |||
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.base.itc.alg.dred; | ||
11 | |||
12 | import java.util.ArrayList; | ||
13 | import java.util.HashMap; | ||
14 | import java.util.HashSet; | ||
15 | import java.util.List; | ||
16 | import java.util.Map; | ||
17 | import java.util.Map.Entry; | ||
18 | import java.util.Set; | ||
19 | |||
20 | import tools.refinery.viatra.runtime.base.itc.alg.misc.DFSPathFinder; | ||
21 | import tools.refinery.viatra.runtime.base.itc.alg.misc.IGraphPathFinder; | ||
22 | import tools.refinery.viatra.runtime.base.itc.alg.misc.Tuple; | ||
23 | import tools.refinery.viatra.runtime.base.itc.alg.misc.dfs.DFSAlg; | ||
24 | import tools.refinery.viatra.runtime.base.itc.igraph.IGraphDataSource; | ||
25 | import tools.refinery.viatra.runtime.base.itc.igraph.IGraphObserver; | ||
26 | import tools.refinery.viatra.runtime.base.itc.igraph.ITcDataSource; | ||
27 | import tools.refinery.viatra.runtime.base.itc.igraph.ITcObserver; | ||
28 | import tools.refinery.viatra.runtime.matchers.util.IMemoryView; | ||
29 | |||
30 | /** | ||
31 | * This class is the optimized implementation of the DRED algorithm. | ||
32 | * | ||
33 | * @author Tamas Szabo | ||
34 | * | ||
35 | * @param <V> | ||
36 | * the type parameter of the nodes in the graph data source | ||
37 | */ | ||
38 | public class DRedAlg<V> implements IGraphObserver<V>, ITcDataSource<V> { | ||
39 | |||
40 | private IGraphDataSource<V> graphDataSource = null; | ||
41 | private DRedTcRelation<V> tc = null; | ||
42 | private DRedTcRelation<V> dtc = null; | ||
43 | private List<ITcObserver<V>> observers; | ||
44 | |||
45 | /** | ||
46 | * Constructs a new DRED algorithm and initializes the transitive closure relation with the given graph data source. | ||
47 | * Attach itself on the graph data source as an observer. | ||
48 | * | ||
49 | * @param gds | ||
50 | * the graph data source instance | ||
51 | */ | ||
52 | public DRedAlg(IGraphDataSource<V> gds) { | ||
53 | this.observers = new ArrayList<ITcObserver<V>>(); | ||
54 | this.graphDataSource = gds; | ||
55 | this.tc = new DRedTcRelation<V>(); | ||
56 | this.dtc = new DRedTcRelation<V>(); | ||
57 | initTc(); | ||
58 | graphDataSource.attachObserver(this); | ||
59 | } | ||
60 | |||
61 | /** | ||
62 | * Constructs a new DRED algorithm and initializes the transitive closure relation with the given relation. Attach | ||
63 | * itself on the graph data source as an observer. | ||
64 | * | ||
65 | * @param gds | ||
66 | * the graph data source instance | ||
67 | * @param tc | ||
68 | * the transitive closure instance | ||
69 | */ | ||
70 | public DRedAlg(IGraphDataSource<V> gds, DRedTcRelation<V> tc) { | ||
71 | this.graphDataSource = gds; | ||
72 | this.tc = tc; | ||
73 | this.dtc = new DRedTcRelation<V>(); | ||
74 | graphDataSource.attachObserver(this); | ||
75 | } | ||
76 | |||
77 | /** | ||
78 | * Initializes the transitive closure relation. | ||
79 | */ | ||
80 | private void initTc() { | ||
81 | DFSAlg<V> dfsa = new DFSAlg<V>(this.graphDataSource); | ||
82 | this.setTcRelation(dfsa.getTcRelation()); | ||
83 | this.graphDataSource.detachObserver(dfsa); | ||
84 | } | ||
85 | |||
86 | @Override | ||
87 | public void edgeInserted(V source, V target) { | ||
88 | if (!source.equals(target)) { | ||
89 | Set<V> tupStarts = null; | ||
90 | Set<V> tupEnds = null; | ||
91 | Set<Tuple<V>> tuples = new HashSet<Tuple<V>>(); | ||
92 | |||
93 | if (!source.equals(target) && tc.addTuple(source, target)) { | ||
94 | tuples.add(new Tuple<V>(source, target)); | ||
95 | } | ||
96 | |||
97 | // 2. d+(tc(x,y)) :- d+(tc(x,z)) & lv(z,y) Descartes product | ||
98 | tupStarts = tc.getTupleStarts(source); | ||
99 | tupEnds = tc.getTupleEnds(target); | ||
100 | |||
101 | for (V s : tupStarts) { | ||
102 | for (V t : tupEnds) { | ||
103 | if (!s.equals(t) && tc.addTuple(s, t)) { | ||
104 | tuples.add(new Tuple<V>(s, t)); | ||
105 | } | ||
106 | } | ||
107 | } | ||
108 | |||
109 | // (s, source) -> (source, target) | ||
110 | // tupStarts = tc.getTupleStarts(source); | ||
111 | for (V s : tupStarts) { | ||
112 | if (!s.equals(target) && tc.addTuple(s, target)) { | ||
113 | tuples.add(new Tuple<V>(s, target)); | ||
114 | } | ||
115 | } | ||
116 | |||
117 | // (source, target) -> (target, t) | ||
118 | // tupEnds = tc.getTupleEnds(target); | ||
119 | for (V t : tupEnds) { | ||
120 | if (!source.equals(t) && tc.addTuple(source, t)) { | ||
121 | tuples.add(new Tuple<V>(source, t)); | ||
122 | } | ||
123 | } | ||
124 | |||
125 | notifyTcObservers(tuples, 1); | ||
126 | } | ||
127 | } | ||
128 | |||
129 | @Override | ||
130 | public void edgeDeleted(V source, V target) { | ||
131 | if (!source.equals(target)) { | ||
132 | |||
133 | // Computing overestimate, Descartes product of A and B sets, where | ||
134 | // A: those nodes from which source is reachable | ||
135 | // B: those nodes which is reachable from target | ||
136 | |||
137 | Map<Tuple<V>, Integer> tuples = new HashMap<Tuple<V>, Integer>(); | ||
138 | Set<V> sources = tc.getTupleStarts(source); | ||
139 | Set<V> targets = tc.getTupleEnds(target); | ||
140 | |||
141 | tc.removeTuple(source, target); | ||
142 | tuples.put(new Tuple<V>(source, target), -1); | ||
143 | |||
144 | for (V s : sources) { | ||
145 | for (V t : targets) { | ||
146 | if (!s.equals(t)) { | ||
147 | tc.removeTuple(s, t); | ||
148 | tuples.put(new Tuple<V>(s, t), -1); | ||
149 | } | ||
150 | } | ||
151 | } | ||
152 | |||
153 | for (V s : sources) { | ||
154 | if (!s.equals(target)) { | ||
155 | tc.removeTuple(s, target); | ||
156 | tuples.put(new Tuple<V>(s, target), -1); | ||
157 | } | ||
158 | } | ||
159 | |||
160 | for (V t : targets) { | ||
161 | if (!source.equals(t)) { | ||
162 | tc.removeTuple(source, t); | ||
163 | tuples.put(new Tuple<V>(source, t), -1); | ||
164 | } | ||
165 | } | ||
166 | |||
167 | // System.out.println("overestimate: "+dtc); | ||
168 | |||
169 | // Modify overestimate with those tuples that have alternative derivations | ||
170 | // 1. q+(tc(x,y)) :- lv(x,y) | ||
171 | for (V s : graphDataSource.getAllNodes()) { | ||
172 | IMemoryView<V> targetNodes = graphDataSource.getTargetNodes(s); | ||
173 | for (Entry<V, Integer> entry : targetNodes.entriesWithMultiplicities()) { | ||
174 | for (int i = 0; i < entry.getValue(); i++) { | ||
175 | V t = entry.getKey(); | ||
176 | if (!s.equals(t)) { | ||
177 | tc.addTuple(s, t); | ||
178 | Tuple<V> tuple = new Tuple<V>(s, t); | ||
179 | Integer count = tuples.get(tuple); | ||
180 | if (count != null && count == -1) { | ||
181 | tuples.remove(tuple); | ||
182 | } | ||
183 | } | ||
184 | |||
185 | } | ||
186 | } | ||
187 | } | ||
188 | |||
189 | // 2. q+(tc(x,y)) :- tcv(x,z) & lv(z,y) | ||
190 | DRedTcRelation<V> newTups = new DRedTcRelation<V>(); | ||
191 | dtc.clear(); | ||
192 | dtc.union(tc); | ||
193 | |||
194 | while (!dtc.isEmpty()) { | ||
195 | |||
196 | newTups.clear(); | ||
197 | newTups.union(dtc); | ||
198 | dtc.clear(); | ||
199 | |||
200 | for (V s : newTups.getTupleStarts()) { | ||
201 | for (V t : newTups.getTupleEnds(s)) { | ||
202 | IMemoryView<V> targetNodes = graphDataSource.getTargetNodes(t); | ||
203 | if (targetNodes != null) { | ||
204 | for (Entry<V, Integer> entry : targetNodes.entriesWithMultiplicities()) { | ||
205 | for (int i = 0; i < entry.getValue(); i++) { | ||
206 | V tn = entry.getKey(); | ||
207 | if (!s.equals(tn) && tc.addTuple(s, tn)) { | ||
208 | dtc.addTuple(s, tn); | ||
209 | tuples.remove(new Tuple<V>(s, tn)); | ||
210 | } | ||
211 | } | ||
212 | } | ||
213 | } | ||
214 | } | ||
215 | } | ||
216 | } | ||
217 | |||
218 | notifyTcObservers(tuples.keySet(), -1); | ||
219 | } | ||
220 | } | ||
221 | |||
222 | @Override | ||
223 | public void nodeInserted(V n) { | ||
224 | // Node inserted does not result new tc tuple. | ||
225 | } | ||
226 | |||
227 | @Override | ||
228 | public void nodeDeleted(V n) { | ||
229 | // FIXME node deletion may involve the deletion of incoming and outgoing edges too | ||
230 | Set<V> set = tc.getTupleEnds(n); | ||
231 | Set<V> modSet = null; | ||
232 | |||
233 | // n -> target | ||
234 | modSet = new HashSet<V>(set); | ||
235 | |||
236 | for (V tn : modSet) { | ||
237 | this.tc.removeTuple(n, tn); | ||
238 | } | ||
239 | |||
240 | // source -> n | ||
241 | set = tc.getTupleStarts(n); | ||
242 | |||
243 | modSet = new HashSet<V>(set); | ||
244 | |||
245 | for (V sn : modSet) { | ||
246 | this.tc.removeTuple(sn, n); | ||
247 | } | ||
248 | } | ||
249 | |||
250 | public DRedTcRelation<V> getTcRelation() { | ||
251 | return this.tc; | ||
252 | } | ||
253 | |||
254 | public void setTcRelation(DRedTcRelation<V> tc) { | ||
255 | this.tc = tc; | ||
256 | } | ||
257 | |||
258 | @Override | ||
259 | public boolean isReachable(V source, V target) { | ||
260 | return tc.containsTuple(source, target); | ||
261 | } | ||
262 | |||
263 | @Override | ||
264 | public void attachObserver(ITcObserver<V> to) { | ||
265 | this.observers.add(to); | ||
266 | } | ||
267 | |||
268 | @Override | ||
269 | public void detachObserver(ITcObserver<V> to) { | ||
270 | this.observers.remove(to); | ||
271 | } | ||
272 | |||
273 | @Override | ||
274 | public Set<V> getAllReachableTargets(V source) { | ||
275 | return tc.getTupleEnds(source); | ||
276 | } | ||
277 | |||
278 | @Override | ||
279 | public Set<V> getAllReachableSources(V target) { | ||
280 | return tc.getTupleStarts(target); | ||
281 | } | ||
282 | |||
283 | protected void notifyTcObservers(Set<Tuple<V>> tuples, int dir) { | ||
284 | for (ITcObserver<V> o : observers) { | ||
285 | for (Tuple<V> t : tuples) { | ||
286 | if (!t.getSource().equals(t.getTarget())) { | ||
287 | if (dir == 1) { | ||
288 | o.tupleInserted(t.getSource(), t.getTarget()); | ||
289 | } | ||
290 | if (dir == -1) { | ||
291 | o.tupleDeleted(t.getSource(), t.getTarget()); | ||
292 | } | ||
293 | } | ||
294 | } | ||
295 | } | ||
296 | } | ||
297 | |||
298 | @Override | ||
299 | public void dispose() { | ||
300 | tc = null; | ||
301 | dtc = null; | ||
302 | } | ||
303 | |||
304 | @Override | ||
305 | public IGraphPathFinder<V> getPathFinder() { | ||
306 | return new DFSPathFinder<V>(graphDataSource, this); | ||
307 | } | ||
308 | } | ||
diff --git a/subprojects/viatra-runtime/src/main/java/tools/refinery/viatra/runtime/base/itc/alg/dred/DRedTcRelation.java b/subprojects/viatra-runtime/src/main/java/tools/refinery/viatra/runtime/base/itc/alg/dred/DRedTcRelation.java deleted file mode 100644 index 8543b79c..00000000 --- a/subprojects/viatra-runtime/src/main/java/tools/refinery/viatra/runtime/base/itc/alg/dred/DRedTcRelation.java +++ /dev/null | |||
@@ -1,223 +0,0 @@ | |||
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.base.itc.alg.dred; | ||
11 | |||
12 | import java.util.HashMap; | ||
13 | import java.util.HashSet; | ||
14 | import java.util.Map; | ||
15 | import java.util.Map.Entry; | ||
16 | import java.util.Set; | ||
17 | |||
18 | import tools.refinery.viatra.runtime.base.itc.alg.misc.ITcRelation; | ||
19 | |||
20 | public class DRedTcRelation<V> implements ITcRelation<V> { | ||
21 | |||
22 | // tc(a,b) means that b is transitively reachable from a | ||
23 | private Map<V, Set<V>> tuplesForward; | ||
24 | |||
25 | // data structure to efficiently get those nodes from which a given node is reachable | ||
26 | // symmetric to tuplesForward | ||
27 | private Map<V, Set<V>> tuplesBackward; | ||
28 | |||
29 | public DRedTcRelation() { | ||
30 | this.tuplesForward = new HashMap<V, Set<V>>(); | ||
31 | this.tuplesBackward = new HashMap<V, Set<V>>(); | ||
32 | } | ||
33 | |||
34 | public void clear() { | ||
35 | this.tuplesForward.clear(); | ||
36 | this.tuplesBackward.clear(); | ||
37 | } | ||
38 | |||
39 | public boolean isEmpty() { | ||
40 | return tuplesForward.isEmpty(); | ||
41 | } | ||
42 | |||
43 | public void removeTuple(V source, V target) { | ||
44 | |||
45 | // removing tuple from 'forward' tc relation | ||
46 | Set<V> sSet = tuplesForward.get(source); | ||
47 | if (sSet != null) { | ||
48 | sSet.remove(target); | ||
49 | if (sSet.size() == 0) | ||
50 | tuplesForward.remove(source); | ||
51 | } | ||
52 | |||
53 | // removing tuple from 'backward' tc relation | ||
54 | Set<V> tSet = tuplesBackward.get(target); | ||
55 | if (tSet != null) { | ||
56 | tSet.remove(source); | ||
57 | if (tSet.size() == 0) | ||
58 | tuplesBackward.remove(target); | ||
59 | } | ||
60 | } | ||
61 | |||
62 | /** | ||
63 | * Returns true if the tc relation did not contain previously such a tuple that is defined by (source,target), false | ||
64 | * otherwise. | ||
65 | * | ||
66 | * @param source | ||
67 | * the source of the tuple | ||
68 | * @param target | ||
69 | * the target of the tuple | ||
70 | * @return true if the relation did not contain previously the tuple | ||
71 | */ | ||
72 | public boolean addTuple(V source, V target) { | ||
73 | |||
74 | // symmetric modification, it is sufficient to check the return value in one collection | ||
75 | // adding tuple to 'forward' tc relation | ||
76 | Set<V> sSet = tuplesForward.get(source); | ||
77 | if (sSet == null) { | ||
78 | Set<V> newSet = new HashSet<V>(); | ||
79 | newSet.add(target); | ||
80 | tuplesForward.put(source, newSet); | ||
81 | } else { | ||
82 | sSet.add(target); | ||
83 | } | ||
84 | |||
85 | // adding tuple to 'backward' tc relation | ||
86 | Set<V> tSet = tuplesBackward.get(target); | ||
87 | if (tSet == null) { | ||
88 | Set<V> newSet = new HashSet<V>(); | ||
89 | newSet.add(source); | ||
90 | tuplesBackward.put(target, newSet); | ||
91 | return true; | ||
92 | } else { | ||
93 | boolean ret = tSet.add(source); | ||
94 | return ret; | ||
95 | } | ||
96 | |||
97 | } | ||
98 | |||
99 | /** | ||
100 | * Union operation of two tc realtions. | ||
101 | * | ||
102 | * @param rA | ||
103 | * the other tc relation | ||
104 | */ | ||
105 | public void union(DRedTcRelation<V> rA) { | ||
106 | for (V source : rA.tuplesForward.keySet()) { | ||
107 | for (V target : rA.tuplesForward.get(source)) { | ||
108 | this.addTuple(source, target); | ||
109 | } | ||
110 | } | ||
111 | } | ||
112 | |||
113 | /** | ||
114 | * Computes the difference of this tc relation and the given rA parameter. | ||
115 | * | ||
116 | * @param rA | ||
117 | * the subtrahend relation | ||
118 | */ | ||
119 | public void difference(DRedTcRelation<V> rA) { | ||
120 | for (V source : rA.tuplesForward.keySet()) { | ||
121 | for (V target : rA.tuplesForward.get(source)) { | ||
122 | this.removeTuple(source, target); | ||
123 | } | ||
124 | } | ||
125 | } | ||
126 | |||
127 | @Override | ||
128 | public Set<V> getTupleEnds(V source) { | ||
129 | Set<V> t = tuplesForward.get(source); | ||
130 | return (t == null) ? new HashSet<V>() : new HashSet<V>(t); | ||
131 | } | ||
132 | |||
133 | /** | ||
134 | * Returns the set of nodes from which the target node is reachable. | ||
135 | * | ||
136 | * @param target | ||
137 | * the target node | ||
138 | * @return the set of source nodes | ||
139 | */ | ||
140 | public Set<V> getTupleStarts(V target) { | ||
141 | Set<V> t = tuplesBackward.get(target); | ||
142 | return (t == null) ? new HashSet<V>() : new HashSet<V>(t); | ||
143 | } | ||
144 | |||
145 | @Override | ||
146 | public Set<V> getTupleStarts() { | ||
147 | Set<V> t = tuplesForward.keySet(); | ||
148 | return new HashSet<V>(t); | ||
149 | } | ||
150 | |||
151 | @Override | ||
152 | public String toString() { | ||
153 | StringBuilder sb = new StringBuilder("TcRelation = "); | ||
154 | |||
155 | for (Entry<V, Set<V>> entry : this.tuplesForward.entrySet()) { | ||
156 | V source = entry.getKey(); | ||
157 | for (V target : entry.getValue()) { | ||
158 | sb.append("(" + source + "," + target + ") "); | ||
159 | } | ||
160 | } | ||
161 | return sb.toString(); | ||
162 | } | ||
163 | |||
164 | /** | ||
165 | * Returns true if a (source, target) node is present in the transitive closure relation, false otherwise. | ||
166 | * | ||
167 | * @param source | ||
168 | * the source node | ||
169 | * @param target | ||
170 | * the target node | ||
171 | * @return true if tuple is present, false otherwise | ||
172 | */ | ||
173 | public boolean containsTuple(V source, V target) { | ||
174 | if (tuplesForward.containsKey(source)) { | ||
175 | if (tuplesForward.get(source).contains(target)) | ||
176 | return true; | ||
177 | } | ||
178 | return false; | ||
179 | } | ||
180 | |||
181 | @SuppressWarnings("unchecked") | ||
182 | @Override | ||
183 | public boolean equals(Object obj) { | ||
184 | if (this == obj) { | ||
185 | return true; | ||
186 | } | ||
187 | if ((obj == null) || (obj.getClass() != this.getClass())) { | ||
188 | return false; | ||
189 | } | ||
190 | |||
191 | DRedTcRelation<V> aTR = (DRedTcRelation<V>) obj; | ||
192 | |||
193 | for (Entry<V, Set<V>> entry : aTR.tuplesForward.entrySet()) { | ||
194 | V source = entry.getKey(); | ||
195 | for (V target : entry.getValue()) { | ||
196 | if (!this.containsTuple(source, target)) | ||
197 | return false; | ||
198 | } | ||
199 | } | ||
200 | |||
201 | for (Entry<V, Set<V>> entry : this.tuplesForward.entrySet()) { | ||
202 | V source = entry.getKey(); | ||
203 | for (V target : entry.getValue()) { | ||
204 | if (!aTR.containsTuple(source, target)) | ||
205 | return false; | ||
206 | } | ||
207 | } | ||
208 | |||
209 | return true; | ||
210 | } | ||
211 | |||
212 | @Override | ||
213 | public int hashCode() { | ||
214 | int hash = 7; | ||
215 | hash = 31 * hash + tuplesForward.hashCode(); | ||
216 | hash = 31 * hash + tuplesBackward.hashCode(); | ||
217 | return hash; | ||
218 | } | ||
219 | |||
220 | public Map<V, Set<V>> getTuplesForward() { | ||
221 | return tuplesForward; | ||
222 | } | ||
223 | } | ||
diff --git a/subprojects/viatra-runtime/src/main/java/tools/refinery/viatra/runtime/base/itc/alg/fw/FloydWarshallAlg.java b/subprojects/viatra-runtime/src/main/java/tools/refinery/viatra/runtime/base/itc/alg/fw/FloydWarshallAlg.java deleted file mode 100644 index 8b8908b1..00000000 --- a/subprojects/viatra-runtime/src/main/java/tools/refinery/viatra/runtime/base/itc/alg/fw/FloydWarshallAlg.java +++ /dev/null | |||
@@ -1,110 +0,0 @@ | |||
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.base.itc.alg.fw; | ||
11 | |||
12 | import java.util.HashMap; | ||
13 | import java.util.Map; | ||
14 | |||
15 | import tools.refinery.viatra.runtime.base.itc.alg.dred.DRedTcRelation; | ||
16 | import tools.refinery.viatra.runtime.base.itc.igraph.IGraphDataSource; | ||
17 | import tools.refinery.viatra.runtime.base.itc.igraph.IGraphObserver; | ||
18 | import tools.refinery.viatra.runtime.base.itc.igraph.IBiDirectionalGraphDataSource; | ||
19 | import tools.refinery.viatra.runtime.base.itc.igraph.IBiDirectionalWrapper; | ||
20 | import tools.refinery.viatra.runtime.matchers.util.IMemoryView; | ||
21 | |||
22 | public class FloydWarshallAlg<V> implements IGraphObserver<V> { | ||
23 | |||
24 | private DRedTcRelation<V> tc = null; | ||
25 | private IBiDirectionalGraphDataSource<V> gds = null; | ||
26 | |||
27 | public FloydWarshallAlg(IGraphDataSource<V> gds) { | ||
28 | if (gds instanceof IBiDirectionalGraphDataSource<?>) { | ||
29 | this.gds = (IBiDirectionalGraphDataSource<V>) gds; | ||
30 | } else { | ||
31 | this.gds = new IBiDirectionalWrapper<V>(gds); | ||
32 | } | ||
33 | |||
34 | this.tc = new DRedTcRelation<V>(); | ||
35 | gds.attachObserver(this); | ||
36 | generateTc(); | ||
37 | } | ||
38 | |||
39 | private void generateTc() { | ||
40 | |||
41 | tc.clear(); | ||
42 | |||
43 | int n = gds.getAllNodes().size(); | ||
44 | Map<V, Integer> mapForw = new HashMap<V, Integer>(); | ||
45 | Map<Integer, V> mapBackw = new HashMap<Integer, V>(); | ||
46 | int[][] P = new int[n][n]; | ||
47 | |||
48 | int i, j, k; | ||
49 | |||
50 | // initialize adjacent matrix | ||
51 | for (i = 0; i < n; i++) { | ||
52 | for (j = 0; j < n; j++) { | ||
53 | P[i][j] = 0; | ||
54 | } | ||
55 | } | ||
56 | |||
57 | i = 0; | ||
58 | for (V node : gds.getAllNodes()) { | ||
59 | mapForw.put(node, i); | ||
60 | mapBackw.put(i, node); | ||
61 | i++; | ||
62 | } | ||
63 | |||
64 | for (V source : gds.getAllNodes()) { | ||
65 | IMemoryView<V> targets = gds.getTargetNodes(source); | ||
66 | for (V target : targets.distinctValues()) { | ||
67 | P[mapForw.get(source)][mapForw.get(target)] = 1; | ||
68 | } | ||
69 | } | ||
70 | |||
71 | for (k = 0; k < n; k++) { | ||
72 | for (i = 0; i < n; i++) { | ||
73 | for (j = 0; j < n; j++) { | ||
74 | P[i][j] = P[i][j] | (P[i][k] & P[k][j]); | ||
75 | } | ||
76 | } | ||
77 | } | ||
78 | |||
79 | for (i = 0; i < n; i++) { | ||
80 | for (j = 0; j < n; j++) { | ||
81 | if (P[i][j] == 1 && i != j) | ||
82 | tc.addTuple(mapBackw.get(i), mapBackw.get(j)); | ||
83 | } | ||
84 | } | ||
85 | } | ||
86 | |||
87 | @Override | ||
88 | public void edgeInserted(V source, V target) { | ||
89 | generateTc(); | ||
90 | } | ||
91 | |||
92 | @Override | ||
93 | public void edgeDeleted(V source, V target) { | ||
94 | generateTc(); | ||
95 | } | ||
96 | |||
97 | @Override | ||
98 | public void nodeInserted(V n) { | ||
99 | generateTc(); | ||
100 | } | ||
101 | |||
102 | @Override | ||
103 | public void nodeDeleted(V n) { | ||
104 | generateTc(); | ||
105 | } | ||
106 | |||
107 | public DRedTcRelation<V> getTcRelation() { | ||
108 | return this.tc; | ||
109 | } | ||
110 | } | ||
diff --git a/subprojects/viatra-runtime/src/main/java/tools/refinery/viatra/runtime/base/itc/alg/misc/dfs/DFSAlg.java b/subprojects/viatra-runtime/src/main/java/tools/refinery/viatra/runtime/base/itc/alg/misc/dfs/DFSAlg.java deleted file mode 100644 index c8d25c4e..00000000 --- a/subprojects/viatra-runtime/src/main/java/tools/refinery/viatra/runtime/base/itc/alg/misc/dfs/DFSAlg.java +++ /dev/null | |||
@@ -1,93 +0,0 @@ | |||
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.base.itc.alg.misc.dfs; | ||
11 | |||
12 | import java.util.HashMap; | ||
13 | |||
14 | import tools.refinery.viatra.runtime.base.itc.alg.dred.DRedTcRelation; | ||
15 | import tools.refinery.viatra.runtime.base.itc.igraph.IGraphDataSource; | ||
16 | import tools.refinery.viatra.runtime.base.itc.igraph.IGraphObserver; | ||
17 | |||
18 | public class DFSAlg<V> implements IGraphObserver<V> { | ||
19 | |||
20 | private IGraphDataSource<V> gds; | ||
21 | private DRedTcRelation<V> tc; | ||
22 | private int[] visited; | ||
23 | private HashMap<V, Integer> nodeMap; | ||
24 | |||
25 | public DFSAlg(IGraphDataSource<V> gds) { | ||
26 | this.gds = gds; | ||
27 | this.tc = new DRedTcRelation<V>(); | ||
28 | gds.attachObserver(this); | ||
29 | deriveTc(); | ||
30 | } | ||
31 | |||
32 | private void deriveTc() { | ||
33 | tc.clear(); | ||
34 | |||
35 | this.visited = new int[gds.getAllNodes().size()]; | ||
36 | nodeMap = new HashMap<V, Integer>(); | ||
37 | |||
38 | int j = 0; | ||
39 | for (V n : gds.getAllNodes()) { | ||
40 | nodeMap.put(n, j); | ||
41 | j++; | ||
42 | } | ||
43 | |||
44 | for (V n : gds.getAllNodes()) { | ||
45 | oneDFS(n, n); | ||
46 | initVisitedArray(); | ||
47 | } | ||
48 | } | ||
49 | |||
50 | private void initVisitedArray() { | ||
51 | for (int i = 0; i < visited.length; i++) | ||
52 | visited[i] = 0; | ||
53 | } | ||
54 | |||
55 | private void oneDFS(V act, V source) { | ||
56 | |||
57 | if (!act.equals(source)) { | ||
58 | tc.addTuple(source, act); | ||
59 | } | ||
60 | |||
61 | visited[nodeMap.get(act)] = 1; | ||
62 | |||
63 | for (V t : gds.getTargetNodes(act).distinctValues()) { | ||
64 | if (visited[nodeMap.get(t)] == 0) { | ||
65 | oneDFS(t, source); | ||
66 | } | ||
67 | } | ||
68 | } | ||
69 | |||
70 | public DRedTcRelation<V> getTcRelation() { | ||
71 | return this.tc; | ||
72 | } | ||
73 | |||
74 | @Override | ||
75 | public void edgeInserted(V source, V target) { | ||
76 | deriveTc(); | ||
77 | } | ||
78 | |||
79 | @Override | ||
80 | public void edgeDeleted(V source, V target) { | ||
81 | deriveTc(); | ||
82 | } | ||
83 | |||
84 | @Override | ||
85 | public void nodeInserted(V n) { | ||
86 | deriveTc(); | ||
87 | } | ||
88 | |||
89 | @Override | ||
90 | public void nodeDeleted(V n) { | ||
91 | deriveTc(); | ||
92 | } | ||
93 | } | ||