1 /*
2 * Copyright (C) 2017 The Guava Authors
3 *
4 * Licensed under the Apache License, Version 2.0 (the "License");
5 * you may not use this file except in compliance with the License.
6 * You may obtain a copy of the License at
7 *
8 * http://www.apache.org/licenses/LICENSE-2.0
9 *
10 * Unless required by applicable law or agreed to in writing, software
11 * distributed under the License is distributed on an "AS IS" BASIS,
12 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13 * See the License for the specific language governing permissions and
14 * limitations under the License.
15 */
16
17 package com.google.common.graph;
18
19 import static com.google.common.base.Preconditions.checkArgument;
20 import static com.google.common.base.Preconditions.checkNotNull;
21 import static java.util.Objects.requireNonNull;
22
23 import com.google.common.annotations.Beta;
24 import com.google.common.collect.AbstractIterator;
25 import com.google.common.collect.ImmutableSet;
26 import com.google.errorprone.annotations.DoNotMock;
27 import java.util.ArrayDeque;
28 import java.util.Deque;
29 import java.util.HashSet;
30 import java.util.Iterator;
31 import java.util.Set;
32 import javax.annotation.CheckForNull;
33
34 /**
35 * An object that can traverse the nodes that are reachable from a specified (set of) start node(s)
36 * using a specified {@link SuccessorsFunction}.
37 *
38 * <p>There are two entry points for creating a {@code Traverser}: {@link
39 * #forTree(SuccessorsFunction)} and {@link #forGraph(SuccessorsFunction)}. You should choose one
40 * based on your answers to the following questions:
41 *
42 * <ol>
43 * <li>Is there only one path to any node that's reachable from any start node? (If so, the graph
44 * to be traversed is a tree or forest even if it is a subgraph of a graph which is neither.)
45 * <li>Are the node objects' implementations of {@code equals()}/{@code hashCode()} <a
46 * href="https://github.com/google/guava/wiki/GraphsExplained#non-recursiveness">recursive</a>?
47 * </ol>
48 *
49 * <p>If your answers are:
50 *
51 * <ul>
52 * <li>(1) "no" and (2) "no", use {@link #forGraph(SuccessorsFunction)}.
53 * <li>(1) "yes" and (2) "yes", use {@link #forTree(SuccessorsFunction)}.
54 * <li>(1) "yes" and (2) "no", you can use either, but {@code forTree()} will be more efficient.
55 * <li>(1) "no" and (2) "yes", <b><i>neither will work</i></b>, but if you transform your node
56 * objects into a non-recursive form, you can use {@code forGraph()}.
57 * </ul>
58 *
59 * @author Jens Nyman
60 * @param <N> Node parameter type
61 * @since 23.1
62 */
63 @Beta
64 @DoNotMock(
65 "Call forGraph or forTree, passing a lambda or a Graph with the desired edges (built with"
66 + " GraphBuilder)")
67 @ElementTypesAreNonnullByDefault
68 public abstract class Traverser<N> {
69 private final SuccessorsFunction<N> successorFunction;
70
71 private Traverser(SuccessorsFunction<N> successorFunction) {
72 this.successorFunction = checkNotNull(successorFunction);
73 }
74
75 /**
76 * Creates a new traverser for the given general {@code graph}.
77 *
78 * <p>Traversers created using this method are guaranteed to visit each node reachable from the
79 * start node(s) at most once.
80 *
81 * <p>If you know that no node in {@code graph} is reachable by more than one path from the start
82 * node(s), consider using {@link #forTree(SuccessorsFunction)} instead.
83 *
84 * <p><b>Performance notes</b>
85 *
86 * <ul>
87 * <li>Traversals require <i>O(n)</i> time (where <i>n</i> is the number of nodes reachable from
88 * the start node), assuming that the node objects have <i>O(1)</i> {@code equals()} and
89 * {@code hashCode()} implementations. (See the <a
90 * href="https://github.com/google/guava/wiki/GraphsExplained#elements-must-be-useable-as-map-keys">
91 * notes on element objects</a> for more information.)
92 * <li>While traversing, the traverser will use <i>O(n)</i> space (where <i>n</i> is the number
93 * of nodes that have thus far been visited), plus <i>O(H)</i> space (where <i>H</i> is the
94 * number of nodes that have been seen but not yet visited, that is, the "horizon").
95 * </ul>
96 *
97 * @param graph {@link SuccessorsFunction} representing a general graph that may have cycles.
98 */
99 public static <N> Traverser<N> forGraph(final SuccessorsFunction<N> graph) {
100 return new Traverser<N>(graph) {
101 @Override
102 Traversal<N> newTraversal() {
103 return Traversal.inGraph(graph);
104 }
105 };
106 }
107
108 /**
109 * Creates a new traverser for a directed acyclic graph that has at most one path from the start
110 * node(s) to any node reachable from the start node(s), and has no paths from any start node to
111 * any other start node, such as a tree or forest.
112 *
113 * <p>{@code forTree()} is especially useful (versus {@code forGraph()}) in cases where the data
114 * structure being traversed is, in addition to being a tree/forest, also defined <a
115 * href="https://github.com/google/guava/wiki/GraphsExplained#non-recursiveness">recursively</a>.
116 * This is because the {@code forTree()}-based implementations don't keep track of visited nodes,
117 * and therefore don't need to call `equals()` or `hashCode()` on the node objects; this saves
118 * both time and space versus traversing the same graph using {@code forGraph()}.
119 *
120 * <p>Providing a graph to be traversed for which there is more than one path from the start
121 * node(s) to any node may lead to:
122 *
123 * <ul>
124 * <li>Traversal not terminating (if the graph has cycles)
125 * <li>Nodes being visited multiple times (if multiple paths exist from any start node to any
126 * node reachable from any start node)
127 * </ul>
128 *
129 * <p><b>Performance notes</b>
130 *
131 * <ul>
132 * <li>Traversals require <i>O(n)</i> time (where <i>n</i> is the number of nodes reachable from
133 * the start node).
134 * <li>While traversing, the traverser will use <i>O(H)</i> space (where <i>H</i> is the number
135 * of nodes that have been seen but not yet visited, that is, the "horizon").
136 * </ul>
137 *
138 * <p><b>Examples</b> (all edges are directed facing downwards)
139 *
140 * <p>The graph below would be valid input with start nodes of {@code a, f, c}. However, if {@code
141 * b} were <i>also</i> a start node, then there would be multiple paths to reach {@code e} and
142 * {@code h}.
143 *
144 * <pre>{@code
145 * a b c
146 * / \ / \ |
147 * / \ / \ |
148 * d e f g
149 * |
150 * |
151 * h
152 * }</pre>
153 *
154 * <p>.
155 *
156 * <p>The graph below would be a valid input with start nodes of {@code a, f}. However, if {@code
157 * b} were a start node, there would be multiple paths to {@code f}.
158 *
159 * <pre>{@code
160 * a b
161 * / \ / \
162 * / \ / \
163 * c d e
164 * \ /
165 * \ /
166 * f
167 * }</pre>
168 *
169 * <p><b>Note on binary trees</b>
170 *
171 * <p>This method can be used to traverse over a binary tree. Given methods {@code
172 * leftChild(node)} and {@code rightChild(node)}, this method can be called as
173 *
174 * <pre>{@code
175 * Traverser.forTree(node -> ImmutableList.of(leftChild(node), rightChild(node)));
176 * }</pre>
177 *
178 * @param tree {@link SuccessorsFunction} representing a directed acyclic graph that has at most
179 * one path between any two nodes
180 */
181 public static <N> Traverser<N> forTree(final SuccessorsFunction<N> tree) {
182 if (tree instanceof BaseGraph) {
183 checkArgument(((BaseGraph<?>) tree).isDirected(), "Undirected graphs can never be trees.");
184 }
185 if (tree instanceof Network) {
186 checkArgument(((Network<?, ?>) tree).isDirected(), "Undirected networks can never be trees.");
187 }
188 return new Traverser<N>(tree) {
189 @Override
190 Traversal<N> newTraversal() {
191 return Traversal.inTree(tree);
192 }
193 };
194 }
195
196 /**
197 * Returns an unmodifiable {@code Iterable} over the nodes reachable from {@code startNode}, in
198 * the order of a breadth-first traversal. That is, all the nodes of depth 0 are returned, then
199 * depth 1, then 2, and so on.
200 *
201 * <p><b>Example:</b> The following graph with {@code startNode} {@code a} would return nodes in
202 * the order {@code abcdef} (assuming successors are returned in alphabetical order).
203 *
204 * <pre>{@code
205 * b ---- a ---- d
206 * | |
207 * | |
208 * e ---- c ---- f
209 * }</pre>
210 *
211 * <p>The behavior of this method is undefined if the nodes, or the topology of the graph, change
212 * while iteration is in progress.
213 *
214 * <p>The returned {@code Iterable} can be iterated over multiple times. Every iterator will
215 * compute its next element on the fly. It is thus possible to limit the traversal to a certain
216 * number of nodes as follows:
217 *
218 * <pre>{@code
219 * Iterables.limit(Traverser.forGraph(graph).breadthFirst(node), maxNumberOfNodes);
220 * }</pre>
221 *
222 * <p>See <a href="https://en.wikipedia.org/wiki/Breadth-first_search">Wikipedia</a> for more
223 * info.
224 *
225 * @throws IllegalArgumentException if {@code startNode} is not an element of the graph
226 */
227 public final Iterable<N> breadthFirst(N startNode) {
228 return breadthFirst(ImmutableSet.of(startNode));
229 }
230
231 /**
232 * Returns an unmodifiable {@code Iterable} over the nodes reachable from any of the {@code
233 * startNodes}, in the order of a breadth-first traversal. This is equivalent to a breadth-first
234 * traversal of a graph with an additional root node whose successors are the listed {@code
235 * startNodes}.
236 *
237 * @throws IllegalArgumentException if any of {@code startNodes} is not an element of the graph
238 * @see #breadthFirst(Object)
239 * @since 24.1
240 */
241 public final Iterable<N> breadthFirst(Iterable<? extends N> startNodes) {
242 final ImmutableSet<N> validated = validate(startNodes);
243 return new Iterable<N>() {
244 @Override
245 public Iterator<N> iterator() {
246 return newTraversal().breadthFirst(validated.iterator());
247 }
248 };
249 }
250
251 /**
252 * Returns an unmodifiable {@code Iterable} over the nodes reachable from {@code startNode}, in
253 * the order of a depth-first pre-order traversal. "Pre-order" implies that nodes appear in the
254 * {@code Iterable} in the order in which they are first visited.
255 *
256 * <p><b>Example:</b> The following graph with {@code startNode} {@code a} would return nodes in
257 * the order {@code abecfd} (assuming successors are returned in alphabetical order).
258 *
259 * <pre>{@code
260 * b ---- a ---- d
261 * | |
262 * | |
263 * e ---- c ---- f
264 * }</pre>
265 *
266 * <p>The behavior of this method is undefined if the nodes, or the topology of the graph, change
267 * while iteration is in progress.
268 *
269 * <p>The returned {@code Iterable} can be iterated over multiple times. Every iterator will
270 * compute its next element on the fly. It is thus possible to limit the traversal to a certain
271 * number of nodes as follows:
272 *
273 * <pre>{@code
274 * Iterables.limit(
275 * Traverser.forGraph(graph).depthFirstPreOrder(node), maxNumberOfNodes);
276 * }</pre>
277 *
278 * <p>See <a href="https://en.wikipedia.org/wiki/Depth-first_search">Wikipedia</a> for more info.
279 *
280 * @throws IllegalArgumentException if {@code startNode} is not an element of the graph
281 */
282 public final Iterable<N> depthFirstPreOrder(N startNode) {
283 return depthFirstPreOrder(ImmutableSet.of(startNode));
284 }
285
286 /**
287 * Returns an unmodifiable {@code Iterable} over the nodes reachable from any of the {@code
288 * startNodes}, in the order of a depth-first pre-order traversal. This is equivalent to a
289 * depth-first pre-order traversal of a graph with an additional root node whose successors are
290 * the listed {@code startNodes}.
291 *
292 * @throws IllegalArgumentException if any of {@code startNodes} is not an element of the graph
293 * @see #depthFirstPreOrder(Object)
294 * @since 24.1
295 */
296 public final Iterable<N> depthFirstPreOrder(Iterable<? extends N> startNodes) {
297 final ImmutableSet<N> validated = validate(startNodes);
298 return new Iterable<N>() {
299 @Override
300 public Iterator<N> iterator() {
301 return newTraversal().preOrder(validated.iterator());
302 }
303 };
304 }
305
306 /**
307 * Returns an unmodifiable {@code Iterable} over the nodes reachable from {@code startNode}, in
308 * the order of a depth-first post-order traversal. "Post-order" implies that nodes appear in the
309 * {@code Iterable} in the order in which they are visited for the last time.
310 *
311 * <p><b>Example:</b> The following graph with {@code startNode} {@code a} would return nodes in
312 * the order {@code fcebda} (assuming successors are returned in alphabetical order).
313 *
314 * <pre>{@code
315 * b ---- a ---- d
316 * | |
317 * | |
318 * e ---- c ---- f
319 * }</pre>
320 *
321 * <p>The behavior of this method is undefined if the nodes, or the topology of the graph, change
322 * while iteration is in progress.
323 *
324 * <p>The returned {@code Iterable} can be iterated over multiple times. Every iterator will
325 * compute its next element on the fly. It is thus possible to limit the traversal to a certain
326 * number of nodes as follows:
327 *
328 * <pre>{@code
329 * Iterables.limit(
330 * Traverser.forGraph(graph).depthFirstPostOrder(node), maxNumberOfNodes);
331 * }</pre>
332 *
333 * <p>See <a href="https://en.wikipedia.org/wiki/Depth-first_search">Wikipedia</a> for more info.
334 *
335 * @throws IllegalArgumentException if {@code startNode} is not an element of the graph
336 */
337 public final Iterable<N> depthFirstPostOrder(N startNode) {
338 return depthFirstPostOrder(ImmutableSet.of(startNode));
339 }
340
341 /**
342 * Returns an unmodifiable {@code Iterable} over the nodes reachable from any of the {@code
343 * startNodes}, in the order of a depth-first post-order traversal. This is equivalent to a
344 * depth-first post-order traversal of a graph with an additional root node whose successors are
345 * the listed {@code startNodes}.
346 *
347 * @throws IllegalArgumentException if any of {@code startNodes} is not an element of the graph
348 * @see #depthFirstPostOrder(Object)
349 * @since 24.1
350 */
351 public final Iterable<N> depthFirstPostOrder(Iterable<? extends N> startNodes) {
352 final ImmutableSet<N> validated = validate(startNodes);
353 return new Iterable<N>() {
354 @Override
355 public Iterator<N> iterator() {
356 return newTraversal().postOrder(validated.iterator());
357 }
358 };
359 }
360
361 abstract Traversal<N> newTraversal();
362
363 @SuppressWarnings("CheckReturnValue")
364 private ImmutableSet<N> validate(Iterable<? extends N> startNodes) {
365 ImmutableSet<N> copy = ImmutableSet.copyOf(startNodes);
366 for (N node : copy) {
367 successorFunction.successors(node); // Will throw if node doesn't exist
368 }
369 return copy;
370 }
371
372 /**
373 * Abstracts away the difference between traversing a graph vs. a tree. For a tree, we just take
374 * the next element from the next non-empty iterator; for graph, we need to loop through the next
375 * non-empty iterator to find first unvisited node.
376 */
377 private abstract static class Traversal<N> {
378 final SuccessorsFunction<N> successorFunction;
379
380 Traversal(SuccessorsFunction<N> successorFunction) {
381 this.successorFunction = successorFunction;
382 }
383
384 static <N> Traversal<N> inGraph(SuccessorsFunction<N> graph) {
385 final Set<N> visited = new HashSet<>();
386 return new Traversal<N>(graph) {
387 @Override
388 @CheckForNull
389 N visitNext(Deque<Iterator<? extends N>> horizon) {
390 Iterator<? extends N> top = horizon.getFirst();
391 while (top.hasNext()) {
392 N element = top.next();
393 // requireNonNull is safe because horizon contains only graph nodes.
394 /*
395 * TODO(cpovirk): Replace these two statements with one (`N element =
396 * requireNonNull(top.next())`) once our checker supports it.
397 *
398 * (The problem is likely
399 * https://github.com/jspecify/nullness-checker-for-checker-framework/blob/61aafa4ae52594830cfc2d61c8b113009dbdb045/src/main/java/com/google/jspecify/nullness/NullSpecAnnotatedTypeFactory.java#L896)
400 */
401 requireNonNull(element);
402 if (visited.add(element)) {
403 return element;
404 }
405 }
406 horizon.removeFirst();
407 return null;
408 }
409 };
410 }
411
412 static <N> Traversal<N> inTree(SuccessorsFunction<N> tree) {
413 return new Traversal<N>(tree) {
414 @CheckForNull
415 @Override
416 N visitNext(Deque<Iterator<? extends N>> horizon) {
417 Iterator<? extends N> top = horizon.getFirst();
418 if (top.hasNext()) {
419 return checkNotNull(top.next());
420 }
421 horizon.removeFirst();
422 return null;
423 }
424 };
425 }
426
427 final Iterator<N> breadthFirst(Iterator<? extends N> startNodes) {
428 return topDown(startNodes, InsertionOrder.BACK);
429 }
430
431 final Iterator<N> preOrder(Iterator<? extends N> startNodes) {
432 return topDown(startNodes, InsertionOrder.FRONT);
433 }
434
435 /**
436 * In top-down traversal, an ancestor node is always traversed before any of its descendant
437 * nodes. The traversal order among descendant nodes (particularly aunts and nieces) are
438 * determined by the {@code InsertionOrder} parameter: nieces are placed at the FRONT before
439 * aunts for pre-order; while in BFS they are placed at the BACK after aunts.
440 */
441 private Iterator<N> topDown(Iterator<? extends N> startNodes, final InsertionOrder order) {
442 final Deque<Iterator<? extends N>> horizon = new ArrayDeque<>();
443 horizon.add(startNodes);
444 return new AbstractIterator<N>() {
445 @Override
446 @CheckForNull
447 protected N computeNext() {
448 do {
449 N next = visitNext(horizon);
450 if (next != null) {
451 Iterator<? extends N> successors = successorFunction.successors(next).iterator();
452 if (successors.hasNext()) {
453 // BFS: horizon.addLast(successors)
454 // Pre-order: horizon.addFirst(successors)
455 order.insertInto(horizon, successors);
456 }
457 return next;
458 }
459 } while (!horizon.isEmpty());
460 return endOfData();
461 }
462 };
463 }
464
465 final Iterator<N> postOrder(Iterator<? extends N> startNodes) {
466 final Deque<N> ancestorStack = new ArrayDeque<>();
467 final Deque<Iterator<? extends N>> horizon = new ArrayDeque<>();
468 horizon.add(startNodes);
469 return new AbstractIterator<N>() {
470 @Override
471 @CheckForNull
472 protected N computeNext() {
473 for (N next = visitNext(horizon); next != null; next = visitNext(horizon)) {
474 Iterator<? extends N> successors = successorFunction.successors(next).iterator();
475 if (!successors.hasNext()) {
476 return next;
477 }
478 horizon.addFirst(successors);
479 ancestorStack.push(next);
480 }
481 return ancestorStack.isEmpty() ? endOfData() : ancestorStack.pop();
482 }
483 };
484 }
485
486 /**
487 * Visits the next node from the top iterator of {@code horizon} and returns the visited node.
488 * Null is returned to indicate reaching the end of the top iterator.
489 *
490 * <p>For example, if horizon is {@code [[a, b], [c, d], [e]]}, {@code visitNext()} will return
491 * {@code [a, b, null, c, d, null, e, null]} sequentially, encoding the topological structure.
492 * (Note, however, that the callers of {@code visitNext()} often insert additional iterators
493 * into {@code horizon} between calls to {@code visitNext()}. This causes them to receive
494 * additional values interleaved with those shown above.)
495 */
496 @CheckForNull
497 abstract N visitNext(Deque<Iterator<? extends N>> horizon);
498 }
499
500 /** Poor man's method reference for {@code Deque::addFirst} and {@code Deque::addLast}. */
501 private enum InsertionOrder {
502 FRONT {
503 @Override
504 <T> void insertInto(Deque<T> deque, T value) {
505 deque.addFirst(value);
506 }
507 },
508 BACK {
509 @Override
510 <T> void insertInto(Deque<T> deque, T value) {
511 deque.addLast(value);
512 }
513 };
514
515 abstract <T> void insertInto(Deque<T> deque, T value);
516 }
517 }