diff options
Diffstat (limited to 'subprojects/viatra-runtime-rete/src/main/java/tools/refinery/viatra/runtime/rete/itc/alg/misc/bfs/BFS.java')
-rw-r--r-- | subprojects/viatra-runtime-rete/src/main/java/tools/refinery/viatra/runtime/rete/itc/alg/misc/bfs/BFS.java | 148 |
1 files changed, 148 insertions, 0 deletions
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 | } | ||