Class Walker<N>
 java.lang.Object

 com.google.mu.util.graph.Walker<N>

 Direct Known Subclasses:
BinaryTreeWalker
,GraphWalker
public abstract class Walker<N> extends java.lang.Object
Implements generic graph and tree traversal algorithms (preorder
,postorder
andbreadthfirst
) as lazily evaluated streams, allowing infinitesize graphs.The following example code explores all islands to find the treasure island:
Optional<Island> treasureIsland = Walker.inGraph(Island::nearbyIslands) .preOrderFrom(homeIsland) .filter(Island::hasTreasure) .findFirst();
None of these streams are safe to run in parallel. Although, multiple threads could traverse the same graph collaboratively by sharing a concurrent node tracker. See
inGraph(findSuccessors, nodeTracker)
for details.For binary trees, use
inBinaryTree(Tree::left, Tree::right)
. Since:
 4.0


Method Summary
Modifier and Type Method Description abstract java.util.stream.Stream<N>
breadthFirstFrom(java.lang.Iterable<? extends N> startNodes)
Starts fromstartNodes
and walks in breadthfirst order.java.util.stream.Stream<N>
breadthFirstFrom(N... startNodes)
Starts fromstartNodes
and walks in breadthfirst order.static <N> BinaryTreeWalker<N>
inBinaryTree(java.util.function.UnaryOperator<N> getLeft, java.util.function.UnaryOperator<N> getRight)
Returns aBinaryTreeWalker
for walking in the binary tree topology as observed bygetLeft
andgetRight
functions.static <N> GraphWalker<N>
inGraph(java.util.function.Function<? super N,? extends java.util.stream.Stream<? extends N>> findSuccessors)
Returns aWalker
to walk the graph topology (possibly with cycles) as observed by thefindSuccessors
function, which finds successors of any given graph node.static <N> GraphWalker<N>
inGraph(java.util.function.Function<? super N,? extends java.util.stream.Stream<? extends N>> findSuccessors, java.util.function.Predicate<? super N> tracker)
Similar toinGraph(Function)
, returns aWalker
that can be used to traverse a graph of nodes.static <N> Walker<N>
inTree(java.util.function.Function<? super N,? extends java.util.stream.Stream<? extends N>> findChildren)
Returns aWalker
to walk the tree topology (no cycles) as observed by thefindChildren
function, which finds children of any given tree node.abstract java.util.stream.Stream<N>
postOrderFrom(java.lang.Iterable<? extends N> startNodes)
Starts fromstartNodes
and walks depth first in postorder (the reverse of a topological sort).java.util.stream.Stream<N>
postOrderFrom(N... startNodes)
Starts fromstartNodes
and walks depth first in postorder (the reverse of a topological sort).abstract java.util.stream.Stream<N>
preOrderFrom(java.lang.Iterable<? extends N> startNodes)
Starts fromstartNodes
and walks depth first in preorder.java.util.stream.Stream<N>
preOrderFrom(N... startNodes)
Starts fromstartNodes
and walks depth first in preorder.



Method Detail

inBinaryTree
public static <N> BinaryTreeWalker<N> inBinaryTree(java.util.function.UnaryOperator<N> getLeft, java.util.function.UnaryOperator<N> getRight)
Returns aBinaryTreeWalker
for walking in the binary tree topology as observed bygetLeft
andgetRight
functions. Both functions return null to indicate that there is no left or right child.It's guaranteed that for any given node,
getLeft
andgetRight
are called lazily, only when the left or the right child is traversed. They are called at most once for each node. Since:
 4.2

inTree
public static <N> Walker<N> inTree(java.util.function.Function<? super N,? extends java.util.stream.Stream<? extends N>> findChildren)
Returns aWalker
to walk the tree topology (no cycles) as observed by thefindChildren
function, which finds children of any given tree node.inTree()
is more efficient thaninGraph()
because it doesn't need to remember nodes that are already visited. On the other hand, the returnedWalker
can walk in cycles if thefindChildren
function unexpectedly represents a cyclic graph. If you need to guard against cycles just in case, you can useinGraph()
with a custom node tracker to check for the critical precondition:Set<N> visited = new HashSet<>(); Walker<N> walker = Walker.inGraph(successorFunction, n > { checkArgument(visited.add(n), "Node with multiple parents: %s", n); return true; });
The returned object is idempotent, stateless and immutable as long as
findChildren
is idempotent, stateless and immutable. Parameters:
findChildren
 Function to get the child nodes for a given node. No children if empty stream or null is returned,

inGraph
public static <N> GraphWalker<N> inGraph(java.util.function.Function<? super N,? extends java.util.stream.Stream<? extends N>> findSuccessors)
Returns aWalker
to walk the graph topology (possibly with cycles) as observed by thefindSuccessors
function, which finds successors of any given graph node.Because the traversal needs to remember which node(s) have been traversed, memory usage is linear to the number of traversed nodes.
 Parameters:
findSuccessors
 Function to get the successor nodes for a given node. No successor if empty stream or null is returned,

inGraph
public static <N> GraphWalker<N> inGraph(java.util.function.Function<? super N,? extends java.util.stream.Stream<? extends N>> findSuccessors, java.util.function.Predicate<? super N> tracker)
Similar toinGraph(Function)
, returns aWalker
that can be used to traverse a graph of nodes.tracker
is used to track every node being traversed. WhenWalker
is about to traverse a node,tracker.test(node)
will be called and the node (together with its edges) will be skipped if false is returned.This is useful for custom node tracking. For example, using a
ConcurrentHashMap
, multiple threads can traverse a large graph concurrently and collaboratively:Walker<Room> concurrentWalker = Walker.inGraph(buildingMap, ConcurrentHashMap.newKeySet()::add); // thread 1: Stream<Room> shield = concurrentWalker.preOrderFrom(roof); shield.forEachOrdered(room > System.out.println("Raided by SHIELD from roof: " + room); // thread 2: Stream<Room> avengers = concurrentWalker.breadthFirstFrom(mainEntrance); avengers.forEachOrdered(room > System.out.println("Raided by Avengers: " + room);
Or, nodes can be tracked by functional equivalence. What gives? Imagine in a pirate treasure hunt, we start from an island and scavenge from island to island. Considering the islands as nodes, we can use any traversal strategy. Say, we picked preorder:
That gives us the treasure island. But what if upon finding the treasure island, we also want to make our own treasure map? It requires not just finding the island, but also recording how we got there. To do this, we can start by defining a class that encodes the route:Optional<Island> treasureIsland = Walker.inGraph(Island::nearbyIslands) .preOrderFrom(startIsland) .filter(Island::hasTreasure) .findFirst();
And then we can modify the treasure hunt code to walk through a stream ofclass Route { private final Island island; private final Route predecessor; // End of the route. Island end() { return island; } // Returns a new Route with this Route as the predecessor. Route extendTo(Island newIsland) { return new Route(newIsland, this); } Stream<Route> nearbyRoutes() { return island.nearbyIslands().map(this::extendTo); } List<Island> islands() { // follow the `predecessor` chain to return all islands along the route. } }
Route
objects in place of islands. A caveat is that Route doesn't defineequals
 even if it did, it'd be recursive and not what we need anyway (we care about unique islands, not unique routes).Long story short, the trick is to use functional equivalence so that the
Walker
still knows which islands have already been searched:Set<Island> searched = new HashSet<>(); Optional<Route> treasureIslandRoute = Walker.inGraph(Route::nearbyRoutes, route > searched.add(route.end())) .preOrderFrom(new Route(startIsland)) .filter(route > route.end().hasTreasure()) .findFirst();
In the case of walking a very large graph with more nodes than can fit in memory, it's conceivable to use
BloomFilter
to track visited nodes, as long as you are okay with probabilistically missing a fraction of the graph nodes due to Bloom filter's inherent falsepositive rates. Because Bloom filters have zero falsenegatives, it's guaranteed that the walker will never walk in cycles. Parameters:
findSuccessors
 Function to get the successor nodes for a given node. No successor if empty stream or null is returned,tracker
 Tracks each node being visited during traversal. Returns false if the node and its edges should be skipped for traversal (for example because it has already been traversed). Despite being aPredicate
, the tracker usually carries sideeffects like storing the tracked nodes in a set (set::add
,bloomFilter::put
etc. will do).

preOrderFrom
@SafeVarargs public final java.util.stream.Stream<N> preOrderFrom(N... startNodes)
Starts fromstartNodes
and walks depth first in preorder.The returned stream may be infinite if the graph or tree has infinite depth or infinite breadth, or both. The stream can still be shortcircuited to consume a limited number of nodes during traversal.

preOrderFrom
public abstract java.util.stream.Stream<N> preOrderFrom(java.lang.Iterable<? extends N> startNodes)
Starts fromstartNodes
and walks depth first in preorder.The returned stream may be infinite if the graph or tree has infinite depth or infinite breadth, or both. The stream can still be shortcircuited to consume a limited number of nodes during traversal.

postOrderFrom
@SafeVarargs public final java.util.stream.Stream<N> postOrderFrom(N... startNodes)
Starts fromstartNodes
and walks depth first in postorder (the reverse of a topological sort).The returned stream may be infinite if the graph or tree has infinite breadth. The stream can still be shortcircuited to consume a limited number of nodes during traversal.
The stream may result in infinite loop when traversing through a node with infinite depth.

postOrderFrom
public abstract java.util.stream.Stream<N> postOrderFrom(java.lang.Iterable<? extends N> startNodes)
Starts fromstartNodes
and walks depth first in postorder (the reverse of a topological sort).The returned stream may be infinite if the graph or tree has infinite breadth. The stream can still be shortcircuited to consume a limited number of nodes during traversal.
The stream may result in infinite loop when traversing through a node with infinite depth.

breadthFirstFrom
@SafeVarargs public final java.util.stream.Stream<N> breadthFirstFrom(N... startNodes)
Starts fromstartNodes
and walks in breadthfirst order.The returned stream may be infinite if the graph or tree has infinite depth or infinite breadth, or both. The stream can still be shortcircuited to consume a limited number of nodes during traversal.

breadthFirstFrom
public abstract java.util.stream.Stream<N> breadthFirstFrom(java.lang.Iterable<? extends N> startNodes)
Starts fromstartNodes
and walks in breadthfirst order.The returned stream may be infinite if the graph or tree has infinite depth or infinite breadth, or both. The stream can still be shortcircuited to consume a limited number of nodes during traversal.

