1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
|
/*******************************************************************************
* Copyright (c) 2010-2013, Tamas Szabo, Istvan Rath and Daniel Varro
* This program and the accompanying materials are made available under the
* terms of the Eclipse Public License v. 2.0 which is available at
* http://www.eclipse.org/legal/epl-v20.html.
*
* SPDX-License-Identifier: EPL-2.0
*******************************************************************************/
package tools.refinery.viatra.runtime.rete.itc.alg.misc;
import tools.refinery.viatra.runtime.matchers.util.IMemoryView;
import tools.refinery.viatra.runtime.rete.itc.graphimpl.Graph;
import tools.refinery.viatra.runtime.rete.itc.igraph.IBiDirectionalGraphDataSource;
import tools.refinery.viatra.runtime.rete.itc.igraph.IGraphDataSource;
import java.util.*;
import java.util.Map.Entry;
/**
* Utility class for graph related operations.
*
* @author Tamas Szabo
*/
public class GraphHelper {
private GraphHelper() {/*Utility class constructor*/}
/**
* Returns the subgraph from the given {@link IBiDirectionalGraphDataSource} which contains the given set of nodes.
*
* @param nodesInSubGraph
* the nodes that are present in the subgraph
* @param graphDataSource
* the graph data source for the original graph
* @return the subgraph associated to the given nodes
*/
public static <V> Graph<V> getSubGraph(Collection<V> nodesInSubGraph,
IBiDirectionalGraphDataSource<V> graphDataSource) {
Graph<V> g = new Graph<V>();
if (nodesInSubGraph != null) {
for (V node : nodesInSubGraph) {
g.insertNode(node);
}
for (V node : nodesInSubGraph) {
IMemoryView<V> sources = graphDataSource.getSourceNodes(node);
for (Entry<V, Integer> entry : sources.entriesWithMultiplicities()) {
for (int i = 0; i < entry.getValue(); i++) {
V s = entry.getKey();
if (nodesInSubGraph.contains(s)) {
g.insertEdge(s, node);
}
}
}
}
}
return g;
}
/**
* Constructs a path between source and target in the given graph. Both the {@link IGraphDataSource} and the set of
* nodes are used, this way it is possible to construct a path in a given subgraph.
*
* The returned {@link List} contains the nodes along the path (this means that there is an edge in the graph
* between two consecutive nodes). A self loop (one edge) is indicated with the source node being present two times
* in the returned {@link List}.
*
* @param source
* the source node
* @param target
* the target node
* @param nodesInGraph
* the nodes that are present in the subgraph
* @param graphDataSource
* the graph data source
* @return the path between the two nodes
*/
public static <V> List<V> constructPath(V source, V target, Set<V> nodesInGraph,
IGraphDataSource<V> graphDataSource) {
Set<V> visitedNodes = new HashSet<V>();
List<V> path = new ArrayList<V>();
visitedNodes.add(source);
path.add(source);
V act = source;
// if source and target are the same node
if (source.equals(target) && graphDataSource.getTargetNodes(source).containsNonZero(target)) {
// the node will be present in the path two times
path.add(source);
return path;
} else {
while (act != null) {
V nextNode = getNextNodeToVisit(act, graphDataSource, nodesInGraph, visitedNodes);
if (nextNode == null && path.size() > 1) {
// needs to backtrack along path
// remove the last element in the path because we can't go
// anywhere from there
path.remove(path.size() - 1);
while (nextNode == null && path.size() > 0) {
V lastPathElement = path.get(path.size() - 1);
nextNode = getNextNodeToVisit(lastPathElement, graphDataSource, nodesInGraph, visitedNodes);
if (nextNode == null) {
path.remove(path.size() - 1);
}
}
}
if (nextNode != null) {
visitedNodes.add(nextNode);
path.add(nextNode);
if (nextNode.equals(target)) {
return path;
}
}
act = nextNode;
}
return null;
}
}
private static <V> V getNextNodeToVisit(V act, IGraphDataSource<V> graphDataSource, Set<V> nodesInSubGraph,
Set<V> visitedNodes) {
IMemoryView<V> targetNodes = graphDataSource.getTargetNodes(act);
for (Entry<V, Integer> entry : targetNodes.entriesWithMultiplicities()) {
for (int i = 0; i < entry.getValue(); i++) {
V node = entry.getKey();
if (nodesInSubGraph.contains(node) && !visitedNodes.contains(node)) {
return node;
}
}
}
return null;
}
/**
* Returns the number of self-loop edges for the given node.
*
* @param node
* the node
* @param graphDataSource
* the graph data source
* @return the number of self-loop edges
*/
public static <V> int getEdgeCount(V node, IGraphDataSource<V> graphDataSource) {
return getEdgeCount(node, node, graphDataSource);
}
/**
* Returns the number of edges between the given source and target nodes.
*
* @param source
* the source node
* @param target
* the target node
* @param graphDataSource
* the graph data source
* @return the number of parallel edges between the two nodes
*/
public static <V> int getEdgeCount(V source, V target, IGraphDataSource<V> graphDataSource) {
Integer count = graphDataSource.getTargetNodes(source).getCount(target);
if (count == null) {
return 0;
} else {
return count;
}
}
}
|
