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