diff options
Diffstat (limited to 'subprojects/viatra-runtime-rete/src/main/java/tools/refinery/viatra/runtime/rete/itc/alg/misc/DFSPathFinder.java')
-rw-r--r-- | subprojects/viatra-runtime-rete/src/main/java/tools/refinery/viatra/runtime/rete/itc/alg/misc/DFSPathFinder.java | 146 |
1 files changed, 146 insertions, 0 deletions
diff --git a/subprojects/viatra-runtime-rete/src/main/java/tools/refinery/viatra/runtime/rete/itc/alg/misc/DFSPathFinder.java b/subprojects/viatra-runtime-rete/src/main/java/tools/refinery/viatra/runtime/rete/itc/alg/misc/DFSPathFinder.java new file mode 100644 index 00000000..2cec33a2 --- /dev/null +++ b/subprojects/viatra-runtime-rete/src/main/java/tools/refinery/viatra/runtime/rete/itc/alg/misc/DFSPathFinder.java | |||
@@ -0,0 +1,146 @@ | |||
1 | /******************************************************************************* | ||
2 | * Copyright (c) 2010-2016, Abel Hegedus and IncQueryLabs Ltd. | ||
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 java.util.ArrayList; | ||
12 | import java.util.Deque; | ||
13 | import java.util.HashSet; | ||
14 | import java.util.Iterator; | ||
15 | import java.util.LinkedList; | ||
16 | import java.util.List; | ||
17 | import java.util.Set; | ||
18 | |||
19 | import tools.refinery.viatra.runtime.rete.itc.igraph.IGraphDataSource; | ||
20 | import tools.refinery.viatra.runtime.rete.itc.igraph.ITcDataSource; | ||
21 | import tools.refinery.viatra.runtime.matchers.util.IMemoryView; | ||
22 | |||
23 | /** | ||
24 | * A depth-first search implementation of the {@link IGraphPathFinder}. | ||
25 | * | ||
26 | * TODO use ITC to filter nodes that must be traversed, instead of checks | ||
27 | * | ||
28 | * @author Abel Hegedus | ||
29 | * | ||
30 | * @param <V> | ||
31 | * the node type of the graph | ||
32 | */ | ||
33 | public class DFSPathFinder<V> implements IGraphPathFinder<V> { | ||
34 | |||
35 | private IGraphDataSource<V> graph; | ||
36 | private ITcDataSource<V> itc; | ||
37 | |||
38 | public DFSPathFinder(IGraphDataSource<V> graph, ITcDataSource<V> itc) { | ||
39 | this.graph = graph; | ||
40 | this.itc = itc; | ||
41 | } | ||
42 | |||
43 | @Override | ||
44 | public Iterable<Deque<V>> getAllPaths(V sourceNode, V targetNode) { | ||
45 | Set<V> endNodes = new HashSet<V>(); | ||
46 | endNodes.add(targetNode); | ||
47 | return getAllPathsToTargets(sourceNode, endNodes); | ||
48 | } | ||
49 | |||
50 | @Override | ||
51 | public Iterable<Deque<V>> getAllPathsToTargets(V sourceNode, Set<V> targetNodes) { | ||
52 | List<Deque<V>> paths = new ArrayList<Deque<V>>(); | ||
53 | Deque<V> visited = new LinkedList<V>(); | ||
54 | Set<V> reachableTargets = new HashSet<V>(); | ||
55 | for (V targetNode : targetNodes) { | ||
56 | if (itc.isReachable(sourceNode, targetNode)) { | ||
57 | reachableTargets.add(targetNode); | ||
58 | } | ||
59 | } | ||
60 | if (!reachableTargets.isEmpty()) { | ||
61 | return paths; | ||
62 | } | ||
63 | visited.add(sourceNode); | ||
64 | return getPaths(paths, visited, reachableTargets); | ||
65 | } | ||
66 | |||
67 | protected Iterable<Deque<V>> getPaths(List<Deque<V>> paths, Deque<V> visited, Set<V> targetNodes) { | ||
68 | IMemoryView<V> nodes = graph.getTargetNodes(visited.getLast()); | ||
69 | // examine adjacent nodes | ||
70 | for (V node : nodes.distinctValues()) { | ||
71 | if (visited.contains(node)) { | ||
72 | continue; | ||
73 | } | ||
74 | if (targetNodes.contains(node)) { | ||
75 | visited.add(node); | ||
76 | // clone visited LinkedList | ||
77 | Deque<V> visitedClone = new LinkedList<V>(visited); | ||
78 | paths.add(visitedClone); | ||
79 | visited.removeLast(); | ||
80 | break; | ||
81 | } | ||
82 | } | ||
83 | |||
84 | // in breadth-first, recursion needs to come after visiting connected nodes | ||
85 | for (V node : nodes.distinctValues()) { | ||
86 | if (visited.contains(node) || targetNodes.contains(node)) { | ||
87 | continue; | ||
88 | } | ||
89 | boolean canReachTarget = false; | ||
90 | for (V target : targetNodes) { | ||
91 | if (itc.isReachable(node, target)) { | ||
92 | canReachTarget = true; | ||
93 | break; | ||
94 | } | ||
95 | } | ||
96 | if (canReachTarget) { | ||
97 | visited.addLast(node); | ||
98 | getPaths(paths, visited, targetNodes); | ||
99 | visited.removeLast(); | ||
100 | } | ||
101 | } | ||
102 | |||
103 | return paths; | ||
104 | } | ||
105 | |||
106 | public String printPaths(List<Deque<V>> paths) { | ||
107 | StringBuilder sb = new StringBuilder(); | ||
108 | for (Deque<V> visited : paths) { | ||
109 | sb.append("Path: "); | ||
110 | for (V node : visited) { | ||
111 | sb.append(node); | ||
112 | sb.append(" --> "); | ||
113 | } | ||
114 | sb.append("\n"); | ||
115 | } | ||
116 | return sb.toString(); | ||
117 | } | ||
118 | |||
119 | @Override | ||
120 | public Deque<V> getPath(V sourceNode, V targetNode) { | ||
121 | // TODO optimize | ||
122 | Iterable<Deque<V>> allPaths = getAllPaths(sourceNode, targetNode); | ||
123 | Iterator<Deque<V>> pathIterator = allPaths.iterator(); | ||
124 | return pathIterator.hasNext() ? pathIterator.next() : new LinkedList<V>(); | ||
125 | } | ||
126 | |||
127 | @Override | ||
128 | public Iterable<Deque<V>> getShortestPaths(V sourceNode, V targetNode) { | ||
129 | // TODO optimize | ||
130 | Iterable<Deque<V>> allPaths = getAllPaths(sourceNode, targetNode); | ||
131 | List<Deque<V>> shortestPaths = new ArrayList<Deque<V>>(); | ||
132 | int shortestPathLength = -1; | ||
133 | for (Deque<V> path : allPaths) { | ||
134 | int pathLength = path.size(); | ||
135 | if (shortestPathLength == -1 || pathLength < shortestPathLength) { | ||
136 | shortestPaths.clear(); | ||
137 | shortestPathLength = pathLength; | ||
138 | } | ||
139 | if (pathLength == shortestPathLength) { | ||
140 | shortestPaths.add(path); | ||
141 | } | ||
142 | } | ||
143 | return shortestPaths; | ||
144 | } | ||
145 | |||
146 | } | ||