001/* 002 * Copyright (C) 2017 The Guava Authors 003 * 004 * Licensed under the Apache License, Version 2.0 (the "License"); 005 * you may not use this file except in compliance with the License. 006 * You may obtain a copy of the License at 007 * 008 * http://www.apache.org/licenses/LICENSE-2.0 009 * 010 * Unless required by applicable law or agreed to in writing, software 011 * distributed under the License is distributed on an "AS IS" BASIS, 012 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 013 * See the License for the specific language governing permissions and 014 * limitations under the License. 015 */ 016 017package com.google.common.graph; 018 019import static com.google.common.base.Preconditions.checkArgument; 020import static com.google.common.base.Preconditions.checkNotNull; 021 022import com.google.common.annotations.Beta; 023import com.google.common.collect.AbstractIterator; 024import com.google.common.collect.ImmutableSet; 025import com.google.common.collect.Iterables; 026import com.google.common.collect.UnmodifiableIterator; 027import java.util.ArrayDeque; 028import java.util.Deque; 029import java.util.HashSet; 030import java.util.Iterator; 031import java.util.Queue; 032import java.util.Set; 033import org.checkerframework.checker.nullness.qual.Nullable; 034 035/** 036 * An object that can traverse the nodes that are reachable from a specified (set of) start node(s) 037 * using a specified {@link SuccessorsFunction}. 038 * 039 * <p>There are two entry points for creating a {@code Traverser}: {@link 040 * #forTree(SuccessorsFunction)} and {@link #forGraph(SuccessorsFunction)}. You should choose one 041 * based on your answers to the following questions: 042 * 043 * <ol> 044 * <li>Is there only one path to any node that's reachable from any start node? (If so, the graph 045 * to be traversed is a tree or forest even if it is a subgraph of a graph which is neither.) 046 * <li>Are the node objects' implementations of {@code equals()}/{@code hashCode()} <a 047 * href="https://github.com/google/guava/wiki/GraphsExplained#non-recursiveness">recursive</a>? 048 * </ol> 049 * 050 * <p>If your answers are: 051 * 052 * <ul> 053 * <li>(1) "no" and (2) "no", use {@link #forGraph(SuccessorsFunction)}. 054 * <li>(1) "yes" and (2) "yes", use {@link #forTree(SuccessorsFunction)}. 055 * <li>(1) "yes" and (2) "no", you can use either, but {@code forTree()} will be more efficient. 056 * <li>(1) "no" and (2) "yes", <b><i>neither will work</i></b>, but if you transform your node 057 * objects into a non-recursive form, you can use {@code forGraph()}. 058 * </ul> 059 * 060 * @author Jens Nyman 061 * @param <N> Node parameter type 062 * @since 23.1 063 */ 064@Beta 065public abstract class Traverser<N> { 066 067 /** 068 * Creates a new traverser for the given general {@code graph}. 069 * 070 * <p>Traversers created using this method are guaranteed to visit each node reachable from the 071 * start node(s) at most once. 072 * 073 * <p>If you know that no node in {@code graph} is reachable by more than one path from the start 074 * node(s), consider using {@link #forTree(SuccessorsFunction)} instead. 075 * 076 * <p><b>Performance notes</b> 077 * 078 * <ul> 079 * <li>Traversals require <i>O(n)</i> time (where <i>n</i> is the number of nodes reachable from 080 * the start node), assuming that the node objects have <i>O(1)</i> {@code equals()} and 081 * {@code hashCode()} implementations. (See the <a 082 * href="https://github.com/google/guava/wiki/GraphsExplained#elements-must-be-useable-as-map-keys"> 083 * notes on element objects</a> for more information.) 084 * <li>While traversing, the traverser will use <i>O(n)</i> space (where <i>n</i> is the number 085 * of nodes that have thus far been visited), plus <i>O(H)</i> space (where <i>H</i> is the 086 * number of nodes that have been seen but not yet visited, that is, the "horizon"). 087 * </ul> 088 * 089 * @param graph {@link SuccessorsFunction} representing a general graph that may have cycles. 090 */ 091 public static <N> Traverser<N> forGraph(SuccessorsFunction<N> graph) { 092 checkNotNull(graph); 093 return new GraphTraverser<>(graph); 094 } 095 096 /** 097 * Creates a new traverser for a directed acyclic graph that has at most one path from the start 098 * node(s) to any node reachable from the start node(s), and has no paths from any start node to 099 * any other start node, such as a tree or forest. 100 * 101 * <p>{@code forTree()} is especially useful (versus {@code forGraph()}) in cases where the data 102 * structure being traversed is, in addition to being a tree/forest, also defined <a 103 * href="https://github.com/google/guava/wiki/GraphsExplained#non-recursiveness">recursively</a>. 104 * This is because the {@code forTree()}-based implementations don't keep track of visited nodes, 105 * and therefore don't need to call `equals()` or `hashCode()` on the node objects; this saves 106 * both time and space versus traversing the same graph using {@code forGraph()}. 107 * 108 * <p>Providing a graph to be traversed for which there is more than one path from the start 109 * node(s) to any node may lead to: 110 * 111 * <ul> 112 * <li>Traversal not terminating (if the graph has cycles) 113 * <li>Nodes being visited multiple times (if multiple paths exist from any start node to any 114 * node reachable from any start node) 115 * </ul> 116 * 117 * <p><b>Performance notes</b> 118 * 119 * <ul> 120 * <li>Traversals require <i>O(n)</i> time (where <i>n</i> is the number of nodes reachable from 121 * the start node). 122 * <li>While traversing, the traverser will use <i>O(H)</i> space (where <i>H</i> is the number 123 * of nodes that have been seen but not yet visited, that is, the "horizon"). 124 * </ul> 125 * 126 * <p><b>Examples</b> (all edges are directed facing downwards) 127 * 128 * <p>The graph below would be valid input with start nodes of {@code a, f, c}. However, if {@code 129 * b} were <i>also</i> a start node, then there would be multiple paths to reach {@code e} and 130 * {@code h}. 131 * 132 * <pre>{@code 133 * a b c 134 * / \ / \ | 135 * / \ / \ | 136 * d e f g 137 * | 138 * | 139 * h 140 * }</pre> 141 * 142 * <p>. 143 * 144 * <p>The graph below would be a valid input with start nodes of {@code a, f}. However, if {@code 145 * b} were a start node, there would be multiple paths to {@code f}. 146 * 147 * <pre>{@code 148 * a b 149 * / \ / \ 150 * / \ / \ 151 * c d e 152 * \ / 153 * \ / 154 * f 155 * }</pre> 156 * 157 * <p><b>Note on binary trees</b> 158 * 159 * <p>This method can be used to traverse over a binary tree. Given methods {@code 160 * leftChild(node)} and {@code rightChild(node)}, this method can be called as 161 * 162 * <pre>{@code 163 * Traverser.forTree(node -> ImmutableList.of(leftChild(node), rightChild(node))); 164 * }</pre> 165 * 166 * @param tree {@link SuccessorsFunction} representing a directed acyclic graph that has at most 167 * one path between any two nodes 168 */ 169 public static <N> Traverser<N> forTree(SuccessorsFunction<N> tree) { 170 checkNotNull(tree); 171 if (tree instanceof BaseGraph) { 172 checkArgument(((BaseGraph<?>) tree).isDirected(), "Undirected graphs can never be trees."); 173 } 174 if (tree instanceof Network) { 175 checkArgument(((Network<?, ?>) tree).isDirected(), "Undirected networks can never be trees."); 176 } 177 return new TreeTraverser<>(tree); 178 } 179 180 /** 181 * Returns an unmodifiable {@code Iterable} over the nodes reachable from {@code startNode}, in 182 * the order of a breadth-first traversal. That is, all the nodes of depth 0 are returned, then 183 * depth 1, then 2, and so on. 184 * 185 * <p><b>Example:</b> The following graph with {@code startNode} {@code a} would return nodes in 186 * the order {@code abcdef} (assuming successors are returned in alphabetical order). 187 * 188 * <pre>{@code 189 * b ---- a ---- d 190 * | | 191 * | | 192 * e ---- c ---- f 193 * }</pre> 194 * 195 * <p>The behavior of this method is undefined if the nodes, or the topology of the graph, change 196 * while iteration is in progress. 197 * 198 * <p>The returned {@code Iterable} can be iterated over multiple times. Every iterator will 199 * compute its next element on the fly. It is thus possible to limit the traversal to a certain 200 * number of nodes as follows: 201 * 202 * <pre>{@code 203 * Iterables.limit(Traverser.forGraph(graph).breadthFirst(node), maxNumberOfNodes); 204 * }</pre> 205 * 206 * <p>See <a href="https://en.wikipedia.org/wiki/Breadth-first_search">Wikipedia</a> for more 207 * info. 208 * 209 * @throws IllegalArgumentException if {@code startNode} is not an element of the graph 210 */ 211 public abstract Iterable<N> breadthFirst(N startNode); 212 213 /** 214 * Returns an unmodifiable {@code Iterable} over the nodes reachable from any of the {@code 215 * startNodes}, in the order of a breadth-first traversal. This is equivalent to a breadth-first 216 * traversal of a graph with an additional root node whose successors are the listed {@code 217 * startNodes}. 218 * 219 * @throws IllegalArgumentException if any of {@code startNodes} is not an element of the graph 220 * @see #breadthFirst(Object) 221 * @since 24.1 222 */ 223 public abstract Iterable<N> breadthFirst(Iterable<? extends N> startNodes); 224 225 /** 226 * Returns an unmodifiable {@code Iterable} over the nodes reachable from {@code startNode}, in 227 * the order of a depth-first pre-order traversal. "Pre-order" implies that nodes appear in the 228 * {@code Iterable} in the order in which they are first visited. 229 * 230 * <p><b>Example:</b> The following graph with {@code startNode} {@code a} would return nodes in 231 * the order {@code abecfd} (assuming successors are returned in alphabetical order). 232 * 233 * <pre>{@code 234 * b ---- a ---- d 235 * | | 236 * | | 237 * e ---- c ---- f 238 * }</pre> 239 * 240 * <p>The behavior of this method is undefined if the nodes, or the topology of the graph, change 241 * while iteration is in progress. 242 * 243 * <p>The returned {@code Iterable} can be iterated over multiple times. Every iterator will 244 * compute its next element on the fly. It is thus possible to limit the traversal to a certain 245 * number of nodes as follows: 246 * 247 * <pre>{@code 248 * Iterables.limit( 249 * Traverser.forGraph(graph).depthFirstPreOrder(node), maxNumberOfNodes); 250 * }</pre> 251 * 252 * <p>See <a href="https://en.wikipedia.org/wiki/Depth-first_search">Wikipedia</a> for more info. 253 * 254 * @throws IllegalArgumentException if {@code startNode} is not an element of the graph 255 */ 256 public abstract Iterable<N> depthFirstPreOrder(N startNode); 257 258 /** 259 * Returns an unmodifiable {@code Iterable} over the nodes reachable from any of the {@code 260 * startNodes}, in the order of a depth-first pre-order traversal. This is equivalent to a 261 * depth-first pre-order traversal of a graph with an additional root node whose successors are 262 * the listed {@code startNodes}. 263 * 264 * @throws IllegalArgumentException if any of {@code startNodes} is not an element of the graph 265 * @see #depthFirstPreOrder(Object) 266 * @since 24.1 267 */ 268 public abstract Iterable<N> depthFirstPreOrder(Iterable<? extends N> startNodes); 269 270 /** 271 * Returns an unmodifiable {@code Iterable} over the nodes reachable from {@code startNode}, in 272 * the order of a depth-first post-order traversal. "Post-order" implies that nodes appear in the 273 * {@code Iterable} in the order in which they are visited for the last time. 274 * 275 * <p><b>Example:</b> The following graph with {@code startNode} {@code a} would return nodes in 276 * the order {@code fcebda} (assuming successors are returned in alphabetical order). 277 * 278 * <pre>{@code 279 * b ---- a ---- d 280 * | | 281 * | | 282 * e ---- c ---- f 283 * }</pre> 284 * 285 * <p>The behavior of this method is undefined if the nodes, or the topology of the graph, change 286 * while iteration is in progress. 287 * 288 * <p>The returned {@code Iterable} can be iterated over multiple times. Every iterator will 289 * compute its next element on the fly. It is thus possible to limit the traversal to a certain 290 * number of nodes as follows: 291 * 292 * <pre>{@code 293 * Iterables.limit( 294 * Traverser.forGraph(graph).depthFirstPostOrder(node), maxNumberOfNodes); 295 * }</pre> 296 * 297 * <p>See <a href="https://en.wikipedia.org/wiki/Depth-first_search">Wikipedia</a> for more info. 298 * 299 * @throws IllegalArgumentException if {@code startNode} is not an element of the graph 300 */ 301 public abstract Iterable<N> depthFirstPostOrder(N startNode); 302 303 /** 304 * Returns an unmodifiable {@code Iterable} over the nodes reachable from any of the {@code 305 * startNodes}, in the order of a depth-first post-order traversal. This is equivalent to a 306 * depth-first post-order traversal of a graph with an additional root node whose successors are 307 * the listed {@code startNodes}. 308 * 309 * @throws IllegalArgumentException if any of {@code startNodes} is not an element of the graph 310 * @see #depthFirstPostOrder(Object) 311 * @since 24.1 312 */ 313 public abstract Iterable<N> depthFirstPostOrder(Iterable<? extends N> startNodes); 314 315 // Avoid subclasses outside of this class 316 private Traverser() {} 317 318 private static final class GraphTraverser<N> extends Traverser<N> { 319 private final SuccessorsFunction<N> graph; 320 321 GraphTraverser(SuccessorsFunction<N> graph) { 322 this.graph = checkNotNull(graph); 323 } 324 325 @Override 326 public Iterable<N> breadthFirst(final N startNode) { 327 checkNotNull(startNode); 328 return breadthFirst(ImmutableSet.of(startNode)); 329 } 330 331 @Override 332 public Iterable<N> breadthFirst(final Iterable<? extends N> startNodes) { 333 checkNotNull(startNodes); 334 if (Iterables.isEmpty(startNodes)) { 335 return ImmutableSet.of(); 336 } 337 for (N startNode : startNodes) { 338 checkThatNodeIsInGraph(startNode); 339 } 340 return new Iterable<N>() { 341 @Override 342 public Iterator<N> iterator() { 343 return new BreadthFirstIterator(startNodes); 344 } 345 }; 346 } 347 348 @Override 349 public Iterable<N> depthFirstPreOrder(final N startNode) { 350 checkNotNull(startNode); 351 return depthFirstPreOrder(ImmutableSet.of(startNode)); 352 } 353 354 @Override 355 public Iterable<N> depthFirstPreOrder(final Iterable<? extends N> startNodes) { 356 checkNotNull(startNodes); 357 if (Iterables.isEmpty(startNodes)) { 358 return ImmutableSet.of(); 359 } 360 for (N startNode : startNodes) { 361 checkThatNodeIsInGraph(startNode); 362 } 363 return new Iterable<N>() { 364 @Override 365 public Iterator<N> iterator() { 366 return new DepthFirstIterator(startNodes, Order.PREORDER); 367 } 368 }; 369 } 370 371 @Override 372 public Iterable<N> depthFirstPostOrder(final N startNode) { 373 checkNotNull(startNode); 374 return depthFirstPostOrder(ImmutableSet.of(startNode)); 375 } 376 377 @Override 378 public Iterable<N> depthFirstPostOrder(final Iterable<? extends N> startNodes) { 379 checkNotNull(startNodes); 380 if (Iterables.isEmpty(startNodes)) { 381 return ImmutableSet.of(); 382 } 383 for (N startNode : startNodes) { 384 checkThatNodeIsInGraph(startNode); 385 } 386 return new Iterable<N>() { 387 @Override 388 public Iterator<N> iterator() { 389 return new DepthFirstIterator(startNodes, Order.POSTORDER); 390 } 391 }; 392 } 393 394 @SuppressWarnings("CheckReturnValue") 395 private void checkThatNodeIsInGraph(N startNode) { 396 // successors() throws an IllegalArgumentException for nodes that are not an element of the 397 // graph. 398 graph.successors(startNode); 399 } 400 401 private final class BreadthFirstIterator extends UnmodifiableIterator<N> { 402 private final Queue<N> queue = new ArrayDeque<>(); 403 private final Set<N> visited = new HashSet<>(); 404 405 BreadthFirstIterator(Iterable<? extends N> roots) { 406 for (N root : roots) { 407 // add all roots to the queue, skipping duplicates 408 if (visited.add(root)) { 409 queue.add(root); 410 } 411 } 412 } 413 414 @Override 415 public boolean hasNext() { 416 return !queue.isEmpty(); 417 } 418 419 @Override 420 public N next() { 421 N current = queue.remove(); 422 for (N neighbor : graph.successors(current)) { 423 if (visited.add(neighbor)) { 424 queue.add(neighbor); 425 } 426 } 427 return current; 428 } 429 } 430 431 private final class DepthFirstIterator extends AbstractIterator<N> { 432 private final Deque<NodeAndSuccessors> stack = new ArrayDeque<>(); 433 private final Set<N> visited = new HashSet<>(); 434 private final Order order; 435 436 DepthFirstIterator(Iterable<? extends N> roots, Order order) { 437 stack.push(new NodeAndSuccessors(null, roots)); 438 this.order = order; 439 } 440 441 @Override 442 protected N computeNext() { 443 while (true) { 444 if (stack.isEmpty()) { 445 return endOfData(); 446 } 447 NodeAndSuccessors nodeAndSuccessors = stack.getFirst(); 448 boolean firstVisit = visited.add(nodeAndSuccessors.node); 449 boolean lastVisit = !nodeAndSuccessors.successorIterator.hasNext(); 450 boolean produceNode = 451 (firstVisit && order == Order.PREORDER) || (lastVisit && order == Order.POSTORDER); 452 if (lastVisit) { 453 stack.pop(); 454 } else { 455 // we need to push a neighbor, but only if we haven't already seen it 456 N successor = nodeAndSuccessors.successorIterator.next(); 457 if (!visited.contains(successor)) { 458 stack.push(withSuccessors(successor)); 459 } 460 } 461 if (produceNode && nodeAndSuccessors.node != null) { 462 return nodeAndSuccessors.node; 463 } 464 } 465 } 466 467 NodeAndSuccessors withSuccessors(N node) { 468 return new NodeAndSuccessors(node, graph.successors(node)); 469 } 470 471 /** A simple tuple of a node and a partially iterated {@link Iterator} of its successors. */ 472 private final class NodeAndSuccessors { 473 final @Nullable N node; 474 final Iterator<? extends N> successorIterator; 475 476 NodeAndSuccessors(@Nullable N node, Iterable<? extends N> successors) { 477 this.node = node; 478 this.successorIterator = successors.iterator(); 479 } 480 } 481 } 482 } 483 484 private static final class TreeTraverser<N> extends Traverser<N> { 485 private final SuccessorsFunction<N> tree; 486 487 TreeTraverser(SuccessorsFunction<N> tree) { 488 this.tree = checkNotNull(tree); 489 } 490 491 @Override 492 public Iterable<N> breadthFirst(final N startNode) { 493 checkNotNull(startNode); 494 return breadthFirst(ImmutableSet.of(startNode)); 495 } 496 497 @Override 498 public Iterable<N> breadthFirst(final Iterable<? extends N> startNodes) { 499 checkNotNull(startNodes); 500 if (Iterables.isEmpty(startNodes)) { 501 return ImmutableSet.of(); 502 } 503 for (N startNode : startNodes) { 504 checkThatNodeIsInTree(startNode); 505 } 506 return new Iterable<N>() { 507 @Override 508 public Iterator<N> iterator() { 509 return new BreadthFirstIterator(startNodes); 510 } 511 }; 512 } 513 514 @Override 515 public Iterable<N> depthFirstPreOrder(final N startNode) { 516 checkNotNull(startNode); 517 return depthFirstPreOrder(ImmutableSet.of(startNode)); 518 } 519 520 @Override 521 public Iterable<N> depthFirstPreOrder(final Iterable<? extends N> startNodes) { 522 checkNotNull(startNodes); 523 if (Iterables.isEmpty(startNodes)) { 524 return ImmutableSet.of(); 525 } 526 for (N node : startNodes) { 527 checkThatNodeIsInTree(node); 528 } 529 return new Iterable<N>() { 530 @Override 531 public Iterator<N> iterator() { 532 return new DepthFirstPreOrderIterator(startNodes); 533 } 534 }; 535 } 536 537 @Override 538 public Iterable<N> depthFirstPostOrder(final N startNode) { 539 checkNotNull(startNode); 540 return depthFirstPostOrder(ImmutableSet.of(startNode)); 541 } 542 543 @Override 544 public Iterable<N> depthFirstPostOrder(final Iterable<? extends N> startNodes) { 545 checkNotNull(startNodes); 546 if (Iterables.isEmpty(startNodes)) { 547 return ImmutableSet.of(); 548 } 549 for (N startNode : startNodes) { 550 checkThatNodeIsInTree(startNode); 551 } 552 return new Iterable<N>() { 553 @Override 554 public Iterator<N> iterator() { 555 return new DepthFirstPostOrderIterator(startNodes); 556 } 557 }; 558 } 559 560 @SuppressWarnings("CheckReturnValue") 561 private void checkThatNodeIsInTree(N startNode) { 562 // successors() throws an IllegalArgumentException for nodes that are not an element of the 563 // graph. 564 tree.successors(startNode); 565 } 566 567 private final class BreadthFirstIterator extends UnmodifiableIterator<N> { 568 private final Queue<N> queue = new ArrayDeque<>(); 569 570 BreadthFirstIterator(Iterable<? extends N> roots) { 571 for (N root : roots) { 572 queue.add(root); 573 } 574 } 575 576 @Override 577 public boolean hasNext() { 578 return !queue.isEmpty(); 579 } 580 581 @Override 582 public N next() { 583 N current = queue.remove(); 584 Iterables.addAll(queue, tree.successors(current)); 585 return current; 586 } 587 } 588 589 private final class DepthFirstPreOrderIterator extends UnmodifiableIterator<N> { 590 private final Deque<Iterator<? extends N>> stack = new ArrayDeque<>(); 591 592 DepthFirstPreOrderIterator(Iterable<? extends N> roots) { 593 stack.addLast(roots.iterator()); 594 } 595 596 @Override 597 public boolean hasNext() { 598 return !stack.isEmpty(); 599 } 600 601 @Override 602 public N next() { 603 Iterator<? extends N> iterator = stack.getLast(); // throws NoSuchElementException if empty 604 N result = checkNotNull(iterator.next()); 605 if (!iterator.hasNext()) { 606 stack.removeLast(); 607 } 608 Iterator<? extends N> childIterator = tree.successors(result).iterator(); 609 if (childIterator.hasNext()) { 610 stack.addLast(childIterator); 611 } 612 return result; 613 } 614 } 615 616 private final class DepthFirstPostOrderIterator extends AbstractIterator<N> { 617 private final ArrayDeque<NodeAndChildren> stack = new ArrayDeque<>(); 618 619 DepthFirstPostOrderIterator(Iterable<? extends N> roots) { 620 stack.addLast(new NodeAndChildren(null, roots)); 621 } 622 623 @Override 624 protected N computeNext() { 625 while (!stack.isEmpty()) { 626 NodeAndChildren top = stack.getLast(); 627 if (top.childIterator.hasNext()) { 628 N child = top.childIterator.next(); 629 stack.addLast(withChildren(child)); 630 } else { 631 stack.removeLast(); 632 if (top.node != null) { 633 return top.node; 634 } 635 } 636 } 637 return endOfData(); 638 } 639 640 NodeAndChildren withChildren(N node) { 641 return new NodeAndChildren(node, tree.successors(node)); 642 } 643 644 /** A simple tuple of a node and a partially iterated {@link Iterator} of its children. */ 645 private final class NodeAndChildren { 646 final @Nullable N node; 647 final Iterator<? extends N> childIterator; 648 649 NodeAndChildren(@Nullable N node, Iterable<? extends N> children) { 650 this.node = node; 651 this.childIterator = children.iterator(); 652 } 653 } 654 } 655 } 656 657 private enum Order { 658 PREORDER, 659 POSTORDER 660 } 661}