176 * Traverses this graph and performs the given action in topological order.
177 */
178 public void ordered(Consumer<T> action) {
179 TopoSorter<T> sorter = new TopoSorter<>(this);
180 sorter.ordered(action);
181 }
182
183 /**
184 * Traverses this graph and performs the given action in reverse topological order.
185 */
186 public void reverse(Consumer<T> action) {
187 TopoSorter<T> sorter = new TopoSorter<>(this);
188 sorter.reverse(action);
189 }
190
191 /**
192 * Returns a transposed graph from this graph.
193 */
194 public Graph<T> transpose() {
195 Builder<T> builder = new Builder<>();
196 nodes.stream().forEach(builder::addNode);
197 // reverse edges
198 edges.keySet().forEach(u -> {
199 edges.get(u).stream()
200 .forEach(v -> builder.addEdge(v, u));
201 });
202 return builder.build();
203 }
204
205 /**
206 * Returns all nodes reachable from the given root.
207 */
208 public Set<T> dfs(T root) {
209 return dfs(Set.of(root));
210 }
211
212 /**
213 * Returns all nodes reachable from the given set of roots.
214 */
215 public Set<T> dfs(Set<T> roots) {
216 Deque<T> deque = new LinkedList<>(roots);
217 Set<T> visited = new HashSet<>();
218 while (!deque.isEmpty()) {
219 T u = deque.pop();
220 if (!visited.contains(u)) {
221 visited.add(u);
222 if (contains(u)) {
223 adjacentNodes(u).stream()
224 .filter(v -> !visited.contains(v))
225 .forEach(deque::push);
226 }
227 }
228 }
229 return visited;
230 }
231
232 public void printGraph(PrintStream out) {
233 out.println("graph for " + nodes);
234 nodes.stream()
235 .forEach(u -> adjacentNodes(u).stream()
236 .forEach(v -> out.format(" %s -> %s%n", u, v)));
237 }
238
239 static class Builder<T> {
240 final Set<T> nodes = new HashSet<>();
241 final Map<T, Set<T>> edges = new HashMap<>();
242
243 public void addNode(T node) {
244 if (nodes.contains(node)) {
245 return;
246 }
247 nodes.add(node);
248 edges.computeIfAbsent(node, _e -> new HashSet<>());
249 }
250
251 public void addEdge(T u, T v) {
252 addNode(u);
253 addNode(v);
254 edges.get(u).add(v);
255 }
285 private void sort() {
286 Deque<T> visited = new LinkedList<>();
287 Deque<T> done = new LinkedList<>();
288 T node;
289 while ((node = nodes.poll()) != null) {
290 if (!visited.contains(node)) {
291 visit(node, visited, done);
292 }
293 }
294 }
295
296 private void visit(T node, Deque<T> visited, Deque<T> done) {
297 if (visited.contains(node)) {
298 if (!done.contains(node)) {
299 throw new IllegalArgumentException("Cyclic detected: " +
300 node + " " + graph.edges().get(node));
301 }
302 return;
303 }
304 visited.add(node);
305 graph.edges().get(node).stream()
306 .forEach(x -> visit(x, visited, done));
307 done.add(node);
308 result.addLast(node);
309 }
310 }
311 }
|
176 * Traverses this graph and performs the given action in topological order.
177 */
178 public void ordered(Consumer<T> action) {
179 TopoSorter<T> sorter = new TopoSorter<>(this);
180 sorter.ordered(action);
181 }
182
183 /**
184 * Traverses this graph and performs the given action in reverse topological order.
185 */
186 public void reverse(Consumer<T> action) {
187 TopoSorter<T> sorter = new TopoSorter<>(this);
188 sorter.reverse(action);
189 }
190
191 /**
192 * Returns a transposed graph from this graph.
193 */
194 public Graph<T> transpose() {
195 Builder<T> builder = new Builder<>();
196 nodes.forEach(builder::addNode);
197 // reverse edges
198 edges.keySet().forEach(u -> {
199 edges.get(u).forEach(v -> builder.addEdge(v, u));
200 });
201 return builder.build();
202 }
203
204 /**
205 * Returns all nodes reachable from the given root.
206 */
207 public Set<T> dfs(T root) {
208 return dfs(Set.of(root));
209 }
210
211 /**
212 * Returns all nodes reachable from the given set of roots.
213 */
214 public Set<T> dfs(Set<T> roots) {
215 Deque<T> deque = new LinkedList<>(roots);
216 Set<T> visited = new HashSet<>();
217 while (!deque.isEmpty()) {
218 T u = deque.pop();
219 if (!visited.contains(u)) {
220 visited.add(u);
221 if (contains(u)) {
222 adjacentNodes(u).stream()
223 .filter(v -> !visited.contains(v))
224 .forEach(deque::push);
225 }
226 }
227 }
228 return visited;
229 }
230
231 public void printGraph(PrintStream out) {
232 out.println("graph for " + nodes);
233 nodes
234 .forEach(u -> adjacentNodes(u)
235 .forEach(v -> out.format(" %s -> %s%n", u, v)));
236 }
237
238 static class Builder<T> {
239 final Set<T> nodes = new HashSet<>();
240 final Map<T, Set<T>> edges = new HashMap<>();
241
242 public void addNode(T node) {
243 if (nodes.contains(node)) {
244 return;
245 }
246 nodes.add(node);
247 edges.computeIfAbsent(node, _e -> new HashSet<>());
248 }
249
250 public void addEdge(T u, T v) {
251 addNode(u);
252 addNode(v);
253 edges.get(u).add(v);
254 }
284 private void sort() {
285 Deque<T> visited = new LinkedList<>();
286 Deque<T> done = new LinkedList<>();
287 T node;
288 while ((node = nodes.poll()) != null) {
289 if (!visited.contains(node)) {
290 visit(node, visited, done);
291 }
292 }
293 }
294
295 private void visit(T node, Deque<T> visited, Deque<T> done) {
296 if (visited.contains(node)) {
297 if (!done.contains(node)) {
298 throw new IllegalArgumentException("Cyclic detected: " +
299 node + " " + graph.edges().get(node));
300 }
301 return;
302 }
303 visited.add(node);
304 graph.edges().get(node)
305 .forEach(x -> visit(x, visited, done));
306 done.add(node);
307 result.addLast(node);
308 }
309 }
310 }
|