public abstract class ConsumingTraverser<N> extends Object
Consumer-based graph traversers.
Implements various graph traversals for graphs represented by ForEachSuccessorFunction. This may be desirable to use instead of Abstract*Traversals in
cases where the overhead of buffering node dependencies in streams/iterables/collections needs to
be avoided (as node dependencies are discovered/consumed without per-node buffering).
The traversals generally avoid extra bookkeeping to detect graph cycles, and so may silently produce undefined results in this case.
| Constructor and Description |
|---|
ConsumingTraverser() |
| Modifier and Type | Method and Description |
|---|---|
static <N> ConsumingTraverser<N> |
breadthFirst(Iterable<? extends N> startNodes,
ForEachSuccessorFunction<N> successors)
Consume nodes via
consumer, starting from startNodes, in a breadth-first walk
of the graph. |
abstract void |
forEach(java.util.function.Consumer<N> consumer) |
<E extends Exception> |
forEachThrowing(ThrowingConsumer<N,E> consumer) |
static <N> ConsumingTraverser<N> |
topologicallySorted(Iterable<? extends N> startNodes,
ForEachSuccessorFunction<N> successors)
Consume nodes via
consumer, starting from startNodes, in a topologically sorted
order. |
public abstract void forEach(java.util.function.Consumer<N> consumer)
public final <E extends Exception> void forEachThrowing(ThrowingConsumer<N,E> consumer) throws E extends Exception
E extends Exceptionpublic static <N> ConsumingTraverser<N> breadthFirst(Iterable<? extends N> startNodes, ForEachSuccessorFunction<N> successors)
consumer, starting from startNodes, in a breadth-first walk
of the graph.
Allocates a set of O(#nodes) to record visited nodes and a queue of O(width).
public static <N> ConsumingTraverser<N> topologicallySorted(Iterable<? extends N> startNodes, ForEachSuccessorFunction<N> successors)
consumer, starting from startNodes, in a topologically sorted
order.ConsumingTraverser for a graph represented by the given ForEachSuccessorFunction.
Allocates a set of O(#nodes) to record visited nodes, a map of (#nodes) to count incoming edges, and a queue of nodes to process. Calls each node's successor consumer function twice.