diff options
Diffstat (limited to 'subprojects/viatra-runtime-rete/src/main/java/tools/refinery/viatra/runtime/rete/itc')
29 files changed, 3444 insertions, 0 deletions
diff --git a/subprojects/viatra-runtime-rete/src/main/java/tools/refinery/viatra/runtime/rete/itc/alg/counting/CountingAlg.java b/subprojects/viatra-runtime-rete/src/main/java/tools/refinery/viatra/runtime/rete/itc/alg/counting/CountingAlg.java new file mode 100644 index 00000000..199b44b1 --- /dev/null +++ b/subprojects/viatra-runtime-rete/src/main/java/tools/refinery/viatra/runtime/rete/itc/alg/counting/CountingAlg.java | |||
@@ -0,0 +1,226 @@ | |||
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.rete.itc.alg.counting; | ||
11 | |||
12 | import java.util.List; | ||
13 | import java.util.Set; | ||
14 | |||
15 | import tools.refinery.viatra.runtime.rete.itc.alg.misc.DFSPathFinder; | ||
16 | import tools.refinery.viatra.runtime.rete.itc.alg.misc.IGraphPathFinder; | ||
17 | import tools.refinery.viatra.runtime.rete.itc.alg.misc.ITcRelation; | ||
18 | import tools.refinery.viatra.runtime.rete.itc.igraph.IBiDirectionalGraphDataSource; | ||
19 | import tools.refinery.viatra.runtime.rete.itc.igraph.IBiDirectionalWrapper; | ||
20 | import tools.refinery.viatra.runtime.rete.itc.igraph.IGraphDataSource; | ||
21 | import tools.refinery.viatra.runtime.rete.itc.igraph.IGraphObserver; | ||
22 | import tools.refinery.viatra.runtime.rete.itc.igraph.ITcDataSource; | ||
23 | import tools.refinery.viatra.runtime.rete.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 | } | ||
diff --git a/subprojects/viatra-runtime-rete/src/main/java/tools/refinery/viatra/runtime/rete/itc/alg/counting/CountingTcRelation.java b/subprojects/viatra-runtime-rete/src/main/java/tools/refinery/viatra/runtime/rete/itc/alg/counting/CountingTcRelation.java new file mode 100644 index 00000000..474c7461 --- /dev/null +++ b/subprojects/viatra-runtime-rete/src/main/java/tools/refinery/viatra/runtime/rete/itc/alg/counting/CountingTcRelation.java | |||
@@ -0,0 +1,259 @@ | |||
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.rete.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.rete.itc.alg.misc.topsort.TopologicalSorting; | ||
17 | import tools.refinery.viatra.runtime.rete.itc.alg.misc.ITcRelation; | ||
18 | import tools.refinery.viatra.runtime.rete.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-rete/src/main/java/tools/refinery/viatra/runtime/rete/itc/alg/incscc/CountingListener.java b/subprojects/viatra-runtime-rete/src/main/java/tools/refinery/viatra/runtime/rete/itc/alg/incscc/CountingListener.java new file mode 100644 index 00000000..7d507d82 --- /dev/null +++ b/subprojects/viatra-runtime-rete/src/main/java/tools/refinery/viatra/runtime/rete/itc/alg/incscc/CountingListener.java | |||
@@ -0,0 +1,36 @@ | |||
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.rete.itc.alg.incscc; | ||
10 | |||
11 | import tools.refinery.viatra.runtime.rete.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 | } | ||
diff --git a/subprojects/viatra-runtime-rete/src/main/java/tools/refinery/viatra/runtime/rete/itc/alg/incscc/IncSCCAlg.java b/subprojects/viatra-runtime-rete/src/main/java/tools/refinery/viatra/runtime/rete/itc/alg/incscc/IncSCCAlg.java new file mode 100644 index 00000000..774e55eb --- /dev/null +++ b/subprojects/viatra-runtime-rete/src/main/java/tools/refinery/viatra/runtime/rete/itc/alg/incscc/IncSCCAlg.java | |||
@@ -0,0 +1,609 @@ | |||
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.rete.itc.alg.incscc; | ||
11 | |||
12 | import tools.refinery.viatra.runtime.matchers.algorithms.UnionFind; | ||
13 | import tools.refinery.viatra.runtime.matchers.util.CollectionsFactory; | ||
14 | import tools.refinery.viatra.runtime.matchers.util.Direction; | ||
15 | import tools.refinery.viatra.runtime.matchers.util.IMemoryView; | ||
16 | import tools.refinery.viatra.runtime.rete.itc.alg.counting.CountingAlg; | ||
17 | import tools.refinery.viatra.runtime.rete.itc.alg.misc.DFSPathFinder; | ||
18 | import tools.refinery.viatra.runtime.rete.itc.alg.misc.GraphHelper; | ||
19 | import tools.refinery.viatra.runtime.rete.itc.alg.misc.IGraphPathFinder; | ||
20 | import tools.refinery.viatra.runtime.rete.itc.alg.misc.Tuple; | ||
21 | import tools.refinery.viatra.runtime.rete.itc.alg.misc.bfs.BFS; | ||
22 | import tools.refinery.viatra.runtime.rete.itc.alg.misc.scc.SCC; | ||
23 | import tools.refinery.viatra.runtime.rete.itc.alg.misc.scc.SCCResult; | ||
24 | import tools.refinery.viatra.runtime.rete.itc.alg.util.CollectionHelper; | ||
25 | import tools.refinery.viatra.runtime.rete.itc.graphimpl.Graph; | ||
26 | import tools.refinery.viatra.runtime.rete.itc.igraph.*; | ||
27 | |||
28 | import java.util.*; | ||
29 | import java.util.Map.Entry; | ||
30 | |||
31 | /** | ||
32 | * Incremental SCC maintenance + counting algorithm. | ||
33 | * | ||
34 | * @author Tamas Szabo | ||
35 | * | ||
36 | * @param <V> | ||
37 | * the type parameter of the nodes in the graph data source | ||
38 | */ | ||
39 | public class IncSCCAlg<V> implements IGraphObserver<V>, ITcDataSource<V> { | ||
40 | |||
41 | public UnionFind<V> sccs; | ||
42 | public IBiDirectionalGraphDataSource<V> gds; | ||
43 | private CountingAlg<V> counting; | ||
44 | private Graph<V> reducedGraph; | ||
45 | private IBiDirectionalGraphDataSource<V> reducedGraphIndexer; | ||
46 | private List<ITcObserver<V>> observers; | ||
47 | private CountingListener<V> countingListener; | ||
48 | |||
49 | public IncSCCAlg(IGraphDataSource<V> graphDataSource) { | ||
50 | |||
51 | if (graphDataSource instanceof IBiDirectionalGraphDataSource<?>) { | ||
52 | gds = (IBiDirectionalGraphDataSource<V>) graphDataSource; | ||
53 | } else { | ||
54 | gds = new IBiDirectionalWrapper<V>(graphDataSource); | ||
55 | } | ||
56 | observers = CollectionsFactory.createObserverList(); | ||
57 | sccs = new UnionFind<V>(); | ||
58 | reducedGraph = new Graph<V>(); | ||
59 | reducedGraphIndexer = new IBiDirectionalWrapper<V>(reducedGraph); | ||
60 | countingListener = new CountingListener<V>(this); | ||
61 | initalizeInternalDataStructures(); | ||
62 | gds.attachObserver(this); | ||
63 | } | ||
64 | |||
65 | private void initalizeInternalDataStructures() { | ||
66 | SCCResult<V> _sccres = SCC.computeSCC(gds); | ||
67 | Set<Set<V>> _sccs = _sccres.getSccs(); | ||
68 | |||
69 | for (Set<V> _set : _sccs) { | ||
70 | sccs.makeSet(_set); | ||
71 | } | ||
72 | |||
73 | // Initalization of the reduced graph | ||
74 | for (V n : sccs.getPartitionHeads()) { | ||
75 | reducedGraph.insertNode(n); | ||
76 | } | ||
77 | |||
78 | for (V source : gds.getAllNodes()) { | ||
79 | final IMemoryView<V> targetNodes = gds.getTargetNodes(source); | ||
80 | for (Entry<V, Integer> entry : targetNodes.entriesWithMultiplicities()) { | ||
81 | for (int i = 0; i < entry.getValue(); i++) { | ||
82 | V target = entry.getKey(); | ||
83 | V sourceRoot = sccs.find(source); | ||
84 | V targetRoot = sccs.find(target); | ||
85 | |||
86 | if (!sourceRoot.equals(targetRoot)) { | ||
87 | reducedGraph.insertEdge(sourceRoot, targetRoot); | ||
88 | } | ||
89 | } | ||
90 | } | ||
91 | } | ||
92 | |||
93 | counting = new CountingAlg<V>(reducedGraph); | ||
94 | } | ||
95 | |||
96 | @Override | ||
97 | public void edgeInserted(V source, V target) { | ||
98 | V sourceRoot = sccs.find(source); | ||
99 | V targetRoot = sccs.find(target); | ||
100 | |||
101 | // Different SCC | ||
102 | if (!sourceRoot.equals(targetRoot)) { | ||
103 | |||
104 | // source is reachable from target? | ||
105 | if (counting.isReachable(targetRoot, sourceRoot)) { | ||
106 | |||
107 | Set<V> predecessorRoots = counting.getAllReachableSources(sourceRoot); | ||
108 | Set<V> successorRoots = counting.getAllReachableTargets(targetRoot); | ||
109 | |||
110 | // 1. intersection of source and target roots, these will be in the merged SCC | ||
111 | Set<V> isectRoots = CollectionHelper.intersection(predecessorRoots, successorRoots); | ||
112 | isectRoots.add(sourceRoot); | ||
113 | isectRoots.add(targetRoot); | ||
114 | |||
115 | // notifications must be issued before Union-Find modifications | ||
116 | if (observers.size() > 0) { | ||
117 | Set<V> sourceSCCs = createSetNullTolerant(predecessorRoots); | ||
118 | sourceSCCs.add(sourceRoot); | ||
119 | Set<V> targetSCCs = createSetNullTolerant(successorRoots); | ||
120 | targetSCCs.add(targetRoot); | ||
121 | |||
122 | // tracing back to actual nodes | ||
123 | for (V sourceSCC : sourceSCCs) { | ||
124 | targetLoop: for (V targetSCC : targetSCCs) { | ||
125 | if (counting.isReachable(sourceSCC, targetSCC)) continue targetLoop; | ||
126 | |||
127 | boolean needsNotification = | ||
128 | // Case 1. sourceSCC and targetSCC are the same and it is a one sized scc. | ||
129 | // Issue notifications only if there is no self-loop present at the moment | ||
130 | (sourceSCC.equals(targetSCC) && sccs.getPartition(sourceSCC).size() == 1 && GraphHelper | ||
131 | .getEdgeCount(sccs.getPartition(sourceSCC).iterator().next(), gds) == 0) | ||
132 | || | ||
133 | // Case 2. sourceSCC and targetSCC are different sccs. | ||
134 | (!sourceSCC.equals(targetSCC)); | ||
135 | // if self loop is already present omit the notification | ||
136 | if (needsNotification) { | ||
137 | notifyTcObservers(sccs.getPartition(sourceSCC), sccs.getPartition(targetSCC), | ||
138 | Direction.INSERT); | ||
139 | } | ||
140 | } | ||
141 | } | ||
142 | } | ||
143 | |||
144 | // 2. delete edges, nodes | ||
145 | List<V> sourceSCCs = new ArrayList<V>(); | ||
146 | List<V> targetSCCs = new ArrayList<V>(); | ||
147 | |||
148 | for (V r : isectRoots) { | ||
149 | List<V> sourceSCCsOfSCC = getSourceSCCsOfSCC(r); | ||
150 | List<V> targetSCCsOfSCC = getTargetSCCsOfSCC(r); | ||
151 | |||
152 | for (V sourceSCC : sourceSCCsOfSCC) { | ||
153 | if (!sourceSCC.equals(r)) { | ||
154 | reducedGraph.deleteEdgeIfExists(sourceSCC, r); | ||
155 | } | ||
156 | } | ||
157 | |||
158 | for (V targetSCC : targetSCCsOfSCC) { | ||
159 | if (!isectRoots.contains(targetSCC) && !r.equals(targetSCC)) { | ||
160 | reducedGraph.deleteEdgeIfExists(r, targetSCC); | ||
161 | } | ||
162 | } | ||
163 | |||
164 | sourceSCCs.addAll(sourceSCCsOfSCC); | ||
165 | targetSCCs.addAll(targetSCCsOfSCC); | ||
166 | } | ||
167 | |||
168 | for (V r : isectRoots) { | ||
169 | reducedGraph.deleteNode(r); | ||
170 | } | ||
171 | |||
172 | // 3. union | ||
173 | Iterator<V> iterator = isectRoots.iterator(); | ||
174 | V newRoot = iterator.next(); | ||
175 | while (iterator.hasNext()) { | ||
176 | newRoot = sccs.union(newRoot, iterator.next()); | ||
177 | } | ||
178 | |||
179 | // 4. add new node | ||
180 | reducedGraph.insertNode(newRoot); | ||
181 | |||
182 | // 5. add edges | ||
183 | Set<V> containedNodes = sccs.getPartition(newRoot); | ||
184 | |||
185 | for (V sourceSCC : sourceSCCs) { | ||
186 | if (!containedNodes.contains(sourceSCC) && !sourceSCC.equals(newRoot)) { | ||
187 | reducedGraph.insertEdge(sourceSCC, newRoot); | ||
188 | } | ||
189 | } | ||
190 | for (V targetSCC : targetSCCs) { | ||
191 | if (!containedNodes.contains(targetSCC) && !targetSCC.equals(newRoot)) { | ||
192 | reducedGraph.insertEdge(newRoot, targetSCC); | ||
193 | } | ||
194 | } | ||
195 | } else { | ||
196 | if (observers.size() > 0 && GraphHelper.getEdgeCount(source, target, gds) == 1) { | ||
197 | counting.attachObserver(countingListener); | ||
198 | } | ||
199 | reducedGraph.insertEdge(sourceRoot, targetRoot); | ||
200 | counting.detachObserver(countingListener); | ||
201 | } | ||
202 | } else { | ||
203 | // Notifications about self-loops | ||
204 | if (observers.size() > 0 && sccs.getPartition(sourceRoot).size() == 1 | ||
205 | && GraphHelper.getEdgeCount(source, target, gds) == 1) { | ||
206 | notifyTcObservers(source, source, Direction.INSERT); | ||
207 | } | ||
208 | } | ||
209 | } | ||
210 | |||
211 | @Override | ||
212 | public void edgeDeleted(V source, V target) { | ||
213 | V sourceRoot = sccs.find(source); | ||
214 | V targetRoot = sccs.find(target); | ||
215 | |||
216 | if (!sourceRoot.equals(targetRoot)) { | ||
217 | if (observers.size() > 0 && GraphHelper.getEdgeCount(source, target, gds) == 0) { | ||
218 | counting.attachObserver(countingListener); | ||
219 | } | ||
220 | reducedGraph.deleteEdgeIfExists(sourceRoot, targetRoot); | ||
221 | counting.detachObserver(countingListener); | ||
222 | } else { | ||
223 | // get the graph for the scc whose root is sourceRoot | ||
224 | Graph<V> g = GraphHelper.getSubGraph(sccs.getPartition(sourceRoot), gds); | ||
225 | |||
226 | // if source is not reachable from target anymore | ||
227 | if (!BFS.isReachable(source, target, g)) { | ||
228 | // create copies of the current state before destructive manipulation | ||
229 | Map<V, Integer> reachableSources = CollectionsFactory.createMap(); | ||
230 | for (Entry<V, Integer> entry : reducedGraphIndexer.getSourceNodes(sourceRoot).entriesWithMultiplicities()) { | ||
231 | reachableSources.put(entry.getKey(), entry.getValue()); | ||
232 | } | ||
233 | Map<V, Integer> reachableTargets = CollectionsFactory.createMap(); | ||
234 | for (Entry<V, Integer> entry : reducedGraphIndexer.getTargetNodes(sourceRoot).entriesWithMultiplicities()) { | ||
235 | reachableTargets.put(entry.getKey(), entry.getValue()); | ||
236 | } | ||
237 | |||
238 | SCCResult<V> _newSccs = SCC.computeSCC(g); | ||
239 | |||
240 | // delete scc node (and with its edges too) | ||
241 | for (Entry<V, Integer> entry : reachableSources.entrySet()) { | ||
242 | V s = entry.getKey(); | ||
243 | for (int i = 0; i < entry.getValue(); i++) { | ||
244 | reducedGraph.deleteEdgeIfExists(s, sourceRoot); | ||
245 | } | ||
246 | } | ||
247 | |||
248 | for (Entry<V, Integer> entry : reachableTargets.entrySet()) { | ||
249 | V t = entry.getKey(); | ||
250 | for (int i = 0; i < entry.getValue(); i++) { | ||
251 | reducedGraph.deleteEdgeIfExists(sourceRoot, t); | ||
252 | } | ||
253 | } | ||
254 | |||
255 | sccs.deleteSet(sourceRoot); | ||
256 | reducedGraph.deleteNode(sourceRoot); | ||
257 | |||
258 | Set<Set<V>> newSCCs = _newSccs.getSccs(); | ||
259 | Set<V> newSCCRoots = CollectionsFactory.createSet(); | ||
260 | |||
261 | // add new nodes and edges to the reduced graph | ||
262 | for (Set<V> newSCC : newSCCs) { | ||
263 | V newRoot = sccs.makeSet(newSCC); | ||
264 | reducedGraph.insertNode(newRoot); | ||
265 | newSCCRoots.add(newRoot); | ||
266 | } | ||
267 | for (V newSCCRoot : newSCCRoots) { | ||
268 | List<V> sourceSCCsOfSCC = getSourceSCCsOfSCC(newSCCRoot); | ||
269 | List<V> targetSCCsOfSCC = getTargetSCCsOfSCC(newSCCRoot); | ||
270 | |||
271 | for (V sourceSCC : sourceSCCsOfSCC) { | ||
272 | if (!sourceSCC.equals(newSCCRoot)) { | ||
273 | reducedGraph.insertEdge(sccs.find(sourceSCC), newSCCRoot); | ||
274 | } | ||
275 | } | ||
276 | for (V targetSCC : targetSCCsOfSCC) { | ||
277 | if (!newSCCRoots.contains(targetSCC) && !targetSCC.equals(newSCCRoot)) | ||
278 | reducedGraph.insertEdge(newSCCRoot, targetSCC); | ||
279 | } | ||
280 | } | ||
281 | |||
282 | // Must be after the union-find modifications | ||
283 | if (observers.size() > 0) { | ||
284 | V newSourceRoot = sccs.find(source); | ||
285 | V newTargetRoot = sccs.find(target); | ||
286 | |||
287 | Set<V> sourceSCCs = createSetNullTolerant(counting.getAllReachableSources(newSourceRoot)); | ||
288 | sourceSCCs.add(newSourceRoot); | ||
289 | |||
290 | Set<V> targetSCCs = createSetNullTolerant(counting.getAllReachableTargets(newTargetRoot)); | ||
291 | targetSCCs.add(newTargetRoot); | ||
292 | |||
293 | for (V sourceSCC : sourceSCCs) { | ||
294 | targetLoop: for (V targetSCC : targetSCCs) { | ||
295 | if (counting.isReachable(sourceSCC, targetSCC)) continue targetLoop; | ||
296 | |||
297 | boolean needsNotification = | ||
298 | // Case 1. sourceSCC and targetSCC are the same and it is a one sized scc. | ||
299 | // Issue notifications only if there is no self-loop present at the moment | ||
300 | (sourceSCC.equals(targetSCC) && sccs.getPartition(sourceSCC).size() == 1 && GraphHelper | ||
301 | .getEdgeCount(sccs.getPartition(sourceSCC).iterator().next(), gds) == 0) | ||
302 | || | ||
303 | // Case 2. sourceSCC and targetSCC are different sccs. | ||
304 | (!sourceSCC.equals(targetSCC)); | ||
305 | // if self loop is already present omit the notification | ||
306 | if (needsNotification) { | ||
307 | notifyTcObservers(sccs.getPartition(sourceSCC), sccs.getPartition(targetSCC), | ||
308 | Direction.DELETE); | ||
309 | } | ||
310 | } | ||
311 | } | ||
312 | } | ||
313 | } else { | ||
314 | // only handle self-loop notifications - sourceRoot equals to targetRoot | ||
315 | if (observers.size() > 0 && sccs.getPartition(sourceRoot).size() == 1 | ||
316 | && GraphHelper.getEdgeCount(source, target, gds) == 0) { | ||
317 | notifyTcObservers(source, source, Direction.DELETE); | ||
318 | } | ||
319 | } | ||
320 | } | ||
321 | } | ||
322 | |||
323 | @Override | ||
324 | public void nodeInserted(V n) { | ||
325 | sccs.makeSet(n); | ||
326 | reducedGraph.insertNode(n); | ||
327 | } | ||
328 | |||
329 | @Override | ||
330 | public void nodeDeleted(V n) { | ||
331 | IMemoryView<V> sources = gds.getSourceNodes(n); | ||
332 | IMemoryView<V> targets = gds.getTargetNodes(n); | ||
333 | |||
334 | for (Entry<V, Integer> entry : sources.entriesWithMultiplicities()) { | ||
335 | for (int i = 0; i < entry.getValue(); i++) { | ||
336 | V source = entry.getKey(); | ||
337 | edgeDeleted(source, n); | ||
338 | } | ||
339 | } | ||
340 | |||
341 | for (Entry<V, Integer> entry : targets.entriesWithMultiplicities()) { | ||
342 | for (int i = 0; i < entry.getValue(); i++) { | ||
343 | V target = entry.getKey(); | ||
344 | edgeDeleted(n, target); | ||
345 | } | ||
346 | } | ||
347 | |||
348 | sccs.deleteSet(n); | ||
349 | } | ||
350 | |||
351 | @Override | ||
352 | public void attachObserver(ITcObserver<V> to) { | ||
353 | observers.add(to); | ||
354 | } | ||
355 | |||
356 | @Override | ||
357 | public void detachObserver(ITcObserver<V> to) { | ||
358 | observers.remove(to); | ||
359 | } | ||
360 | |||
361 | @Override | ||
362 | public Set<V> getAllReachableTargets(V source) { | ||
363 | V sourceRoot = sccs.find(source); | ||
364 | Set<V> containedNodes = sccs.getPartition(sourceRoot); | ||
365 | Set<V> targets = CollectionsFactory.createSet(); | ||
366 | |||
367 | if (containedNodes.size() > 1 || GraphHelper.getEdgeCount(source, gds) == 1) { | ||
368 | targets.addAll(containedNodes); | ||
369 | } | ||
370 | |||
371 | Set<V> rootSet = counting.getAllReachableTargets(sourceRoot); | ||
372 | if (rootSet != null) { | ||
373 | for (V _root : rootSet) { | ||
374 | targets.addAll(sccs.getPartition(_root)); | ||
375 | } | ||
376 | } | ||
377 | |||
378 | return targets; | ||
379 | } | ||
380 | |||
381 | @Override | ||
382 | public Set<V> getAllReachableSources(V target) { | ||
383 | V targetRoot = sccs.find(target); | ||
384 | Set<V> containedNodes = sccs.getPartition(targetRoot); | ||
385 | Set<V> sources = CollectionsFactory.createSet(); | ||
386 | |||
387 | if (containedNodes.size() > 1 || GraphHelper.getEdgeCount(target, gds) == 1) { | ||
388 | sources.addAll(containedNodes); | ||
389 | } | ||
390 | |||
391 | Set<V> rootSet = counting.getAllReachableSources(targetRoot); | ||
392 | if (rootSet != null) { | ||
393 | for (V _root : rootSet) { | ||
394 | sources.addAll(sccs.getPartition(_root)); | ||
395 | } | ||
396 | } | ||
397 | return sources; | ||
398 | } | ||
399 | |||
400 | @Override | ||
401 | public boolean isReachable(V source, V target) { | ||
402 | V sourceRoot = sccs.find(source); | ||
403 | V targetRoot = sccs.find(target); | ||
404 | |||
405 | if (sourceRoot.equals(targetRoot)) | ||
406 | return true; | ||
407 | else | ||
408 | return counting.isReachable(sourceRoot, targetRoot); | ||
409 | } | ||
410 | |||
411 | public List<V> getReachabilityPath(V source, V target) { | ||
412 | if (!isReachable(source, target)) { | ||
413 | return null; | ||
414 | } else { | ||
415 | Set<V> sccsInSubGraph = CollectionHelper.intersection(counting.getAllReachableTargets(source), | ||
416 | counting.getAllReachableSources(target)); | ||
417 | sccsInSubGraph.add(sccs.find(source)); | ||
418 | sccsInSubGraph.add(sccs.find(target)); | ||
419 | Set<V> nodesInSubGraph = CollectionsFactory.createSet(); | ||
420 | |||
421 | for (V sccRoot : sccsInSubGraph) { | ||
422 | nodesInSubGraph.addAll(sccs.getPartition(sccRoot)); | ||
423 | } | ||
424 | |||
425 | return GraphHelper.constructPath(source, target, nodesInSubGraph, gds); | ||
426 | } | ||
427 | } | ||
428 | |||
429 | /** | ||
430 | * Return the SCCs from which the SCC represented by the root node is reachable. Note that an SCC can be present | ||
431 | * multiple times in the returned list (multiple edges between the two SCCs). | ||
432 | * | ||
433 | * @param root | ||
434 | * @return the list of reachable target SCCs | ||
435 | */ | ||
436 | private List<V> getSourceSCCsOfSCC(V root) { | ||
437 | List<V> sourceSCCs = new ArrayList<V>(); | ||
438 | |||
439 | for (V containedNode : this.sccs.getPartition(root)) { | ||
440 | IMemoryView<V> sourceNodes = this.gds.getSourceNodes(containedNode); | ||
441 | for (V source : sourceNodes.distinctValues()) { | ||
442 | sourceSCCs.add(this.sccs.find(source)); | ||
443 | } | ||
444 | } | ||
445 | |||
446 | return sourceSCCs; | ||
447 | } | ||
448 | |||
449 | /** | ||
450 | * Returns true if the SCC represented by the given root node has incoming edges in the reduced graph, | ||
451 | * false otherwise (if this SCC is a source in the reduced graph). | ||
452 | * | ||
453 | * @param root the root node of an SCC | ||
454 | * @return true if it has incoming edges, false otherwise | ||
455 | * @since 1.6 | ||
456 | */ | ||
457 | public boolean hasIncomingEdges(final V root) { | ||
458 | for (final V containedNode : this.sccs.getPartition(root)) { | ||
459 | final IMemoryView<V> sourceNodes = this.gds.getSourceNodes(containedNode); | ||
460 | for (final V source : sourceNodes.distinctValues()) { | ||
461 | final V otherRoot = this.sccs.find(source); | ||
462 | if (!Objects.equals(root, otherRoot)) { | ||
463 | return true; | ||
464 | } | ||
465 | } | ||
466 | } | ||
467 | return false; | ||
468 | } | ||
469 | |||
470 | /** | ||
471 | * Return the SCCs which are reachable from the SCC represented by the root node. Note that an SCC can be present | ||
472 | * multiple times in the returned list (multiple edges between the two SCCs). | ||
473 | * | ||
474 | * @param root | ||
475 | * @return the list of reachable target SCCs | ||
476 | */ | ||
477 | private List<V> getTargetSCCsOfSCC(V root) { | ||
478 | List<V> targetSCCs = new ArrayList<V>(); | ||
479 | |||
480 | for (V containedNode : this.sccs.getPartition(root)) { | ||
481 | IMemoryView<V> targetNodes = this.gds.getTargetNodes(containedNode); | ||
482 | for (V target : targetNodes.distinctValues()) { | ||
483 | targetSCCs.add(this.sccs.find(target)); | ||
484 | } | ||
485 | } | ||
486 | |||
487 | return targetSCCs; | ||
488 | } | ||
489 | |||
490 | /** | ||
491 | * Returns true if the SCC represented by the given root node has outgoing edges in the reduced graph, | ||
492 | * false otherwise (if this SCC is a sink in the reduced graph). | ||
493 | * | ||
494 | * @param root the root node of an SCC | ||
495 | * @return true if it has outgoing edges, false otherwise | ||
496 | * @since 1.6 | ||
497 | */ | ||
498 | public boolean hasOutgoingEdges(V root) { | ||
499 | for (final V containedNode : this.sccs.getPartition(root)) { | ||
500 | final IMemoryView<V> targetNodes = this.gds.getTargetNodes(containedNode); | ||
501 | for (final V target : targetNodes.distinctValues()) { | ||
502 | final V otherRoot = this.sccs.find(target); | ||
503 | if (!Objects.equals(root, otherRoot)) { | ||
504 | return true; | ||
505 | } | ||
506 | } | ||
507 | } | ||
508 | return false; | ||
509 | } | ||
510 | |||
511 | @Override | ||
512 | public void dispose() { | ||
513 | gds.detachObserver(this); | ||
514 | counting.dispose(); | ||
515 | } | ||
516 | |||
517 | /** | ||
518 | * Call this method to notify the observers of the transitive closure relation. The tuples used in the notification | ||
519 | * will be the Descartes product of the two sets given. | ||
520 | * | ||
521 | * @param sources | ||
522 | * the source nodes | ||
523 | * @param targets | ||
524 | * the target nodes | ||
525 | * @param direction | ||
526 | */ | ||
527 | protected void notifyTcObservers(Set<V> sources, Set<V> targets, Direction direction) { | ||
528 | for (V s : sources) { | ||
529 | for (V t : targets) { | ||
530 | notifyTcObservers(s, t, direction); | ||
531 | } | ||
532 | } | ||
533 | } | ||
534 | |||
535 | private void notifyTcObservers(V source, V target, Direction direction) { | ||
536 | for (ITcObserver<V> observer : observers) { | ||
537 | if (direction == Direction.INSERT) { | ||
538 | observer.tupleInserted(source, target); | ||
539 | } | ||
540 | if (direction == Direction.DELETE) { | ||
541 | observer.tupleDeleted(source, target); | ||
542 | } | ||
543 | } | ||
544 | } | ||
545 | |||
546 | /** | ||
547 | * Returns the node that is selected as the representative of the SCC containing the argument. | ||
548 | * @since 1.6 | ||
549 | */ | ||
550 | public V getRepresentative(V node) { | ||
551 | return sccs.find(node); | ||
552 | } | ||
553 | |||
554 | public Set<Tuple<V>> getTcRelation() { | ||
555 | Set<Tuple<V>> resultSet = new HashSet<Tuple<V>>(); | ||
556 | |||
557 | for (V sourceRoot : sccs.getPartitionHeads()) { | ||
558 | Set<V> sources = sccs.getPartition(sourceRoot); | ||
559 | if (sources.size() > 1 || GraphHelper.getEdgeCount(sources.iterator().next(), gds) == 1) { | ||
560 | for (V source : sources) { | ||
561 | for (V target : sources) { | ||
562 | resultSet.add(new Tuple<V>(source, target)); | ||
563 | } | ||
564 | } | ||
565 | } | ||
566 | |||
567 | Set<V> reachableTargets = counting.getAllReachableTargets(sourceRoot); | ||
568 | if (reachableTargets != null) { | ||
569 | for (V targetRoot : reachableTargets) { | ||
570 | for (V source : sources) { | ||
571 | for (V target : sccs.getPartition(targetRoot)) { | ||
572 | resultSet.add(new Tuple<V>(source, target)); | ||
573 | } | ||
574 | } | ||
575 | } | ||
576 | } | ||
577 | } | ||
578 | |||
579 | return resultSet; | ||
580 | } | ||
581 | |||
582 | public boolean isIsolated(V node) { | ||
583 | IMemoryView<V> targets = gds.getTargetNodes(node); | ||
584 | IMemoryView<V> sources = gds.getSourceNodes(node); | ||
585 | return targets.isEmpty() && sources.isEmpty(); | ||
586 | } | ||
587 | |||
588 | @Override | ||
589 | public IGraphPathFinder<V> getPathFinder() { | ||
590 | return new DFSPathFinder<V>(gds, this); | ||
591 | } | ||
592 | |||
593 | /** | ||
594 | * The graph of SCCs; each SCC is represented by its representative node (see {@link #getRepresentative(Object)}) | ||
595 | * @since 1.6 | ||
596 | */ | ||
597 | public Graph<V> getReducedGraph() { | ||
598 | return reducedGraph; | ||
599 | } | ||
600 | |||
601 | private static <V> Set<V> createSetNullTolerant(Set<V> initial) { | ||
602 | if (initial != null) | ||
603 | return CollectionsFactory.createSet(initial); | ||
604 | else | ||
605 | return CollectionsFactory.createSet(); | ||
606 | } | ||
607 | |||
608 | |||
609 | } | ||
diff --git a/subprojects/viatra-runtime-rete/src/main/java/tools/refinery/viatra/runtime/rete/itc/alg/misc/DFSPathFinder.java b/subprojects/viatra-runtime-rete/src/main/java/tools/refinery/viatra/runtime/rete/itc/alg/misc/DFSPathFinder.java new file mode 100644 index 00000000..2cec33a2 --- /dev/null +++ b/subprojects/viatra-runtime-rete/src/main/java/tools/refinery/viatra/runtime/rete/itc/alg/misc/DFSPathFinder.java | |||
@@ -0,0 +1,146 @@ | |||
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.rete.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.rete.itc.igraph.IGraphDataSource; | ||
20 | import tools.refinery.viatra.runtime.rete.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-rete/src/main/java/tools/refinery/viatra/runtime/rete/itc/alg/misc/Edge.java b/subprojects/viatra-runtime-rete/src/main/java/tools/refinery/viatra/runtime/rete/itc/alg/misc/Edge.java new file mode 100644 index 00000000..862c99b3 --- /dev/null +++ b/subprojects/viatra-runtime-rete/src/main/java/tools/refinery/viatra/runtime/rete/itc/alg/misc/Edge.java | |||
@@ -0,0 +1,38 @@ | |||
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.rete.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-rete/src/main/java/tools/refinery/viatra/runtime/rete/itc/alg/misc/GraphHelper.java b/subprojects/viatra-runtime-rete/src/main/java/tools/refinery/viatra/runtime/rete/itc/alg/misc/GraphHelper.java new file mode 100644 index 00000000..b79e4d45 --- /dev/null +++ b/subprojects/viatra-runtime-rete/src/main/java/tools/refinery/viatra/runtime/rete/itc/alg/misc/GraphHelper.java | |||
@@ -0,0 +1,169 @@ | |||
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.rete.itc.alg.misc; | ||
10 | |||
11 | import tools.refinery.viatra.runtime.matchers.util.IMemoryView; | ||
12 | import tools.refinery.viatra.runtime.rete.itc.graphimpl.Graph; | ||
13 | import tools.refinery.viatra.runtime.rete.itc.igraph.IBiDirectionalGraphDataSource; | ||
14 | import tools.refinery.viatra.runtime.rete.itc.igraph.IGraphDataSource; | ||
15 | |||
16 | import java.util.*; | ||
17 | import java.util.Map.Entry; | ||
18 | |||
19 | /** | ||
20 | * Utility class for graph related operations. | ||
21 | * | ||
22 | * @author Tamas Szabo | ||
23 | */ | ||
24 | public class GraphHelper { | ||
25 | |||
26 | private GraphHelper() {/*Utility class constructor*/} | ||
27 | |||
28 | /** | ||
29 | * Returns the subgraph from the given {@link IBiDirectionalGraphDataSource} which contains the given set of nodes. | ||
30 | * | ||
31 | * @param nodesInSubGraph | ||
32 | * the nodes that are present in the subgraph | ||
33 | * @param graphDataSource | ||
34 | * the graph data source for the original graph | ||
35 | * @return the subgraph associated to the given nodes | ||
36 | */ | ||
37 | public static <V> Graph<V> getSubGraph(Collection<V> nodesInSubGraph, | ||
38 | IBiDirectionalGraphDataSource<V> graphDataSource) { | ||
39 | Graph<V> g = new Graph<V>(); | ||
40 | if (nodesInSubGraph != null) { | ||
41 | for (V node : nodesInSubGraph) { | ||
42 | g.insertNode(node); | ||
43 | } | ||
44 | |||
45 | for (V node : nodesInSubGraph) { | ||
46 | IMemoryView<V> sources = graphDataSource.getSourceNodes(node); | ||
47 | for (Entry<V, Integer> entry : sources.entriesWithMultiplicities()) { | ||
48 | for (int i = 0; i < entry.getValue(); i++) { | ||
49 | V s = entry.getKey(); | ||
50 | if (nodesInSubGraph.contains(s)) { | ||
51 | g.insertEdge(s, node); | ||
52 | } | ||
53 | } | ||
54 | } | ||
55 | } | ||
56 | } | ||
57 | |||
58 | return g; | ||
59 | } | ||
60 | |||
61 | /** | ||
62 | * Constructs a path between source and target in the given graph. Both the {@link IGraphDataSource} and the set of | ||
63 | * nodes are used, this way it is possible to construct a path in a given subgraph. | ||
64 | * | ||
65 | * The returned {@link List} contains the nodes along the path (this means that there is an edge in the graph | ||
66 | * between two consecutive nodes). A self loop (one edge) is indicated with the source node being present two times | ||
67 | * in the returned {@link List}. | ||
68 | * | ||
69 | * @param source | ||
70 | * the source node | ||
71 | * @param target | ||
72 | * the target node | ||
73 | * @param nodesInGraph | ||
74 | * the nodes that are present in the subgraph | ||
75 | * @param graphDataSource | ||
76 | * the graph data source | ||
77 | * @return the path between the two nodes | ||
78 | */ | ||
79 | public static <V> List<V> constructPath(V source, V target, Set<V> nodesInGraph, | ||
80 | IGraphDataSource<V> graphDataSource) { | ||
81 | Set<V> visitedNodes = new HashSet<V>(); | ||
82 | List<V> path = new ArrayList<V>(); | ||
83 | |||
84 | visitedNodes.add(source); | ||
85 | path.add(source); | ||
86 | V act = source; | ||
87 | |||
88 | // if source and target are the same node | ||
89 | if (source.equals(target) && graphDataSource.getTargetNodes(source).containsNonZero(target)) { | ||
90 | // the node will be present in the path two times | ||
91 | path.add(source); | ||
92 | return path; | ||
93 | } else { | ||
94 | while (act != null) { | ||
95 | V nextNode = getNextNodeToVisit(act, graphDataSource, nodesInGraph, visitedNodes); | ||
96 | if (nextNode == null && path.size() > 1) { | ||
97 | // needs to backtrack along path | ||
98 | // remove the last element in the path because we can't go | ||
99 | // anywhere from there | ||
100 | path.remove(path.size() - 1); | ||
101 | while (nextNode == null && path.size() > 0) { | ||
102 | V lastPathElement = path.get(path.size() - 1); | ||
103 | nextNode = getNextNodeToVisit(lastPathElement, graphDataSource, nodesInGraph, visitedNodes); | ||
104 | if (nextNode == null) { | ||
105 | path.remove(path.size() - 1); | ||
106 | } | ||
107 | } | ||
108 | } | ||
109 | |||
110 | if (nextNode != null) { | ||
111 | visitedNodes.add(nextNode); | ||
112 | path.add(nextNode); | ||
113 | if (nextNode.equals(target)) { | ||
114 | return path; | ||
115 | } | ||
116 | } | ||
117 | act = nextNode; | ||
118 | } | ||
119 | return null; | ||
120 | } | ||
121 | } | ||
122 | |||
123 | private static <V> V getNextNodeToVisit(V act, IGraphDataSource<V> graphDataSource, Set<V> nodesInSubGraph, | ||
124 | Set<V> visitedNodes) { | ||
125 | IMemoryView<V> targetNodes = graphDataSource.getTargetNodes(act); | ||
126 | for (Entry<V, Integer> entry : targetNodes.entriesWithMultiplicities()) { | ||
127 | for (int i = 0; i < entry.getValue(); i++) { | ||
128 | V node = entry.getKey(); | ||
129 | if (nodesInSubGraph.contains(node) && !visitedNodes.contains(node)) { | ||
130 | return node; | ||
131 | } | ||
132 | } | ||
133 | } | ||
134 | return null; | ||
135 | } | ||
136 | |||
137 | /** | ||
138 | * Returns the number of self-loop edges for the given node. | ||
139 | * | ||
140 | * @param node | ||
141 | * the node | ||
142 | * @param graphDataSource | ||
143 | * the graph data source | ||
144 | * @return the number of self-loop edges | ||
145 | */ | ||
146 | public static <V> int getEdgeCount(V node, IGraphDataSource<V> graphDataSource) { | ||
147 | return getEdgeCount(node, node, graphDataSource); | ||
148 | } | ||
149 | |||
150 | /** | ||
151 | * Returns the number of edges between the given source and target nodes. | ||
152 | * | ||
153 | * @param source | ||
154 | * the source node | ||
155 | * @param target | ||
156 | * the target node | ||
157 | * @param graphDataSource | ||
158 | * the graph data source | ||
159 | * @return the number of parallel edges between the two nodes | ||
160 | */ | ||
161 | public static <V> int getEdgeCount(V source, V target, IGraphDataSource<V> graphDataSource) { | ||
162 | Integer count = graphDataSource.getTargetNodes(source).getCount(target); | ||
163 | if (count == null) { | ||
164 | return 0; | ||
165 | } else { | ||
166 | return count; | ||
167 | } | ||
168 | } | ||
169 | } | ||
diff --git a/subprojects/viatra-runtime-rete/src/main/java/tools/refinery/viatra/runtime/rete/itc/alg/misc/IGraphPathFinder.java b/subprojects/viatra-runtime-rete/src/main/java/tools/refinery/viatra/runtime/rete/itc/alg/misc/IGraphPathFinder.java new file mode 100644 index 00000000..624f9f7d --- /dev/null +++ b/subprojects/viatra-runtime-rete/src/main/java/tools/refinery/viatra/runtime/rete/itc/alg/misc/IGraphPathFinder.java | |||
@@ -0,0 +1,67 @@ | |||
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.rete.itc.alg.misc; | ||
10 | |||
11 | import java.util.Deque; | ||
12 | import java.util.Set; | ||
13 | |||
14 | import tools.refinery.viatra.runtime.rete.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 | } | ||
diff --git a/subprojects/viatra-runtime-rete/src/main/java/tools/refinery/viatra/runtime/rete/itc/alg/misc/ITcRelation.java b/subprojects/viatra-runtime-rete/src/main/java/tools/refinery/viatra/runtime/rete/itc/alg/misc/ITcRelation.java new file mode 100644 index 00000000..9fd85ae1 --- /dev/null +++ b/subprojects/viatra-runtime-rete/src/main/java/tools/refinery/viatra/runtime/rete/itc/alg/misc/ITcRelation.java | |||
@@ -0,0 +1,31 @@ | |||
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.rete.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-rete/src/main/java/tools/refinery/viatra/runtime/rete/itc/alg/misc/Tuple.java b/subprojects/viatra-runtime-rete/src/main/java/tools/refinery/viatra/runtime/rete/itc/alg/misc/Tuple.java new file mode 100644 index 00000000..84c79dcf --- /dev/null +++ b/subprojects/viatra-runtime-rete/src/main/java/tools/refinery/viatra/runtime/rete/itc/alg/misc/Tuple.java | |||
@@ -0,0 +1,60 @@ | |||
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.rete.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-rete/src/main/java/tools/refinery/viatra/runtime/rete/itc/alg/misc/bfs/BFS.java b/subprojects/viatra-runtime-rete/src/main/java/tools/refinery/viatra/runtime/rete/itc/alg/misc/bfs/BFS.java new file mode 100644 index 00000000..22ce8962 --- /dev/null +++ b/subprojects/viatra-runtime-rete/src/main/java/tools/refinery/viatra/runtime/rete/itc/alg/misc/bfs/BFS.java | |||
@@ -0,0 +1,148 @@ | |||
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.rete.itc.alg.misc.bfs; | ||
11 | |||
12 | import tools.refinery.viatra.runtime.rete.itc.igraph.IBiDirectionalGraphDataSource; | ||
13 | import tools.refinery.viatra.runtime.rete.itc.igraph.IGraphDataSource; | ||
14 | |||
15 | import java.util.*; | ||
16 | |||
17 | public class BFS<V> { | ||
18 | |||
19 | private BFS() {/*Utility class constructor*/} | ||
20 | |||
21 | /** | ||
22 | * Performs a breadth first search on the given graph to determine whether source is reachable from target. | ||
23 | * | ||
24 | * @param <V> | ||
25 | * the type parameter of the nodes in the graph | ||
26 | * @param source | ||
27 | * the source node | ||
28 | * @param target | ||
29 | * the target node | ||
30 | * @param graph | ||
31 | * the graph data source | ||
32 | * @return true if source is reachable from target, false otherwise | ||
33 | */ | ||
34 | public static <V> boolean isReachable(V source, V target, IGraphDataSource<V> graph) { | ||
35 | Deque<V> nodeQueue = new ArrayDeque<V>(); | ||
36 | Set<V> visited = new HashSet<V>(); | ||
37 | |||
38 | nodeQueue.add(source); | ||
39 | visited.add(source); | ||
40 | |||
41 | boolean ret = _isReachable(target, graph, nodeQueue, visited); | ||
42 | return ret; | ||
43 | } | ||
44 | |||
45 | private static <V> boolean _isReachable(V target, IGraphDataSource<V> graph, Deque<V> nodeQueue, Set<V> visited) { | ||
46 | |||
47 | while (!nodeQueue.isEmpty()) { | ||
48 | V node = nodeQueue.removeFirst(); | ||
49 | for (V t : graph.getTargetNodes(node).distinctValues()){ | ||
50 | if (t.equals(target)) { | ||
51 | return true; | ||
52 | } | ||
53 | if (!visited.contains(t)) { | ||
54 | visited.add(t); | ||
55 | nodeQueue.addLast(t); | ||
56 | } | ||
57 | } | ||
58 | } | ||
59 | return false; | ||
60 | } | ||
61 | |||
62 | public static <V> Set<V> reachableSources(IBiDirectionalGraphDataSource<V> graph, V target) { | ||
63 | Set<V> retSet = new HashSet<V>(); | ||
64 | retSet.add(target); | ||
65 | Deque<V> nodeQueue = new ArrayDeque<V>(); | ||
66 | nodeQueue.add(target); | ||
67 | |||
68 | _reachableSources(graph, nodeQueue, retSet); | ||
69 | |||
70 | return retSet; | ||
71 | } | ||
72 | |||
73 | private static <V> void _reachableSources(IBiDirectionalGraphDataSource<V> graph, Deque<V> nodeQueue, | ||
74 | Set<V> retSet) { | ||
75 | while (!nodeQueue.isEmpty()) { | ||
76 | V node = nodeQueue.removeFirst(); | ||
77 | for (V _node : graph.getSourceNodes(node).distinctValues()) { | ||
78 | if (!retSet.contains(_node)) { | ||
79 | retSet.add(_node); | ||
80 | nodeQueue.addLast(_node); | ||
81 | } | ||
82 | } | ||
83 | } | ||
84 | } | ||
85 | |||
86 | public static <V> Set<V> reachableTargets(IGraphDataSource<V> graph, V source) { | ||
87 | Set<V> retSet = new HashSet<V>(); | ||
88 | retSet.add(source); | ||
89 | Deque<V> nodeQueue = new ArrayDeque<V>(); | ||
90 | nodeQueue.add(source); | ||
91 | |||
92 | _reachableTargets(graph, nodeQueue, retSet); | ||
93 | |||
94 | return retSet; | ||
95 | } | ||
96 | |||
97 | private static <V> void _reachableTargets(IGraphDataSource<V> graph, Deque<V> nodeQueue, Set<V> retSet) { | ||
98 | while (!nodeQueue.isEmpty()) { | ||
99 | V node = nodeQueue.removeFirst(); | ||
100 | |||
101 | for (V _node : graph.getTargetNodes(node).distinctValues()) { | ||
102 | |||
103 | if (!retSet.contains(_node)) { | ||
104 | retSet.add(_node); | ||
105 | nodeQueue.addLast(_node); | ||
106 | } | ||
107 | } | ||
108 | } | ||
109 | } | ||
110 | |||
111 | /** | ||
112 | * Performs a breadth first search on the given graph and collects all the nodes along the path from source to | ||
113 | * target if such path exists. | ||
114 | * | ||
115 | * @param <V> | ||
116 | * the type parameter of the nodes in the graph | ||
117 | * @param source | ||
118 | * the source node | ||
119 | * @param target | ||
120 | * the target node | ||
121 | * @param graph | ||
122 | * the graph data source | ||
123 | * @return the set of nodes along the path | ||
124 | */ | ||
125 | public static <V> Set<V> collectNodesAlongPath(V source, V target, IGraphDataSource<V> graph) { | ||
126 | Set<V> path = new HashSet<V>(); | ||
127 | _collectNodesAlongPath(source, target, graph, path); | ||
128 | return path; | ||
129 | } | ||
130 | |||
131 | private static <V> boolean _collectNodesAlongPath(V node, V target, IGraphDataSource<V> graph, Set<V> path) { | ||
132 | |||
133 | boolean res = false; | ||
134 | |||
135 | // end recursion | ||
136 | if (node.equals(target)) { | ||
137 | path.add(node); | ||
138 | return true; | ||
139 | } else { | ||
140 | for (V _nodeT : graph.getTargetNodes(node).distinctValues()) { | ||
141 | res = (_collectNodesAlongPath(_nodeT, target, graph, path)) || res; | ||
142 | } | ||
143 | if (res) | ||
144 | path.add(node); | ||
145 | return res; | ||
146 | } | ||
147 | } | ||
148 | } | ||
diff --git a/subprojects/viatra-runtime-rete/src/main/java/tools/refinery/viatra/runtime/rete/itc/alg/misc/scc/PKAlg.java b/subprojects/viatra-runtime-rete/src/main/java/tools/refinery/viatra/runtime/rete/itc/alg/misc/scc/PKAlg.java new file mode 100644 index 00000000..892d048e --- /dev/null +++ b/subprojects/viatra-runtime-rete/src/main/java/tools/refinery/viatra/runtime/rete/itc/alg/misc/scc/PKAlg.java | |||
@@ -0,0 +1,179 @@ | |||
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.rete.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.rete.itc.igraph.IBiDirectionalGraphDataSource; | ||
19 | import tools.refinery.viatra.runtime.rete.itc.igraph.IBiDirectionalWrapper; | ||
20 | import tools.refinery.viatra.runtime.rete.itc.igraph.IGraphDataSource; | ||
21 | import tools.refinery.viatra.runtime.rete.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-rete/src/main/java/tools/refinery/viatra/runtime/rete/itc/alg/misc/scc/SCC.java b/subprojects/viatra-runtime-rete/src/main/java/tools/refinery/viatra/runtime/rete/itc/alg/misc/scc/SCC.java new file mode 100644 index 00000000..de070839 --- /dev/null +++ b/subprojects/viatra-runtime-rete/src/main/java/tools/refinery/viatra/runtime/rete/itc/alg/misc/scc/SCC.java | |||
@@ -0,0 +1,143 @@ | |||
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.rete.itc.alg.misc.scc; | ||
11 | |||
12 | import tools.refinery.viatra.runtime.matchers.util.CollectionsFactory; | ||
13 | import tools.refinery.viatra.runtime.rete.itc.igraph.IGraphDataSource; | ||
14 | |||
15 | import java.util.*; | ||
16 | |||
17 | /** | ||
18 | * Efficient algorithms to compute the Strongly Connected Components in a directed graph. | ||
19 | * | ||
20 | * @author Tamas Szabo | ||
21 | * | ||
22 | * @param <V> | ||
23 | * the type parameter of the nodes in the graph | ||
24 | */ | ||
25 | public class SCC<V> { | ||
26 | |||
27 | private SCC() {/*Utility class constructor*/} | ||
28 | |||
29 | public static long sccId = 0; | ||
30 | |||
31 | /** | ||
32 | * Computes the SCCs for the given graph and returns them as a multiset. (Iterative version of Tarjan's algorithm) | ||
33 | * | ||
34 | * @param g | ||
35 | * the directed graph data source | ||
36 | * @return the set of SCCs | ||
37 | */ | ||
38 | public static <V> SCCResult<V> computeSCC(IGraphDataSource<V> g) { | ||
39 | int index = 0; | ||
40 | Set<Set<V>> ret = new HashSet<Set<V>>(); | ||
41 | |||
42 | // stores the lowlink and index information for the given node | ||
43 | Map<V, SCCProperty> nodeMap = CollectionsFactory.createMap(); | ||
44 | |||
45 | // stores all target nodes of a given node - the list will be modified | ||
46 | Map<V, Set<V>> targetNodeMap = CollectionsFactory.createMap(); | ||
47 | |||
48 | // stores those target nodes for a given node which have not been visited | ||
49 | Map<V, Set<V>> notVisitedMap = CollectionsFactory.createMap(); | ||
50 | |||
51 | // stores the nodes during the traversal | ||
52 | Deque<V> nodeStack = new ArrayDeque<V>(); | ||
53 | |||
54 | // stores the nodes which belong to an scc (there can be many sccs in the stack at the same time) | ||
55 | Deque<V> sccStack = new ArrayDeque<V>(); | ||
56 | |||
57 | boolean sink = false, finishedTraversal = true; | ||
58 | |||
59 | // initialize all nodes with 0 index and 0 lowlink | ||
60 | Set<V> allNodes = g.getAllNodes(); | ||
61 | for (V n : allNodes) { | ||
62 | nodeMap.put(n, new SCCProperty(0, 0)); | ||
63 | } | ||
64 | |||
65 | for (V n : allNodes) { | ||
66 | // if the node has not been visited yet | ||
67 | if (nodeMap.get(n).getIndex() == 0) { | ||
68 | nodeStack.push(n); | ||
69 | |||
70 | while (!nodeStack.isEmpty()) { | ||
71 | V currentNode = nodeStack.peekLast(); | ||
72 | sink = false; | ||
73 | finishedTraversal = false; | ||
74 | SCCProperty prop = nodeMap.get(currentNode); | ||
75 | |||
76 | if (nodeMap.get(currentNode).getIndex() == 0) { | ||
77 | index++; | ||
78 | sccStack.addLast(currentNode); | ||
79 | prop.setIndex(index); | ||
80 | prop.setLowlink(index); | ||
81 | |||
82 | notVisitedMap.put(currentNode, new HashSet<V>()); | ||
83 | |||
84 | // storing the target nodes of the actual node | ||
85 | if (g.getTargetNodes(currentNode) != null) { | ||
86 | Set<V> targets = g.getTargetNodes(currentNode).distinctValues(); | ||
87 | targetNodeMap.put(currentNode, CollectionsFactory.createSet(targets)); | ||
88 | } | ||
89 | } | ||
90 | |||
91 | if (targetNodeMap.get(currentNode) != null) { | ||
92 | |||
93 | // remove node from stack, the exploration of its children has finished | ||
94 | if (targetNodeMap.get(currentNode).size() == 0) { | ||
95 | targetNodeMap.remove(currentNode); | ||
96 | |||
97 | nodeStack.removeLast(); | ||
98 | |||
99 | for (V targetNode : g.getTargetNodes(currentNode).distinctValues()) { | ||
100 | if (notVisitedMap.get(currentNode).contains(targetNode)) { | ||
101 | prop.setLowlink(Math.min(prop.getLowlink(), nodeMap.get(targetNode).getLowlink())); | ||
102 | } else if (sccStack.contains(targetNode)) { | ||
103 | prop.setLowlink(Math.min(prop.getLowlink(), nodeMap.get(targetNode).getIndex())); | ||
104 | } | ||
105 | } | ||
106 | |||
107 | finishedTraversal = true; | ||
108 | } else { | ||
109 | V targetNode = targetNodeMap.get(currentNode).iterator().next(); | ||
110 | targetNodeMap.get(currentNode).remove(targetNode); | ||
111 | // if the targetNode has not yet been visited push it to the stack | ||
112 | // and mark it in the notVisitedMap | ||
113 | if (nodeMap.get(targetNode).getIndex() == 0) { | ||
114 | notVisitedMap.get(currentNode).add(targetNode); | ||
115 | nodeStack.addLast(targetNode); | ||
116 | } | ||
117 | } | ||
118 | } | ||
119 | // if currentNode has no target nodes | ||
120 | else { | ||
121 | nodeStack.removeLast(); | ||
122 | sink = true; | ||
123 | } | ||
124 | |||
125 | // create scc if node is a sink or an scc has been found | ||
126 | if ((sink || finishedTraversal) && (prop.getLowlink() == prop.getIndex())) { | ||
127 | Set<V> sc = new HashSet<V>(); | ||
128 | V targetNode = null; | ||
129 | |||
130 | do { | ||
131 | targetNode = sccStack.removeLast(); | ||
132 | sc.add(targetNode); | ||
133 | } while (!targetNode.equals(currentNode)); | ||
134 | |||
135 | ret.add(sc); | ||
136 | } | ||
137 | } | ||
138 | } | ||
139 | } | ||
140 | |||
141 | return new SCCResult<V>(ret, g); | ||
142 | } | ||
143 | } | ||
diff --git a/subprojects/viatra-runtime-rete/src/main/java/tools/refinery/viatra/runtime/rete/itc/alg/misc/scc/SCCProperty.java b/subprojects/viatra-runtime-rete/src/main/java/tools/refinery/viatra/runtime/rete/itc/alg/misc/scc/SCCProperty.java new file mode 100644 index 00000000..51ee834e --- /dev/null +++ b/subprojects/viatra-runtime-rete/src/main/java/tools/refinery/viatra/runtime/rete/itc/alg/misc/scc/SCCProperty.java | |||
@@ -0,0 +1,37 @@ | |||
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.rete.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-rete/src/main/java/tools/refinery/viatra/runtime/rete/itc/alg/misc/scc/SCCResult.java b/subprojects/viatra-runtime-rete/src/main/java/tools/refinery/viatra/runtime/rete/itc/alg/misc/scc/SCCResult.java new file mode 100644 index 00000000..2e511fd6 --- /dev/null +++ b/subprojects/viatra-runtime-rete/src/main/java/tools/refinery/viatra/runtime/rete/itc/alg/misc/scc/SCCResult.java | |||
@@ -0,0 +1,81 @@ | |||
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.rete.itc.alg.misc.scc; | ||
11 | |||
12 | import java.util.Map.Entry; | ||
13 | import java.util.Set; | ||
14 | |||
15 | import tools.refinery.viatra.runtime.rete.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-rete/src/main/java/tools/refinery/viatra/runtime/rete/itc/alg/misc/topsort/TopologicalSorting.java b/subprojects/viatra-runtime-rete/src/main/java/tools/refinery/viatra/runtime/rete/itc/alg/misc/topsort/TopologicalSorting.java new file mode 100644 index 00000000..89be6804 --- /dev/null +++ b/subprojects/viatra-runtime-rete/src/main/java/tools/refinery/viatra/runtime/rete/itc/alg/misc/topsort/TopologicalSorting.java | |||
@@ -0,0 +1,73 @@ | |||
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.rete.itc.alg.misc.topsort; | ||
11 | |||
12 | import tools.refinery.viatra.runtime.rete.itc.igraph.IGraphDataSource; | ||
13 | |||
14 | import java.util.*; | ||
15 | |||
16 | /** | ||
17 | * @since 1.6 | ||
18 | */ | ||
19 | public class TopologicalSorting { | ||
20 | |||
21 | private TopologicalSorting() {/*Utility class constructor*/} | ||
22 | |||
23 | private static final class Pair<T> { | ||
24 | public T element; | ||
25 | public boolean isParent; | ||
26 | |||
27 | public Pair(final T element, final boolean isParent) { | ||
28 | this.element = element; | ||
29 | this.isParent = isParent; | ||
30 | } | ||
31 | } | ||
32 | |||
33 | /** | ||
34 | * Returns a topological ordering for the given graph data source. | ||
35 | * Output format: if there is an a -> b (transitive) reachability, then node <code>a</code> will come before node <code>b</code> in the resulting list. | ||
36 | * | ||
37 | * @param gds the graph data source | ||
38 | * @return a topological ordering | ||
39 | */ | ||
40 | public static <T> List<T> compute(final IGraphDataSource<T> gds) { | ||
41 | final Set<T> visited = new HashSet<T>(); | ||
42 | final LinkedList<T> result = new LinkedList<T>(); | ||
43 | final Deque<Pair<T>> dfsStack = new ArrayDeque<Pair<T>>(); | ||
44 | |||
45 | for (final T node : gds.getAllNodes()) { | ||
46 | if (!visited.contains(node)) { | ||
47 | dfsStack.addLast(new Pair<T>(node, false)); | ||
48 | } | ||
49 | |||
50 | while (!dfsStack.isEmpty()) { | ||
51 | final Pair<T> head = dfsStack.removeLast(); | ||
52 | final T source = head.element; | ||
53 | |||
54 | if (head.isParent) { | ||
55 | // we have already seen source, push it to the resulting stack | ||
56 | result.addFirst(source); | ||
57 | } else { | ||
58 | // first time we see source, continue with its children | ||
59 | visited.add(source); | ||
60 | dfsStack.addLast(new Pair<T>(source, true)); | ||
61 | |||
62 | for (final T target : gds.getTargetNodes(source).distinctValues()) { | ||
63 | if (!visited.contains(target)) { | ||
64 | dfsStack.addLast(new Pair<T>(target, false)); | ||
65 | } | ||
66 | } | ||
67 | } | ||
68 | } | ||
69 | } | ||
70 | |||
71 | return result; | ||
72 | } | ||
73 | } | ||
diff --git a/subprojects/viatra-runtime-rete/src/main/java/tools/refinery/viatra/runtime/rete/itc/alg/representative/RepresentativeElectionAlgorithm.java b/subprojects/viatra-runtime-rete/src/main/java/tools/refinery/viatra/runtime/rete/itc/alg/representative/RepresentativeElectionAlgorithm.java new file mode 100644 index 00000000..794dabc0 --- /dev/null +++ b/subprojects/viatra-runtime-rete/src/main/java/tools/refinery/viatra/runtime/rete/itc/alg/representative/RepresentativeElectionAlgorithm.java | |||
@@ -0,0 +1,174 @@ | |||
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.rete.itc.alg.representative; | ||
7 | |||
8 | import tools.refinery.viatra.runtime.rete.itc.graphimpl.Graph; | ||
9 | import tools.refinery.viatra.runtime.rete.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(Set<Object> toMerge) { | ||
49 | if (toMerge.isEmpty()) { | ||
50 | return; | ||
51 | } | ||
52 | var representativesToMerge = new HashSet<>(); | ||
53 | Object bestRepresentative = null; | ||
54 | Set<Object> bestSet = null; | ||
55 | for (var object : toMerge) { | ||
56 | var representative = getRepresentative(object); | ||
57 | if (representativesToMerge.add(representative)) { | ||
58 | var component = getComponent(representative); | ||
59 | if (bestSet == null || bestSet.size() < component.size()) { | ||
60 | bestRepresentative = representative; | ||
61 | bestSet = component; | ||
62 | } | ||
63 | } | ||
64 | } | ||
65 | if (bestRepresentative == null) { | ||
66 | throw new AssertionError("Could not determine best representative"); | ||
67 | } | ||
68 | for (var representative : representativesToMerge) { | ||
69 | if (!bestRepresentative.equals(representative)) { | ||
70 | components.remove(representative); | ||
71 | } | ||
72 | } | ||
73 | components.put(bestRepresentative, toMerge); | ||
74 | for (var object : toMerge) { | ||
75 | var previousRepresentative = representatives.put(object, bestRepresentative); | ||
76 | if (!bestSet.contains(object)) { | ||
77 | notifyToObservers(object, previousRepresentative, bestRepresentative); | ||
78 | } | ||
79 | } | ||
80 | } | ||
81 | |||
82 | protected void merge(Object leftRepresentative, Object rightRepresentative) { | ||
83 | if (leftRepresentative.equals(rightRepresentative)) { | ||
84 | return; | ||
85 | } | ||
86 | var leftSet = getComponent(leftRepresentative); | ||
87 | var rightSet = getComponent(rightRepresentative); | ||
88 | if (leftSet.size() < rightSet.size()) { | ||
89 | merge(rightRepresentative, rightSet, leftRepresentative, leftSet); | ||
90 | } else { | ||
91 | merge(leftRepresentative, leftSet, rightRepresentative, rightSet); | ||
92 | } | ||
93 | } | ||
94 | |||
95 | private void merge(Object preservedRepresentative, Set<Object> preservedSet, Object removedRepresentative, | ||
96 | Set<Object> removedSet) { | ||
97 | components.remove(removedRepresentative); | ||
98 | for (var node : removedSet) { | ||
99 | representatives.put(node, preservedRepresentative); | ||
100 | preservedSet.add(node); | ||
101 | notifyToObservers(node, removedRepresentative, preservedRepresentative); | ||
102 | } | ||
103 | } | ||
104 | |||
105 | protected void assignNewRepresentative(Object oldRepresentative, Set<Object> set) { | ||
106 | var iterator = set.iterator(); | ||
107 | if (!iterator.hasNext()) { | ||
108 | return; | ||
109 | } | ||
110 | var newRepresentative = iterator.next(); | ||
111 | components.put(newRepresentative, set); | ||
112 | for (var node : set) { | ||
113 | var oldRepresentativeOfNode = representatives.put(node, newRepresentative); | ||
114 | if (!oldRepresentative.equals(oldRepresentativeOfNode)) { | ||
115 | throw new IllegalArgumentException("Node %s was not represented by %s but by %s" | ||
116 | .formatted(node, oldRepresentative, oldRepresentativeOfNode)); | ||
117 | } | ||
118 | notifyToObservers(node, oldRepresentative, newRepresentative); | ||
119 | } | ||
120 | } | ||
121 | |||
122 | public void setObserver(RepresentativeObserver observer) { | ||
123 | this.observer = observer; | ||
124 | } | ||
125 | |||
126 | public Map<Object, Set<Object>> getComponents() { | ||
127 | return components; | ||
128 | } | ||
129 | |||
130 | public Object getRepresentative(Object node) { | ||
131 | return representatives.get(node); | ||
132 | } | ||
133 | |||
134 | public Set<Object> getComponent(Object representative) { | ||
135 | return components.get(representative); | ||
136 | } | ||
137 | |||
138 | public void dispose() { | ||
139 | graph.detachObserver(this); | ||
140 | } | ||
141 | |||
142 | @Override | ||
143 | public void nodeInserted(Object n) { | ||
144 | var component = new HashSet<>(1); | ||
145 | component.add(n); | ||
146 | initializeSet(component); | ||
147 | notifyToObservers(n, n, Direction.INSERT); | ||
148 | } | ||
149 | |||
150 | @Override | ||
151 | public void nodeDeleted(Object n) { | ||
152 | var representative = representatives.remove(n); | ||
153 | if (!representative.equals(n)) { | ||
154 | throw new IllegalStateException("Trying to delete node with dangling edges"); | ||
155 | } | ||
156 | components.remove(representative); | ||
157 | notifyToObservers(n, representative, Direction.DELETE); | ||
158 | } | ||
159 | |||
160 | protected void notifyToObservers(Object node, Object oldRepresentative, Object newRepresentative) { | ||
161 | notifyToObservers(node, oldRepresentative, Direction.DELETE); | ||
162 | notifyToObservers(node, newRepresentative, Direction.INSERT); | ||
163 | } | ||
164 | |||
165 | protected void notifyToObservers(Object node, Object representative, Direction direction) { | ||
166 | if (observer != null) { | ||
167 | observer.tupleChanged(node, representative, direction); | ||
168 | } | ||
169 | } | ||
170 | |||
171 | public interface Factory { | ||
172 | RepresentativeElectionAlgorithm create(Graph<Object> graph); | ||
173 | } | ||
174 | } | ||
diff --git a/subprojects/viatra-runtime-rete/src/main/java/tools/refinery/viatra/runtime/rete/itc/alg/representative/RepresentativeObserver.java b/subprojects/viatra-runtime-rete/src/main/java/tools/refinery/viatra/runtime/rete/itc/alg/representative/RepresentativeObserver.java new file mode 100644 index 00000000..6b772fa8 --- /dev/null +++ b/subprojects/viatra-runtime-rete/src/main/java/tools/refinery/viatra/runtime/rete/itc/alg/representative/RepresentativeObserver.java | |||
@@ -0,0 +1,12 @@ | |||
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.rete.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-rete/src/main/java/tools/refinery/viatra/runtime/rete/itc/alg/representative/StronglyConnectedComponentAlgorithm.java b/subprojects/viatra-runtime-rete/src/main/java/tools/refinery/viatra/runtime/rete/itc/alg/representative/StronglyConnectedComponentAlgorithm.java new file mode 100644 index 00000000..0463301b --- /dev/null +++ b/subprojects/viatra-runtime-rete/src/main/java/tools/refinery/viatra/runtime/rete/itc/alg/representative/StronglyConnectedComponentAlgorithm.java | |||
@@ -0,0 +1,69 @@ | |||
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.rete.itc.alg.representative; | ||
7 | |||
8 | import tools.refinery.viatra.runtime.rete.itc.alg.misc.GraphHelper; | ||
9 | import tools.refinery.viatra.runtime.rete.itc.alg.misc.bfs.BFS; | ||
10 | import tools.refinery.viatra.runtime.rete.itc.alg.misc.scc.SCC; | ||
11 | import tools.refinery.viatra.runtime.rete.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 | var sources = BFS.reachableSources(graph, target); | ||
39 | var targets = BFS.reachableTargets(graph, source); | ||
40 | sources.retainAll(targets); | ||
41 | merge(sources); | ||
42 | } | ||
43 | } | ||
44 | |||
45 | @Override | ||
46 | public void edgeDeleted(Object source, Object target) { | ||
47 | var sourceRoot = getRepresentative(source); | ||
48 | var targetRoot = getRepresentative(target); | ||
49 | if (!sourceRoot.equals(targetRoot)) { | ||
50 | // New edge does not change strongly connected components. | ||
51 | return; | ||
52 | } | ||
53 | var component = GraphHelper.getSubGraph(getComponent(sourceRoot), graph); | ||
54 | if (!BFS.isReachable(source, target, component)) { | ||
55 | var newSCCs = SCC.computeSCC(component).getSccs(); | ||
56 | split(sourceRoot, newSCCs); | ||
57 | } | ||
58 | } | ||
59 | |||
60 | private void split(Object preservedRepresentative, Collection<? extends Set<Object>> sets) { | ||
61 | for (var set : sets) { | ||
62 | if (set.contains(preservedRepresentative)) { | ||
63 | components.put(preservedRepresentative, set); | ||
64 | } else { | ||
65 | assignNewRepresentative(preservedRepresentative, set); | ||
66 | } | ||
67 | } | ||
68 | } | ||
69 | } | ||
diff --git a/subprojects/viatra-runtime-rete/src/main/java/tools/refinery/viatra/runtime/rete/itc/alg/representative/WeaklyConnectedComponentAlgorithm.java b/subprojects/viatra-runtime-rete/src/main/java/tools/refinery/viatra/runtime/rete/itc/alg/representative/WeaklyConnectedComponentAlgorithm.java new file mode 100644 index 00000000..704f0235 --- /dev/null +++ b/subprojects/viatra-runtime-rete/src/main/java/tools/refinery/viatra/runtime/rete/itc/alg/representative/WeaklyConnectedComponentAlgorithm.java | |||
@@ -0,0 +1,85 @@ | |||
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.rete.itc.alg.representative; | ||
7 | |||
8 | import tools.refinery.viatra.runtime.rete.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-rete/src/main/java/tools/refinery/viatra/runtime/rete/itc/alg/util/CollectionHelper.java b/subprojects/viatra-runtime-rete/src/main/java/tools/refinery/viatra/runtime/rete/itc/alg/util/CollectionHelper.java new file mode 100644 index 00000000..6655be6d --- /dev/null +++ b/subprojects/viatra-runtime-rete/src/main/java/tools/refinery/viatra/runtime/rete/itc/alg/util/CollectionHelper.java | |||
@@ -0,0 +1,64 @@ | |||
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.rete.itc.alg.util; | ||
10 | |||
11 | import tools.refinery.viatra.runtime.matchers.util.CollectionsFactory; | ||
12 | |||
13 | import java.util.Set; | ||
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-rete/src/main/java/tools/refinery/viatra/runtime/rete/itc/graphimpl/DotGenerator.java b/subprojects/viatra-runtime-rete/src/main/java/tools/refinery/viatra/runtime/rete/itc/graphimpl/DotGenerator.java new file mode 100644 index 00000000..f7f6b5ed --- /dev/null +++ b/subprojects/viatra-runtime-rete/src/main/java/tools/refinery/viatra/runtime/rete/itc/graphimpl/DotGenerator.java | |||
@@ -0,0 +1,160 @@ | |||
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.rete.itc.graphimpl; | ||
10 | |||
11 | import tools.refinery.viatra.runtime.rete.itc.alg.misc.scc.SCC; | ||
12 | import tools.refinery.viatra.runtime.rete.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-rete/src/main/java/tools/refinery/viatra/runtime/rete/itc/graphimpl/Graph.java b/subprojects/viatra-runtime-rete/src/main/java/tools/refinery/viatra/runtime/rete/itc/graphimpl/Graph.java new file mode 100644 index 00000000..91604cb2 --- /dev/null +++ b/subprojects/viatra-runtime-rete/src/main/java/tools/refinery/viatra/runtime/rete/itc/graphimpl/Graph.java | |||
@@ -0,0 +1,185 @@ | |||
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.rete.itc.graphimpl; | ||
11 | |||
12 | import tools.refinery.viatra.runtime.rete.itc.igraph.IGraphDataSource; | ||
13 | import tools.refinery.viatra.runtime.rete.itc.igraph.IGraphObserver; | ||
14 | import tools.refinery.viatra.runtime.rete.itc.igraph.IBiDirectionalGraphDataSource; | ||
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-rete/src/main/java/tools/refinery/viatra/runtime/rete/itc/igraph/IBiDirectionalGraphDataSource.java b/subprojects/viatra-runtime-rete/src/main/java/tools/refinery/viatra/runtime/rete/itc/igraph/IBiDirectionalGraphDataSource.java new file mode 100644 index 00000000..4fcaa71f --- /dev/null +++ b/subprojects/viatra-runtime-rete/src/main/java/tools/refinery/viatra/runtime/rete/itc/igraph/IBiDirectionalGraphDataSource.java | |||
@@ -0,0 +1,37 @@ | |||
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.rete.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-rete/src/main/java/tools/refinery/viatra/runtime/rete/itc/igraph/IBiDirectionalWrapper.java b/subprojects/viatra-runtime-rete/src/main/java/tools/refinery/viatra/runtime/rete/itc/igraph/IBiDirectionalWrapper.java new file mode 100644 index 00000000..c4315ca2 --- /dev/null +++ b/subprojects/viatra-runtime-rete/src/main/java/tools/refinery/viatra/runtime/rete/itc/igraph/IBiDirectionalWrapper.java | |||
@@ -0,0 +1,110 @@ | |||
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.rete.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-rete/src/main/java/tools/refinery/viatra/runtime/rete/itc/igraph/IGraphDataSource.java b/subprojects/viatra-runtime-rete/src/main/java/tools/refinery/viatra/runtime/rete/itc/igraph/IGraphDataSource.java new file mode 100644 index 00000000..9159a692 --- /dev/null +++ b/subprojects/viatra-runtime-rete/src/main/java/tools/refinery/viatra/runtime/rete/itc/igraph/IGraphDataSource.java | |||
@@ -0,0 +1,70 @@ | |||
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.rete.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-rete/src/main/java/tools/refinery/viatra/runtime/rete/itc/igraph/IGraphObserver.java b/subprojects/viatra-runtime-rete/src/main/java/tools/refinery/viatra/runtime/rete/itc/igraph/IGraphObserver.java new file mode 100644 index 00000000..a282216d --- /dev/null +++ b/subprojects/viatra-runtime-rete/src/main/java/tools/refinery/viatra/runtime/rete/itc/igraph/IGraphObserver.java | |||
@@ -0,0 +1,55 @@ | |||
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.rete.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-rete/src/main/java/tools/refinery/viatra/runtime/rete/itc/igraph/ITcDataSource.java b/subprojects/viatra-runtime-rete/src/main/java/tools/refinery/viatra/runtime/rete/itc/igraph/ITcDataSource.java new file mode 100644 index 00000000..5ede600f --- /dev/null +++ b/subprojects/viatra-runtime-rete/src/main/java/tools/refinery/viatra/runtime/rete/itc/igraph/ITcDataSource.java | |||
@@ -0,0 +1,82 @@ | |||
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.rete.itc.igraph; | ||
11 | |||
12 | import java.util.Set; | ||
13 | |||
14 | import tools.refinery.viatra.runtime.rete.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-rete/src/main/java/tools/refinery/viatra/runtime/rete/itc/igraph/ITcObserver.java b/subprojects/viatra-runtime-rete/src/main/java/tools/refinery/viatra/runtime/rete/itc/igraph/ITcObserver.java new file mode 100644 index 00000000..74e0cb75 --- /dev/null +++ b/subprojects/viatra-runtime-rete/src/main/java/tools/refinery/viatra/runtime/rete/itc/igraph/ITcObserver.java | |||
@@ -0,0 +1,39 @@ | |||
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.rete.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 | } | ||