aboutsummaryrefslogtreecommitdiffstats
path: root/subprojects/viatra-runtime-base-itc/src/main/java/tools/refinery/viatra/runtime/base/itc/alg/dred/DRedAlg.java
diff options
context:
space:
mode:
Diffstat (limited to 'subprojects/viatra-runtime-base-itc/src/main/java/tools/refinery/viatra/runtime/base/itc/alg/dred/DRedAlg.java')
-rw-r--r--subprojects/viatra-runtime-base-itc/src/main/java/tools/refinery/viatra/runtime/base/itc/alg/dred/DRedAlg.java308
1 files changed, 0 insertions, 308 deletions
diff --git a/subprojects/viatra-runtime-base-itc/src/main/java/tools/refinery/viatra/runtime/base/itc/alg/dred/DRedAlg.java b/subprojects/viatra-runtime-base-itc/src/main/java/tools/refinery/viatra/runtime/base/itc/alg/dred/DRedAlg.java
deleted file mode 100644
index b92d08bf..00000000
--- a/subprojects/viatra-runtime-base-itc/src/main/java/tools/refinery/viatra/runtime/base/itc/alg/dred/DRedAlg.java
+++ /dev/null
@@ -1,308 +0,0 @@
1/*******************************************************************************
2 * Copyright (c) 2010-2012, Tamas Szabo, Istvan Rath and Daniel Varro
3 * This program and the accompanying materials are made available under the
4 * terms of the Eclipse Public License v. 2.0 which is available at
5 * http://www.eclipse.org/legal/epl-v20.html.
6 *
7 * SPDX-License-Identifier: EPL-2.0
8 *******************************************************************************/
9
10package tools.refinery.viatra.runtime.base.itc.alg.dred;
11
12import java.util.ArrayList;
13import java.util.HashMap;
14import java.util.HashSet;
15import java.util.List;
16import java.util.Map;
17import java.util.Map.Entry;
18import java.util.Set;
19
20import tools.refinery.viatra.runtime.base.itc.alg.misc.DFSPathFinder;
21import tools.refinery.viatra.runtime.base.itc.alg.misc.IGraphPathFinder;
22import tools.refinery.viatra.runtime.base.itc.alg.misc.Tuple;
23import tools.refinery.viatra.runtime.base.itc.alg.misc.dfs.DFSAlg;
24import tools.refinery.viatra.runtime.base.itc.igraph.IGraphDataSource;
25import tools.refinery.viatra.runtime.base.itc.igraph.IGraphObserver;
26import tools.refinery.viatra.runtime.base.itc.igraph.ITcDataSource;
27import tools.refinery.viatra.runtime.base.itc.igraph.ITcObserver;
28import tools.refinery.viatra.runtime.matchers.util.IMemoryView;
29
30/**
31 * This class is the optimized implementation of the DRED algorithm.
32 *
33 * @author Tamas Szabo
34 *
35 * @param <V>
36 * the type parameter of the nodes in the graph data source
37 */
38public class DRedAlg<V> implements IGraphObserver<V>, ITcDataSource<V> {
39
40 private IGraphDataSource<V> graphDataSource = null;
41 private DRedTcRelation<V> tc = null;
42 private DRedTcRelation<V> dtc = null;
43 private List<ITcObserver<V>> observers;
44
45 /**
46 * Constructs a new DRED algorithm and initializes the transitive closure relation with the given graph data source.
47 * Attach itself on the graph data source as an observer.
48 *
49 * @param gds
50 * the graph data source instance
51 */
52 public DRedAlg(IGraphDataSource<V> gds) {
53 this.observers = new ArrayList<ITcObserver<V>>();
54 this.graphDataSource = gds;
55 this.tc = new DRedTcRelation<V>();
56 this.dtc = new DRedTcRelation<V>();
57 initTc();
58 graphDataSource.attachObserver(this);
59 }
60
61 /**
62 * Constructs a new DRED algorithm and initializes the transitive closure relation with the given relation. Attach
63 * itself on the graph data source as an observer.
64 *
65 * @param gds
66 * the graph data source instance
67 * @param tc
68 * the transitive closure instance
69 */
70 public DRedAlg(IGraphDataSource<V> gds, DRedTcRelation<V> tc) {
71 this.graphDataSource = gds;
72 this.tc = tc;
73 this.dtc = new DRedTcRelation<V>();
74 graphDataSource.attachObserver(this);
75 }
76
77 /**
78 * Initializes the transitive closure relation.
79 */
80 private void initTc() {
81 DFSAlg<V> dfsa = new DFSAlg<V>(this.graphDataSource);
82 this.setTcRelation(dfsa.getTcRelation());
83 this.graphDataSource.detachObserver(dfsa);
84 }
85
86 @Override
87 public void edgeInserted(V source, V target) {
88 if (!source.equals(target)) {
89 Set<V> tupStarts = null;
90 Set<V> tupEnds = null;
91 Set<Tuple<V>> tuples = new HashSet<Tuple<V>>();
92
93 if (!source.equals(target) && tc.addTuple(source, target)) {
94 tuples.add(new Tuple<V>(source, target));
95 }
96
97 // 2. d+(tc(x,y)) :- d+(tc(x,z)) & lv(z,y) Descartes product
98 tupStarts = tc.getTupleStarts(source);
99 tupEnds = tc.getTupleEnds(target);
100
101 for (V s : tupStarts) {
102 for (V t : tupEnds) {
103 if (!s.equals(t) && tc.addTuple(s, t)) {
104 tuples.add(new Tuple<V>(s, t));
105 }
106 }
107 }
108
109 // (s, source) -> (source, target)
110 // tupStarts = tc.getTupleStarts(source);
111 for (V s : tupStarts) {
112 if (!s.equals(target) && tc.addTuple(s, target)) {
113 tuples.add(new Tuple<V>(s, target));
114 }
115 }
116
117 // (source, target) -> (target, t)
118 // tupEnds = tc.getTupleEnds(target);
119 for (V t : tupEnds) {
120 if (!source.equals(t) && tc.addTuple(source, t)) {
121 tuples.add(new Tuple<V>(source, t));
122 }
123 }
124
125 notifyTcObservers(tuples, 1);
126 }
127 }
128
129 @Override
130 public void edgeDeleted(V source, V target) {
131 if (!source.equals(target)) {
132
133 // Computing overestimate, Descartes product of A and B sets, where
134 // A: those nodes from which source is reachable
135 // B: those nodes which is reachable from target
136
137 Map<Tuple<V>, Integer> tuples = new HashMap<Tuple<V>, Integer>();
138 Set<V> sources = tc.getTupleStarts(source);
139 Set<V> targets = tc.getTupleEnds(target);
140
141 tc.removeTuple(source, target);
142 tuples.put(new Tuple<V>(source, target), -1);
143
144 for (V s : sources) {
145 for (V t : targets) {
146 if (!s.equals(t)) {
147 tc.removeTuple(s, t);
148 tuples.put(new Tuple<V>(s, t), -1);
149 }
150 }
151 }
152
153 for (V s : sources) {
154 if (!s.equals(target)) {
155 tc.removeTuple(s, target);
156 tuples.put(new Tuple<V>(s, target), -1);
157 }
158 }
159
160 for (V t : targets) {
161 if (!source.equals(t)) {
162 tc.removeTuple(source, t);
163 tuples.put(new Tuple<V>(source, t), -1);
164 }
165 }
166
167 // System.out.println("overestimate: "+dtc);
168
169 // Modify overestimate with those tuples that have alternative derivations
170 // 1. q+(tc(x,y)) :- lv(x,y)
171 for (V s : graphDataSource.getAllNodes()) {
172 IMemoryView<V> targetNodes = graphDataSource.getTargetNodes(s);
173 for (Entry<V, Integer> entry : targetNodes.entriesWithMultiplicities()) {
174 for (int i = 0; i < entry.getValue(); i++) {
175 V t = entry.getKey();
176 if (!s.equals(t)) {
177 tc.addTuple(s, t);
178 Tuple<V> tuple = new Tuple<V>(s, t);
179 Integer count = tuples.get(tuple);
180 if (count != null && count == -1) {
181 tuples.remove(tuple);
182 }
183 }
184
185 }
186 }
187 }
188
189 // 2. q+(tc(x,y)) :- tcv(x,z) & lv(z,y)
190 DRedTcRelation<V> newTups = new DRedTcRelation<V>();
191 dtc.clear();
192 dtc.union(tc);
193
194 while (!dtc.isEmpty()) {
195
196 newTups.clear();
197 newTups.union(dtc);
198 dtc.clear();
199
200 for (V s : newTups.getTupleStarts()) {
201 for (V t : newTups.getTupleEnds(s)) {
202 IMemoryView<V> targetNodes = graphDataSource.getTargetNodes(t);
203 if (targetNodes != null) {
204 for (Entry<V, Integer> entry : targetNodes.entriesWithMultiplicities()) {
205 for (int i = 0; i < entry.getValue(); i++) {
206 V tn = entry.getKey();
207 if (!s.equals(tn) && tc.addTuple(s, tn)) {
208 dtc.addTuple(s, tn);
209 tuples.remove(new Tuple<V>(s, tn));
210 }
211 }
212 }
213 }
214 }
215 }
216 }
217
218 notifyTcObservers(tuples.keySet(), -1);
219 }
220 }
221
222 @Override
223 public void nodeInserted(V n) {
224 // Node inserted does not result new tc tuple.
225 }
226
227 @Override
228 public void nodeDeleted(V n) {
229 // FIXME node deletion may involve the deletion of incoming and outgoing edges too
230 Set<V> set = tc.getTupleEnds(n);
231 Set<V> modSet = null;
232
233 // n -> target
234 modSet = new HashSet<V>(set);
235
236 for (V tn : modSet) {
237 this.tc.removeTuple(n, tn);
238 }
239
240 // source -> n
241 set = tc.getTupleStarts(n);
242
243 modSet = new HashSet<V>(set);
244
245 for (V sn : modSet) {
246 this.tc.removeTuple(sn, n);
247 }
248 }
249
250 public DRedTcRelation<V> getTcRelation() {
251 return this.tc;
252 }
253
254 public void setTcRelation(DRedTcRelation<V> tc) {
255 this.tc = tc;
256 }
257
258 @Override
259 public boolean isReachable(V source, V target) {
260 return tc.containsTuple(source, target);
261 }
262
263 @Override
264 public void attachObserver(ITcObserver<V> to) {
265 this.observers.add(to);
266 }
267
268 @Override
269 public void detachObserver(ITcObserver<V> to) {
270 this.observers.remove(to);
271 }
272
273 @Override
274 public Set<V> getAllReachableTargets(V source) {
275 return tc.getTupleEnds(source);
276 }
277
278 @Override
279 public Set<V> getAllReachableSources(V target) {
280 return tc.getTupleStarts(target);
281 }
282
283 protected void notifyTcObservers(Set<Tuple<V>> tuples, int dir) {
284 for (ITcObserver<V> o : observers) {
285 for (Tuple<V> t : tuples) {
286 if (!t.getSource().equals(t.getTarget())) {
287 if (dir == 1) {
288 o.tupleInserted(t.getSource(), t.getTarget());
289 }
290 if (dir == -1) {
291 o.tupleDeleted(t.getSource(), t.getTarget());
292 }
293 }
294 }
295 }
296 }
297
298 @Override
299 public void dispose() {
300 tc = null;
301 dtc = null;
302 }
303
304 @Override
305 public IGraphPathFinder<V> getPathFinder() {
306 return new DFSPathFinder<V>(graphDataSource, this);
307 }
308}
generated by cgit v1.2.3-70-g09d2 (git 2.46.0) at 2024-09-06 07:25:50 +0000