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.compatqual.NullableDecl;
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        @NullableDecl final N node;
474        final Iterator<? extends N> successorIterator;
475
476        NodeAndSuccessors(@NullableDecl 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        @NullableDecl final N node;
647        final Iterator<? extends N> childIterator;
648
649        NodeAndChildren(@NullableDecl 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}