https://github.com/google/guava/guava: Guava is a suite of core and expanded libraries that include utility classes, google's collections, io classes, and much much more. 
/*
 * Copyright (C) 2017 The Guava Authors
 *
 * Licensed under the Apache License, Version 2.0 (the "License");
 * you may not use this file except in compliance with the License.
 * You may obtain a copy of the License at
 *
 * http://www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS,
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 * See the License for the specific language governing permissions and
 * limitations under the License.
 */

package com.google.common.graph;

import static com.google.common.base.Preconditions.checkArgument;
import static com.google.common.base.Preconditions.checkNotNull;

import com.google.common.annotations.Beta;
import com.google.common.collect.AbstractIterator;
import com.google.common.collect.ImmutableSet;
import com.google.errorprone.annotations.DoNotMock;
import java.util.ArrayDeque;
import java.util.Deque;
import java.util.HashSet;
import java.util.Iterator;
import java.util.Set;
import org.checkerframework.checker.nullness.qual.Nullable;


An object that can traverse the nodes that are reachable from a specified (set of) start node(s) using a specified SuccessorsFunction. 
There are two entry points for creating a Traverser: forTree(SuccessorsFunction<Object>) and forGraph(SuccessorsFunction<Object>). You should choose one based on your answers to the following questions: 
    
  
  1. Is there only one path to any node that's reachable from any start node? (If so, the graph
      to be traversed is a tree or forest even if it is a subgraph of a graph which is neither.)
  
  2. Are the node objects' implementations of equals()/hashCode() recursive?



If your answers are:



Author:Jens Nyman
Type parameters:
  • <N> – Node parameter type
Since:23.1
/**
 * An object that can traverse the nodes that are reachable from a specified (set of) start node(s)
 * using a specified {@link SuccessorsFunction}.
 *
 * <p>There are two entry points for creating a {@code Traverser}: {@link
 * #forTree(SuccessorsFunction)} and {@link #forGraph(SuccessorsFunction)}. You should choose one
 * based on your answers to the following questions:
 *
 * <ol>
 *   <li>Is there only one path to any node that's reachable from any start node? (If so, the graph
 *       to be traversed is a tree or forest even if it is a subgraph of a graph which is neither.)
 *   <li>Are the node objects' implementations of {@code equals()}/{@code hashCode()} <a
 *       href="https://github.com/google/guava/wiki/GraphsExplained#non-recursiveness">recursive</a>?
 * </ol>
 *
 * <p>If your answers are:
 *
 * <ul>
 *   <li>(1) "no" and (2) "no", use {@link #forGraph(SuccessorsFunction)}.
 *   <li>(1) "yes" and (2) "yes", use {@link #forTree(SuccessorsFunction)}.
 *   <li>(1) "yes" and (2) "no", you can use either, but {@code forTree()} will be more efficient.
 *   <li>(1) "no" and (2) "yes", <b><i>neither will work</i></b>, but if you transform your node
 *       objects into a non-recursive form, you can use {@code forGraph()}.
 * </ul>
 *
 * @author Jens Nyman
 * @param <N> Node parameter type
 * @since 23.1
 */
@Beta
@DoNotMock(
    "Call forGraph or forTree, passing a lambda or a Graph with the desired edges (built with"
        + " GraphBuilder)")
public abstract class Traverser<N> {
  private final SuccessorsFunction<N> successorFunction;

  private Traverser(SuccessorsFunction<N> successorFunction) {
    this.successorFunction = checkNotNull(successorFunction);
  }

  
Creates a new traverser for the given general graph. 
Traversers created using this method are guaranteed to visit each node reachable from the
start node(s) at most once.

If you know that no node in graph is reachable by more than one path from the start node(s), consider using forTree(SuccessorsFunction<Object>) instead. 
Performance notes

    
  
  • Traversals require O(n) time (where n is the number of nodes reachable from
      the start node), assuming that the node objects have O(1) equals() and hashCode() implementations. (See the 
      notes on element objects for more information.)
  
  • While traversing, the traverser will use O(n) space (where n is the number
      of nodes that have thus far been visited), plus O(H) space (where H is the
      number of nodes that have been seen but not yet visited, that is, the "horizon").



Params:
/**
   * Creates a new traverser for the given general {@code graph}.
   *
   * <p>Traversers created using this method are guaranteed to visit each node reachable from the
   * start node(s) at most once.
   *
   * <p>If you know that no node in {@code graph} is reachable by more than one path from the start
   * node(s), consider using {@link #forTree(SuccessorsFunction)} instead.
   *
   * <p><b>Performance notes</b>
   *
   * <ul>
   *   <li>Traversals require <i>O(n)</i> time (where <i>n</i> is the number of nodes reachable from
   *       the start node), assuming that the node objects have <i>O(1)</i> {@code equals()} and
   *       {@code hashCode()} implementations. (See the <a
   *       href="https://github.com/google/guava/wiki/GraphsExplained#elements-must-be-useable-as-map-keys">
   *       notes on element objects</a> for more information.)
   *   <li>While traversing, the traverser will use <i>O(n)</i> space (where <i>n</i> is the number
   *       of nodes that have thus far been visited), plus <i>O(H)</i> space (where <i>H</i> is the
   *       number of nodes that have been seen but not yet visited, that is, the "horizon").
   * </ul>
   *
   * @param graph {@link SuccessorsFunction} representing a general graph that may have cycles.
   */
  public static <N> Traverser<N> forGraph(final SuccessorsFunction<N> graph) {
    return new Traverser<N>(graph) {
      @Override
      Traversal<N> newTraversal() {
        return Traversal.inGraph(graph);
      }
    };
  }

  
Creates a new traverser for a directed acyclic graph that has at most one path from the start
node(s) to any node reachable from the start node(s), and has no paths from any start node to
any other start node, such as a tree or forest.

forTree() is especially useful (versus forGraph()) in cases where the data structure being traversed is, in addition to being a tree/forest, also defined recursively. This is because the forTree()-based implementations don't keep track of visited nodes, and therefore don't need to call `equals()` or `hashCode()` on the node objects; this saves both time and space versus traversing the same graph using forGraph(). 
Providing a graph to be traversed for which there is more than one path from the start
node(s) to any node may lead to:

    
  
  • Traversal not terminating (if the graph has cycles)
  
  • Nodes being visited multiple times (if multiple paths exist from any start node to any
      node reachable from any start node)



Performance notes

    
  
  • Traversals require O(n) time (where n is the number of nodes reachable from
      the start node).
  
  • While traversing, the traverser will use O(H) space (where H is the number
      of nodes that have been seen but not yet visited, that is, the "horizon").



Examples (all edges are directed facing downwards)

The graph below would be valid input with start nodes of a, f, c. However, if 
b were also a start node, then there would be multiple paths to reach e and h. 

   a     b      c
  / \   / \     |
 /   \ /   \    |
d     e     f   g
      |
      |
      h



.

The graph below would be a valid input with start nodes of a, f. However, if 
b were a start node, there would be multiple paths to f. 

   a     b
  / \   / \
 /   \ /   \
c     d     e
       \   /
        \ /
         f



Note on binary trees

This method can be used to traverse over a binary tree. Given methods 
leftChild(node) and rightChild(node), this method can be called as 

Traverser.forTree(node -> ImmutableList.of(leftChild(node), rightChild(node)));



Params:
  • tree – SuccessorsFunction representing a directed acyclic graph that has at most one path between any two nodes
/**
   * Creates a new traverser for a directed acyclic graph that has at most one path from the start
   * node(s) to any node reachable from the start node(s), and has no paths from any start node to
   * any other start node, such as a tree or forest.
   *
   * <p>{@code forTree()} is especially useful (versus {@code forGraph()}) in cases where the data
   * structure being traversed is, in addition to being a tree/forest, also defined <a
   * href="https://github.com/google/guava/wiki/GraphsExplained#non-recursiveness">recursively</a>.
   * This is because the {@code forTree()}-based implementations don't keep track of visited nodes,
   * and therefore don't need to call `equals()` or `hashCode()` on the node objects; this saves
   * both time and space versus traversing the same graph using {@code forGraph()}.
   *
   * <p>Providing a graph to be traversed for which there is more than one path from the start
   * node(s) to any node may lead to:
   *
   * <ul>
   *   <li>Traversal not terminating (if the graph has cycles)
   *   <li>Nodes being visited multiple times (if multiple paths exist from any start node to any
   *       node reachable from any start node)
   * </ul>
   *
   * <p><b>Performance notes</b>
   *
   * <ul>
   *   <li>Traversals require <i>O(n)</i> time (where <i>n</i> is the number of nodes reachable from
   *       the start node).
   *   <li>While traversing, the traverser will use <i>O(H)</i> space (where <i>H</i> is the number
   *       of nodes that have been seen but not yet visited, that is, the "horizon").
   * </ul>
   *
   * <p><b>Examples</b> (all edges are directed facing downwards)
   *
   * <p>The graph below would be valid input with start nodes of {@code a, f, c}. However, if {@code
   * b} were <i>also</i> a start node, then there would be multiple paths to reach {@code e} and
   * {@code h}.
   *
   * <pre>{@code
   *    a     b      c
   *   / \   / \     |
   *  /   \ /   \    |
   * d     e     f   g
   *       |
   *       |
   *       h
   * }</pre>
   *
   * <p>.
   *
   * <p>The graph below would be a valid input with start nodes of {@code a, f}. However, if {@code
   * b} were a start node, there would be multiple paths to {@code f}.
   *
   * <pre>{@code
   *    a     b
   *   / \   / \
   *  /   \ /   \
   * c     d     e
   *        \   /
   *         \ /
   *          f
   * }</pre>
   *
   * <p><b>Note on binary trees</b>
   *
   * <p>This method can be used to traverse over a binary tree. Given methods {@code
   * leftChild(node)} and {@code rightChild(node)}, this method can be called as
   *
   * <pre>{@code
   * Traverser.forTree(node -> ImmutableList.of(leftChild(node), rightChild(node)));
   * }</pre>
   *
   * @param tree {@link SuccessorsFunction} representing a directed acyclic graph that has at most
   *     one path between any two nodes
   */
  public static <N> Traverser<N> forTree(final SuccessorsFunction<N> tree) {
    if (tree instanceof BaseGraph) {
      checkArgument(((BaseGraph<?>) tree).isDirected(), "Undirected graphs can never be trees.");
    }
    if (tree instanceof Network) {
      checkArgument(((Network<?, ?>) tree).isDirected(), "Undirected networks can never be trees.");
    }
    return new Traverser<N>(tree) {
      @Override
      Traversal<N> newTraversal() {
        return Traversal.inTree(tree);
      }
    };
  }

  
Returns an unmodifiable Iterable over the nodes reachable from startNode, in the order of a breadth-first traversal. That is, all the nodes of depth 0 are returned, then depth 1, then 2, and so on. 
Example: The following graph with startNode a would return nodes in the order abcdef (assuming successors are returned in alphabetical order). 

b ---- a ---- d
|      |
|      |
e ---- c ---- f



The behavior of this method is undefined if the nodes, or the topology of the graph, change
while iteration is in progress.

The returned Iterable can be iterated over multiple times. Every iterator will compute its next element on the fly. It is thus possible to limit the traversal to a certain number of nodes as follows: 

Iterables.limit(Traverser.forGraph(graph).breadthFirst(node), maxNumberOfNodes);



See Wikipedia for more
info.

Throws:
/**
   * Returns an unmodifiable {@code Iterable} over the nodes reachable from {@code startNode}, in
   * the order of a breadth-first traversal. That is, all the nodes of depth 0 are returned, then
   * depth 1, then 2, and so on.
   *
   * <p><b>Example:</b> The following graph with {@code startNode} {@code a} would return nodes in
   * the order {@code abcdef} (assuming successors are returned in alphabetical order).
   *
   * <pre>{@code
   * b ---- a ---- d
   * |      |
   * |      |
   * e ---- c ---- f
   * }</pre>
   *
   * <p>The behavior of this method is undefined if the nodes, or the topology of the graph, change
   * while iteration is in progress.
   *
   * <p>The returned {@code Iterable} can be iterated over multiple times. Every iterator will
   * compute its next element on the fly. It is thus possible to limit the traversal to a certain
   * number of nodes as follows:
   *
   * <pre>{@code
   * Iterables.limit(Traverser.forGraph(graph).breadthFirst(node), maxNumberOfNodes);
   * }</pre>
   *
   * <p>See <a href="https://en.wikipedia.org/wiki/Breadth-first_search">Wikipedia</a> for more
   * info.
   *
   * @throws IllegalArgumentException if {@code startNode} is not an element of the graph
   */
  public final Iterable<N> breadthFirst(N startNode) {
    return breadthFirst(ImmutableSet.of(startNode));
  }

  
Returns an unmodifiable Iterable over the nodes reachable from any of the 
startNodes, in the order of a breadth-first traversal. This is equivalent to a breadth-first traversal of a graph with an additional root node whose successors are the listed 
startNodes. 
Throws:
See Also:
Since:24.1
/**
   * Returns an unmodifiable {@code Iterable} over the nodes reachable from any of the {@code
   * startNodes}, in the order of a breadth-first traversal. This is equivalent to a breadth-first
   * traversal of a graph with an additional root node whose successors are the listed {@code
   * startNodes}.
   *
   * @throws IllegalArgumentException if any of {@code startNodes} is not an element of the graph
   * @see #breadthFirst(Object)
   * @since 24.1
   */
  public final Iterable<N> breadthFirst(Iterable<? extends N> startNodes) {
    final ImmutableSet<N> validated = validate(startNodes);
    return new Iterable<N>() {
      @Override
      public Iterator<N> iterator() {
        return newTraversal().breadthFirst(validated.iterator());
      }
    };
  }

  
Returns an unmodifiable Iterable over the nodes reachable from startNode, in the order of a depth-first pre-order traversal. "Pre-order" implies that nodes appear in the Iterable in the order in which they are first visited. 
Example: The following graph with startNode a would return nodes in the order abecfd (assuming successors are returned in alphabetical order). 

b ---- a ---- d
|      |
|      |
e ---- c ---- f



The behavior of this method is undefined if the nodes, or the topology of the graph, change
while iteration is in progress.

The returned Iterable can be iterated over multiple times. Every iterator will compute its next element on the fly. It is thus possible to limit the traversal to a certain number of nodes as follows: 

Iterables.limit(
    Traverser.forGraph(graph).depthFirstPreOrder(node), maxNumberOfNodes);



See Wikipedia for more info.

Throws:
/**
   * Returns an unmodifiable {@code Iterable} over the nodes reachable from {@code startNode}, in
   * the order of a depth-first pre-order traversal. "Pre-order" implies that nodes appear in the
   * {@code Iterable} in the order in which they are first visited.
   *
   * <p><b>Example:</b> The following graph with {@code startNode} {@code a} would return nodes in
   * the order {@code abecfd} (assuming successors are returned in alphabetical order).
   *
   * <pre>{@code
   * b ---- a ---- d
   * |      |
   * |      |
   * e ---- c ---- f
   * }</pre>
   *
   * <p>The behavior of this method is undefined if the nodes, or the topology of the graph, change
   * while iteration is in progress.
   *
   * <p>The returned {@code Iterable} can be iterated over multiple times. Every iterator will
   * compute its next element on the fly. It is thus possible to limit the traversal to a certain
   * number of nodes as follows:
   *
   * <pre>{@code
   * Iterables.limit(
   *     Traverser.forGraph(graph).depthFirstPreOrder(node), maxNumberOfNodes);
   * }</pre>
   *
   * <p>See <a href="https://en.wikipedia.org/wiki/Depth-first_search">Wikipedia</a> for more info.
   *
   * @throws IllegalArgumentException if {@code startNode} is not an element of the graph
   */
  public final Iterable<N> depthFirstPreOrder(N startNode) {
    return depthFirstPreOrder(ImmutableSet.of(startNode));
  }

  
Returns an unmodifiable Iterable over the nodes reachable from any of the 
startNodes, in the order of a depth-first pre-order traversal. This is equivalent to a depth-first pre-order traversal of a graph with an additional root node whose successors are the listed startNodes. 
Throws:
See Also:
Since:24.1
/**
   * Returns an unmodifiable {@code Iterable} over the nodes reachable from any of the {@code
   * startNodes}, in the order of a depth-first pre-order traversal. This is equivalent to a
   * depth-first pre-order traversal of a graph with an additional root node whose successors are
   * the listed {@code startNodes}.
   *
   * @throws IllegalArgumentException if any of {@code startNodes} is not an element of the graph
   * @see #depthFirstPreOrder(Object)
   * @since 24.1
   */
  public final Iterable<N> depthFirstPreOrder(Iterable<? extends N> startNodes) {
    final ImmutableSet<N> validated = validate(startNodes);
    return new Iterable<N>() {
      @Override
      public Iterator<N> iterator() {
        return newTraversal().preOrder(validated.iterator());
      }
    };
  }

  
Returns an unmodifiable Iterable over the nodes reachable from startNode, in the order of a depth-first post-order traversal. "Post-order" implies that nodes appear in the Iterable in the order in which they are visited for the last time. 
Example: The following graph with startNode a would return nodes in the order fcebda (assuming successors are returned in alphabetical order). 

b ---- a ---- d
|      |
|      |
e ---- c ---- f



The behavior of this method is undefined if the nodes, or the topology of the graph, change
while iteration is in progress.

The returned Iterable can be iterated over multiple times. Every iterator will compute its next element on the fly. It is thus possible to limit the traversal to a certain number of nodes as follows: 

Iterables.limit(
    Traverser.forGraph(graph).depthFirstPostOrder(node), maxNumberOfNodes);



See Wikipedia for more info.

Throws:
/**
   * Returns an unmodifiable {@code Iterable} over the nodes reachable from {@code startNode}, in
   * the order of a depth-first post-order traversal. "Post-order" implies that nodes appear in the
   * {@code Iterable} in the order in which they are visited for the last time.
   *
   * <p><b>Example:</b> The following graph with {@code startNode} {@code a} would return nodes in
   * the order {@code fcebda} (assuming successors are returned in alphabetical order).
   *
   * <pre>{@code
   * b ---- a ---- d
   * |      |
   * |      |
   * e ---- c ---- f
   * }</pre>
   *
   * <p>The behavior of this method is undefined if the nodes, or the topology of the graph, change
   * while iteration is in progress.
   *
   * <p>The returned {@code Iterable} can be iterated over multiple times. Every iterator will
   * compute its next element on the fly. It is thus possible to limit the traversal to a certain
   * number of nodes as follows:
   *
   * <pre>{@code
   * Iterables.limit(
   *     Traverser.forGraph(graph).depthFirstPostOrder(node), maxNumberOfNodes);
   * }</pre>
   *
   * <p>See <a href="https://en.wikipedia.org/wiki/Depth-first_search">Wikipedia</a> for more info.
   *
   * @throws IllegalArgumentException if {@code startNode} is not an element of the graph
   */
  public final Iterable<N> depthFirstPostOrder(N startNode) {
    return depthFirstPostOrder(ImmutableSet.of(startNode));
  }

  
Returns an unmodifiable Iterable over the nodes reachable from any of the 
startNodes, in the order of a depth-first post-order traversal. This is equivalent to a depth-first post-order traversal of a graph with an additional root node whose successors are the listed startNodes. 
Throws:
See Also:
Since:24.1
/**
   * Returns an unmodifiable {@code Iterable} over the nodes reachable from any of the {@code
   * startNodes}, in the order of a depth-first post-order traversal. This is equivalent to a
   * depth-first post-order traversal of a graph with an additional root node whose successors are
   * the listed {@code startNodes}.
   *
   * @throws IllegalArgumentException if any of {@code startNodes} is not an element of the graph
   * @see #depthFirstPostOrder(Object)
   * @since 24.1
   */
  public final Iterable<N> depthFirstPostOrder(Iterable<? extends N> startNodes) {
    final ImmutableSet<N> validated = validate(startNodes);
    return new Iterable<N>() {
      @Override
      public Iterator<N> iterator() {
        return newTraversal().postOrder(validated.iterator());
      }
    };
  }

  abstract Traversal<N> newTraversal();

  @SuppressWarnings("CheckReturnValue")
  private ImmutableSet<N> validate(Iterable<? extends N> startNodes) {
    ImmutableSet<N> copy = ImmutableSet.copyOf(startNodes);
    for (N node : copy) {
      successorFunction.successors(node); // Will throw if node doesn't exist
    }
    return copy;
  }

  
Abstracts away the difference between traversing a graph vs. a tree. For a tree, we just take
the next element from the next non-empty iterator; for graph, we need to loop through the next
non-empty iterator to find first unvisited node.

/**
   * Abstracts away the difference between traversing a graph vs. a tree. For a tree, we just take
   * the next element from the next non-empty iterator; for graph, we need to loop through the next
   * non-empty iterator to find first unvisited node.
   */
  private abstract static class Traversal<N> {
    final SuccessorsFunction<N> successorFunction;

    Traversal(SuccessorsFunction<N> successorFunction) {
      this.successorFunction = successorFunction;
    }

    static <N> Traversal<N> inGraph(SuccessorsFunction<N> graph) {
      final Set<N> visited = new HashSet<>();
      return new Traversal<N>(graph) {
        @Override
        N visitNext(Deque<Iterator<? extends N>> horizon) {
          Iterator<? extends N> top = horizon.getFirst();
          while (top.hasNext()) {
            N element = checkNotNull(top.next());
            if (visited.add(element)) {
              return element;
            }
          }
          horizon.removeFirst();
          return null;
        }
      };
    }

    static <N> Traversal<N> inTree(SuccessorsFunction<N> tree) {
      return new Traversal<N>(tree) {
        @Override
        N visitNext(Deque<Iterator<? extends N>> horizon) {
          Iterator<? extends N> top = horizon.getFirst();
          if (top.hasNext()) {
            return checkNotNull(top.next());
          }
          horizon.removeFirst();
          return null;
        }
      };
    }

    final Iterator<N> breadthFirst(Iterator<? extends N> startNodes) {
      return topDown(startNodes, InsertionOrder.BACK);
    }

    final Iterator<N> preOrder(Iterator<? extends N> startNodes) {
      return topDown(startNodes, InsertionOrder.FRONT);
    }

    
In top-down traversal, an ancestor node is always traversed before any of its descendant nodes. The traversal order among descendant nodes (particularly aunts and nieces) are determined by the InsertionOrder parameter: nieces are placed at the FRONT before aunts for pre-order; while in BFS they are placed at the BACK after aunts. 
/**
     * In top-down traversal, an ancestor node is always traversed before any of its descendant
     * nodes. The traversal order among descendant nodes (particularly aunts and nieces) are
     * determined by the {@code InsertionOrder} parameter: nieces are placed at the FRONT before
     * aunts for pre-order; while in BFS they are placed at the BACK after aunts.
     */
    private Iterator<N> topDown(Iterator<? extends N> startNodes, final InsertionOrder order) {
      final Deque<Iterator<? extends N>> horizon = new ArrayDeque<>();
      horizon.add(startNodes);
      return new AbstractIterator<N>() {
        @Override
        protected N computeNext() {
          do {
            N next = visitNext(horizon);
            if (next != null) {
              Iterator<? extends N> successors = successorFunction.successors(next).iterator();
              if (successors.hasNext()) {
                // BFS: horizon.addLast(successors)
                // Pre-order: horizon.addFirst(successors)
                order.insertInto(horizon, successors);
              }
              return next;
            }
          } while (!horizon.isEmpty());
          return endOfData();
        }
      };
    }

    final Iterator<N> postOrder(Iterator<? extends N> startNodes) {
      final Deque<N> ancestorStack = new ArrayDeque<>();
      final Deque<Iterator<? extends N>> horizon = new ArrayDeque<>();
      horizon.add(startNodes);
      return new AbstractIterator<N>() {
        @Override
        protected N computeNext() {
          for (N next = visitNext(horizon); next != null; next = visitNext(horizon)) {
            Iterator<? extends N> successors = successorFunction.successors(next).iterator();
            if (!successors.hasNext()) {
              return next;
            }
            horizon.addFirst(successors);
            ancestorStack.push(next);
          }
          return ancestorStack.isEmpty() ? endOfData() : ancestorStack.pop();
        }
      };
    }

    
Visits the next node from the top iterator of horizon and returns the visited node. Null is returned to indicate reaching the end of the top iterator. 
For example, if horizon is [[a, b], [c, d], [e]], visitNext() will return [a, b, null, c, d, null, e, null] sequentially, encoding the topological structure. (Note, however, that the callers of visitNext() often insert additional iterators into horizon between calls to visitNext(). This causes them to receive additional values interleaved with those shown above.) 
/**
     * Visits the next node from the top iterator of {@code horizon} and returns the visited node.
     * Null is returned to indicate reaching the end of the top iterator.
     *
     * <p>For example, if horizon is {@code [[a, b], [c, d], [e]]}, {@code visitNext()} will return
     * {@code [a, b, null, c, d, null, e, null]} sequentially, encoding the topological structure.
     * (Note, however, that the callers of {@code visitNext()} often insert additional iterators
     * into {@code horizon} between calls to {@code visitNext()}. This causes them to receive
     * additional values interleaved with those shown above.)
     */
    @Nullable
    abstract N visitNext(Deque<Iterator<? extends N>> horizon);
  }

  
Poor man's method reference for Deque::addFirst and Deque::addLast. 
/** Poor man's method reference for {@code Deque::addFirst} and {@code Deque::addLast}. */
  private enum InsertionOrder {
    FRONT {
      @Override
      <T> void insertInto(Deque<T> deque, T value) {
        deque.addFirst(value);
      }
    },
    BACK {
      @Override
      <T> void insertInto(Deque<T> deque, T value) {
        deque.addLast(value);
      }
    };

    abstract <T> void insertInto(Deque<T> deque, T value);
  }
}