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