aboutsummaryrefslogtreecommitdiffstats
path: root/subprojects/viatra-runtime-base-itc
diff options
context:
space:
mode:
Diffstat (limited to 'subprojects/viatra-runtime-base-itc')
-rw-r--r--subprojects/viatra-runtime-base-itc/about.html26
-rw-r--r--subprojects/viatra-runtime-base-itc/build.gradle.kts13
-rw-r--r--subprojects/viatra-runtime-base-itc/src/main/java/tools/refinery/viatra/runtime/base/itc/alg/counting/CountingAlg.java226
-rw-r--r--subprojects/viatra-runtime-base-itc/src/main/java/tools/refinery/viatra/runtime/base/itc/alg/counting/CountingTcRelation.java259
-rw-r--r--subprojects/viatra-runtime-base-itc/src/main/java/tools/refinery/viatra/runtime/base/itc/alg/dred/DRedAlg.java308
-rw-r--r--subprojects/viatra-runtime-base-itc/src/main/java/tools/refinery/viatra/runtime/base/itc/alg/dred/DRedTcRelation.java223
-rw-r--r--subprojects/viatra-runtime-base-itc/src/main/java/tools/refinery/viatra/runtime/base/itc/alg/fw/FloydWarshallAlg.java110
-rw-r--r--subprojects/viatra-runtime-base-itc/src/main/java/tools/refinery/viatra/runtime/base/itc/alg/incscc/CountingListener.java36
-rw-r--r--subprojects/viatra-runtime-base-itc/src/main/java/tools/refinery/viatra/runtime/base/itc/alg/incscc/IncSCCAlg.java645
-rw-r--r--subprojects/viatra-runtime-base-itc/src/main/java/tools/refinery/viatra/runtime/base/itc/alg/misc/DFSPathFinder.java146
-rw-r--r--subprojects/viatra-runtime-base-itc/src/main/java/tools/refinery/viatra/runtime/base/itc/alg/misc/Edge.java38
-rw-r--r--subprojects/viatra-runtime-base-itc/src/main/java/tools/refinery/viatra/runtime/base/itc/alg/misc/GraphHelper.java173
-rw-r--r--subprojects/viatra-runtime-base-itc/src/main/java/tools/refinery/viatra/runtime/base/itc/alg/misc/IGraphPathFinder.java67
-rw-r--r--subprojects/viatra-runtime-base-itc/src/main/java/tools/refinery/viatra/runtime/base/itc/alg/misc/ITcRelation.java31
-rw-r--r--subprojects/viatra-runtime-base-itc/src/main/java/tools/refinery/viatra/runtime/base/itc/alg/misc/Tuple.java60
-rw-r--r--subprojects/viatra-runtime-base-itc/src/main/java/tools/refinery/viatra/runtime/base/itc/alg/misc/bfs/BFS.java151
-rw-r--r--subprojects/viatra-runtime-base-itc/src/main/java/tools/refinery/viatra/runtime/base/itc/alg/misc/dfs/DFSAlg.java93
-rw-r--r--subprojects/viatra-runtime-base-itc/src/main/java/tools/refinery/viatra/runtime/base/itc/alg/misc/scc/PKAlg.java179
-rw-r--r--subprojects/viatra-runtime-base-itc/src/main/java/tools/refinery/viatra/runtime/base/itc/alg/misc/scc/SCC.java146
-rw-r--r--subprojects/viatra-runtime-base-itc/src/main/java/tools/refinery/viatra/runtime/base/itc/alg/misc/scc/SCCProperty.java37
-rw-r--r--subprojects/viatra-runtime-base-itc/src/main/java/tools/refinery/viatra/runtime/base/itc/alg/misc/scc/SCCResult.java81
-rw-r--r--subprojects/viatra-runtime-base-itc/src/main/java/tools/refinery/viatra/runtime/base/itc/alg/misc/topsort/TopologicalSorting.java77
-rw-r--r--subprojects/viatra-runtime-base-itc/src/main/java/tools/refinery/viatra/runtime/base/itc/alg/representative/RepresentativeElectionAlgorithm.java140
-rw-r--r--subprojects/viatra-runtime-base-itc/src/main/java/tools/refinery/viatra/runtime/base/itc/alg/representative/RepresentativeObserver.java12
-rw-r--r--subprojects/viatra-runtime-base-itc/src/main/java/tools/refinery/viatra/runtime/base/itc/alg/representative/StronglyConnectedComponentAlgorithm.java66
-rw-r--r--subprojects/viatra-runtime-base-itc/src/main/java/tools/refinery/viatra/runtime/base/itc/alg/representative/WeaklyConnectedComponentAlgorithm.java85
-rw-r--r--subprojects/viatra-runtime-base-itc/src/main/java/tools/refinery/viatra/runtime/base/itc/alg/util/CollectionHelper.java64
-rw-r--r--subprojects/viatra-runtime-base-itc/src/main/java/tools/refinery/viatra/runtime/base/itc/graphimpl/DotGenerator.java160
-rw-r--r--subprojects/viatra-runtime-base-itc/src/main/java/tools/refinery/viatra/runtime/base/itc/graphimpl/Graph.java185
-rw-r--r--subprojects/viatra-runtime-base-itc/src/main/java/tools/refinery/viatra/runtime/base/itc/igraph/IBiDirectionalGraphDataSource.java37
-rw-r--r--subprojects/viatra-runtime-base-itc/src/main/java/tools/refinery/viatra/runtime/base/itc/igraph/IBiDirectionalWrapper.java110
-rw-r--r--subprojects/viatra-runtime-base-itc/src/main/java/tools/refinery/viatra/runtime/base/itc/igraph/IGraphDataSource.java70
-rw-r--r--subprojects/viatra-runtime-base-itc/src/main/java/tools/refinery/viatra/runtime/base/itc/igraph/IGraphObserver.java55
-rw-r--r--subprojects/viatra-runtime-base-itc/src/main/java/tools/refinery/viatra/runtime/base/itc/igraph/ITcDataSource.java82
-rw-r--r--subprojects/viatra-runtime-base-itc/src/main/java/tools/refinery/viatra/runtime/base/itc/igraph/ITcObserver.java39
35 files changed, 0 insertions, 4230 deletions
diff --git a/subprojects/viatra-runtime-base-itc/about.html b/subprojects/viatra-runtime-base-itc/about.html
deleted file mode 100644
index d1d5593a..00000000
--- a/subprojects/viatra-runtime-base-itc/about.html
+++ /dev/null
@@ -1,26 +0,0 @@
1<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.0//EN">
2<html>
3<!--
4 Copyright (c) 2017, Eclipse.org Foundation, Inc.
5
6 SPDX-License-Identifier: LicenseRef-EPL-Steward
7-->
8<head>
9<title>About</title>
10<meta http-equiv=Content-Type content="text/html; charset=ISO-8859-1">
11</head>
12<body lang="EN-US">
13<h2>About This Content</h2>
14
15<p>March 18, 2019</p>
16<h3>License</h3>
17
18<p>The Eclipse Foundation makes available all content in this plug-in (&quot;Content&quot;). Unless otherwise indicated below, the Content is provided to you under the terms and conditions of the
19Eclipse Public License Version 2.0 (&quot;EPL&quot;). A copy of the EPL is available at <a href="http://www.eclipse.org/org/documents/epl-v20.php">http://www.eclipse.org/legal/epl-v20.html</a>.
20For purposes of the EPL, &quot;Program&quot; will mean the Content.</p>
21
22<p>If you did not receive this Content directly from the Eclipse Foundation, the Content is being redistributed by another party (&quot;Redistributor&quot;) and different terms and conditions may
23apply to your use of any object code in the Content. Check the Redistributor's license that was provided with the Content. If no such license exists, contact the Redistributor. Unless otherwise
24indicated below, the terms and conditions of the EPL still apply to any source code in the Content and such source code may be obtained at <a href="http://www.eclipse.org/">http://www.eclipse.org</a>.</p>
25</body>
26</html>
diff --git a/subprojects/viatra-runtime-base-itc/build.gradle.kts b/subprojects/viatra-runtime-base-itc/build.gradle.kts
deleted file mode 100644
index 2fcdf5c4..00000000
--- a/subprojects/viatra-runtime-base-itc/build.gradle.kts
+++ /dev/null
@@ -1,13 +0,0 @@
1/*
2 * SPDX-FileCopyrightText: 2021-2023 The Refinery Authors <https://refinery.tools/>
3 *
4 * SPDX-License-Identifier: EPL-2.0
5 */
6
7plugins {
8 id("tools.refinery.gradle.java-library")
9}
10
11dependencies {
12 implementation(project(":refinery-viatra-runtime-matchers"))
13}
diff --git a/subprojects/viatra-runtime-base-itc/src/main/java/tools/refinery/viatra/runtime/base/itc/alg/counting/CountingAlg.java b/subprojects/viatra-runtime-base-itc/src/main/java/tools/refinery/viatra/runtime/base/itc/alg/counting/CountingAlg.java
deleted file mode 100644
index d0367cde..00000000
--- a/subprojects/viatra-runtime-base-itc/src/main/java/tools/refinery/viatra/runtime/base/itc/alg/counting/CountingAlg.java
+++ /dev/null
@@ -1,226 +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
10package tools.refinery.viatra.runtime.base.itc.alg.counting;
11
12import java.util.List;
13import java.util.Set;
14
15import tools.refinery.viatra.runtime.base.itc.alg.misc.DFSPathFinder;
16import tools.refinery.viatra.runtime.base.itc.alg.misc.IGraphPathFinder;
17import tools.refinery.viatra.runtime.base.itc.alg.misc.ITcRelation;
18import tools.refinery.viatra.runtime.base.itc.igraph.IBiDirectionalGraphDataSource;
19import tools.refinery.viatra.runtime.base.itc.igraph.IBiDirectionalWrapper;
20import tools.refinery.viatra.runtime.base.itc.igraph.IGraphDataSource;
21import tools.refinery.viatra.runtime.base.itc.igraph.IGraphObserver;
22import tools.refinery.viatra.runtime.base.itc.igraph.ITcDataSource;
23import tools.refinery.viatra.runtime.base.itc.igraph.ITcObserver;
24import tools.refinery.viatra.runtime.matchers.util.CollectionsFactory;
25import tools.refinery.viatra.runtime.matchers.util.IMemoryView;
26
27/**
28 * This class is the optimized implementation of the Counting algorithm.
29 *
30 * @author Tamas Szabo
31 *
32 * @param <V>
33 * the type parameter of the nodes in the graph data source
34 */
35public class CountingAlg<V> implements IGraphObserver<V>, ITcDataSource<V> {
36
37 private CountingTcRelation<V> tc = null;
38 private IBiDirectionalGraphDataSource<V> gds = null;
39 private List<ITcObserver<V>> observers;
40
41 /**
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.
44 *
45 * @param gds
46 * the graph data source instance
47 */
48 public CountingAlg(IGraphDataSource<V> gds) {
49
50 if (gds instanceof IBiDirectionalGraphDataSource<?>) {
51 this.gds = (IBiDirectionalGraphDataSource<V>) gds;
52 } else {
53 this.gds = new IBiDirectionalWrapper<V>(gds);
54 }
55
56 observers = CollectionsFactory.<ITcObserver<V>>createObserverList();
57 tc = new CountingTcRelation<V>(true);
58
59 initTc();
60 gds.attachObserver(this);
61 }
62
63 /**
64 * Initializes the transitive closure relation.
65 */
66 private void initTc() {
67 this.setTcRelation(CountingTcRelation.createFrom(gds));
68 }
69
70 @Override
71 public void edgeInserted(V source, V target) {
72 if (!source.equals(target)) {
73 deriveTc(source, target, true);
74 }
75 }
76
77 @Override
78 public void edgeDeleted(V source, V target) {
79 if (!source.equals(target)) {
80 deriveTc(source, target, false);
81 }
82 }
83
84 @Override
85 public void nodeInserted(V n) {
86
87 }
88
89 @Override
90 public void nodeDeleted(V n) {
91 this.tc.deleteTupleEnd(n);
92 }
93
94 /**
95 * Derives the transitive closure relation when an edge is inserted or deleted.
96 *
97 * @param source
98 * the source of the edge
99 * @param target
100 * the target of the edge
101 * @param dCount
102 * the value is -1 if an edge was deleted and +1 if an edge was inserted
103 */
104 private void deriveTc(V source, V target, boolean isInsertion) {
105
106 // if (dCount == 1 && isReachable(target, source)) {
107 // System.out.println("The graph contains cycle with (" + source + ","+ target + ") edge!");
108 // }
109
110 CountingTcRelation<V> dtc = new CountingTcRelation<V>(false);
111 Set<V> tupEnds = null;
112
113 // 1. d(tc(x,y)) :- d(l(x,y))
114 if (tc.updateTuple(source, target, isInsertion)) {
115 dtc.updateTuple(source, target, true /* deltas implicitly have the same sign as isInsertion*/);
116 notifyTcObservers(source, target, isInsertion);
117 }
118
119 // 2. d(tc(x,y)) :- d(l(x,z)) & tc(z,y)
120 tupEnds = tc.getTupleEnds(target);
121 if (tupEnds != null) {
122 for (V tupEnd : tupEnds) {
123 if (!tupEnd.equals(source)) {
124 if (tc.updateTuple(source, tupEnd, isInsertion)) {
125 dtc.updateTuple(source, tupEnd, true /* deltas implicitly have the same sign as isInsertion*/);
126 notifyTcObservers(source, tupEnd, isInsertion);
127 }
128 }
129 }
130 }
131
132 // 3. d(tc(x,y)) :- lv(x,z) & d(tc(z,y))
133 CountingTcRelation<V> newTuples = dtc;
134 CountingTcRelation<V> tmp = null;
135 dtc = new CountingTcRelation<V>(false);
136
137 IMemoryView<V> nodes = null;
138
139 while (!newTuples.isEmpty()) {
140
141 tmp = dtc;
142 dtc = newTuples;
143 newTuples = tmp;
144 newTuples.clear();
145
146 for (V tS : dtc.getTupleStarts()) {
147 nodes = gds.getSourceNodes(tS);
148 for (V nS : nodes.distinctValues()) {
149 int count = nodes.getCount(nS);
150 for (int i = 0; i < count; i++) {
151 tupEnds = dtc.getTupleEnds(tS);
152 if (tupEnds != null) {
153 for (V tT : tupEnds) {
154 if (!nS.equals(tT)) {
155 if (tc.updateTuple(nS, tT, isInsertion)) {
156 newTuples.updateTuple(nS, tT, true /* deltas implicitly have the same sign as isInsertion*/);
157 notifyTcObservers(nS, tT, isInsertion);
158 }
159 }
160 }
161 }
162 }
163 }
164 }
165 }
166
167 // System.out.println(tc);
168 }
169
170 public ITcRelation<V> getTcRelation() {
171 return this.tc;
172 }
173
174 public void setTcRelation(CountingTcRelation<V> tc) {
175 this.tc = tc;
176 }
177
178 @Override
179 public boolean isReachable(V source, V target) {
180 return tc.containsTuple(source, target);
181 }
182
183 @Override
184 public void attachObserver(ITcObserver<V> to) {
185 this.observers.add(to);
186
187 }
188
189 @Override
190 public void detachObserver(ITcObserver<V> to) {
191 this.observers.remove(to);
192 }
193
194 @Override
195 public Set<V> getAllReachableTargets(V source) {
196 return tc.getTupleEnds(source);
197 }
198
199 @Override
200 public Set<V> getAllReachableSources(V target) {
201 return tc.getTupleStarts(target);
202 }
203
204 private void notifyTcObservers(V source, V target, boolean isInsertion) {
205 if (isInsertion) {
206 for (ITcObserver<V> o : observers) {
207 o.tupleInserted(source, target);
208 }
209 } else {
210 for (ITcObserver<V> o : observers) {
211 o.tupleDeleted(source, target);
212 }
213 }
214 }
215
216 @Override
217 public void dispose() {
218 tc.clear();
219 this.gds.detachObserver(this);
220 }
221
222 @Override
223 public IGraphPathFinder<V> getPathFinder() {
224 return new DFSPathFinder<V>(gds, this);
225 }
226} \ No newline at end of file
diff --git a/subprojects/viatra-runtime-base-itc/src/main/java/tools/refinery/viatra/runtime/base/itc/alg/counting/CountingTcRelation.java b/subprojects/viatra-runtime-base-itc/src/main/java/tools/refinery/viatra/runtime/base/itc/alg/counting/CountingTcRelation.java
deleted file mode 100644
index 8f804dfd..00000000
--- a/subprojects/viatra-runtime-base-itc/src/main/java/tools/refinery/viatra/runtime/base/itc/alg/counting/CountingTcRelation.java
+++ /dev/null
@@ -1,259 +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
10package tools.refinery.viatra.runtime.base.itc.alg.counting;
11
12import java.util.Collections;
13import java.util.List;
14import java.util.Set;
15
16import tools.refinery.viatra.runtime.base.itc.alg.misc.ITcRelation;
17import tools.refinery.viatra.runtime.base.itc.alg.misc.topsort.TopologicalSorting;
18import tools.refinery.viatra.runtime.base.itc.igraph.IBiDirectionalGraphDataSource;
19import tools.refinery.viatra.runtime.matchers.util.CollectionsFactory;
20import tools.refinery.viatra.runtime.matchers.util.CollectionsFactory.MemoryType;
21import tools.refinery.viatra.runtime.matchers.util.IMemoryView;
22import tools.refinery.viatra.runtime.matchers.util.IMultiLookup;
23import tools.refinery.viatra.runtime.matchers.util.IMultiLookup.ChangeGranularity;
24
25/**
26 * Transitive closure relation implementation for the Counting algorithm.
27 *
28 * @author Tamas Szabo
29 *
30 * @param <V>
31 */
32public class CountingTcRelation<V> implements ITcRelation<V> {
33
34 private IMultiLookup<V, V> tuplesForward = null;
35 private IMultiLookup<V, V> tuplesBackward = null;
36
37 protected CountingTcRelation(boolean backwardIndexing) {
38 tuplesForward = CollectionsFactory.createMultiLookup(Object.class, MemoryType.MULTISETS, Object.class);
39 if (backwardIndexing)
40 tuplesBackward = CollectionsFactory.createMultiLookup(Object.class, MemoryType.MULTISETS, Object.class);
41 }
42
43 protected boolean isEmpty() {
44 return 0 == this.tuplesForward.countKeys();
45 }
46
47 protected void clear() {
48 this.tuplesForward.clear();
49
50 if (tuplesBackward != null) {
51 this.tuplesBackward.clear();
52 }
53 }
54
55 protected void union(CountingTcRelation<V> rA) {
56 IMultiLookup<V, V> rForward = rA.tuplesForward;
57 for (V source : rForward.distinctKeys()) {
58 IMemoryView<V> targetBag = rForward.lookup(source);
59 for (V target : targetBag.distinctValues()) {
60 this.addTuple(source, target, targetBag.getCount(target));
61 }
62 }
63 }
64
65 public int getCount(V source, V target) {
66 IMemoryView<V> bucket = tuplesForward.lookup(source);
67 return bucket == null ? 0 : bucket.getCount(target);
68 }
69
70 /**
71 * Returns true if the tc relation did not contain previously such a tuple that is defined by (source,target), false
72 * otherwise (in this case count is incremented with the given count parameter).
73 *
74 * @param source
75 * the source of the tuple
76 * @param target
77 * the target of the tuple
78 * @param count
79 * the count of the tuple, must be positive
80 * @return true if the relation did not contain previously the tuple
81 */
82 public boolean addTuple(V source, V target, int count) {
83 if (tuplesBackward != null) {
84 tuplesBackward.addPairPositiveMultiplicity(target, source, count);
85 }
86
87 ChangeGranularity change =
88 tuplesForward.addPairPositiveMultiplicity(source, target, count);
89
90 return change != ChangeGranularity.DUPLICATE;
91 }
92
93 /**
94 * Derivation count of the tuple (source,target) is incremented or decremented.
95 * Returns true iff updated to / from zero derivation count.
96 * @since 1.7
97 */
98 public boolean updateTuple(V source, V target, boolean isInsertion) {
99 if (isInsertion) {
100 if (tuplesBackward != null) {
101 tuplesBackward.addPair(target, source);
102 }
103 ChangeGranularity change =
104 tuplesForward.addPair(source, target);
105 return change != ChangeGranularity.DUPLICATE;
106 } else {
107 if (tuplesBackward != null) {
108 tuplesBackward.removePair(target, source);
109 }
110 ChangeGranularity change =
111 tuplesForward.removePair(source, target);
112 return change != ChangeGranularity.DUPLICATE;
113 }
114 }
115
116 public void deleteTupleEnd(V deleted) {
117 Set<V> sourcesToDelete = CollectionsFactory.createSet();
118 Set<V> targetsToDelete = CollectionsFactory.createSet();
119
120 for (V target : tuplesForward.lookupOrEmpty(deleted).distinctValues()) {
121 targetsToDelete.add(target);
122 }
123 if (tuplesBackward != null) {
124 for (V source : tuplesBackward.lookupOrEmpty(deleted).distinctValues()) {
125 sourcesToDelete.add(source);
126 }
127 } else {
128 for (V sourceCandidate : tuplesForward.distinctKeys()) {
129 if (tuplesForward.lookupOrEmpty(sourceCandidate).containsNonZero(deleted))
130 sourcesToDelete.add(sourceCandidate);
131 }
132 }
133
134 for (V source : sourcesToDelete) {
135 int count = tuplesForward.lookupOrEmpty(source).getCount(deleted);
136 for (int i=0; i< count; ++i) tuplesForward.removePair(source, deleted);
137 }
138 for (V target : targetsToDelete) {
139 int count = tuplesForward.lookupOrEmpty(deleted).getCount(target);
140 for (int i=0; i< count; ++i) tuplesForward.removePair(deleted, target);
141 }
142
143 if (tuplesBackward != null) {
144 for (V source : sourcesToDelete) {
145 int count = tuplesBackward.lookupOrEmpty(deleted).getCount(source);
146 for (int i=0; i< count; ++i) tuplesBackward.removePair(deleted, source);
147 }
148 for (V target : targetsToDelete) {
149 int count = tuplesBackward.lookupOrEmpty(target).getCount(deleted);
150 for (int i=0; i< count; ++i) tuplesBackward.removePair(target, deleted);
151 }
152 }
153 }
154
155 @Override
156 public String toString() {
157 StringBuilder sb = new StringBuilder("TcRelation = ");
158
159 for (V source : tuplesForward.distinctKeys()) {
160 IMemoryView<V> targets = tuplesForward.lookup(source);
161 for (V target : targets.distinctValues()) {
162 sb.append("{(" + source + "," + target + ")," + targets.getCount(target) + "} ");
163 }
164 }
165
166 return sb.toString();
167 }
168
169 @Override
170 public Set<V> getTupleEnds(V source) {
171 IMemoryView<V> tupEnds = tuplesForward.lookup(source);
172 if (tupEnds == null)
173 return null;
174 return tupEnds.distinctValues();
175 }
176
177 /**
178 * Returns the set of nodes from which the target node is reachable, if already computed.
179 *
180 * @param target
181 * the target node
182 * @return the set of source nodes
183 * @throws UnsupportedOperationException if backwards index not computed
184 */
185 public Set<V> getTupleStarts(V target) {
186 if (tuplesBackward != null) {
187 IMemoryView<V> tupStarts = tuplesBackward.lookup(target);
188 if (tupStarts == null)
189 return null;
190 return tupStarts.distinctValues();
191 } else {
192 throw new UnsupportedOperationException("built without backward indexing");
193 }
194 }
195
196 @Override
197 public Set<V> getTupleStarts() {
198 Set<V> nodes = CollectionsFactory.createSet();
199 for (V s : tuplesForward.distinctKeys()) {
200 nodes.add(s);
201 }
202 return nodes;
203 }
204
205 /**
206 * Returns true if a (source, target) node is present in the transitive closure relation, false otherwise.
207 *
208 * @param source
209 * the source node
210 * @param target
211 * the target node
212 * @return true if tuple is present, false otherwise
213 */
214 public boolean containsTuple(V source, V target) {
215 return tuplesForward.lookupOrEmpty(source).containsNonZero(target);
216 }
217
218 @SuppressWarnings("unchecked")
219 @Override
220 public boolean equals(Object obj) {
221 if (this == obj) {
222 return true;
223 } else if (obj == null || this.getClass() != obj.getClass()) {
224 return false;
225 } else {
226 CountingTcRelation<V> aTR = (CountingTcRelation<V>) obj;
227
228 return tuplesForward.equals(aTR.tuplesForward);
229 }
230 }
231
232 @Override
233 public int hashCode() {
234 return tuplesForward.hashCode();
235 }
236
237 public static <V> CountingTcRelation<V> createFrom(IBiDirectionalGraphDataSource<V> gds) {
238 List<V> topologicalSorting = TopologicalSorting.compute(gds);
239 CountingTcRelation<V> tc = new CountingTcRelation<V>(true);
240 Collections.reverse(topologicalSorting);
241 for (V n : topologicalSorting) {
242 IMemoryView<V> sourceNodes = gds.getSourceNodes(n);
243 Set<V> tupEnds = tc.getTupleEnds(n);
244 for (V s : sourceNodes.distinctValues()) {
245 int count = sourceNodes.getCount(s);
246 for (int i = 0; i < count; i++) {
247 tc.updateTuple(s, n, true);
248 if (tupEnds != null) {
249 for (V t : tupEnds) {
250 tc.updateTuple(s, t, true);
251 }
252 }
253 }
254 }
255 }
256
257 return tc;
258 }
259}
diff --git a/subprojects/viatra-runtime-base-itc/src/main/java/tools/refinery/viatra/runtime/base/itc/alg/dred/DRedAlg.java b/subprojects/viatra-runtime-base-itc/src/main/java/tools/refinery/viatra/runtime/base/itc/alg/dred/DRedAlg.java
deleted file mode 100644
index b92d08bf..00000000
--- a/subprojects/viatra-runtime-base-itc/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
10package tools.refinery.viatra.runtime.base.itc.alg.dred;
11
12import java.util.ArrayList;
13import java.util.HashMap;
14import java.util.HashSet;
15import java.util.List;
16import java.util.Map;
17import java.util.Map.Entry;
18import java.util.Set;
19
20import tools.refinery.viatra.runtime.base.itc.alg.misc.DFSPathFinder;
21import tools.refinery.viatra.runtime.base.itc.alg.misc.IGraphPathFinder;
22import tools.refinery.viatra.runtime.base.itc.alg.misc.Tuple;
23import tools.refinery.viatra.runtime.base.itc.alg.misc.dfs.DFSAlg;
24import tools.refinery.viatra.runtime.base.itc.igraph.IGraphDataSource;
25import tools.refinery.viatra.runtime.base.itc.igraph.IGraphObserver;
26import tools.refinery.viatra.runtime.base.itc.igraph.ITcDataSource;
27import tools.refinery.viatra.runtime.base.itc.igraph.ITcObserver;
28import 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 */
38public 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-base-itc/src/main/java/tools/refinery/viatra/runtime/base/itc/alg/dred/DRedTcRelation.java b/subprojects/viatra-runtime-base-itc/src/main/java/tools/refinery/viatra/runtime/base/itc/alg/dred/DRedTcRelation.java
deleted file mode 100644
index 8543b79c..00000000
--- a/subprojects/viatra-runtime-base-itc/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
10package tools.refinery.viatra.runtime.base.itc.alg.dred;
11
12import java.util.HashMap;
13import java.util.HashSet;
14import java.util.Map;
15import java.util.Map.Entry;
16import java.util.Set;
17
18import tools.refinery.viatra.runtime.base.itc.alg.misc.ITcRelation;
19
20public 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-base-itc/src/main/java/tools/refinery/viatra/runtime/base/itc/alg/fw/FloydWarshallAlg.java b/subprojects/viatra-runtime-base-itc/src/main/java/tools/refinery/viatra/runtime/base/itc/alg/fw/FloydWarshallAlg.java
deleted file mode 100644
index b369f1a1..00000000
--- a/subprojects/viatra-runtime-base-itc/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
10package tools.refinery.viatra.runtime.base.itc.alg.fw;
11
12import java.util.HashMap;
13import java.util.Map;
14
15import tools.refinery.viatra.runtime.base.itc.alg.dred.DRedTcRelation;
16import tools.refinery.viatra.runtime.base.itc.igraph.IBiDirectionalGraphDataSource;
17import tools.refinery.viatra.runtime.base.itc.igraph.IBiDirectionalWrapper;
18import tools.refinery.viatra.runtime.base.itc.igraph.IGraphDataSource;
19import tools.refinery.viatra.runtime.base.itc.igraph.IGraphObserver;
20import tools.refinery.viatra.runtime.matchers.util.IMemoryView;
21
22public 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-base-itc/src/main/java/tools/refinery/viatra/runtime/base/itc/alg/incscc/CountingListener.java b/subprojects/viatra-runtime-base-itc/src/main/java/tools/refinery/viatra/runtime/base/itc/alg/incscc/CountingListener.java
deleted file mode 100644
index fdf64f77..00000000
--- a/subprojects/viatra-runtime-base-itc/src/main/java/tools/refinery/viatra/runtime/base/itc/alg/incscc/CountingListener.java
+++ /dev/null
@@ -1,36 +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 *******************************************************************************/
9package tools.refinery.viatra.runtime.base.itc.alg.incscc;
10
11import tools.refinery.viatra.runtime.base.itc.igraph.ITcObserver;
12import tools.refinery.viatra.runtime.matchers.util.Direction;
13
14/**
15 * @author Tamas Szabo
16 *
17 */
18public class CountingListener<V> implements ITcObserver<V> {
19
20 private IncSCCAlg<V> alg;
21
22 public CountingListener(IncSCCAlg<V> alg) {
23 this.alg = alg;
24 }
25
26 @Override
27 public void tupleInserted(V source, V target) {
28 alg.notifyTcObservers(alg.sccs.getPartition(source), alg.sccs.getPartition(target), Direction.INSERT);
29 }
30
31 @Override
32 public void tupleDeleted(V source, V target) {
33 alg.notifyTcObservers(alg.sccs.getPartition(source), alg.sccs.getPartition(target), Direction.DELETE);
34 }
35
36} \ No newline at end of file
diff --git a/subprojects/viatra-runtime-base-itc/src/main/java/tools/refinery/viatra/runtime/base/itc/alg/incscc/IncSCCAlg.java b/subprojects/viatra-runtime-base-itc/src/main/java/tools/refinery/viatra/runtime/base/itc/alg/incscc/IncSCCAlg.java
deleted file mode 100644
index f1e0ad44..00000000
--- a/subprojects/viatra-runtime-base-itc/src/main/java/tools/refinery/viatra/runtime/base/itc/alg/incscc/IncSCCAlg.java
+++ /dev/null
@@ -1,645 +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
10package tools.refinery.viatra.runtime.base.itc.alg.incscc;
11
12import java.util.ArrayList;
13import java.util.HashSet;
14import java.util.Iterator;
15import java.util.List;
16import java.util.Map;
17import java.util.Map.Entry;
18import java.util.Objects;
19import java.util.Set;
20
21import tools.refinery.viatra.runtime.base.itc.alg.counting.CountingAlg;
22import tools.refinery.viatra.runtime.base.itc.alg.dred.DRedTcRelation;
23import tools.refinery.viatra.runtime.base.itc.alg.misc.DFSPathFinder;
24import tools.refinery.viatra.runtime.base.itc.alg.misc.GraphHelper;
25import tools.refinery.viatra.runtime.base.itc.alg.misc.IGraphPathFinder;
26import tools.refinery.viatra.runtime.base.itc.alg.misc.Tuple;
27import tools.refinery.viatra.runtime.base.itc.alg.misc.bfs.BFS;
28import tools.refinery.viatra.runtime.base.itc.alg.misc.scc.SCC;
29import tools.refinery.viatra.runtime.base.itc.alg.misc.scc.SCCResult;
30import tools.refinery.viatra.runtime.base.itc.alg.util.CollectionHelper;
31import tools.refinery.viatra.runtime.base.itc.graphimpl.Graph;
32import tools.refinery.viatra.runtime.base.itc.igraph.IBiDirectionalGraphDataSource;
33import tools.refinery.viatra.runtime.base.itc.igraph.IBiDirectionalWrapper;
34import tools.refinery.viatra.runtime.base.itc.igraph.IGraphDataSource;
35import tools.refinery.viatra.runtime.base.itc.igraph.IGraphObserver;
36import tools.refinery.viatra.runtime.base.itc.igraph.ITcDataSource;
37import tools.refinery.viatra.runtime.base.itc.igraph.ITcObserver;
38import tools.refinery.viatra.runtime.matchers.algorithms.UnionFind;
39import tools.refinery.viatra.runtime.matchers.util.CollectionsFactory;
40import tools.refinery.viatra.runtime.matchers.util.Direction;
41import tools.refinery.viatra.runtime.matchers.util.IMemoryView;
42
43/**
44 * Incremental SCC maintenance + counting algorithm.
45 *
46 * @author Tamas Szabo
47 *
48 * @param <V>
49 * the type parameter of the nodes in the graph data source
50 */
51public class IncSCCAlg<V> implements IGraphObserver<V>, ITcDataSource<V> {
52
53 public UnionFind<V> sccs;
54 public IBiDirectionalGraphDataSource<V> gds;
55 private CountingAlg<V> counting;
56 private Graph<V> reducedGraph;
57 private IBiDirectionalGraphDataSource<V> reducedGraphIndexer;
58 private List<ITcObserver<V>> observers;
59 private CountingListener<V> countingListener;
60
61 public IncSCCAlg(IGraphDataSource<V> graphDataSource) {
62
63 if (graphDataSource instanceof IBiDirectionalGraphDataSource<?>) {
64 gds = (IBiDirectionalGraphDataSource<V>) graphDataSource;
65 } else {
66 gds = new IBiDirectionalWrapper<V>(graphDataSource);
67 }
68 observers = CollectionsFactory.createObserverList();
69 sccs = new UnionFind<V>();
70 reducedGraph = new Graph<V>();
71 reducedGraphIndexer = new IBiDirectionalWrapper<V>(reducedGraph);
72 countingListener = new CountingListener<V>(this);
73 initalizeInternalDataStructures();
74 gds.attachObserver(this);
75 }
76
77 private void initalizeInternalDataStructures() {
78 SCCResult<V> _sccres = SCC.computeSCC(gds);
79 Set<Set<V>> _sccs = _sccres.getSccs();
80
81 for (Set<V> _set : _sccs) {
82 sccs.makeSet(_set);
83 }
84
85 // Initalization of the reduced graph
86 for (V n : sccs.getPartitionHeads()) {
87 reducedGraph.insertNode(n);
88 }
89
90 for (V source : gds.getAllNodes()) {
91 final IMemoryView<V> targetNodes = gds.getTargetNodes(source);
92 for (Entry<V, Integer> entry : targetNodes.entriesWithMultiplicities()) {
93 for (int i = 0; i < entry.getValue(); i++) {
94 V target = entry.getKey();
95 V sourceRoot = sccs.find(source);
96 V targetRoot = sccs.find(target);
97
98 if (!sourceRoot.equals(targetRoot)) {
99 reducedGraph.insertEdge(sourceRoot, targetRoot);
100 }
101 }
102 }
103 }
104
105 counting = new CountingAlg<V>(reducedGraph);
106 }
107
108 @Override
109 public void edgeInserted(V source, V target) {
110 V sourceRoot = sccs.find(source);
111 V targetRoot = sccs.find(target);
112
113 // Different SCC
114 if (!sourceRoot.equals(targetRoot)) {
115
116 // source is reachable from target?
117 if (counting.isReachable(targetRoot, sourceRoot)) {
118
119 Set<V> predecessorRoots = counting.getAllReachableSources(sourceRoot);
120 Set<V> successorRoots = counting.getAllReachableTargets(targetRoot);
121
122 // 1. intersection of source and target roots, these will be in the merged SCC
123 Set<V> isectRoots = CollectionHelper.intersection(predecessorRoots, successorRoots);
124 isectRoots.add(sourceRoot);
125 isectRoots.add(targetRoot);
126
127 // notifications must be issued before Union-Find modifications
128 if (observers.size() > 0) {
129 Set<V> sourceSCCs = createSetNullTolerant(predecessorRoots);
130 sourceSCCs.add(sourceRoot);
131 Set<V> targetSCCs = createSetNullTolerant(successorRoots);
132 targetSCCs.add(targetRoot);
133
134 // tracing back to actual nodes
135 for (V sourceSCC : sourceSCCs) {
136 targetLoop: for (V targetSCC : targetSCCs) {
137 if (counting.isReachable(sourceSCC, targetSCC)) continue targetLoop;
138
139 boolean needsNotification =
140 // Case 1. sourceSCC and targetSCC are the same and it is a one sized scc.
141 // Issue notifications only if there is no self-loop present at the moment
142 (sourceSCC.equals(targetSCC) && sccs.getPartition(sourceSCC).size() == 1 && GraphHelper
143 .getEdgeCount(sccs.getPartition(sourceSCC).iterator().next(), gds) == 0)
144 ||
145 // Case 2. sourceSCC and targetSCC are different sccs.
146 (!sourceSCC.equals(targetSCC));
147 // if self loop is already present omit the notification
148 if (needsNotification) {
149 notifyTcObservers(sccs.getPartition(sourceSCC), sccs.getPartition(targetSCC),
150 Direction.INSERT);
151 }
152 }
153 }
154 }
155
156 // 2. delete edges, nodes
157 List<V> sourceSCCs = new ArrayList<V>();
158 List<V> targetSCCs = new ArrayList<V>();
159
160 for (V r : isectRoots) {
161 List<V> sourceSCCsOfSCC = getSourceSCCsOfSCC(r);
162 List<V> targetSCCsOfSCC = getTargetSCCsOfSCC(r);
163
164 for (V sourceSCC : sourceSCCsOfSCC) {
165 if (!sourceSCC.equals(r)) {
166 reducedGraph.deleteEdgeIfExists(sourceSCC, r);
167 }
168 }
169
170 for (V targetSCC : targetSCCsOfSCC) {
171 if (!isectRoots.contains(targetSCC) && !r.equals(targetSCC)) {
172 reducedGraph.deleteEdgeIfExists(r, targetSCC);
173 }
174 }
175
176 sourceSCCs.addAll(sourceSCCsOfSCC);
177 targetSCCs.addAll(targetSCCsOfSCC);
178 }
179
180 for (V r : isectRoots) {
181 reducedGraph.deleteNode(r);
182 }
183
184 // 3. union
185 Iterator<V> iterator = isectRoots.iterator();
186 V newRoot = iterator.next();
187 while (iterator.hasNext()) {
188 newRoot = sccs.union(newRoot, iterator.next());
189 }
190
191 // 4. add new node
192 reducedGraph.insertNode(newRoot);
193
194 // 5. add edges
195 Set<V> containedNodes = sccs.getPartition(newRoot);
196
197 for (V sourceSCC : sourceSCCs) {
198 if (!containedNodes.contains(sourceSCC) && !sourceSCC.equals(newRoot)) {
199 reducedGraph.insertEdge(sourceSCC, newRoot);
200 }
201 }
202 for (V targetSCC : targetSCCs) {
203 if (!containedNodes.contains(targetSCC) && !targetSCC.equals(newRoot)) {
204 reducedGraph.insertEdge(newRoot, targetSCC);
205 }
206 }
207 } else {
208 if (observers.size() > 0 && GraphHelper.getEdgeCount(source, target, gds) == 1) {
209 counting.attachObserver(countingListener);
210 }
211 reducedGraph.insertEdge(sourceRoot, targetRoot);
212 counting.detachObserver(countingListener);
213 }
214 } else {
215 // Notifications about self-loops
216 if (observers.size() > 0 && sccs.getPartition(sourceRoot).size() == 1
217 && GraphHelper.getEdgeCount(source, target, gds) == 1) {
218 notifyTcObservers(source, source, Direction.INSERT);
219 }
220 }
221 }
222
223 @Override
224 public void edgeDeleted(V source, V target) {
225 V sourceRoot = sccs.find(source);
226 V targetRoot = sccs.find(target);
227
228 if (!sourceRoot.equals(targetRoot)) {
229 if (observers.size() > 0 && GraphHelper.getEdgeCount(source, target, gds) == 0) {
230 counting.attachObserver(countingListener);
231 }
232 reducedGraph.deleteEdgeIfExists(sourceRoot, targetRoot);
233 counting.detachObserver(countingListener);
234 } else {
235 // get the graph for the scc whose root is sourceRoot
236 Graph<V> g = GraphHelper.getSubGraph(sccs.getPartition(sourceRoot), gds);
237
238 // if source is not reachable from target anymore
239 if (!BFS.isReachable(source, target, g)) {
240 // create copies of the current state before destructive manipulation
241 Map<V, Integer> reachableSources = CollectionsFactory.createMap();
242 for (Entry<V, Integer> entry : reducedGraphIndexer.getSourceNodes(sourceRoot).entriesWithMultiplicities()) {
243 reachableSources.put(entry.getKey(), entry.getValue());
244 }
245 Map<V, Integer> reachableTargets = CollectionsFactory.createMap();
246 for (Entry<V, Integer> entry : reducedGraphIndexer.getTargetNodes(sourceRoot).entriesWithMultiplicities()) {
247 reachableTargets.put(entry.getKey(), entry.getValue());
248 }
249
250 SCCResult<V> _newSccs = SCC.computeSCC(g);
251
252 // delete scc node (and with its edges too)
253 for (Entry<V, Integer> entry : reachableSources.entrySet()) {
254 V s = entry.getKey();
255 for (int i = 0; i < entry.getValue(); i++) {
256 reducedGraph.deleteEdgeIfExists(s, sourceRoot);
257 }
258 }
259
260 for (Entry<V, Integer> entry : reachableTargets.entrySet()) {
261 V t = entry.getKey();
262 for (int i = 0; i < entry.getValue(); i++) {
263 reducedGraph.deleteEdgeIfExists(sourceRoot, t);
264 }
265 }
266
267 sccs.deleteSet(sourceRoot);
268 reducedGraph.deleteNode(sourceRoot);
269
270 Set<Set<V>> newSCCs = _newSccs.getSccs();
271 Set<V> newSCCRoots = CollectionsFactory.createSet();
272
273 // add new nodes and edges to the reduced graph
274 for (Set<V> newSCC : newSCCs) {
275 V newRoot = sccs.makeSet(newSCC);
276 reducedGraph.insertNode(newRoot);
277 newSCCRoots.add(newRoot);
278 }
279 for (V newSCCRoot : newSCCRoots) {
280 List<V> sourceSCCsOfSCC = getSourceSCCsOfSCC(newSCCRoot);
281 List<V> targetSCCsOfSCC = getTargetSCCsOfSCC(newSCCRoot);
282
283 for (V sourceSCC : sourceSCCsOfSCC) {
284 if (!sourceSCC.equals(newSCCRoot)) {
285 reducedGraph.insertEdge(sccs.find(sourceSCC), newSCCRoot);
286 }
287 }
288 for (V targetSCC : targetSCCsOfSCC) {
289 if (!newSCCRoots.contains(targetSCC) && !targetSCC.equals(newSCCRoot))
290 reducedGraph.insertEdge(newSCCRoot, targetSCC);
291 }
292 }
293
294 // Must be after the union-find modifications
295 if (observers.size() > 0) {
296 V newSourceRoot = sccs.find(source);
297 V newTargetRoot = sccs.find(target);
298
299 Set<V> sourceSCCs = createSetNullTolerant(counting.getAllReachableSources(newSourceRoot));
300 sourceSCCs.add(newSourceRoot);
301
302 Set<V> targetSCCs = createSetNullTolerant(counting.getAllReachableTargets(newTargetRoot));
303 targetSCCs.add(newTargetRoot);
304
305 for (V sourceSCC : sourceSCCs) {
306 targetLoop: for (V targetSCC : targetSCCs) {
307 if (counting.isReachable(sourceSCC, targetSCC)) continue targetLoop;
308
309 boolean needsNotification =
310 // Case 1. sourceSCC and targetSCC are the same and it is a one sized scc.
311 // Issue notifications only if there is no self-loop present at the moment
312 (sourceSCC.equals(targetSCC) && sccs.getPartition(sourceSCC).size() == 1 && GraphHelper
313 .getEdgeCount(sccs.getPartition(sourceSCC).iterator().next(), gds) == 0)
314 ||
315 // Case 2. sourceSCC and targetSCC are different sccs.
316 (!sourceSCC.equals(targetSCC));
317 // if self loop is already present omit the notification
318 if (needsNotification) {
319 notifyTcObservers(sccs.getPartition(sourceSCC), sccs.getPartition(targetSCC),
320 Direction.DELETE);
321 }
322 }
323 }
324 }
325 } else {
326 // only handle self-loop notifications - sourceRoot equals to targetRoot
327 if (observers.size() > 0 && sccs.getPartition(sourceRoot).size() == 1
328 && GraphHelper.getEdgeCount(source, target, gds) == 0) {
329 notifyTcObservers(source, source, Direction.DELETE);
330 }
331 }
332 }
333 }
334
335 @Override
336 public void nodeInserted(V n) {
337 sccs.makeSet(n);
338 reducedGraph.insertNode(n);
339 }
340
341 @Override
342 public void nodeDeleted(V n) {
343 IMemoryView<V> sources = gds.getSourceNodes(n);
344 IMemoryView<V> targets = gds.getTargetNodes(n);
345
346 for (Entry<V, Integer> entry : sources.entriesWithMultiplicities()) {
347 for (int i = 0; i < entry.getValue(); i++) {
348 V source = entry.getKey();
349 edgeDeleted(source, n);
350 }
351 }
352
353 for (Entry<V, Integer> entry : targets.entriesWithMultiplicities()) {
354 for (int i = 0; i < entry.getValue(); i++) {
355 V target = entry.getKey();
356 edgeDeleted(n, target);
357 }
358 }
359
360 sccs.deleteSet(n);
361 }
362
363 @Override
364 public void attachObserver(ITcObserver<V> to) {
365 observers.add(to);
366 }
367
368 @Override
369 public void detachObserver(ITcObserver<V> to) {
370 observers.remove(to);
371 }
372
373 @Override
374 public Set<V> getAllReachableTargets(V source) {
375 V sourceRoot = sccs.find(source);
376 Set<V> containedNodes = sccs.getPartition(sourceRoot);
377 Set<V> targets = CollectionsFactory.createSet();
378
379 if (containedNodes.size() > 1 || GraphHelper.getEdgeCount(source, gds) == 1) {
380 targets.addAll(containedNodes);
381 }
382
383 Set<V> rootSet = counting.getAllReachableTargets(sourceRoot);
384 if (rootSet != null) {
385 for (V _root : rootSet) {
386 targets.addAll(sccs.getPartition(_root));
387 }
388 }
389
390 return targets;
391 }
392
393 @Override
394 public Set<V> getAllReachableSources(V target) {
395 V targetRoot = sccs.find(target);
396 Set<V> containedNodes = sccs.getPartition(targetRoot);
397 Set<V> sources = CollectionsFactory.createSet();
398
399 if (containedNodes.size() > 1 || GraphHelper.getEdgeCount(target, gds) == 1) {
400 sources.addAll(containedNodes);
401 }
402
403 Set<V> rootSet = counting.getAllReachableSources(targetRoot);
404 if (rootSet != null) {
405 for (V _root : rootSet) {
406 sources.addAll(sccs.getPartition(_root));
407 }
408 }
409 return sources;
410 }
411
412 @Override
413 public boolean isReachable(V source, V target) {
414 V sourceRoot = sccs.find(source);
415 V targetRoot = sccs.find(target);
416
417 if (sourceRoot.equals(targetRoot))
418 return true;
419 else
420 return counting.isReachable(sourceRoot, targetRoot);
421 }
422
423 public List<V> getReachabilityPath(V source, V target) {
424 if (!isReachable(source, target)) {
425 return null;
426 } else {
427 Set<V> sccsInSubGraph = CollectionHelper.intersection(counting.getAllReachableTargets(source),
428 counting.getAllReachableSources(target));
429 sccsInSubGraph.add(sccs.find(source));
430 sccsInSubGraph.add(sccs.find(target));
431 Set<V> nodesInSubGraph = CollectionsFactory.createSet();
432
433 for (V sccRoot : sccsInSubGraph) {
434 nodesInSubGraph.addAll(sccs.getPartition(sccRoot));
435 }
436
437 return GraphHelper.constructPath(source, target, nodesInSubGraph, gds);
438 }
439 }
440
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 /**
466 * 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).
468 *
469 * @param root
470 * @return the list of reachable target SCCs
471 */
472 private List<V> getSourceSCCsOfSCC(V root) {
473 List<V> sourceSCCs = new ArrayList<V>();
474
475 for (V containedNode : this.sccs.getPartition(root)) {
476 IMemoryView<V> sourceNodes = this.gds.getSourceNodes(containedNode);
477 for (V source : sourceNodes.distinctValues()) {
478 sourceSCCs.add(this.sccs.find(source));
479 }
480 }
481
482 return sourceSCCs;
483 }
484
485 /**
486 * Returns true if the SCC represented by the given root node has incoming edges in the reduced graph,
487 * false otherwise (if this SCC is a source in the reduced graph).
488 *
489 * @param root the root node of an SCC
490 * @return true if it has incoming edges, false otherwise
491 * @since 1.6
492 */
493 public boolean hasIncomingEdges(final V root) {
494 for (final V containedNode : this.sccs.getPartition(root)) {
495 final IMemoryView<V> sourceNodes = this.gds.getSourceNodes(containedNode);
496 for (final V source : sourceNodes.distinctValues()) {
497 final V otherRoot = this.sccs.find(source);
498 if (!Objects.equals(root, otherRoot)) {
499 return true;
500 }
501 }
502 }
503 return false;
504 }
505
506 /**
507 * Return the SCCs which are reachable from the SCC represented by the root node. Note that an SCC can be present
508 * multiple times in the returned list (multiple edges between the two SCCs).
509 *
510 * @param root
511 * @return the list of reachable target SCCs
512 */
513 private List<V> getTargetSCCsOfSCC(V root) {
514 List<V> targetSCCs = new ArrayList<V>();
515
516 for (V containedNode : this.sccs.getPartition(root)) {
517 IMemoryView<V> targetNodes = this.gds.getTargetNodes(containedNode);
518 for (V target : targetNodes.distinctValues()) {
519 targetSCCs.add(this.sccs.find(target));
520 }
521 }
522
523 return targetSCCs;
524 }
525
526 /**
527 * Returns true if the SCC represented by the given root node has outgoing edges in the reduced graph,
528 * false otherwise (if this SCC is a sink in the reduced graph).
529 *
530 * @param root the root node of an SCC
531 * @return true if it has outgoing edges, false otherwise
532 * @since 1.6
533 */
534 public boolean hasOutgoingEdges(V root) {
535 for (final V containedNode : this.sccs.getPartition(root)) {
536 final IMemoryView<V> targetNodes = this.gds.getTargetNodes(containedNode);
537 for (final V target : targetNodes.distinctValues()) {
538 final V otherRoot = this.sccs.find(target);
539 if (!Objects.equals(root, otherRoot)) {
540 return true;
541 }
542 }
543 }
544 return false;
545 }
546
547 @Override
548 public void dispose() {
549 gds.detachObserver(this);
550 counting.dispose();
551 }
552
553 /**
554 * Call this method to notify the observers of the transitive closure relation. The tuples used in the notification
555 * will be the Descartes product of the two sets given.
556 *
557 * @param sources
558 * the source nodes
559 * @param targets
560 * the target nodes
561 * @param direction
562 */
563 protected void notifyTcObservers(Set<V> sources, Set<V> targets, Direction direction) {
564 for (V s : sources) {
565 for (V t : targets) {
566 notifyTcObservers(s, t, direction);
567 }
568 }
569 }
570
571 private void notifyTcObservers(V source, V target, Direction direction) {
572 for (ITcObserver<V> observer : observers) {
573 if (direction == Direction.INSERT) {
574 observer.tupleInserted(source, target);
575 }
576 if (direction == Direction.DELETE) {
577 observer.tupleDeleted(source, target);
578 }
579 }
580 }
581
582 /**
583 * Returns the node that is selected as the representative of the SCC containing the argument.
584 * @since 1.6
585 */
586 public V getRepresentative(V node) {
587 return sccs.find(node);
588 }
589
590 public Set<Tuple<V>> getTcRelation() {
591 Set<Tuple<V>> resultSet = new HashSet<Tuple<V>>();
592
593 for (V sourceRoot : sccs.getPartitionHeads()) {
594 Set<V> sources = sccs.getPartition(sourceRoot);
595 if (sources.size() > 1 || GraphHelper.getEdgeCount(sources.iterator().next(), gds) == 1) {
596 for (V source : sources) {
597 for (V target : sources) {
598 resultSet.add(new Tuple<V>(source, target));
599 }
600 }
601 }
602
603 Set<V> reachableTargets = counting.getAllReachableTargets(sourceRoot);
604 if (reachableTargets != null) {
605 for (V targetRoot : reachableTargets) {
606 for (V source : sources) {
607 for (V target : sccs.getPartition(targetRoot)) {
608 resultSet.add(new Tuple<V>(source, target));
609 }
610 }
611 }
612 }
613 }
614
615 return resultSet;
616 }
617
618 public boolean isIsolated(V node) {
619 IMemoryView<V> targets = gds.getTargetNodes(node);
620 IMemoryView<V> sources = gds.getSourceNodes(node);
621 return targets.isEmpty() && sources.isEmpty();
622 }
623
624 @Override
625 public IGraphPathFinder<V> getPathFinder() {
626 return new DFSPathFinder<V>(gds, this);
627 }
628
629 /**
630 * The graph of SCCs; each SCC is represented by its representative node (see {@link #getRepresentative(Object)})
631 * @since 1.6
632 */
633 public Graph<V> getReducedGraph() {
634 return reducedGraph;
635 }
636
637 private static <V> Set<V> createSetNullTolerant(Set<V> initial) {
638 if (initial != null)
639 return CollectionsFactory.createSet(initial);
640 else
641 return CollectionsFactory.createSet();
642 }
643
644
645}
diff --git a/subprojects/viatra-runtime-base-itc/src/main/java/tools/refinery/viatra/runtime/base/itc/alg/misc/DFSPathFinder.java b/subprojects/viatra-runtime-base-itc/src/main/java/tools/refinery/viatra/runtime/base/itc/alg/misc/DFSPathFinder.java
deleted file mode 100644
index 51017b1a..00000000
--- a/subprojects/viatra-runtime-base-itc/src/main/java/tools/refinery/viatra/runtime/base/itc/alg/misc/DFSPathFinder.java
+++ /dev/null
@@ -1,146 +0,0 @@
1/*******************************************************************************
2 * Copyright (c) 2010-2016, Abel Hegedus and IncQueryLabs Ltd.
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 *******************************************************************************/
9package tools.refinery.viatra.runtime.base.itc.alg.misc;
10
11import java.util.ArrayList;
12import java.util.Deque;
13import java.util.HashSet;
14import java.util.Iterator;
15import java.util.LinkedList;
16import java.util.List;
17import java.util.Set;
18
19import tools.refinery.viatra.runtime.base.itc.igraph.IGraphDataSource;
20import tools.refinery.viatra.runtime.base.itc.igraph.ITcDataSource;
21import tools.refinery.viatra.runtime.matchers.util.IMemoryView;
22
23/**
24 * A depth-first search implementation of the {@link IGraphPathFinder}.
25 *
26 * TODO use ITC to filter nodes that must be traversed, instead of checks
27 *
28 * @author Abel Hegedus
29 *
30 * @param <V>
31 * the node type of the graph
32 */
33public class DFSPathFinder<V> implements IGraphPathFinder<V> {
34
35 private IGraphDataSource<V> graph;
36 private ITcDataSource<V> itc;
37
38 public DFSPathFinder(IGraphDataSource<V> graph, ITcDataSource<V> itc) {
39 this.graph = graph;
40 this.itc = itc;
41 }
42
43 @Override
44 public Iterable<Deque<V>> getAllPaths(V sourceNode, V targetNode) {
45 Set<V> endNodes = new HashSet<V>();
46 endNodes.add(targetNode);
47 return getAllPathsToTargets(sourceNode, endNodes);
48 }
49
50 @Override
51 public Iterable<Deque<V>> getAllPathsToTargets(V sourceNode, Set<V> targetNodes) {
52 List<Deque<V>> paths = new ArrayList<Deque<V>>();
53 Deque<V> visited = new LinkedList<V>();
54 Set<V> reachableTargets = new HashSet<V>();
55 for (V targetNode : targetNodes) {
56 if (itc.isReachable(sourceNode, targetNode)) {
57 reachableTargets.add(targetNode);
58 }
59 }
60 if (!reachableTargets.isEmpty()) {
61 return paths;
62 }
63 visited.add(sourceNode);
64 return getPaths(paths, visited, reachableTargets);
65 }
66
67 protected Iterable<Deque<V>> getPaths(List<Deque<V>> paths, Deque<V> visited, Set<V> targetNodes) {
68 IMemoryView<V> nodes = graph.getTargetNodes(visited.getLast());
69 // examine adjacent nodes
70 for (V node : nodes.distinctValues()) {
71 if (visited.contains(node)) {
72 continue;
73 }
74 if (targetNodes.contains(node)) {
75 visited.add(node);
76 // clone visited LinkedList
77 Deque<V> visitedClone = new LinkedList<V>(visited);
78 paths.add(visitedClone);
79 visited.removeLast();
80 break;
81 }
82 }
83
84 // in breadth-first, recursion needs to come after visiting connected nodes
85 for (V node : nodes.distinctValues()) {
86 if (visited.contains(node) || targetNodes.contains(node)) {
87 continue;
88 }
89 boolean canReachTarget = false;
90 for (V target : targetNodes) {
91 if (itc.isReachable(node, target)) {
92 canReachTarget = true;
93 break;
94 }
95 }
96 if (canReachTarget) {
97 visited.addLast(node);
98 getPaths(paths, visited, targetNodes);
99 visited.removeLast();
100 }
101 }
102
103 return paths;
104 }
105
106 public String printPaths(List<Deque<V>> paths) {
107 StringBuilder sb = new StringBuilder();
108 for (Deque<V> visited : paths) {
109 sb.append("Path: ");
110 for (V node : visited) {
111 sb.append(node);
112 sb.append(" --> ");
113 }
114 sb.append("\n");
115 }
116 return sb.toString();
117 }
118
119 @Override
120 public Deque<V> getPath(V sourceNode, V targetNode) {
121 // TODO optimize
122 Iterable<Deque<V>> allPaths = getAllPaths(sourceNode, targetNode);
123 Iterator<Deque<V>> pathIterator = allPaths.iterator();
124 return pathIterator.hasNext() ? pathIterator.next() : new LinkedList<V>();
125 }
126
127 @Override
128 public Iterable<Deque<V>> getShortestPaths(V sourceNode, V targetNode) {
129 // TODO optimize
130 Iterable<Deque<V>> allPaths = getAllPaths(sourceNode, targetNode);
131 List<Deque<V>> shortestPaths = new ArrayList<Deque<V>>();
132 int shortestPathLength = -1;
133 for (Deque<V> path : allPaths) {
134 int pathLength = path.size();
135 if (shortestPathLength == -1 || pathLength < shortestPathLength) {
136 shortestPaths.clear();
137 shortestPathLength = pathLength;
138 }
139 if (pathLength == shortestPathLength) {
140 shortestPaths.add(path);
141 }
142 }
143 return shortestPaths;
144 }
145
146}
diff --git a/subprojects/viatra-runtime-base-itc/src/main/java/tools/refinery/viatra/runtime/base/itc/alg/misc/Edge.java b/subprojects/viatra-runtime-base-itc/src/main/java/tools/refinery/viatra/runtime/base/itc/alg/misc/Edge.java
deleted file mode 100644
index cf68d36a..00000000
--- a/subprojects/viatra-runtime-base-itc/src/main/java/tools/refinery/viatra/runtime/base/itc/alg/misc/Edge.java
+++ /dev/null
@@ -1,38 +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
10package tools.refinery.viatra.runtime.base.itc.alg.misc;
11
12public class Edge<V> {
13 private V source;
14 private V target;
15
16 public Edge(V source, V target) {
17 super();
18 this.source = source;
19 this.target = target;
20 }
21
22 public V getSource() {
23 return source;
24 }
25
26 public void setSource(V source) {
27 this.source = source;
28 }
29
30 public V getTarget() {
31 return target;
32 }
33
34 public void setTarget(V target) {
35 this.target = target;
36 }
37
38}
diff --git a/subprojects/viatra-runtime-base-itc/src/main/java/tools/refinery/viatra/runtime/base/itc/alg/misc/GraphHelper.java b/subprojects/viatra-runtime-base-itc/src/main/java/tools/refinery/viatra/runtime/base/itc/alg/misc/GraphHelper.java
deleted file mode 100644
index 194e979b..00000000
--- a/subprojects/viatra-runtime-base-itc/src/main/java/tools/refinery/viatra/runtime/base/itc/alg/misc/GraphHelper.java
+++ /dev/null
@@ -1,173 +0,0 @@
1/*******************************************************************************
2 * Copyright (c) 2010-2013, 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 *******************************************************************************/
9package tools.refinery.viatra.runtime.base.itc.alg.misc;
10
11import java.util.ArrayList;
12import java.util.Collection;
13import java.util.HashSet;
14import java.util.List;
15import java.util.Map.Entry;
16import java.util.Set;
17
18import tools.refinery.viatra.runtime.base.itc.graphimpl.Graph;
19import tools.refinery.viatra.runtime.base.itc.igraph.IBiDirectionalGraphDataSource;
20import tools.refinery.viatra.runtime.base.itc.igraph.IGraphDataSource;
21import tools.refinery.viatra.runtime.matchers.util.IMemoryView;
22
23/**
24 * Utility class for graph related operations.
25 *
26 * @author Tamas Szabo
27 */
28public class GraphHelper {
29
30 private GraphHelper() {/*Utility class constructor*/}
31
32 /**
33 * Returns the subgraph from the given {@link IBiDirectionalGraphDataSource} which contains the given set of nodes.
34 *
35 * @param nodesInSubGraph
36 * the nodes that are present in the subgraph
37 * @param graphDataSource
38 * the graph data source for the original graph
39 * @return the subgraph associated to the given nodes
40 */
41 public static <V> Graph<V> getSubGraph(Collection<V> nodesInSubGraph,
42 IBiDirectionalGraphDataSource<V> graphDataSource) {
43 Graph<V> g = new Graph<V>();
44 if (nodesInSubGraph != null) {
45 for (V node : nodesInSubGraph) {
46 g.insertNode(node);
47 }
48
49 for (V node : nodesInSubGraph) {
50 IMemoryView<V> sources = graphDataSource.getSourceNodes(node);
51 for (Entry<V, Integer> entry : sources.entriesWithMultiplicities()) {
52 for (int i = 0; i < entry.getValue(); i++) {
53 V s = entry.getKey();
54 if (nodesInSubGraph.contains(s)) {
55 g.insertEdge(s, node);
56 }
57 }
58 }
59 }
60 }
61
62 return g;
63 }
64
65 /**
66 * 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.
68 *
69 * 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
71 * in the returned {@link List}.
72 *
73 * @param source
74 * the source node
75 * @param target
76 * the target node
77 * @param nodesInGraph
78 * the nodes that are present in the subgraph
79 * @param graphDataSource
80 * the graph data source
81 * @return the path between the two nodes
82 */
83 public static <V> List<V> constructPath(V source, V target, Set<V> nodesInGraph,
84 IGraphDataSource<V> graphDataSource) {
85 Set<V> visitedNodes = new HashSet<V>();
86 List<V> path = new ArrayList<V>();
87
88 visitedNodes.add(source);
89 path.add(source);
90 V act = source;
91
92 // if source and target are the same node
93 if (source.equals(target) && graphDataSource.getTargetNodes(source).containsNonZero(target)) {
94 // the node will be present in the path two times
95 path.add(source);
96 return path;
97 } else {
98 while (act != null) {
99 V nextNode = getNextNodeToVisit(act, graphDataSource, nodesInGraph, visitedNodes);
100 if (nextNode == null && path.size() > 1) {
101 // needs to backtrack along path
102 // remove the last element in the path because we can't go
103 // anywhere from there
104 path.remove(path.size() - 1);
105 while (nextNode == null && path.size() > 0) {
106 V lastPathElement = path.get(path.size() - 1);
107 nextNode = getNextNodeToVisit(lastPathElement, graphDataSource, nodesInGraph, visitedNodes);
108 if (nextNode == null) {
109 path.remove(path.size() - 1);
110 }
111 }
112 }
113
114 if (nextNode != null) {
115 visitedNodes.add(nextNode);
116 path.add(nextNode);
117 if (nextNode.equals(target)) {
118 return path;
119 }
120 }
121 act = nextNode;
122 }
123 return null;
124 }
125 }
126
127 private static <V> V getNextNodeToVisit(V act, IGraphDataSource<V> graphDataSource, Set<V> nodesInSubGraph,
128 Set<V> visitedNodes) {
129 IMemoryView<V> targetNodes = graphDataSource.getTargetNodes(act);
130 for (Entry<V, Integer> entry : targetNodes.entriesWithMultiplicities()) {
131 for (int i = 0; i < entry.getValue(); i++) {
132 V node = entry.getKey();
133 if (nodesInSubGraph.contains(node) && !visitedNodes.contains(node)) {
134 return node;
135 }
136 }
137 }
138 return null;
139 }
140
141 /**
142 * Returns the number of self-loop edges for the given node.
143 *
144 * @param node
145 * the node
146 * @param graphDataSource
147 * the graph data source
148 * @return the number of self-loop edges
149 */
150 public static <V> int getEdgeCount(V node, IGraphDataSource<V> graphDataSource) {
151 return getEdgeCount(node, node, graphDataSource);
152 }
153
154 /**
155 * Returns the number of edges between the given source and target nodes.
156 *
157 * @param source
158 * the source node
159 * @param target
160 * the target node
161 * @param graphDataSource
162 * the graph data source
163 * @return the number of parallel edges between the two nodes
164 */
165 public static <V> int getEdgeCount(V source, V target, IGraphDataSource<V> graphDataSource) {
166 Integer count = graphDataSource.getTargetNodes(source).getCount(target);
167 if (count == null) {
168 return 0;
169 } else {
170 return count;
171 }
172 }
173}
diff --git a/subprojects/viatra-runtime-base-itc/src/main/java/tools/refinery/viatra/runtime/base/itc/alg/misc/IGraphPathFinder.java b/subprojects/viatra-runtime-base-itc/src/main/java/tools/refinery/viatra/runtime/base/itc/alg/misc/IGraphPathFinder.java
deleted file mode 100644
index cebb09c8..00000000
--- a/subprojects/viatra-runtime-base-itc/src/main/java/tools/refinery/viatra/runtime/base/itc/alg/misc/IGraphPathFinder.java
+++ /dev/null
@@ -1,67 +0,0 @@
1/*******************************************************************************
2 * Copyright (c) 2010-2013, Abel Hegedus, 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 *******************************************************************************/
9package tools.refinery.viatra.runtime.base.itc.alg.misc;
10
11import java.util.Deque;
12import java.util.Set;
13
14import tools.refinery.viatra.runtime.base.itc.igraph.ITcDataSource;
15
16/**
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.
19 *
20 * @author Abel Hegedus
21 *
22 * @param <V> the node type of the graph
23 */
24public interface IGraphPathFinder<V> {
25
26 /**
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.
29 *
30 * @param sourceNode the source 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.
33 */
34 Deque<V> getPath(V sourceNode, V targetNode);
35
36 /**
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.
39 *
40 * @param sourceNode the source 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.
43 */
44 Iterable<Deque<V>> getShortestPaths(V sourceNode, V targetNode);
45
46 /**
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.
49 *
50 * @param sourceNode the source 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.
53 */
54 Iterable<Deque<V>> getAllPaths(V sourceNode, V targetNode);
55
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
58 * between them, an empty collection is returned.
59 *
60 * @param sourceNode the source node of the path
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.
63 */
64 Iterable<Deque<V>> getAllPathsToTargets(V sourceNode, Set<V> targetNodes);
65
66
67} \ No newline at end of file
diff --git a/subprojects/viatra-runtime-base-itc/src/main/java/tools/refinery/viatra/runtime/base/itc/alg/misc/ITcRelation.java b/subprojects/viatra-runtime-base-itc/src/main/java/tools/refinery/viatra/runtime/base/itc/alg/misc/ITcRelation.java
deleted file mode 100644
index a41ff6c7..00000000
--- a/subprojects/viatra-runtime-base-itc/src/main/java/tools/refinery/viatra/runtime/base/itc/alg/misc/ITcRelation.java
+++ /dev/null
@@ -1,31 +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
10package tools.refinery.viatra.runtime.base.itc.alg.misc;
11
12import java.util.Set;
13
14public interface ITcRelation<V> {
15
16 /**
17 * Returns the starting nodes from a transitive closure relation.
18 *
19 * @return the set of starting nodes
20 */
21 public Set<V> getTupleStarts();
22
23 /**
24 * Returns the set of nodes that are reachable from the given node.
25 *
26 * @param start
27 * the starting node
28 * @return the set of reachable nodes
29 */
30 public Set<V> getTupleEnds(V start);
31}
diff --git a/subprojects/viatra-runtime-base-itc/src/main/java/tools/refinery/viatra/runtime/base/itc/alg/misc/Tuple.java b/subprojects/viatra-runtime-base-itc/src/main/java/tools/refinery/viatra/runtime/base/itc/alg/misc/Tuple.java
deleted file mode 100644
index a2d54a59..00000000
--- a/subprojects/viatra-runtime-base-itc/src/main/java/tools/refinery/viatra/runtime/base/itc/alg/misc/Tuple.java
+++ /dev/null
@@ -1,60 +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
10package tools.refinery.viatra.runtime.base.itc.alg.misc;
11
12public class Tuple<V> {
13
14 private V source;
15 private V target;
16
17 public Tuple(V source, V target) {
18 super();
19 this.source = source;
20 this.target = target;
21 }
22
23 public V getSource() {
24 return source;
25 }
26
27 public void setSource(V source) {
28 this.source = source;
29 }
30
31 public V getTarget() {
32 return target;
33 }
34
35 public void setTarget(V target) {
36 this.target = target;
37 }
38
39 @Override
40 public String toString() {
41 return "(" + source.toString() + "," + target.toString() + ")";
42 }
43
44 @Override
45 public boolean equals(Object o) {
46 if (o instanceof Tuple) {
47 Tuple<?> t = (Tuple<?>) o;
48
49 if (t.getSource().equals(this.source) && t.getTarget().equals(this.target)) {
50 return true;
51 }
52 }
53 return false;
54 }
55
56 @Override
57 public int hashCode() {
58 return source.hashCode() + target.hashCode();
59 }
60}
diff --git a/subprojects/viatra-runtime-base-itc/src/main/java/tools/refinery/viatra/runtime/base/itc/alg/misc/bfs/BFS.java b/subprojects/viatra-runtime-base-itc/src/main/java/tools/refinery/viatra/runtime/base/itc/alg/misc/bfs/BFS.java
deleted file mode 100644
index 798f31d2..00000000
--- a/subprojects/viatra-runtime-base-itc/src/main/java/tools/refinery/viatra/runtime/base/itc/alg/misc/bfs/BFS.java
+++ /dev/null
@@ -1,151 +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
10package tools.refinery.viatra.runtime.base.itc.alg.misc.bfs;
11
12import java.util.ArrayList;
13import java.util.HashSet;
14import java.util.List;
15import java.util.Set;
16
17import tools.refinery.viatra.runtime.base.itc.igraph.IBiDirectionalGraphDataSource;
18import tools.refinery.viatra.runtime.base.itc.igraph.IGraphDataSource;
19
20public class BFS<V> {
21
22 private BFS() {/*Utility class constructor*/}
23
24 /**
25 * Performs a breadth first search on the given graph to determine whether source is reachable from target.
26 *
27 * @param <V>
28 * the type parameter of the nodes in the graph
29 * @param source
30 * the source node
31 * @param target
32 * the target node
33 * @param graph
34 * the graph data source
35 * @return true if source is reachable from target, false otherwise
36 */
37 public static <V> boolean isReachable(V source, V target, IGraphDataSource<V> graph) {
38 List<V> nodeQueue = new ArrayList<V>();
39 Set<V> visited = new HashSet<V>();
40
41 nodeQueue.add(source);
42 visited.add(source);
43
44 boolean ret = _isReachable(target, graph, nodeQueue, visited);
45 return ret;
46 }
47
48 private static <V> boolean _isReachable(V target, IGraphDataSource<V> graph, List<V> nodeQueue, Set<V> visited) {
49
50 while (!nodeQueue.isEmpty()) {
51 V node = nodeQueue.remove(0);
52 for (V t : graph.getTargetNodes(node).distinctValues()){
53 if (t.equals(target)) {
54 return true;
55 }
56 if (!visited.contains(t)) {
57 visited.add(t);
58 nodeQueue.add(t);
59 }
60 }
61 }
62 return false;
63 }
64
65 public static <V> Set<V> reachableSources(IBiDirectionalGraphDataSource<V> graph, V target) {
66 Set<V> retSet = new HashSet<V>();
67 retSet.add(target);
68 List<V> nodeQueue = new ArrayList<V>();
69 nodeQueue.add(target);
70
71 _reachableSources(graph, nodeQueue, retSet);
72
73 return retSet;
74 }
75
76 private static <V> void _reachableSources(IBiDirectionalGraphDataSource<V> graph, List<V> nodeQueue,
77 Set<V> retSet) {
78 while (!nodeQueue.isEmpty()) {
79 V node = nodeQueue.remove(0);
80 for (V _node : graph.getSourceNodes(node).distinctValues()) {
81 if (!retSet.contains(_node)) {
82 retSet.add(_node);
83 nodeQueue.add(_node);
84 }
85 }
86 }
87 }
88
89 public static <V> Set<V> reachableTargets(IGraphDataSource<V> graph, V source) {
90 Set<V> retSet = new HashSet<V>();
91 retSet.add(source);
92 List<V> nodeQueue = new ArrayList<V>();
93 nodeQueue.add(source);
94
95 _reachableTargets(graph, nodeQueue, retSet);
96
97 return retSet;
98 }
99
100 private static <V> void _reachableTargets(IGraphDataSource<V> graph, List<V> nodeQueue, Set<V> retSet) {
101 while (!nodeQueue.isEmpty()) {
102 V node = nodeQueue.remove(0);
103
104 for (V _node : graph.getTargetNodes(node).distinctValues()) {
105
106 if (!retSet.contains(_node)) {
107 retSet.add(_node);
108 nodeQueue.add(_node);
109 }
110 }
111 }
112 }
113
114 /**
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.
117 *
118 * @param <V>
119 * the type parameter of the nodes in the graph
120 * @param source
121 * the source node
122 * @param target
123 * the target node
124 * @param graph
125 * the graph data source
126 * @return the set of nodes along the path
127 */
128 public static <V> Set<V> collectNodesAlongPath(V source, V target, IGraphDataSource<V> graph) {
129 Set<V> path = new HashSet<V>();
130 _collectNodesAlongPath(source, target, graph, path);
131 return path;
132 }
133
134 private static <V> boolean _collectNodesAlongPath(V node, V target, IGraphDataSource<V> graph, Set<V> path) {
135
136 boolean res = false;
137
138 // end recursion
139 if (node.equals(target)) {
140 path.add(node);
141 return true;
142 } else {
143 for (V _nodeT : graph.getTargetNodes(node).distinctValues()) {
144 res = (_collectNodesAlongPath(_nodeT, target, graph, path)) || res;
145 }
146 if (res)
147 path.add(node);
148 return res;
149 }
150 }
151}
diff --git a/subprojects/viatra-runtime-base-itc/src/main/java/tools/refinery/viatra/runtime/base/itc/alg/misc/dfs/DFSAlg.java b/subprojects/viatra-runtime-base-itc/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-base-itc/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
10package tools.refinery.viatra.runtime.base.itc.alg.misc.dfs;
11
12import java.util.HashMap;
13
14import tools.refinery.viatra.runtime.base.itc.alg.dred.DRedTcRelation;
15import tools.refinery.viatra.runtime.base.itc.igraph.IGraphDataSource;
16import tools.refinery.viatra.runtime.base.itc.igraph.IGraphObserver;
17
18public 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}
diff --git a/subprojects/viatra-runtime-base-itc/src/main/java/tools/refinery/viatra/runtime/base/itc/alg/misc/scc/PKAlg.java b/subprojects/viatra-runtime-base-itc/src/main/java/tools/refinery/viatra/runtime/base/itc/alg/misc/scc/PKAlg.java
deleted file mode 100644
index c99a48ab..00000000
--- a/subprojects/viatra-runtime-base-itc/src/main/java/tools/refinery/viatra/runtime/base/itc/alg/misc/scc/PKAlg.java
+++ /dev/null
@@ -1,179 +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
10package tools.refinery.viatra.runtime.base.itc.alg.misc.scc;
11
12import java.util.ArrayList;
13import java.util.Collections;
14import java.util.HashMap;
15import java.util.List;
16import java.util.Map;
17
18import tools.refinery.viatra.runtime.base.itc.igraph.IBiDirectionalGraphDataSource;
19import tools.refinery.viatra.runtime.base.itc.igraph.IBiDirectionalWrapper;
20import tools.refinery.viatra.runtime.base.itc.igraph.IGraphDataSource;
21import tools.refinery.viatra.runtime.base.itc.igraph.IGraphObserver;
22
23public class PKAlg<V> implements IGraphObserver<V> {
24
25 /**
26 * Maps the nodes to their indicies.
27 */
28 private Map<V, Integer> node2index;
29 private Map<Integer, V> index2node;
30 private Map<V, Boolean> node2mark;
31
32 /**
33 * Maps the index of a node to the index in the topsort.
34 */
35 private Map<Integer, Integer> index2topsort;
36 private Map<Integer, Integer> topsort2index;
37
38 /**
39 * Index associated to the inserted nodes (incrementing with every insertion).
40 */
41 private int index;
42
43 /**
44 * Index within the topsort for the target node when edge insertion occurs.
45 */
46 private int lower_bound;
47
48 /**
49 * Index within the topsort for the source node when edge insertion occurs.
50 */
51 private int upper_bound;
52
53 private List<V> RF;
54 private List<V> RB;
55 private IBiDirectionalGraphDataSource<V> gds;
56
57 public PKAlg(IGraphDataSource<V> gds) {
58 if (gds instanceof IBiDirectionalGraphDataSource<?>) {
59 this.gds = (IBiDirectionalGraphDataSource<V>) gds;
60 } else {
61 this.gds = new IBiDirectionalWrapper<V>(gds);
62 }
63
64 node2mark = new HashMap<V, Boolean>();
65 node2index = new HashMap<V, Integer>();
66 index2node = new HashMap<Integer, V>();
67 index2topsort = new HashMap<Integer, Integer>();
68 topsort2index = new HashMap<Integer, Integer>();
69 index = 0;
70
71 gds.attachObserver(this);
72 }
73
74 @Override
75 public void edgeInserted(V source, V target) {
76
77 RF = new ArrayList<V>();
78 RB = new ArrayList<V>();
79
80 lower_bound = index2topsort.get(node2index.get(target));
81 upper_bound = index2topsort.get(node2index.get(source));
82
83 if (lower_bound < upper_bound) {
84 dfsForward(target);
85 dfsBackward(source);
86 reorder();
87 }
88 }
89
90 private List<Integer> getIndicies(List<V> list) {
91 List<Integer> indicies = new ArrayList<Integer>();
92
93 for (V n : list)
94 indicies.add(index2topsort.get(node2index.get(n)));
95
96 return indicies;
97 }
98
99 private void reorder() {
100
101 Collections.reverse(RB);
102
103 // azon csomopontok indexei amelyek sorrendje nem jo
104 List<Integer> L = getIndicies(RF);
105 L.addAll(getIndicies(RB));
106 Collections.sort(L);
107
108 for (int i = 0; i < RB.size(); i++) {
109 index2topsort.put(node2index.get(RB.get(i)), L.get(i));
110 topsort2index.put(L.get(i), node2index.get(RB.get(i)));
111 }
112
113 for (int i = 0; i < RF.size(); i++) {
114 index2topsort.put(node2index.get(RF.get(i)), L.get(i + RB.size()));
115 topsort2index.put(L.get(i + RB.size()), node2index.get(RF.get(i)));
116 }
117 }
118
119 @SuppressWarnings("unused")
120 private List<V> getTopSort() {
121 List<V> topsort = new ArrayList<V>();
122
123 for (int i : topsort2index.values()) {
124 topsort.add(index2node.get(i));
125 }
126
127 return topsort;
128 }
129
130 private void dfsBackward(V node) {
131 node2mark.put(node, true);
132 RB.add(node);
133
134 for (V sn : gds.getSourceNodes(node).distinctValues()) {
135 int top_id = index2topsort.get(node2index.get(sn));
136
137 if (!node2mark.get(sn) && lower_bound < top_id)
138 dfsBackward(sn);
139 }
140 }
141
142 private void dfsForward(V node) {
143 node2mark.put(node, true);
144 RF.add(node);
145
146 for (V tn : gds.getTargetNodes(node).distinctValues()) {
147 int top_id = index2topsort.get(node2index.get(tn));
148
149 if (top_id == upper_bound)
150 System.out.println("!!!Cycle detected!!!");
151 else if (!node2mark.get(tn) && top_id < upper_bound)
152 dfsForward(tn);
153 }
154 }
155
156 @Override
157 public void edgeDeleted(V source, V target) {
158 // Edge deletion does not affect topsort
159 }
160
161 @Override
162 public void nodeInserted(V n) {
163 node2mark.put(n, false);
164 node2index.put(n, index);
165 index2node.put(index, n);
166 index2topsort.put(index, index);
167 topsort2index.put(index, index);
168 index++;
169 }
170
171 @Override
172 public void nodeDeleted(V n) {
173 node2mark.remove(n);
174 int node_id = node2index.remove(n);
175 index2node.remove(node_id);
176 int top_id = index2topsort.remove(node_id);
177 topsort2index.remove(top_id);
178 }
179}
diff --git a/subprojects/viatra-runtime-base-itc/src/main/java/tools/refinery/viatra/runtime/base/itc/alg/misc/scc/SCC.java b/subprojects/viatra-runtime-base-itc/src/main/java/tools/refinery/viatra/runtime/base/itc/alg/misc/scc/SCC.java
deleted file mode 100644
index 8915998b..00000000
--- a/subprojects/viatra-runtime-base-itc/src/main/java/tools/refinery/viatra/runtime/base/itc/alg/misc/scc/SCC.java
+++ /dev/null
@@ -1,146 +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
10package tools.refinery.viatra.runtime.base.itc.alg.misc.scc;
11
12import java.util.HashSet;
13import java.util.Map;
14import java.util.Set;
15import java.util.Stack;
16
17import tools.refinery.viatra.runtime.base.itc.igraph.IGraphDataSource;
18import tools.refinery.viatra.runtime.matchers.util.CollectionsFactory;
19
20/**
21 * Efficient algorithms to compute the Strongly Connected Components in a directed graph.
22 *
23 * @author Tamas Szabo
24 *
25 * @param <V>
26 * the type parameter of the nodes in the graph
27 */
28public class SCC<V> {
29
30 private SCC() {/*Utility class constructor*/}
31
32 public static long sccId = 0;
33
34 /**
35 * Computes the SCCs for the given graph and returns them as a multiset. (Iterative version of Tarjan's algorithm)
36 *
37 * @param g
38 * the directed graph data source
39 * @return the set of SCCs
40 */
41 public static <V> SCCResult<V> computeSCC(IGraphDataSource<V> g) {
42 int index = 0;
43 Set<Set<V>> ret = new HashSet<Set<V>>();
44
45 // stores the lowlink and index information for the given node
46 Map<V, SCCProperty> nodeMap = CollectionsFactory.createMap();
47
48 // stores all target nodes of a given node - the list will be modified
49 Map<V, Set<V>> targetNodeMap = CollectionsFactory.createMap();
50
51 // stores those target nodes for a given node which have not been visited
52 Map<V, Set<V>> notVisitedMap = CollectionsFactory.createMap();
53
54 // stores the nodes during the traversal
55 Stack<V> nodeStack = new Stack<V>();
56
57 // stores the nodes which belong to an scc (there can be many sccs in the stack at the same time)
58 Stack<V> sccStack = new Stack<V>();
59
60 boolean sink = false, finishedTraversal = true;
61
62 // initialize all nodes with 0 index and 0 lowlink
63 Set<V> allNodes = g.getAllNodes();
64 for (V n : allNodes) {
65 nodeMap.put(n, new SCCProperty(0, 0));
66 }
67
68 for (V n : allNodes) {
69 // if the node has not been visited yet
70 if (nodeMap.get(n).getIndex() == 0) {
71 nodeStack.push(n);
72
73 while (!nodeStack.isEmpty()) {
74 V currentNode = nodeStack.peek();
75 sink = false;
76 finishedTraversal = false;
77 SCCProperty prop = nodeMap.get(currentNode);
78
79 if (nodeMap.get(currentNode).getIndex() == 0) {
80 index++;
81 sccStack.push(currentNode);
82 prop.setIndex(index);
83 prop.setLowlink(index);
84
85 notVisitedMap.put(currentNode, new HashSet<V>());
86
87 // storing the target nodes of the actual node
88 if (g.getTargetNodes(currentNode) != null) {
89 Set<V> targets = g.getTargetNodes(currentNode).distinctValues();
90 targetNodeMap.put(currentNode, CollectionsFactory.createSet(targets));
91 }
92 }
93
94 if (targetNodeMap.get(currentNode) != null) {
95
96 // remove node from stack, the exploration of its children has finished
97 if (targetNodeMap.get(currentNode).size() == 0) {
98 targetNodeMap.remove(currentNode);
99
100 nodeStack.pop();
101
102 for (V targetNode : g.getTargetNodes(currentNode).distinctValues()) {
103 if (notVisitedMap.get(currentNode).contains(targetNode)) {
104 prop.setLowlink(Math.min(prop.getLowlink(), nodeMap.get(targetNode).getLowlink()));
105 } else if (sccStack.contains(targetNode)) {
106 prop.setLowlink(Math.min(prop.getLowlink(), nodeMap.get(targetNode).getIndex()));
107 }
108 }
109
110 finishedTraversal = true;
111 } else {
112 V targetNode = targetNodeMap.get(currentNode).iterator().next();
113 targetNodeMap.get(currentNode).remove(targetNode);
114 // if the targetNode has not yet been visited push it to the stack
115 // and mark it in the notVisitedMap
116 if (nodeMap.get(targetNode).getIndex() == 0) {
117 notVisitedMap.get(currentNode).add(targetNode);
118 nodeStack.add(targetNode);
119 }
120 }
121 }
122 // if currentNode has no target nodes
123 else {
124 nodeStack.pop();
125 sink = true;
126 }
127
128 // create scc if node is a sink or an scc has been found
129 if ((sink || finishedTraversal) && (prop.getLowlink() == prop.getIndex())) {
130 Set<V> sc = new HashSet<V>();
131 V targetNode = null;
132
133 do {
134 targetNode = sccStack.pop();
135 sc.add(targetNode);
136 } while (!targetNode.equals(currentNode));
137
138 ret.add(sc);
139 }
140 }
141 }
142 }
143
144 return new SCCResult<V>(ret, g);
145 }
146}
diff --git a/subprojects/viatra-runtime-base-itc/src/main/java/tools/refinery/viatra/runtime/base/itc/alg/misc/scc/SCCProperty.java b/subprojects/viatra-runtime-base-itc/src/main/java/tools/refinery/viatra/runtime/base/itc/alg/misc/scc/SCCProperty.java
deleted file mode 100644
index b26e3d37..00000000
--- a/subprojects/viatra-runtime-base-itc/src/main/java/tools/refinery/viatra/runtime/base/itc/alg/misc/scc/SCCProperty.java
+++ /dev/null
@@ -1,37 +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
10package tools.refinery.viatra.runtime.base.itc.alg.misc.scc;
11
12public class SCCProperty {
13 private int index;
14 private int lowlink;
15
16 public SCCProperty(int index, int lowlink) {
17 super();
18 this.index = index;
19 this.lowlink = lowlink;
20 }
21
22 public int getIndex() {
23 return index;
24 }
25
26 public void setIndex(int index) {
27 this.index = index;
28 }
29
30 public int getLowlink() {
31 return lowlink;
32 }
33
34 public void setLowlink(int lowlink) {
35 this.lowlink = lowlink;
36 }
37}
diff --git a/subprojects/viatra-runtime-base-itc/src/main/java/tools/refinery/viatra/runtime/base/itc/alg/misc/scc/SCCResult.java b/subprojects/viatra-runtime-base-itc/src/main/java/tools/refinery/viatra/runtime/base/itc/alg/misc/scc/SCCResult.java
deleted file mode 100644
index fde59d3b..00000000
--- a/subprojects/viatra-runtime-base-itc/src/main/java/tools/refinery/viatra/runtime/base/itc/alg/misc/scc/SCCResult.java
+++ /dev/null
@@ -1,81 +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
10package tools.refinery.viatra.runtime.base.itc.alg.misc.scc;
11
12import java.util.Map.Entry;
13import java.util.Set;
14
15import tools.refinery.viatra.runtime.base.itc.igraph.IGraphDataSource;
16
17public class SCCResult<V> {
18
19 private Set<Set<V>> sccs;
20 private IGraphDataSource<V> gds;
21
22 public SCCResult(Set<Set<V>> sccs, IGraphDataSource<V> gds) {
23 this.sccs = sccs;
24 this.gds = gds;
25 }
26
27 public Set<Set<V>> getSccs() {
28 return sccs;
29 }
30
31 public int getSCCCount() {
32 return sccs.size();
33 }
34
35 public double getAverageNodeCount() {
36 double a = 0;
37
38 for (Set<V> s : sccs) {
39 a += s.size();
40 }
41
42 return a / sccs.size();
43 }
44
45 public double getAverageEdgeCount() {
46 long edgeSum = 0;
47
48 for (Set<V> scc : sccs) {
49 for (V source : scc) {
50 for (Entry<V, Integer> entry : gds.getTargetNodes(source).entriesWithMultiplicities()) {
51 if (scc.contains(entry.getKey())) {
52 edgeSum += entry.getValue();
53 }
54 }
55 }
56 }
57
58 return (double) edgeSum / (double) sccs.size();
59 }
60
61 public int getBiggestSCCSize() {
62 int max = 0;
63
64 for (Set<V> scc : sccs) {
65 if (scc.size() > max)
66 max = scc.size();
67 }
68
69 return max;
70 }
71
72 public long getSumOfSquares() {
73 long sum = 0;
74
75 for (Set<V> scc : sccs) {
76 sum += scc.size() * scc.size();
77 }
78
79 return sum;
80 }
81}
diff --git a/subprojects/viatra-runtime-base-itc/src/main/java/tools/refinery/viatra/runtime/base/itc/alg/misc/topsort/TopologicalSorting.java b/subprojects/viatra-runtime-base-itc/src/main/java/tools/refinery/viatra/runtime/base/itc/alg/misc/topsort/TopologicalSorting.java
deleted file mode 100644
index dd18e6c8..00000000
--- a/subprojects/viatra-runtime-base-itc/src/main/java/tools/refinery/viatra/runtime/base/itc/alg/misc/topsort/TopologicalSorting.java
+++ /dev/null
@@ -1,77 +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
10package tools.refinery.viatra.runtime.base.itc.alg.misc.topsort;
11
12import java.util.HashSet;
13import java.util.LinkedList;
14import java.util.List;
15import java.util.Set;
16import java.util.Stack;
17
18import tools.refinery.viatra.runtime.base.itc.igraph.IGraphDataSource;
19
20/**
21 * @since 1.6
22 */
23public class TopologicalSorting {
24
25 private TopologicalSorting() {/*Utility class constructor*/}
26
27 private static final class Pair<T> {
28 public T element;
29 public boolean isParent;
30
31 public Pair(final T element, final boolean isParent) {
32 this.element = element;
33 this.isParent = isParent;
34 }
35 }
36
37 /**
38 * 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.
40 *
41 * @param gds the graph data source
42 * @return a topological ordering
43 */
44 public static <T> List<T> compute(final IGraphDataSource<T> gds) {
45 final Set<T> visited = new HashSet<T>();
46 final LinkedList<T> result = new LinkedList<T>();
47 final Stack<Pair<T>> dfsStack = new Stack<Pair<T>>();
48
49 for (final T node : gds.getAllNodes()) {
50 if (!visited.contains(node)) {
51 dfsStack.push(new Pair<T>(node, false));
52 }
53
54 while (!dfsStack.isEmpty()) {
55 final Pair<T> head = dfsStack.pop();
56 final T source = head.element;
57
58 if (head.isParent) {
59 // we have already seen source, push it to the resulting stack
60 result.addFirst(source);
61 } else {
62 // first time we see source, continue with its children
63 visited.add(source);
64 dfsStack.push(new Pair<T>(source, true));
65
66 for (final T target : gds.getTargetNodes(source).distinctValues()) {
67 if (!visited.contains(target)) {
68 dfsStack.push(new Pair<T>(target, false));
69 }
70 }
71 }
72 }
73 }
74
75 return result;
76 }
77}
diff --git a/subprojects/viatra-runtime-base-itc/src/main/java/tools/refinery/viatra/runtime/base/itc/alg/representative/RepresentativeElectionAlgorithm.java b/subprojects/viatra-runtime-base-itc/src/main/java/tools/refinery/viatra/runtime/base/itc/alg/representative/RepresentativeElectionAlgorithm.java
deleted file mode 100644
index 51015404..00000000
--- a/subprojects/viatra-runtime-base-itc/src/main/java/tools/refinery/viatra/runtime/base/itc/alg/representative/RepresentativeElectionAlgorithm.java
+++ /dev/null
@@ -1,140 +0,0 @@
1/*
2 * SPDX-FileCopyrightText: 2023 The Refinery Authors <https://refinery.tools/>
3 *
4 * SPDX-License-Identifier: EPL-2.0
5 */
6package tools.refinery.viatra.runtime.base.itc.alg.representative;
7
8import tools.refinery.viatra.runtime.base.itc.graphimpl.Graph;
9import tools.refinery.viatra.runtime.base.itc.igraph.IGraphObserver;
10import tools.refinery.viatra.runtime.matchers.util.Direction;
11
12import java.util.HashMap;
13import java.util.HashSet;
14import java.util.Map;
15import java.util.Set;
16
17public abstract class RepresentativeElectionAlgorithm implements IGraphObserver<Object> {
18 protected final Graph<Object> graph;
19 protected final Map<Object, Object> representatives = new HashMap<>();
20 protected final Map<Object, Set<Object>> components = new HashMap<>();
21 private RepresentativeObserver observer;
22
23 protected RepresentativeElectionAlgorithm(Graph<Object> graph) {
24 this.graph = graph;
25 initializeComponents();
26 graph.attachObserver(this);
27 }
28
29 protected abstract void initializeComponents();
30
31 protected void initializeSet(Set<Object> set) {
32 var iterator = set.iterator();
33 if (!iterator.hasNext()) {
34 // Set is empty.
35 return;
36 }
37 var representative = iterator.next();
38 for (var node : set) {
39 var oldRepresentative = representatives.put(node, representative);
40 if (oldRepresentative != null && !representative.equals(oldRepresentative)) {
41 throw new IllegalStateException("Node %s is already in a set represented by %s, cannot add it to %s"
42 .formatted(node, oldRepresentative, set));
43 }
44 }
45 components.put(representative, set);
46 }
47
48 protected void merge(Object leftRepresentative, Object rightRepresentative) {
49 if (leftRepresentative.equals(rightRepresentative)) {
50 return;
51 }
52 var leftSet = getComponent(leftRepresentative);
53 var rightSet = getComponent(rightRepresentative);
54 if (leftSet.size() < rightSet.size()) {
55 merge(rightRepresentative, rightSet, leftRepresentative, leftSet);
56 } else {
57 merge(leftRepresentative, leftSet, rightRepresentative, rightSet);
58 }
59 }
60
61 private void merge(Object preservedRepresentative, Set<Object> preservedSet, Object removedRepresentative,
62 Set<Object> removedSet) {
63 components.remove(removedRepresentative);
64 for (var node : removedSet) {
65 representatives.put(node, preservedRepresentative);
66 preservedSet.add(node);
67 notifyToObservers(node, removedRepresentative, preservedRepresentative);
68 }
69 }
70
71 protected void assignNewRepresentative(Object oldRepresentative, Set<Object> set) {
72 var iterator = set.iterator();
73 if (!iterator.hasNext()) {
74 return;
75 }
76 var newRepresentative = iterator.next();
77 components.put(newRepresentative, set);
78 for (var node : set) {
79 var oldRepresentativeOfNode = representatives.put(node, newRepresentative);
80 if (!oldRepresentative.equals(oldRepresentativeOfNode)) {
81 throw new IllegalArgumentException("Node %s was not represented by %s but by %s"
82 .formatted(node, oldRepresentative, oldRepresentativeOfNode));
83 }
84 notifyToObservers(node, oldRepresentative, newRepresentative);
85 }
86 }
87
88 public void setObserver(RepresentativeObserver observer) {
89 this.observer = observer;
90 }
91
92 public Map<Object, Set<Object>> getComponents() {
93 return components;
94 }
95
96 public Object getRepresentative(Object node) {
97 return representatives.get(node);
98 }
99
100 public Set<Object> getComponent(Object representative) {
101 return components.get(representative);
102 }
103
104 public void dispose() {
105 graph.detachObserver(this);
106 }
107
108 @Override
109 public void nodeInserted(Object n) {
110 var component = new HashSet<>(1);
111 component.add(n);
112 initializeSet(component);
113 notifyToObservers(n, n, Direction.INSERT);
114 }
115
116 @Override
117 public void nodeDeleted(Object n) {
118 var representative = representatives.remove(n);
119 if (!representative.equals(n)) {
120 throw new IllegalStateException("Trying to delete node with dangling edges");
121 }
122 components.remove(representative);
123 notifyToObservers(n, representative, Direction.DELETE);
124 }
125
126 protected void notifyToObservers(Object node, Object oldRepresentative, Object newRepresentative) {
127 notifyToObservers(node, oldRepresentative, Direction.DELETE);
128 notifyToObservers(node, newRepresentative, Direction.INSERT);
129 }
130
131 protected void notifyToObservers(Object node, Object representative, Direction direction) {
132 if (observer != null) {
133 observer.tupleChanged(node, representative, direction);
134 }
135 }
136
137 public interface Factory {
138 RepresentativeElectionAlgorithm create(Graph<Object> graph);
139 }
140}
diff --git a/subprojects/viatra-runtime-base-itc/src/main/java/tools/refinery/viatra/runtime/base/itc/alg/representative/RepresentativeObserver.java b/subprojects/viatra-runtime-base-itc/src/main/java/tools/refinery/viatra/runtime/base/itc/alg/representative/RepresentativeObserver.java
deleted file mode 100644
index 93cce1ea..00000000
--- a/subprojects/viatra-runtime-base-itc/src/main/java/tools/refinery/viatra/runtime/base/itc/alg/representative/RepresentativeObserver.java
+++ /dev/null
@@ -1,12 +0,0 @@
1/*
2 * SPDX-FileCopyrightText: 2023 The Refinery Authors <https://refinery.tools/>
3 *
4 * SPDX-License-Identifier: EPL-2.0
5 */
6package tools.refinery.viatra.runtime.base.itc.alg.representative;
7
8import tools.refinery.viatra.runtime.matchers.util.Direction;
9
10public interface RepresentativeObserver {
11 void tupleChanged(Object node, Object representative, Direction direction);
12}
diff --git a/subprojects/viatra-runtime-base-itc/src/main/java/tools/refinery/viatra/runtime/base/itc/alg/representative/StronglyConnectedComponentAlgorithm.java b/subprojects/viatra-runtime-base-itc/src/main/java/tools/refinery/viatra/runtime/base/itc/alg/representative/StronglyConnectedComponentAlgorithm.java
deleted file mode 100644
index ba42bb13..00000000
--- a/subprojects/viatra-runtime-base-itc/src/main/java/tools/refinery/viatra/runtime/base/itc/alg/representative/StronglyConnectedComponentAlgorithm.java
+++ /dev/null
@@ -1,66 +0,0 @@
1/*
2 * SPDX-FileCopyrightText: 2023 The Refinery Authors <https://refinery.tools/>
3 *
4 * SPDX-License-Identifier: EPL-2.0
5 */
6package tools.refinery.viatra.runtime.base.itc.alg.representative;
7
8import tools.refinery.viatra.runtime.base.itc.alg.misc.GraphHelper;
9import tools.refinery.viatra.runtime.base.itc.alg.misc.bfs.BFS;
10import tools.refinery.viatra.runtime.base.itc.alg.misc.scc.SCC;
11import tools.refinery.viatra.runtime.base.itc.graphimpl.Graph;
12
13import java.util.Collection;
14import java.util.Set;
15
16public class StronglyConnectedComponentAlgorithm extends RepresentativeElectionAlgorithm {
17 public StronglyConnectedComponentAlgorithm(Graph<Object> graph) {
18 super(graph);
19 }
20
21 @Override
22 protected void initializeComponents() {
23 var computedSCCs = SCC.computeSCC(graph).getSccs();
24 for (var computedSCC : computedSCCs) {
25 initializeSet(computedSCC);
26 }
27 }
28
29 @Override
30 public void edgeInserted(Object source, Object target) {
31 var sourceRoot = getRepresentative(source);
32 var targetRoot = getRepresentative(target);
33 if (sourceRoot.equals(targetRoot)) {
34 // New edge does not change strongly connected components.
35 return;
36 }
37 if (BFS.isReachable(target, source, graph)) {
38 merge(sourceRoot, targetRoot);
39 }
40 }
41
42 @Override
43 public void edgeDeleted(Object source, Object target) {
44 var sourceRoot = getRepresentative(source);
45 var targetRoot = getRepresentative(target);
46 if (!sourceRoot.equals(targetRoot)) {
47 // New edge does not change strongly connected components.
48 return;
49 }
50 var component = GraphHelper.getSubGraph(getComponent(sourceRoot), graph);
51 if (!BFS.isReachable(source, target, component)) {
52 var newSCCs = SCC.computeSCC(component).getSccs();
53 split(sourceRoot, newSCCs);
54 }
55 }
56
57 private void split(Object preservedRepresentative, Collection<? extends Set<Object>> sets) {
58 for (var set : sets) {
59 if (set.contains(preservedRepresentative)) {
60 components.put(preservedRepresentative, set);
61 } else {
62 assignNewRepresentative(preservedRepresentative, set);
63 }
64 }
65 }
66}
diff --git a/subprojects/viatra-runtime-base-itc/src/main/java/tools/refinery/viatra/runtime/base/itc/alg/representative/WeaklyConnectedComponentAlgorithm.java b/subprojects/viatra-runtime-base-itc/src/main/java/tools/refinery/viatra/runtime/base/itc/alg/representative/WeaklyConnectedComponentAlgorithm.java
deleted file mode 100644
index 22159499..00000000
--- a/subprojects/viatra-runtime-base-itc/src/main/java/tools/refinery/viatra/runtime/base/itc/alg/representative/WeaklyConnectedComponentAlgorithm.java
+++ /dev/null
@@ -1,85 +0,0 @@
1/*
2 * SPDX-FileCopyrightText: 2023 The Refinery Authors <https://refinery.tools/>
3 *
4 * SPDX-License-Identifier: EPL-2.0
5 */
6package tools.refinery.viatra.runtime.base.itc.alg.representative;
7
8import tools.refinery.viatra.runtime.base.itc.graphimpl.Graph;
9
10import java.util.ArrayDeque;
11import java.util.HashSet;
12import java.util.Set;
13
14public class WeaklyConnectedComponentAlgorithm extends RepresentativeElectionAlgorithm {
15 public WeaklyConnectedComponentAlgorithm(Graph<Object> graph) {
16 super(graph);
17 }
18
19 @Override
20 protected void initializeComponents() {
21 for (var node : graph.getAllNodes()) {
22 if (representatives.containsKey(node)) {
23 continue;
24 }
25 var reachable = getReachableNodes(node);
26 initializeSet(reachable);
27 }
28 }
29
30 @Override
31 public void edgeInserted(Object source, Object target) {
32 var sourceRoot = getRepresentative(source);
33 var targetRoot = getRepresentative(target);
34 merge(sourceRoot, targetRoot);
35 }
36
37 @Override
38 public void edgeDeleted(Object source, Object target) {
39 var sourceRoot = getRepresentative(source);
40 var targetRoot = getRepresentative(target);
41 if (!sourceRoot.equals(targetRoot)) {
42 throw new IllegalArgumentException("Trying to remove edge not in graph");
43 }
44 var targetReachable = getReachableNodes(target);
45 if (!targetReachable.contains(source)) {
46 split(sourceRoot, targetReachable);
47 }
48 }
49
50 private void split(Object sourceRepresentative, Set<Object> targetReachable) {
51 var sourceComponent = getComponent(sourceRepresentative);
52 sourceComponent.removeAll(targetReachable);
53 if (targetReachable.contains(sourceRepresentative)) {
54 components.put(sourceRepresentative, targetReachable);
55 assignNewRepresentative(sourceRepresentative, sourceComponent);
56 } else {
57 assignNewRepresentative(sourceRepresentative, targetReachable);
58 }
59 }
60
61 private Set<Object> getReachableNodes(Object source) {
62 var retSet = new HashSet<>();
63 retSet.add(source);
64 var nodeQueue = new ArrayDeque<>();
65 nodeQueue.addLast(source);
66
67 while (!nodeQueue.isEmpty()) {
68 var node = nodeQueue.removeFirst();
69 for (var neighbor : graph.getTargetNodes(node).distinctValues()) {
70 if (!retSet.contains(neighbor)) {
71 retSet.add(neighbor);
72 nodeQueue.addLast(neighbor);
73 }
74 }
75 for (var neighbor : graph.getSourceNodes(node).distinctValues()) {
76 if (!retSet.contains(neighbor)) {
77 retSet.add(neighbor);
78 nodeQueue.addLast(neighbor);
79 }
80 }
81 }
82
83 return retSet;
84 }
85}
diff --git a/subprojects/viatra-runtime-base-itc/src/main/java/tools/refinery/viatra/runtime/base/itc/alg/util/CollectionHelper.java b/subprojects/viatra-runtime-base-itc/src/main/java/tools/refinery/viatra/runtime/base/itc/alg/util/CollectionHelper.java
deleted file mode 100644
index c9b3cafa..00000000
--- a/subprojects/viatra-runtime-base-itc/src/main/java/tools/refinery/viatra/runtime/base/itc/alg/util/CollectionHelper.java
+++ /dev/null
@@ -1,64 +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 *******************************************************************************/
9package tools.refinery.viatra.runtime.base.itc.alg.util;
10
11import java.util.Set;
12
13import tools.refinery.viatra.runtime.matchers.util.CollectionsFactory;
14
15/**
16 * @author Tamas Szabo
17 *
18 */
19public class CollectionHelper {
20
21 private CollectionHelper() {/*Utility class constructor*/}
22
23 /**
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.
26 *
27 * @param set1
28 * the first set (can be null, interpreted as empty)
29 * @param set2
30 * the second set (can be null, interpreted as empty)
31 * @return the intersection of the sets
32 * @since 1.7
33 */
34 public static <V> Set<V> intersection(Set<V> set1, Set<V> set2) {
35 if (set1 == null || set2 == null)
36 return CollectionsFactory.createSet();
37
38 Set<V> intersection = CollectionsFactory.createSet(set1);
39 intersection.retainAll(set2);
40 return intersection;
41 }
42
43
44 /**
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.
47 *
48 * @param set1
49 * the first set (can be null, interpreted as empty)
50 * @param set2
51 * the second set (can be null, interpreted as empty)
52 * @return the difference of the sets
53 * @since 1.7
54 */
55 public static <V> Set<V> difference(Set<V> set1, Set<V> set2) {
56 if (set1 == null)
57 return CollectionsFactory.createSet();
58
59 Set<V> difference = CollectionsFactory.createSet(set1);
60 if (set2 != null) difference.removeAll(set2);
61 return difference;
62 }
63
64}
diff --git a/subprojects/viatra-runtime-base-itc/src/main/java/tools/refinery/viatra/runtime/base/itc/graphimpl/DotGenerator.java b/subprojects/viatra-runtime-base-itc/src/main/java/tools/refinery/viatra/runtime/base/itc/graphimpl/DotGenerator.java
deleted file mode 100644
index 0e21f323..00000000
--- a/subprojects/viatra-runtime-base-itc/src/main/java/tools/refinery/viatra/runtime/base/itc/graphimpl/DotGenerator.java
+++ /dev/null
@@ -1,160 +0,0 @@
1/*******************************************************************************
2 * Copyright (c) 2010-2019, 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 *******************************************************************************/
9package tools.refinery.viatra.runtime.base.itc.graphimpl;
10
11import tools.refinery.viatra.runtime.base.itc.alg.misc.scc.SCC;
12import tools.refinery.viatra.runtime.base.itc.alg.misc.scc.SCCResult;
13import tools.refinery.viatra.runtime.matchers.util.IMemoryView;
14
15import java.util.HashMap;
16import java.util.Map;
17import java.util.Set;
18import java.util.function.Function;
19
20/**
21 * This class contains utility methods to generate dot representations for {@link Graph} instances.
22 *
23 * @author Tamas Szabo
24 * @since 2.3
25 */
26public class DotGenerator {
27
28 private static final String[] colors = new String[] { "yellow", "blue", "red", "green", "gray", "cyan" };
29
30 private DotGenerator() {
31
32 }
33
34 /**
35 * Generates the dot representation for the given graph.
36 *
37 * @param graph
38 * the graph
39 * @param colorSCCs
40 * specifies if the strongly connected components with size greater than shall be colored
41 * @param nameFunction
42 * use this function to provide custom names to nodes, null if the default toString shall be used
43 * @param colorFunction
44 * use this function to provide custom color to nodes, null if the default white color shall be used
45 * @param edgeFunction
46 * use this function to provide custom edge labels, null if no edge label shall be printed
47 * @return the dot representation as a string
48 */
49 public static <V> String generateDot(final Graph<V> graph, final boolean colorSCCs,
50 final Function<V, String> nameFunction, final Function<V, String> colorFunction,
51 final Function<V, Function<V, String>> edgeFunction) {
52 final Map<V, String> colorMap = new HashMap<V, String>();
53
54 if (colorSCCs) {
55 final SCCResult<V> result = SCC.computeSCC(graph);
56 final Set<Set<V>> sccs = result.getSccs();
57
58 int i = 0;
59 for (final Set<V> scc : sccs) {
60 if (scc.size() > 1) {
61 for (final V node : scc) {
62 final String color = colorMap.get(node);
63 if (color == null) {
64 colorMap.put(node, colors[i % colors.length]);
65 } else {
66 colorMap.put(node, colorMap.get(node) + ":" + colors[i % colors.length]);
67 }
68 }
69 i++;
70 }
71 }
72
73 // if a node has no color yet, then make it white
74 for (final V node : graph.getAllNodes()) {
75 if (!colorMap.containsKey(node)) {
76 colorMap.put(node, "white");
77 }
78 }
79 } else {
80 for (final V node : graph.getAllNodes()) {
81 colorMap.put(node, "white");
82 }
83 }
84
85 if (colorFunction != null) {
86 for (final V node : graph.getAllNodes()) {
87 colorMap.put(node, colorFunction.apply(node));
88 }
89 }
90
91 final StringBuilder builder = new StringBuilder();
92 builder.append("digraph g {\n");
93
94 for (final V node : graph.getAllNodes()) {
95 final String nodePresentation = nameFunction == null ? node.toString() : nameFunction.apply(node);
96 builder.append("\"" + nodePresentation + "\"");
97 builder.append("[style=filled,fillcolor=" + colorMap.get(node) + "]");
98 builder.append(";\n");
99 }
100
101 for (final V source : graph.getAllNodes()) {
102 final IMemoryView<V> targets = graph.getTargetNodes(source);
103 if (!targets.isEmpty()) {
104 final String sourcePresentation = nameFunction == null ? source.toString() : nameFunction.apply(source);
105 for (final V target : targets.distinctValues()) {
106 String edgeLabel = null;
107 if (edgeFunction != null) {
108 final Function<V, String> v1 = edgeFunction.apply(source);
109 if (v1 != null) {
110 edgeLabel = v1.apply(target);
111 }
112 }
113
114 final String targetPresentation = nameFunction == null ? target.toString()
115 : nameFunction.apply(target);
116
117 builder.append("\"" + sourcePresentation + "\" -> \"" + targetPresentation + "\"");
118 if (edgeLabel != null) {
119 builder.append("[label=\"" + edgeLabel + "\"]");
120 }
121 builder.append(";\n");
122 }
123 }
124 }
125
126 builder.append("}");
127 return builder.toString();
128 }
129
130 /**
131 * Generates the dot representation for the given graph. No special pretty printing customization will be applied.
132 *
133 * @param graph
134 * the graph
135 * @return the dot representation as a string
136 */
137 public static <V> String generateDot(final Graph<V> graph) {
138 return generateDot(graph, false, null, null, null);
139 }
140
141 /**
142 * Returns a simple name shortener function that can be used in the graphviz visualization to help with readability.
143 * WARNING: if you shorten the name of the {@link Node}s too much, the visualization may become incorrect because
144 * grahpviz will treat different nodes as the same if their shortened names are the same.
145 *
146 * @param maxLength
147 * the maximum length of the text that is kept from the toString of the objects in the graph
148 * @return the shrunk toString value
149 */
150 public static <V> Function<V, String> getNameShortener(final int maxLength) {
151 return new Function<V, String>() {
152 @Override
153 public String apply(final V obj) {
154 final String value = obj.toString();
155 return value.substring(0, Math.min(value.length(), maxLength));
156 }
157 };
158 }
159
160}
diff --git a/subprojects/viatra-runtime-base-itc/src/main/java/tools/refinery/viatra/runtime/base/itc/graphimpl/Graph.java b/subprojects/viatra-runtime-base-itc/src/main/java/tools/refinery/viatra/runtime/base/itc/graphimpl/Graph.java
deleted file mode 100644
index 70cbc77e..00000000
--- a/subprojects/viatra-runtime-base-itc/src/main/java/tools/refinery/viatra/runtime/base/itc/graphimpl/Graph.java
+++ /dev/null
@@ -1,185 +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
10package tools.refinery.viatra.runtime.base.itc.graphimpl;
11
12import tools.refinery.viatra.runtime.base.itc.igraph.IBiDirectionalGraphDataSource;
13import tools.refinery.viatra.runtime.base.itc.igraph.IGraphDataSource;
14import tools.refinery.viatra.runtime.base.itc.igraph.IGraphObserver;
15import tools.refinery.viatra.runtime.matchers.util.CollectionsFactory;
16import tools.refinery.viatra.runtime.matchers.util.CollectionsFactory.MemoryType;
17import tools.refinery.viatra.runtime.matchers.util.IMemoryView;
18import tools.refinery.viatra.runtime.matchers.util.IMultiLookup;
19
20import java.util.List;
21import java.util.Map;
22import java.util.Map.Entry;
23import java.util.Set;
24
25public class Graph<V> implements IGraphDataSource<V>, IBiDirectionalGraphDataSource<V> {
26
27 // source -> target -> count
28 private IMultiLookup<V, V> outgoingEdges;
29 // target -> source -> count
30 private IMultiLookup<V, V> incomingEdges;
31
32 private Set<V> nodes;
33
34 private List<IGraphObserver<V>> observers;
35
36 public Graph() {
37 outgoingEdges = CollectionsFactory.createMultiLookup(Object.class, MemoryType.MULTISETS, Object.class);
38 incomingEdges = CollectionsFactory.createMultiLookup(Object.class, MemoryType.MULTISETS, Object.class);
39 nodes = CollectionsFactory.createSet();
40 observers = CollectionsFactory.createObserverList();
41 }
42
43 public void insertEdge(V source, V target) {
44 outgoingEdges.addPair(source, target);
45 incomingEdges.addPair(target, source);
46
47 for (IGraphObserver<V> go : observers) {
48 go.edgeInserted(source, target);
49 }
50 }
51
52 /**
53 * No-op if trying to delete edge that does not exist
54 *
55 * @since 2.0
56 * @see #deleteEdgeIfExists(Object, Object)
57 */
58 public void deleteEdgeIfExists(V source, V target) {
59 boolean containedEdge = outgoingEdges.lookupOrEmpty(source).containsNonZero(target);
60 if (containedEdge) {
61 deleteEdgeThatExists(source, target);
62 }
63 }
64
65 /**
66 * @throws IllegalStateException
67 * if trying to delete edge that does not exist
68 * @since 2.0
69 * @see #deleteEdgeIfExists(Object, Object)
70 */
71 public void deleteEdgeThatExists(V source, V target) {
72 outgoingEdges.removePair(source, target);
73 incomingEdges.removePair(target, source);
74 for (IGraphObserver<V> go : observers) {
75 go.edgeDeleted(source, target);
76 }
77 }
78
79 /**
80 * @deprecated use explicitly {@link #deleteEdgeThatExists(Object, Object)} or
81 * {@link #deleteEdgeIfExists(Object, Object)} instead. To preserve backwards compatibility, this method
82 * delegates to the latter.
83 *
84 */
85 @Deprecated
86 public void deleteEdge(V source, V target) {
87 deleteEdgeIfExists(source, target);
88 }
89
90 /**
91 * Insert the given node into the graph.
92 */
93 public void insertNode(V node) {
94 if (nodes.add(node)) {
95 for (IGraphObserver<V> go : observers) {
96 go.nodeInserted(node);
97 }
98 }
99 }
100
101 /**
102 * Deletes the given node AND all of the edges going in and out from the node.
103 */
104 public void deleteNode(V node) {
105 if (nodes.remove(node)) {
106 IMemoryView<V> incomingView = incomingEdges.lookup(node);
107 if (incomingView != null) {
108 Map<V, Integer> incoming = CollectionsFactory.createMap(incomingView.asMap());
109
110 for (Entry<V, Integer> entry : incoming.entrySet()) {
111 for (int i = 0; i < entry.getValue(); i++) {
112 deleteEdgeThatExists(entry.getKey(), node);
113 }
114 }
115 }
116
117 IMemoryView<V> outgoingView = outgoingEdges.lookup(node);
118 if (outgoingView != null) {
119 Map<V, Integer> outgoing = CollectionsFactory.createMap(outgoingView.asMap());
120
121 for (Entry<V, Integer> entry : outgoing.entrySet()) {
122 for (int i = 0; i < entry.getValue(); i++) {
123 deleteEdgeThatExists(node, entry.getKey());
124 }
125 }
126 }
127
128 for (IGraphObserver<V> go : observers) {
129 go.nodeDeleted(node);
130 }
131 }
132 }
133
134 @Override
135 public void attachObserver(IGraphObserver<V> go) {
136 observers.add(go);
137 }
138
139 @Override
140 public void attachAsFirstObserver(IGraphObserver<V> observer) {
141 observers.add(0, observer);
142 }
143
144 @Override
145 public void detachObserver(IGraphObserver<V> go) {
146 observers.remove(go);
147 }
148
149 @Override
150 public Set<V> getAllNodes() {
151 return nodes;
152 }
153
154 @Override
155 public IMemoryView<V> getTargetNodes(V source) {
156 return outgoingEdges.lookupOrEmpty(source);
157 }
158
159 @Override
160 public IMemoryView<V> getSourceNodes(V target) {
161 return incomingEdges.lookupOrEmpty(target);
162 }
163
164 @Override
165 public String toString() {
166 StringBuilder sb = new StringBuilder();
167 sb.append("nodes = ");
168 for (V n : getAllNodes()) {
169 sb.append(n.toString());
170 sb.append(" ");
171 }
172 sb.append(" edges = ");
173 for (V source : outgoingEdges.distinctKeys()) {
174 IMemoryView<V> targets = outgoingEdges.lookup(source);
175 for (V target : targets.distinctValues()) {
176 int count = targets.getCount(target);
177 for (int i = 0; i < count; i++) {
178 sb.append("(" + source + "," + target + ") ");
179 }
180 }
181 }
182 return sb.toString();
183 }
184
185}
diff --git a/subprojects/viatra-runtime-base-itc/src/main/java/tools/refinery/viatra/runtime/base/itc/igraph/IBiDirectionalGraphDataSource.java b/subprojects/viatra-runtime-base-itc/src/main/java/tools/refinery/viatra/runtime/base/itc/igraph/IBiDirectionalGraphDataSource.java
deleted file mode 100644
index 64659447..00000000
--- a/subprojects/viatra-runtime-base-itc/src/main/java/tools/refinery/viatra/runtime/base/itc/igraph/IBiDirectionalGraphDataSource.java
+++ /dev/null
@@ -1,37 +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
10package tools.refinery.viatra.runtime.base.itc.igraph;
11
12import tools.refinery.viatra.runtime.matchers.util.IMemoryView;
13import tools.refinery.viatra.runtime.matchers.util.IMultiset;
14
15/**
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.
18 *
19 * @author Tamas Szabo
20 *
21 * @param <V> the type of the nodes in the graph
22 */
23public interface IBiDirectionalGraphDataSource<V> extends IGraphDataSource<V> {
24
25 /**
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.
28 *
29 * The method must not return null.
30 *
31 * @param target the target node
32 * @return the multiset of source nodes
33 * @since 2.0
34 */
35 public IMemoryView<V> getSourceNodes(V target);
36
37}
diff --git a/subprojects/viatra-runtime-base-itc/src/main/java/tools/refinery/viatra/runtime/base/itc/igraph/IBiDirectionalWrapper.java b/subprojects/viatra-runtime-base-itc/src/main/java/tools/refinery/viatra/runtime/base/itc/igraph/IBiDirectionalWrapper.java
deleted file mode 100644
index becab0eb..00000000
--- a/subprojects/viatra-runtime-base-itc/src/main/java/tools/refinery/viatra/runtime/base/itc/igraph/IBiDirectionalWrapper.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
10package tools.refinery.viatra.runtime.base.itc.igraph;
11
12import java.util.Set;
13
14import tools.refinery.viatra.runtime.matchers.util.CollectionsFactory;
15import tools.refinery.viatra.runtime.matchers.util.CollectionsFactory.MemoryType;
16import tools.refinery.viatra.runtime.matchers.util.IMemoryView;
17import tools.refinery.viatra.runtime.matchers.util.IMultiLookup;
18
19/**
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
22 * {@link IGraphDataSource} implementations.
23 *
24 * @author Tamas Szabo
25 *
26 * @param <V>
27 * the type parameter of the nodes in the graph data source
28 */
29public class IBiDirectionalWrapper<V> implements IBiDirectionalGraphDataSource<V>, IGraphObserver<V> {
30
31 private IGraphDataSource<V> wrappedDataSource;
32 // target -> source -> count
33 private IMultiLookup<V, V> incomingEdges;
34
35 public IBiDirectionalWrapper(IGraphDataSource<V> gds) {
36 this.wrappedDataSource = gds;
37
38 this.incomingEdges = CollectionsFactory.createMultiLookup(
39 Object.class, MemoryType.MULTISETS, Object.class);
40
41 if (gds.getAllNodes() != null) {
42 for (V source : gds.getAllNodes()) {
43 IMemoryView<V> targets = gds.getTargetNodes(source);
44 for (V target : targets.distinctValues()) {
45 int count = targets.getCount(target);
46 for (int i = 0; i < count; i++) {
47 edgeInserted(source, target);
48 }
49 }
50 }
51 }
52
53 gds.attachAsFirstObserver(this);
54 }
55
56 @Override
57 public void attachObserver(IGraphObserver<V> observer) {
58 wrappedDataSource.attachObserver(observer);
59 }
60
61 @Override
62 public void attachAsFirstObserver(IGraphObserver<V> observer) {
63 wrappedDataSource.attachAsFirstObserver(observer);
64 }
65
66 @Override
67 public void detachObserver(IGraphObserver<V> observer) {
68 wrappedDataSource.detachObserver(observer);
69 }
70
71 @Override
72 public Set<V> getAllNodes() {
73 return wrappedDataSource.getAllNodes();
74 }
75
76 @Override
77 public IMemoryView<V> getTargetNodes(V source) {
78 return wrappedDataSource.getTargetNodes(source);
79 }
80
81 @Override
82 public IMemoryView<V> getSourceNodes(V target) {
83 return incomingEdges.lookupOrEmpty(target);
84 }
85
86 @Override
87 public void edgeInserted(V source, V target) {
88 incomingEdges.addPair(target, source);
89 }
90
91 @Override
92 public void edgeDeleted(V source, V target) {
93 incomingEdges.removePair(target, source);
94 }
95
96 @Override
97 public void nodeInserted(V n) {
98
99 }
100
101 @Override
102 public void nodeDeleted(V node) {
103
104 }
105
106 @Override
107 public String toString() {
108 return wrappedDataSource.toString();
109 }
110}
diff --git a/subprojects/viatra-runtime-base-itc/src/main/java/tools/refinery/viatra/runtime/base/itc/igraph/IGraphDataSource.java b/subprojects/viatra-runtime-base-itc/src/main/java/tools/refinery/viatra/runtime/base/itc/igraph/IGraphDataSource.java
deleted file mode 100644
index 3fa65936..00000000
--- a/subprojects/viatra-runtime-base-itc/src/main/java/tools/refinery/viatra/runtime/base/itc/igraph/IGraphDataSource.java
+++ /dev/null
@@ -1,70 +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
10package tools.refinery.viatra.runtime.base.itc.igraph;
11
12import tools.refinery.viatra.runtime.matchers.util.IMemoryView;
13import tools.refinery.viatra.runtime.matchers.util.IMultiset;
14
15import java.util.Set;
16
17/**
18 * The interface prescribes the set of operations that a graph data source must support.
19 * <p> Note that the old version of the interface is broken at version 1.6;
20 * MultiSets are now presented as Maps instead of Lists.
21 *
22 * @author Tamas Szabo
23 *
24 * @param <V>
25 * the type of the nodes in the graph
26 */
27public interface IGraphDataSource<V> {
28
29 /**
30 * Attaches a new graph observer to this graph data source. Observers will be notified in the order they have been registered.
31 *
32 * @param observer the graph observer
33 */
34 public void attachObserver(IGraphObserver<V> observer);
35
36 /**
37 * Attaches a new graph observer to this graph data source as the first one.
38 * In the notification order this observer will be the first one as long as another call to this method happens.
39 *
40 * @param observer the graph observer
41 * @since 1.6
42 */
43 public void attachAsFirstObserver(IGraphObserver<V> observer);
44
45 /**
46 * Detaches an already registered graph observer from this graph data source.
47 *
48 * @param observer the graph observer
49 */
50 public void detachObserver(IGraphObserver<V> observer);
51
52 /**
53 * Returns the complete set of nodes in the graph data source.
54 *
55 * @return the set of all nodes
56 */
57 public Set<V> getAllNodes();
58
59 /**
60 * Returns the target nodes for the given source node.
61 * The returned data structure is an {@link IMultiset} because of potential parallel edges in the graph data source.
62 *
63 * The method must not return null.
64 *
65 * @param source the source node
66 * @return the multiset of target nodes
67 * @since 2.0
68 */
69 public IMemoryView<V> getTargetNodes(V source);
70}
diff --git a/subprojects/viatra-runtime-base-itc/src/main/java/tools/refinery/viatra/runtime/base/itc/igraph/IGraphObserver.java b/subprojects/viatra-runtime-base-itc/src/main/java/tools/refinery/viatra/runtime/base/itc/igraph/IGraphObserver.java
deleted file mode 100644
index 5cb2d9fa..00000000
--- a/subprojects/viatra-runtime-base-itc/src/main/java/tools/refinery/viatra/runtime/base/itc/igraph/IGraphObserver.java
+++ /dev/null
@@ -1,55 +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
10package tools.refinery.viatra.runtime.base.itc.igraph;
11
12/**
13 * Interface GraphObserver is used to observ the changes in a graph; edge and node insertion/deleteion.
14 *
15 * @author Tamas Szabo
16 *
17 */
18public interface IGraphObserver<V> {
19
20 /**
21 * Used to notify when an edge is inserted into the graph.
22 *
23 * @param source
24 * the source of the edge
25 * @param target
26 * the target of the edge
27 */
28 public void edgeInserted(V source, V target);
29
30 /**
31 * Used to notify when an edge is deleted from the graph.
32 *
33 * @param source
34 * the source of the edge
35 * @param target
36 * the target of the edge
37 */
38 public void edgeDeleted(V source, V target);
39
40 /**
41 * Used to notify when a node is inserted into the graph.
42 *
43 * @param n
44 * the node
45 */
46 public void nodeInserted(V n);
47
48 /**
49 * Used to notify when a node is deleted from the graph.
50 *
51 * @param n
52 * the node
53 */
54 public void nodeDeleted(V n);
55}
diff --git a/subprojects/viatra-runtime-base-itc/src/main/java/tools/refinery/viatra/runtime/base/itc/igraph/ITcDataSource.java b/subprojects/viatra-runtime-base-itc/src/main/java/tools/refinery/viatra/runtime/base/itc/igraph/ITcDataSource.java
deleted file mode 100644
index 5924b723..00000000
--- a/subprojects/viatra-runtime-base-itc/src/main/java/tools/refinery/viatra/runtime/base/itc/igraph/ITcDataSource.java
+++ /dev/null
@@ -1,82 +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
10package tools.refinery.viatra.runtime.base.itc.igraph;
11
12import java.util.Set;
13
14import tools.refinery.viatra.runtime.base.itc.alg.misc.IGraphPathFinder;
15
16/**
17 * This interface defines those methods that a transitive reachability data source should provide.
18 *
19 * @author Tamas Szabo
20 *
21 * @param <V>
22 * the type parameter of the node
23 */
24public interface ITcDataSource<V> {
25
26 /**
27 * Attach a transitive closure relation observer.
28 *
29 * @param to
30 * the observer object
31 */
32 public void attachObserver(ITcObserver<V> to);
33
34 /**
35 * Detach a transitive closure relation observer.
36 *
37 * @param to
38 * the observer object
39 */
40 public void detachObserver(ITcObserver<V> to);
41
42 /**
43 * Returns all nodes which are reachable from the source node.
44 *
45 * @param source
46 * the source node
47 * @return the set of target nodes
48 */
49 public Set<V> getAllReachableTargets(V source);
50
51 /**
52 * Returns all nodes from which the target node is reachable.
53 *
54 * @param target
55 * the target node
56 * @return the set of source nodes
57 */
58 public Set<V> getAllReachableSources(V target);
59
60 /**
61 * Returns true if the target node is reachable from the source node.
62 *
63 * @param source
64 * the source node
65 * @param target
66 * the target node
67 * @return true if target is reachable from source, false otherwise
68 */
69 public boolean isReachable(V source, V target);
70
71 /**
72 * The returned {@link IGraphPathFinder} can be used to retrieve paths between nodes using transitive reachability.
73 *
74 * @return a path finder for the graph.
75 */
76 public IGraphPathFinder<V> getPathFinder();
77
78 /**
79 * Call this method to properly dispose the data structures of a transitive closure algorithm.
80 */
81 public void dispose();
82}
diff --git a/subprojects/viatra-runtime-base-itc/src/main/java/tools/refinery/viatra/runtime/base/itc/igraph/ITcObserver.java b/subprojects/viatra-runtime-base-itc/src/main/java/tools/refinery/viatra/runtime/base/itc/igraph/ITcObserver.java
deleted file mode 100644
index fded53f1..00000000
--- a/subprojects/viatra-runtime-base-itc/src/main/java/tools/refinery/viatra/runtime/base/itc/igraph/ITcObserver.java
+++ /dev/null
@@ -1,39 +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
10package tools.refinery.viatra.runtime.base.itc.igraph;
11
12/**
13 * Interface ITcObserver is used to observe the changes in a transitive closure relation; tuple insertion/deletion.
14 *
15 * @author Szabo Tamas
16 *
17 */
18public interface ITcObserver<V> {
19
20 /**
21 * Used to notify when a tuple is inserted into the transitive closure relation.
22 *
23 * @param source
24 * the source of the tuple
25 * @param target
26 * the target of the tuple
27 */
28 public void tupleInserted(V source, V target);
29
30 /**
31 * Used to notify when a tuple is deleted from the transitive closure relation.
32 *
33 * @param source
34 * the source of the tuple
35 * @param target
36 * the target of the tuple
37 */
38 public void tupleDeleted(V source, V target);
39}
generated by cgit v1.2.3-54-g00ecf (git 2.45.2) at 2024-07-21 05:57:57 +0000