diff options
Diffstat (limited to 'subprojects/viatra-runtime-base-itc/src/main')
33 files changed, 0 insertions, 4191 deletions
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 | |||
10 | package tools.refinery.viatra.runtime.base.itc.alg.counting; | ||
11 | |||
12 | import java.util.List; | ||
13 | import java.util.Set; | ||
14 | |||
15 | import tools.refinery.viatra.runtime.base.itc.alg.misc.DFSPathFinder; | ||
16 | import tools.refinery.viatra.runtime.base.itc.alg.misc.IGraphPathFinder; | ||
17 | import tools.refinery.viatra.runtime.base.itc.alg.misc.ITcRelation; | ||
18 | import tools.refinery.viatra.runtime.base.itc.igraph.IBiDirectionalGraphDataSource; | ||
19 | import tools.refinery.viatra.runtime.base.itc.igraph.IBiDirectionalWrapper; | ||
20 | import tools.refinery.viatra.runtime.base.itc.igraph.IGraphDataSource; | ||
21 | import tools.refinery.viatra.runtime.base.itc.igraph.IGraphObserver; | ||
22 | import tools.refinery.viatra.runtime.base.itc.igraph.ITcDataSource; | ||
23 | import tools.refinery.viatra.runtime.base.itc.igraph.ITcObserver; | ||
24 | import tools.refinery.viatra.runtime.matchers.util.CollectionsFactory; | ||
25 | import 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 | */ | ||
35 | public 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 | |||
10 | package tools.refinery.viatra.runtime.base.itc.alg.counting; | ||
11 | |||
12 | import java.util.Collections; | ||
13 | import java.util.List; | ||
14 | import java.util.Set; | ||
15 | |||
16 | import tools.refinery.viatra.runtime.base.itc.alg.misc.ITcRelation; | ||
17 | import tools.refinery.viatra.runtime.base.itc.alg.misc.topsort.TopologicalSorting; | ||
18 | import tools.refinery.viatra.runtime.base.itc.igraph.IBiDirectionalGraphDataSource; | ||
19 | import tools.refinery.viatra.runtime.matchers.util.CollectionsFactory; | ||
20 | import tools.refinery.viatra.runtime.matchers.util.CollectionsFactory.MemoryType; | ||
21 | import tools.refinery.viatra.runtime.matchers.util.IMemoryView; | ||
22 | import tools.refinery.viatra.runtime.matchers.util.IMultiLookup; | ||
23 | import 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 | */ | ||
32 | public 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 | |||
10 | package tools.refinery.viatra.runtime.base.itc.alg.dred; | ||
11 | |||
12 | import java.util.ArrayList; | ||
13 | import java.util.HashMap; | ||
14 | import java.util.HashSet; | ||
15 | import java.util.List; | ||
16 | import java.util.Map; | ||
17 | import java.util.Map.Entry; | ||
18 | import java.util.Set; | ||
19 | |||
20 | import tools.refinery.viatra.runtime.base.itc.alg.misc.DFSPathFinder; | ||
21 | import tools.refinery.viatra.runtime.base.itc.alg.misc.IGraphPathFinder; | ||
22 | import tools.refinery.viatra.runtime.base.itc.alg.misc.Tuple; | ||
23 | import tools.refinery.viatra.runtime.base.itc.alg.misc.dfs.DFSAlg; | ||
24 | import tools.refinery.viatra.runtime.base.itc.igraph.IGraphDataSource; | ||
25 | import tools.refinery.viatra.runtime.base.itc.igraph.IGraphObserver; | ||
26 | import tools.refinery.viatra.runtime.base.itc.igraph.ITcDataSource; | ||
27 | import tools.refinery.viatra.runtime.base.itc.igraph.ITcObserver; | ||
28 | import tools.refinery.viatra.runtime.matchers.util.IMemoryView; | ||
29 | |||
30 | /** | ||
31 | * This class is the optimized implementation of the DRED algorithm. | ||
32 | * | ||
33 | * @author Tamas Szabo | ||
34 | * | ||
35 | * @param <V> | ||
36 | * the type parameter of the nodes in the graph data source | ||
37 | */ | ||
38 | public class DRedAlg<V> implements IGraphObserver<V>, ITcDataSource<V> { | ||
39 | |||
40 | private IGraphDataSource<V> graphDataSource = null; | ||
41 | private DRedTcRelation<V> tc = null; | ||
42 | private DRedTcRelation<V> dtc = null; | ||
43 | private List<ITcObserver<V>> observers; | ||
44 | |||
45 | /** | ||
46 | * Constructs a new DRED algorithm and initializes the transitive closure relation with the given graph data source. | ||
47 | * Attach itself on the graph data source as an observer. | ||
48 | * | ||
49 | * @param gds | ||
50 | * the graph data source instance | ||
51 | */ | ||
52 | public DRedAlg(IGraphDataSource<V> gds) { | ||
53 | this.observers = new ArrayList<ITcObserver<V>>(); | ||
54 | this.graphDataSource = gds; | ||
55 | this.tc = new DRedTcRelation<V>(); | ||
56 | this.dtc = new DRedTcRelation<V>(); | ||
57 | initTc(); | ||
58 | graphDataSource.attachObserver(this); | ||
59 | } | ||
60 | |||
61 | /** | ||
62 | * Constructs a new DRED algorithm and initializes the transitive closure relation with the given relation. Attach | ||
63 | * itself on the graph data source as an observer. | ||
64 | * | ||
65 | * @param gds | ||
66 | * the graph data source instance | ||
67 | * @param tc | ||
68 | * the transitive closure instance | ||
69 | */ | ||
70 | public DRedAlg(IGraphDataSource<V> gds, DRedTcRelation<V> tc) { | ||
71 | this.graphDataSource = gds; | ||
72 | this.tc = tc; | ||
73 | this.dtc = new DRedTcRelation<V>(); | ||
74 | graphDataSource.attachObserver(this); | ||
75 | } | ||
76 | |||
77 | /** | ||
78 | * Initializes the transitive closure relation. | ||
79 | */ | ||
80 | private void initTc() { | ||
81 | DFSAlg<V> dfsa = new DFSAlg<V>(this.graphDataSource); | ||
82 | this.setTcRelation(dfsa.getTcRelation()); | ||
83 | this.graphDataSource.detachObserver(dfsa); | ||
84 | } | ||
85 | |||
86 | @Override | ||
87 | public void edgeInserted(V source, V target) { | ||
88 | if (!source.equals(target)) { | ||
89 | Set<V> tupStarts = null; | ||
90 | Set<V> tupEnds = null; | ||
91 | Set<Tuple<V>> tuples = new HashSet<Tuple<V>>(); | ||
92 | |||
93 | if (!source.equals(target) && tc.addTuple(source, target)) { | ||
94 | tuples.add(new Tuple<V>(source, target)); | ||
95 | } | ||
96 | |||
97 | // 2. d+(tc(x,y)) :- d+(tc(x,z)) & lv(z,y) Descartes product | ||
98 | tupStarts = tc.getTupleStarts(source); | ||
99 | tupEnds = tc.getTupleEnds(target); | ||
100 | |||
101 | for (V s : tupStarts) { | ||
102 | for (V t : tupEnds) { | ||
103 | if (!s.equals(t) && tc.addTuple(s, t)) { | ||
104 | tuples.add(new Tuple<V>(s, t)); | ||
105 | } | ||
106 | } | ||
107 | } | ||
108 | |||
109 | // (s, source) -> (source, target) | ||
110 | // tupStarts = tc.getTupleStarts(source); | ||
111 | for (V s : tupStarts) { | ||
112 | if (!s.equals(target) && tc.addTuple(s, target)) { | ||
113 | tuples.add(new Tuple<V>(s, target)); | ||
114 | } | ||
115 | } | ||
116 | |||
117 | // (source, target) -> (target, t) | ||
118 | // tupEnds = tc.getTupleEnds(target); | ||
119 | for (V t : tupEnds) { | ||
120 | if (!source.equals(t) && tc.addTuple(source, t)) { | ||
121 | tuples.add(new Tuple<V>(source, t)); | ||
122 | } | ||
123 | } | ||
124 | |||
125 | notifyTcObservers(tuples, 1); | ||
126 | } | ||
127 | } | ||
128 | |||
129 | @Override | ||
130 | public void edgeDeleted(V source, V target) { | ||
131 | if (!source.equals(target)) { | ||
132 | |||
133 | // Computing overestimate, Descartes product of A and B sets, where | ||
134 | // A: those nodes from which source is reachable | ||
135 | // B: those nodes which is reachable from target | ||
136 | |||
137 | Map<Tuple<V>, Integer> tuples = new HashMap<Tuple<V>, Integer>(); | ||
138 | Set<V> sources = tc.getTupleStarts(source); | ||
139 | Set<V> targets = tc.getTupleEnds(target); | ||
140 | |||
141 | tc.removeTuple(source, target); | ||
142 | tuples.put(new Tuple<V>(source, target), -1); | ||
143 | |||
144 | for (V s : sources) { | ||
145 | for (V t : targets) { | ||
146 | if (!s.equals(t)) { | ||
147 | tc.removeTuple(s, t); | ||
148 | tuples.put(new Tuple<V>(s, t), -1); | ||
149 | } | ||
150 | } | ||
151 | } | ||
152 | |||
153 | for (V s : sources) { | ||
154 | if (!s.equals(target)) { | ||
155 | tc.removeTuple(s, target); | ||
156 | tuples.put(new Tuple<V>(s, target), -1); | ||
157 | } | ||
158 | } | ||
159 | |||
160 | for (V t : targets) { | ||
161 | if (!source.equals(t)) { | ||
162 | tc.removeTuple(source, t); | ||
163 | tuples.put(new Tuple<V>(source, t), -1); | ||
164 | } | ||
165 | } | ||
166 | |||
167 | // System.out.println("overestimate: "+dtc); | ||
168 | |||
169 | // Modify overestimate with those tuples that have alternative derivations | ||
170 | // 1. q+(tc(x,y)) :- lv(x,y) | ||
171 | for (V s : graphDataSource.getAllNodes()) { | ||
172 | IMemoryView<V> targetNodes = graphDataSource.getTargetNodes(s); | ||
173 | for (Entry<V, Integer> entry : targetNodes.entriesWithMultiplicities()) { | ||
174 | for (int i = 0; i < entry.getValue(); i++) { | ||
175 | V t = entry.getKey(); | ||
176 | if (!s.equals(t)) { | ||
177 | tc.addTuple(s, t); | ||
178 | Tuple<V> tuple = new Tuple<V>(s, t); | ||
179 | Integer count = tuples.get(tuple); | ||
180 | if (count != null && count == -1) { | ||
181 | tuples.remove(tuple); | ||
182 | } | ||
183 | } | ||
184 | |||
185 | } | ||
186 | } | ||
187 | } | ||
188 | |||
189 | // 2. q+(tc(x,y)) :- tcv(x,z) & lv(z,y) | ||
190 | DRedTcRelation<V> newTups = new DRedTcRelation<V>(); | ||
191 | dtc.clear(); | ||
192 | dtc.union(tc); | ||
193 | |||
194 | while (!dtc.isEmpty()) { | ||
195 | |||
196 | newTups.clear(); | ||
197 | newTups.union(dtc); | ||
198 | dtc.clear(); | ||
199 | |||
200 | for (V s : newTups.getTupleStarts()) { | ||
201 | for (V t : newTups.getTupleEnds(s)) { | ||
202 | IMemoryView<V> targetNodes = graphDataSource.getTargetNodes(t); | ||
203 | if (targetNodes != null) { | ||
204 | for (Entry<V, Integer> entry : targetNodes.entriesWithMultiplicities()) { | ||
205 | for (int i = 0; i < entry.getValue(); i++) { | ||
206 | V tn = entry.getKey(); | ||
207 | if (!s.equals(tn) && tc.addTuple(s, tn)) { | ||
208 | dtc.addTuple(s, tn); | ||
209 | tuples.remove(new Tuple<V>(s, tn)); | ||
210 | } | ||
211 | } | ||
212 | } | ||
213 | } | ||
214 | } | ||
215 | } | ||
216 | } | ||
217 | |||
218 | notifyTcObservers(tuples.keySet(), -1); | ||
219 | } | ||
220 | } | ||
221 | |||
222 | @Override | ||
223 | public void nodeInserted(V n) { | ||
224 | // Node inserted does not result new tc tuple. | ||
225 | } | ||
226 | |||
227 | @Override | ||
228 | public void nodeDeleted(V n) { | ||
229 | // FIXME node deletion may involve the deletion of incoming and outgoing edges too | ||
230 | Set<V> set = tc.getTupleEnds(n); | ||
231 | Set<V> modSet = null; | ||
232 | |||
233 | // n -> target | ||
234 | modSet = new HashSet<V>(set); | ||
235 | |||
236 | for (V tn : modSet) { | ||
237 | this.tc.removeTuple(n, tn); | ||
238 | } | ||
239 | |||
240 | // source -> n | ||
241 | set = tc.getTupleStarts(n); | ||
242 | |||
243 | modSet = new HashSet<V>(set); | ||
244 | |||
245 | for (V sn : modSet) { | ||
246 | this.tc.removeTuple(sn, n); | ||
247 | } | ||
248 | } | ||
249 | |||
250 | public DRedTcRelation<V> getTcRelation() { | ||
251 | return this.tc; | ||
252 | } | ||
253 | |||
254 | public void setTcRelation(DRedTcRelation<V> tc) { | ||
255 | this.tc = tc; | ||
256 | } | ||
257 | |||
258 | @Override | ||
259 | public boolean isReachable(V source, V target) { | ||
260 | return tc.containsTuple(source, target); | ||
261 | } | ||
262 | |||
263 | @Override | ||
264 | public void attachObserver(ITcObserver<V> to) { | ||
265 | this.observers.add(to); | ||
266 | } | ||
267 | |||
268 | @Override | ||
269 | public void detachObserver(ITcObserver<V> to) { | ||
270 | this.observers.remove(to); | ||
271 | } | ||
272 | |||
273 | @Override | ||
274 | public Set<V> getAllReachableTargets(V source) { | ||
275 | return tc.getTupleEnds(source); | ||
276 | } | ||
277 | |||
278 | @Override | ||
279 | public Set<V> getAllReachableSources(V target) { | ||
280 | return tc.getTupleStarts(target); | ||
281 | } | ||
282 | |||
283 | protected void notifyTcObservers(Set<Tuple<V>> tuples, int dir) { | ||
284 | for (ITcObserver<V> o : observers) { | ||
285 | for (Tuple<V> t : tuples) { | ||
286 | if (!t.getSource().equals(t.getTarget())) { | ||
287 | if (dir == 1) { | ||
288 | o.tupleInserted(t.getSource(), t.getTarget()); | ||
289 | } | ||
290 | if (dir == -1) { | ||
291 | o.tupleDeleted(t.getSource(), t.getTarget()); | ||
292 | } | ||
293 | } | ||
294 | } | ||
295 | } | ||
296 | } | ||
297 | |||
298 | @Override | ||
299 | public void dispose() { | ||
300 | tc = null; | ||
301 | dtc = null; | ||
302 | } | ||
303 | |||
304 | @Override | ||
305 | public IGraphPathFinder<V> getPathFinder() { | ||
306 | return new DFSPathFinder<V>(graphDataSource, this); | ||
307 | } | ||
308 | } | ||
diff --git a/subprojects/viatra-runtime-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 | |||
10 | package tools.refinery.viatra.runtime.base.itc.alg.dred; | ||
11 | |||
12 | import java.util.HashMap; | ||
13 | import java.util.HashSet; | ||
14 | import java.util.Map; | ||
15 | import java.util.Map.Entry; | ||
16 | import java.util.Set; | ||
17 | |||
18 | import tools.refinery.viatra.runtime.base.itc.alg.misc.ITcRelation; | ||
19 | |||
20 | public class DRedTcRelation<V> implements ITcRelation<V> { | ||
21 | |||
22 | // tc(a,b) means that b is transitively reachable from a | ||
23 | private Map<V, Set<V>> tuplesForward; | ||
24 | |||
25 | // data structure to efficiently get those nodes from which a given node is reachable | ||
26 | // symmetric to tuplesForward | ||
27 | private Map<V, Set<V>> tuplesBackward; | ||
28 | |||
29 | public DRedTcRelation() { | ||
30 | this.tuplesForward = new HashMap<V, Set<V>>(); | ||
31 | this.tuplesBackward = new HashMap<V, Set<V>>(); | ||
32 | } | ||
33 | |||
34 | public void clear() { | ||
35 | this.tuplesForward.clear(); | ||
36 | this.tuplesBackward.clear(); | ||
37 | } | ||
38 | |||
39 | public boolean isEmpty() { | ||
40 | return tuplesForward.isEmpty(); | ||
41 | } | ||
42 | |||
43 | public void removeTuple(V source, V target) { | ||
44 | |||
45 | // removing tuple from 'forward' tc relation | ||
46 | Set<V> sSet = tuplesForward.get(source); | ||
47 | if (sSet != null) { | ||
48 | sSet.remove(target); | ||
49 | if (sSet.size() == 0) | ||
50 | tuplesForward.remove(source); | ||
51 | } | ||
52 | |||
53 | // removing tuple from 'backward' tc relation | ||
54 | Set<V> tSet = tuplesBackward.get(target); | ||
55 | if (tSet != null) { | ||
56 | tSet.remove(source); | ||
57 | if (tSet.size() == 0) | ||
58 | tuplesBackward.remove(target); | ||
59 | } | ||
60 | } | ||
61 | |||
62 | /** | ||
63 | * Returns true if the tc relation did not contain previously such a tuple that is defined by (source,target), false | ||
64 | * otherwise. | ||
65 | * | ||
66 | * @param source | ||
67 | * the source of the tuple | ||
68 | * @param target | ||
69 | * the target of the tuple | ||
70 | * @return true if the relation did not contain previously the tuple | ||
71 | */ | ||
72 | public boolean addTuple(V source, V target) { | ||
73 | |||
74 | // symmetric modification, it is sufficient to check the return value in one collection | ||
75 | // adding tuple to 'forward' tc relation | ||
76 | Set<V> sSet = tuplesForward.get(source); | ||
77 | if (sSet == null) { | ||
78 | Set<V> newSet = new HashSet<V>(); | ||
79 | newSet.add(target); | ||
80 | tuplesForward.put(source, newSet); | ||
81 | } else { | ||
82 | sSet.add(target); | ||
83 | } | ||
84 | |||
85 | // adding tuple to 'backward' tc relation | ||
86 | Set<V> tSet = tuplesBackward.get(target); | ||
87 | if (tSet == null) { | ||
88 | Set<V> newSet = new HashSet<V>(); | ||
89 | newSet.add(source); | ||
90 | tuplesBackward.put(target, newSet); | ||
91 | return true; | ||
92 | } else { | ||
93 | boolean ret = tSet.add(source); | ||
94 | return ret; | ||
95 | } | ||
96 | |||
97 | } | ||
98 | |||
99 | /** | ||
100 | * Union operation of two tc realtions. | ||
101 | * | ||
102 | * @param rA | ||
103 | * the other tc relation | ||
104 | */ | ||
105 | public void union(DRedTcRelation<V> rA) { | ||
106 | for (V source : rA.tuplesForward.keySet()) { | ||
107 | for (V target : rA.tuplesForward.get(source)) { | ||
108 | this.addTuple(source, target); | ||
109 | } | ||
110 | } | ||
111 | } | ||
112 | |||
113 | /** | ||
114 | * Computes the difference of this tc relation and the given rA parameter. | ||
115 | * | ||
116 | * @param rA | ||
117 | * the subtrahend relation | ||
118 | */ | ||
119 | public void difference(DRedTcRelation<V> rA) { | ||
120 | for (V source : rA.tuplesForward.keySet()) { | ||
121 | for (V target : rA.tuplesForward.get(source)) { | ||
122 | this.removeTuple(source, target); | ||
123 | } | ||
124 | } | ||
125 | } | ||
126 | |||
127 | @Override | ||
128 | public Set<V> getTupleEnds(V source) { | ||
129 | Set<V> t = tuplesForward.get(source); | ||
130 | return (t == null) ? new HashSet<V>() : new HashSet<V>(t); | ||
131 | } | ||
132 | |||
133 | /** | ||
134 | * Returns the set of nodes from which the target node is reachable. | ||
135 | * | ||
136 | * @param target | ||
137 | * the target node | ||
138 | * @return the set of source nodes | ||
139 | */ | ||
140 | public Set<V> getTupleStarts(V target) { | ||
141 | Set<V> t = tuplesBackward.get(target); | ||
142 | return (t == null) ? new HashSet<V>() : new HashSet<V>(t); | ||
143 | } | ||
144 | |||
145 | @Override | ||
146 | public Set<V> getTupleStarts() { | ||
147 | Set<V> t = tuplesForward.keySet(); | ||
148 | return new HashSet<V>(t); | ||
149 | } | ||
150 | |||
151 | @Override | ||
152 | public String toString() { | ||
153 | StringBuilder sb = new StringBuilder("TcRelation = "); | ||
154 | |||
155 | for (Entry<V, Set<V>> entry : this.tuplesForward.entrySet()) { | ||
156 | V source = entry.getKey(); | ||
157 | for (V target : entry.getValue()) { | ||
158 | sb.append("(" + source + "," + target + ") "); | ||
159 | } | ||
160 | } | ||
161 | return sb.toString(); | ||
162 | } | ||
163 | |||
164 | /** | ||
165 | * Returns true if a (source, target) node is present in the transitive closure relation, false otherwise. | ||
166 | * | ||
167 | * @param source | ||
168 | * the source node | ||
169 | * @param target | ||
170 | * the target node | ||
171 | * @return true if tuple is present, false otherwise | ||
172 | */ | ||
173 | public boolean containsTuple(V source, V target) { | ||
174 | if (tuplesForward.containsKey(source)) { | ||
175 | if (tuplesForward.get(source).contains(target)) | ||
176 | return true; | ||
177 | } | ||
178 | return false; | ||
179 | } | ||
180 | |||
181 | @SuppressWarnings("unchecked") | ||
182 | @Override | ||
183 | public boolean equals(Object obj) { | ||
184 | if (this == obj) { | ||
185 | return true; | ||
186 | } | ||
187 | if ((obj == null) || (obj.getClass() != this.getClass())) { | ||
188 | return false; | ||
189 | } | ||
190 | |||
191 | DRedTcRelation<V> aTR = (DRedTcRelation<V>) obj; | ||
192 | |||
193 | for (Entry<V, Set<V>> entry : aTR.tuplesForward.entrySet()) { | ||
194 | V source = entry.getKey(); | ||
195 | for (V target : entry.getValue()) { | ||
196 | if (!this.containsTuple(source, target)) | ||
197 | return false; | ||
198 | } | ||
199 | } | ||
200 | |||
201 | for (Entry<V, Set<V>> entry : this.tuplesForward.entrySet()) { | ||
202 | V source = entry.getKey(); | ||
203 | for (V target : entry.getValue()) { | ||
204 | if (!aTR.containsTuple(source, target)) | ||
205 | return false; | ||
206 | } | ||
207 | } | ||
208 | |||
209 | return true; | ||
210 | } | ||
211 | |||
212 | @Override | ||
213 | public int hashCode() { | ||
214 | int hash = 7; | ||
215 | hash = 31 * hash + tuplesForward.hashCode(); | ||
216 | hash = 31 * hash + tuplesBackward.hashCode(); | ||
217 | return hash; | ||
218 | } | ||
219 | |||
220 | public Map<V, Set<V>> getTuplesForward() { | ||
221 | return tuplesForward; | ||
222 | } | ||
223 | } | ||
diff --git a/subprojects/viatra-runtime-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 | |||
10 | package tools.refinery.viatra.runtime.base.itc.alg.fw; | ||
11 | |||
12 | import java.util.HashMap; | ||
13 | import java.util.Map; | ||
14 | |||
15 | import tools.refinery.viatra.runtime.base.itc.alg.dred.DRedTcRelation; | ||
16 | import tools.refinery.viatra.runtime.base.itc.igraph.IBiDirectionalGraphDataSource; | ||
17 | import tools.refinery.viatra.runtime.base.itc.igraph.IBiDirectionalWrapper; | ||
18 | import tools.refinery.viatra.runtime.base.itc.igraph.IGraphDataSource; | ||
19 | import tools.refinery.viatra.runtime.base.itc.igraph.IGraphObserver; | ||
20 | import tools.refinery.viatra.runtime.matchers.util.IMemoryView; | ||
21 | |||
22 | public class FloydWarshallAlg<V> implements IGraphObserver<V> { | ||
23 | |||
24 | private DRedTcRelation<V> tc = null; | ||
25 | private IBiDirectionalGraphDataSource<V> gds = null; | ||
26 | |||
27 | public FloydWarshallAlg(IGraphDataSource<V> gds) { | ||
28 | if (gds instanceof IBiDirectionalGraphDataSource<?>) { | ||
29 | this.gds = (IBiDirectionalGraphDataSource<V>) gds; | ||
30 | } else { | ||
31 | this.gds = new IBiDirectionalWrapper<V>(gds); | ||
32 | } | ||
33 | |||
34 | this.tc = new DRedTcRelation<V>(); | ||
35 | gds.attachObserver(this); | ||
36 | generateTc(); | ||
37 | } | ||
38 | |||
39 | private void generateTc() { | ||
40 | |||
41 | tc.clear(); | ||
42 | |||
43 | int n = gds.getAllNodes().size(); | ||
44 | Map<V, Integer> mapForw = new HashMap<V, Integer>(); | ||
45 | Map<Integer, V> mapBackw = new HashMap<Integer, V>(); | ||
46 | int[][] P = new int[n][n]; | ||
47 | |||
48 | int i, j, k; | ||
49 | |||
50 | // initialize adjacent matrix | ||
51 | for (i = 0; i < n; i++) { | ||
52 | for (j = 0; j < n; j++) { | ||
53 | P[i][j] = 0; | ||
54 | } | ||
55 | } | ||
56 | |||
57 | i = 0; | ||
58 | for (V node : gds.getAllNodes()) { | ||
59 | mapForw.put(node, i); | ||
60 | mapBackw.put(i, node); | ||
61 | i++; | ||
62 | } | ||
63 | |||
64 | for (V source : gds.getAllNodes()) { | ||
65 | IMemoryView<V> targets = gds.getTargetNodes(source); | ||
66 | for (V target : targets.distinctValues()) { | ||
67 | P[mapForw.get(source)][mapForw.get(target)] = 1; | ||
68 | } | ||
69 | } | ||
70 | |||
71 | for (k = 0; k < n; k++) { | ||
72 | for (i = 0; i < n; i++) { | ||
73 | for (j = 0; j < n; j++) { | ||
74 | P[i][j] = P[i][j] | (P[i][k] & P[k][j]); | ||
75 | } | ||
76 | } | ||
77 | } | ||
78 | |||
79 | for (i = 0; i < n; i++) { | ||
80 | for (j = 0; j < n; j++) { | ||
81 | if (P[i][j] == 1 && i != j) | ||
82 | tc.addTuple(mapBackw.get(i), mapBackw.get(j)); | ||
83 | } | ||
84 | } | ||
85 | } | ||
86 | |||
87 | @Override | ||
88 | public void edgeInserted(V source, V target) { | ||
89 | generateTc(); | ||
90 | } | ||
91 | |||
92 | @Override | ||
93 | public void edgeDeleted(V source, V target) { | ||
94 | generateTc(); | ||
95 | } | ||
96 | |||
97 | @Override | ||
98 | public void nodeInserted(V n) { | ||
99 | generateTc(); | ||
100 | } | ||
101 | |||
102 | @Override | ||
103 | public void nodeDeleted(V n) { | ||
104 | generateTc(); | ||
105 | } | ||
106 | |||
107 | public DRedTcRelation<V> getTcRelation() { | ||
108 | return this.tc; | ||
109 | } | ||
110 | } | ||
diff --git a/subprojects/viatra-runtime-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 | *******************************************************************************/ | ||
9 | package tools.refinery.viatra.runtime.base.itc.alg.incscc; | ||
10 | |||
11 | import tools.refinery.viatra.runtime.base.itc.igraph.ITcObserver; | ||
12 | import tools.refinery.viatra.runtime.matchers.util.Direction; | ||
13 | |||
14 | /** | ||
15 | * @author Tamas Szabo | ||
16 | * | ||
17 | */ | ||
18 | public 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 | |||
10 | package tools.refinery.viatra.runtime.base.itc.alg.incscc; | ||
11 | |||
12 | import java.util.ArrayList; | ||
13 | import java.util.HashSet; | ||
14 | import java.util.Iterator; | ||
15 | import java.util.List; | ||
16 | import java.util.Map; | ||
17 | import java.util.Map.Entry; | ||
18 | import java.util.Objects; | ||
19 | import java.util.Set; | ||
20 | |||
21 | import tools.refinery.viatra.runtime.base.itc.alg.counting.CountingAlg; | ||
22 | import tools.refinery.viatra.runtime.base.itc.alg.dred.DRedTcRelation; | ||
23 | import tools.refinery.viatra.runtime.base.itc.alg.misc.DFSPathFinder; | ||
24 | import tools.refinery.viatra.runtime.base.itc.alg.misc.GraphHelper; | ||
25 | import tools.refinery.viatra.runtime.base.itc.alg.misc.IGraphPathFinder; | ||
26 | import tools.refinery.viatra.runtime.base.itc.alg.misc.Tuple; | ||
27 | import tools.refinery.viatra.runtime.base.itc.alg.misc.bfs.BFS; | ||
28 | import tools.refinery.viatra.runtime.base.itc.alg.misc.scc.SCC; | ||
29 | import tools.refinery.viatra.runtime.base.itc.alg.misc.scc.SCCResult; | ||
30 | import tools.refinery.viatra.runtime.base.itc.alg.util.CollectionHelper; | ||
31 | import tools.refinery.viatra.runtime.base.itc.graphimpl.Graph; | ||
32 | import tools.refinery.viatra.runtime.base.itc.igraph.IBiDirectionalGraphDataSource; | ||
33 | import tools.refinery.viatra.runtime.base.itc.igraph.IBiDirectionalWrapper; | ||
34 | import tools.refinery.viatra.runtime.base.itc.igraph.IGraphDataSource; | ||
35 | import tools.refinery.viatra.runtime.base.itc.igraph.IGraphObserver; | ||
36 | import tools.refinery.viatra.runtime.base.itc.igraph.ITcDataSource; | ||
37 | import tools.refinery.viatra.runtime.base.itc.igraph.ITcObserver; | ||
38 | import tools.refinery.viatra.runtime.matchers.algorithms.UnionFind; | ||
39 | import tools.refinery.viatra.runtime.matchers.util.CollectionsFactory; | ||
40 | import tools.refinery.viatra.runtime.matchers.util.Direction; | ||
41 | import 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 | */ | ||
51 | public 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 | *******************************************************************************/ | ||
9 | package tools.refinery.viatra.runtime.base.itc.alg.misc; | ||
10 | |||
11 | import java.util.ArrayList; | ||
12 | import java.util.Deque; | ||
13 | import java.util.HashSet; | ||
14 | import java.util.Iterator; | ||
15 | import java.util.LinkedList; | ||
16 | import java.util.List; | ||
17 | import java.util.Set; | ||
18 | |||
19 | import tools.refinery.viatra.runtime.base.itc.igraph.IGraphDataSource; | ||
20 | import tools.refinery.viatra.runtime.base.itc.igraph.ITcDataSource; | ||
21 | import 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 | */ | ||
33 | public 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 | |||
10 | package tools.refinery.viatra.runtime.base.itc.alg.misc; | ||
11 | |||
12 | public 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 | *******************************************************************************/ | ||
9 | package tools.refinery.viatra.runtime.base.itc.alg.misc; | ||
10 | |||
11 | import java.util.ArrayList; | ||
12 | import java.util.Collection; | ||
13 | import java.util.HashSet; | ||
14 | import java.util.List; | ||
15 | import java.util.Map.Entry; | ||
16 | import java.util.Set; | ||
17 | |||
18 | import tools.refinery.viatra.runtime.base.itc.graphimpl.Graph; | ||
19 | import tools.refinery.viatra.runtime.base.itc.igraph.IBiDirectionalGraphDataSource; | ||
20 | import tools.refinery.viatra.runtime.base.itc.igraph.IGraphDataSource; | ||
21 | import tools.refinery.viatra.runtime.matchers.util.IMemoryView; | ||
22 | |||
23 | /** | ||
24 | * Utility class for graph related operations. | ||
25 | * | ||
26 | * @author Tamas Szabo | ||
27 | */ | ||
28 | public 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 | *******************************************************************************/ | ||
9 | package tools.refinery.viatra.runtime.base.itc.alg.misc; | ||
10 | |||
11 | import java.util.Deque; | ||
12 | import java.util.Set; | ||
13 | |||
14 | import 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 | */ | ||
24 | public 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 | |||
10 | package tools.refinery.viatra.runtime.base.itc.alg.misc; | ||
11 | |||
12 | import java.util.Set; | ||
13 | |||
14 | public 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 | |||
10 | package tools.refinery.viatra.runtime.base.itc.alg.misc; | ||
11 | |||
12 | public 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 | |||
10 | package tools.refinery.viatra.runtime.base.itc.alg.misc.bfs; | ||
11 | |||
12 | import java.util.ArrayList; | ||
13 | import java.util.HashSet; | ||
14 | import java.util.List; | ||
15 | import java.util.Set; | ||
16 | |||
17 | import tools.refinery.viatra.runtime.base.itc.igraph.IBiDirectionalGraphDataSource; | ||
18 | import tools.refinery.viatra.runtime.base.itc.igraph.IGraphDataSource; | ||
19 | |||
20 | public class BFS<V> { | ||
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 | |||
10 | package tools.refinery.viatra.runtime.base.itc.alg.misc.dfs; | ||
11 | |||
12 | import java.util.HashMap; | ||
13 | |||
14 | import tools.refinery.viatra.runtime.base.itc.alg.dred.DRedTcRelation; | ||
15 | import tools.refinery.viatra.runtime.base.itc.igraph.IGraphDataSource; | ||
16 | import tools.refinery.viatra.runtime.base.itc.igraph.IGraphObserver; | ||
17 | |||
18 | public class DFSAlg<V> implements IGraphObserver<V> { | ||
19 | |||
20 | private IGraphDataSource<V> gds; | ||
21 | private DRedTcRelation<V> tc; | ||
22 | private int[] visited; | ||
23 | private HashMap<V, Integer> nodeMap; | ||
24 | |||
25 | public DFSAlg(IGraphDataSource<V> gds) { | ||
26 | this.gds = gds; | ||
27 | this.tc = new DRedTcRelation<V>(); | ||
28 | gds.attachObserver(this); | ||
29 | deriveTc(); | ||
30 | } | ||
31 | |||
32 | private void deriveTc() { | ||
33 | tc.clear(); | ||
34 | |||
35 | this.visited = new int[gds.getAllNodes().size()]; | ||
36 | nodeMap = new HashMap<V, Integer>(); | ||
37 | |||
38 | int j = 0; | ||
39 | for (V n : gds.getAllNodes()) { | ||
40 | nodeMap.put(n, j); | ||
41 | j++; | ||
42 | } | ||
43 | |||
44 | for (V n : gds.getAllNodes()) { | ||
45 | oneDFS(n, n); | ||
46 | initVisitedArray(); | ||
47 | } | ||
48 | } | ||
49 | |||
50 | private void initVisitedArray() { | ||
51 | for (int i = 0; i < visited.length; i++) | ||
52 | visited[i] = 0; | ||
53 | } | ||
54 | |||
55 | private void oneDFS(V act, V source) { | ||
56 | |||
57 | if (!act.equals(source)) { | ||
58 | tc.addTuple(source, act); | ||
59 | } | ||
60 | |||
61 | visited[nodeMap.get(act)] = 1; | ||
62 | |||
63 | for (V t : gds.getTargetNodes(act).distinctValues()) { | ||
64 | if (visited[nodeMap.get(t)] == 0) { | ||
65 | oneDFS(t, source); | ||
66 | } | ||
67 | } | ||
68 | } | ||
69 | |||
70 | public DRedTcRelation<V> getTcRelation() { | ||
71 | return this.tc; | ||
72 | } | ||
73 | |||
74 | @Override | ||
75 | public void edgeInserted(V source, V target) { | ||
76 | deriveTc(); | ||
77 | } | ||
78 | |||
79 | @Override | ||
80 | public void edgeDeleted(V source, V target) { | ||
81 | deriveTc(); | ||
82 | } | ||
83 | |||
84 | @Override | ||
85 | public void nodeInserted(V n) { | ||
86 | deriveTc(); | ||
87 | } | ||
88 | |||
89 | @Override | ||
90 | public void nodeDeleted(V n) { | ||
91 | deriveTc(); | ||
92 | } | ||
93 | } | ||
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 | |||
10 | package tools.refinery.viatra.runtime.base.itc.alg.misc.scc; | ||
11 | |||
12 | import java.util.ArrayList; | ||
13 | import java.util.Collections; | ||
14 | import java.util.HashMap; | ||
15 | import java.util.List; | ||
16 | import java.util.Map; | ||
17 | |||
18 | import tools.refinery.viatra.runtime.base.itc.igraph.IBiDirectionalGraphDataSource; | ||
19 | import tools.refinery.viatra.runtime.base.itc.igraph.IBiDirectionalWrapper; | ||
20 | import tools.refinery.viatra.runtime.base.itc.igraph.IGraphDataSource; | ||
21 | import tools.refinery.viatra.runtime.base.itc.igraph.IGraphObserver; | ||
22 | |||
23 | public 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 | |||
10 | package tools.refinery.viatra.runtime.base.itc.alg.misc.scc; | ||
11 | |||
12 | import java.util.HashSet; | ||
13 | import java.util.Map; | ||
14 | import java.util.Set; | ||
15 | import java.util.Stack; | ||
16 | |||
17 | import tools.refinery.viatra.runtime.base.itc.igraph.IGraphDataSource; | ||
18 | import 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 | */ | ||
28 | public 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 | |||
10 | package tools.refinery.viatra.runtime.base.itc.alg.misc.scc; | ||
11 | |||
12 | public 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 | |||
10 | package tools.refinery.viatra.runtime.base.itc.alg.misc.scc; | ||
11 | |||
12 | import java.util.Map.Entry; | ||
13 | import java.util.Set; | ||
14 | |||
15 | import tools.refinery.viatra.runtime.base.itc.igraph.IGraphDataSource; | ||
16 | |||
17 | public 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 | |||
10 | package tools.refinery.viatra.runtime.base.itc.alg.misc.topsort; | ||
11 | |||
12 | import java.util.HashSet; | ||
13 | import java.util.LinkedList; | ||
14 | import java.util.List; | ||
15 | import java.util.Set; | ||
16 | import java.util.Stack; | ||
17 | |||
18 | import tools.refinery.viatra.runtime.base.itc.igraph.IGraphDataSource; | ||
19 | |||
20 | /** | ||
21 | * @since 1.6 | ||
22 | */ | ||
23 | public 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 | */ | ||
6 | package tools.refinery.viatra.runtime.base.itc.alg.representative; | ||
7 | |||
8 | import tools.refinery.viatra.runtime.base.itc.graphimpl.Graph; | ||
9 | import tools.refinery.viatra.runtime.base.itc.igraph.IGraphObserver; | ||
10 | import tools.refinery.viatra.runtime.matchers.util.Direction; | ||
11 | |||
12 | import java.util.HashMap; | ||
13 | import java.util.HashSet; | ||
14 | import java.util.Map; | ||
15 | import java.util.Set; | ||
16 | |||
17 | public 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 | */ | ||
6 | package tools.refinery.viatra.runtime.base.itc.alg.representative; | ||
7 | |||
8 | import tools.refinery.viatra.runtime.matchers.util.Direction; | ||
9 | |||
10 | public 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 | */ | ||
6 | package tools.refinery.viatra.runtime.base.itc.alg.representative; | ||
7 | |||
8 | import tools.refinery.viatra.runtime.base.itc.alg.misc.GraphHelper; | ||
9 | import tools.refinery.viatra.runtime.base.itc.alg.misc.bfs.BFS; | ||
10 | import tools.refinery.viatra.runtime.base.itc.alg.misc.scc.SCC; | ||
11 | import tools.refinery.viatra.runtime.base.itc.graphimpl.Graph; | ||
12 | |||
13 | import java.util.Collection; | ||
14 | import java.util.Set; | ||
15 | |||
16 | public 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 | */ | ||
6 | package tools.refinery.viatra.runtime.base.itc.alg.representative; | ||
7 | |||
8 | import tools.refinery.viatra.runtime.base.itc.graphimpl.Graph; | ||
9 | |||
10 | import java.util.ArrayDeque; | ||
11 | import java.util.HashSet; | ||
12 | import java.util.Set; | ||
13 | |||
14 | public 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 | *******************************************************************************/ | ||
9 | package tools.refinery.viatra.runtime.base.itc.alg.util; | ||
10 | |||
11 | import java.util.Set; | ||
12 | |||
13 | import tools.refinery.viatra.runtime.matchers.util.CollectionsFactory; | ||
14 | |||
15 | /** | ||
16 | * @author Tamas Szabo | ||
17 | * | ||
18 | */ | ||
19 | public 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 | *******************************************************************************/ | ||
9 | package tools.refinery.viatra.runtime.base.itc.graphimpl; | ||
10 | |||
11 | import tools.refinery.viatra.runtime.base.itc.alg.misc.scc.SCC; | ||
12 | import tools.refinery.viatra.runtime.base.itc.alg.misc.scc.SCCResult; | ||
13 | import tools.refinery.viatra.runtime.matchers.util.IMemoryView; | ||
14 | |||
15 | import java.util.HashMap; | ||
16 | import java.util.Map; | ||
17 | import java.util.Set; | ||
18 | import 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 | */ | ||
26 | public 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 | |||
10 | package tools.refinery.viatra.runtime.base.itc.graphimpl; | ||
11 | |||
12 | import tools.refinery.viatra.runtime.base.itc.igraph.IBiDirectionalGraphDataSource; | ||
13 | import tools.refinery.viatra.runtime.base.itc.igraph.IGraphDataSource; | ||
14 | import tools.refinery.viatra.runtime.base.itc.igraph.IGraphObserver; | ||
15 | import tools.refinery.viatra.runtime.matchers.util.CollectionsFactory; | ||
16 | import tools.refinery.viatra.runtime.matchers.util.CollectionsFactory.MemoryType; | ||
17 | import tools.refinery.viatra.runtime.matchers.util.IMemoryView; | ||
18 | import tools.refinery.viatra.runtime.matchers.util.IMultiLookup; | ||
19 | |||
20 | import java.util.List; | ||
21 | import java.util.Map; | ||
22 | import java.util.Map.Entry; | ||
23 | import java.util.Set; | ||
24 | |||
25 | public 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 | |||
10 | package tools.refinery.viatra.runtime.base.itc.igraph; | ||
11 | |||
12 | import tools.refinery.viatra.runtime.matchers.util.IMemoryView; | ||
13 | import 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 | */ | ||
23 | public 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 | |||
10 | package tools.refinery.viatra.runtime.base.itc.igraph; | ||
11 | |||
12 | import java.util.Set; | ||
13 | |||
14 | import tools.refinery.viatra.runtime.matchers.util.CollectionsFactory; | ||
15 | import tools.refinery.viatra.runtime.matchers.util.CollectionsFactory.MemoryType; | ||
16 | import tools.refinery.viatra.runtime.matchers.util.IMemoryView; | ||
17 | import 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 | */ | ||
29 | public 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 | |||
10 | package tools.refinery.viatra.runtime.base.itc.igraph; | ||
11 | |||
12 | import tools.refinery.viatra.runtime.matchers.util.IMemoryView; | ||
13 | import tools.refinery.viatra.runtime.matchers.util.IMultiset; | ||
14 | |||
15 | import 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 | */ | ||
27 | public 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 | |||
10 | package 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 | */ | ||
18 | public 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 | |||
10 | package tools.refinery.viatra.runtime.base.itc.igraph; | ||
11 | |||
12 | import java.util.Set; | ||
13 | |||
14 | import 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 | */ | ||
24 | public 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 | |||
10 | package 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 | */ | ||
18 | public 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 | } | ||