diff options
Diffstat (limited to 'subprojects/viatra-runtime/src/main/java/tools/refinery/viatra/runtime/base/itc/alg/misc/dfs/DFSAlg.java')
-rw-r--r-- | subprojects/viatra-runtime/src/main/java/tools/refinery/viatra/runtime/base/itc/alg/misc/dfs/DFSAlg.java | 93 |
1 files changed, 93 insertions, 0 deletions
diff --git a/subprojects/viatra-runtime/src/main/java/tools/refinery/viatra/runtime/base/itc/alg/misc/dfs/DFSAlg.java b/subprojects/viatra-runtime/src/main/java/tools/refinery/viatra/runtime/base/itc/alg/misc/dfs/DFSAlg.java new file mode 100644 index 00000000..c8d25c4e --- /dev/null +++ b/subprojects/viatra-runtime/src/main/java/tools/refinery/viatra/runtime/base/itc/alg/misc/dfs/DFSAlg.java | |||
@@ -0,0 +1,93 @@ | |||
1 | /******************************************************************************* | ||
2 | * Copyright (c) 2010-2012, Tamas Szabo, Istvan Rath and Daniel Varro | ||
3 | * This program and the accompanying materials are made available under the | ||
4 | * terms of the Eclipse Public License v. 2.0 which is available at | ||
5 | * http://www.eclipse.org/legal/epl-v20.html. | ||
6 | * | ||
7 | * SPDX-License-Identifier: EPL-2.0 | ||
8 | *******************************************************************************/ | ||
9 | |||
10 | package tools.refinery.viatra.runtime.base.itc.alg.misc.dfs; | ||
11 | |||
12 | import java.util.HashMap; | ||
13 | |||
14 | import tools.refinery.viatra.runtime.base.itc.alg.dred.DRedTcRelation; | ||
15 | import tools.refinery.viatra.runtime.base.itc.igraph.IGraphDataSource; | ||
16 | import tools.refinery.viatra.runtime.base.itc.igraph.IGraphObserver; | ||
17 | |||
18 | public class DFSAlg<V> implements IGraphObserver<V> { | ||
19 | |||
20 | private IGraphDataSource<V> gds; | ||
21 | private DRedTcRelation<V> tc; | ||
22 | private int[] visited; | ||
23 | private HashMap<V, Integer> nodeMap; | ||
24 | |||
25 | public DFSAlg(IGraphDataSource<V> gds) { | ||
26 | this.gds = gds; | ||
27 | this.tc = new DRedTcRelation<V>(); | ||
28 | gds.attachObserver(this); | ||
29 | deriveTc(); | ||
30 | } | ||
31 | |||
32 | private void deriveTc() { | ||
33 | tc.clear(); | ||
34 | |||
35 | this.visited = new int[gds.getAllNodes().size()]; | ||
36 | nodeMap = new HashMap<V, Integer>(); | ||
37 | |||
38 | int j = 0; | ||
39 | for (V n : gds.getAllNodes()) { | ||
40 | nodeMap.put(n, j); | ||
41 | j++; | ||
42 | } | ||
43 | |||
44 | for (V n : gds.getAllNodes()) { | ||
45 | oneDFS(n, n); | ||
46 | initVisitedArray(); | ||
47 | } | ||
48 | } | ||
49 | |||
50 | private void initVisitedArray() { | ||
51 | for (int i = 0; i < visited.length; i++) | ||
52 | visited[i] = 0; | ||
53 | } | ||
54 | |||
55 | private void oneDFS(V act, V source) { | ||
56 | |||
57 | if (!act.equals(source)) { | ||
58 | tc.addTuple(source, act); | ||
59 | } | ||
60 | |||
61 | visited[nodeMap.get(act)] = 1; | ||
62 | |||
63 | for (V t : gds.getTargetNodes(act).distinctValues()) { | ||
64 | if (visited[nodeMap.get(t)] == 0) { | ||
65 | oneDFS(t, source); | ||
66 | } | ||
67 | } | ||
68 | } | ||
69 | |||
70 | public DRedTcRelation<V> getTcRelation() { | ||
71 | return this.tc; | ||
72 | } | ||
73 | |||
74 | @Override | ||
75 | public void edgeInserted(V source, V target) { | ||
76 | deriveTc(); | ||
77 | } | ||
78 | |||
79 | @Override | ||
80 | public void edgeDeleted(V source, V target) { | ||
81 | deriveTc(); | ||
82 | } | ||
83 | |||
84 | @Override | ||
85 | public void nodeInserted(V n) { | ||
86 | deriveTc(); | ||
87 | } | ||
88 | |||
89 | @Override | ||
90 | public void nodeDeleted(V n) { | ||
91 | deriveTc(); | ||
92 | } | ||
93 | } | ||