Class Traversals
Visitor's Scala API is driven by type classes supplied implicitly. This façade takes the two
that matter — NeighbourFunction and Evaluator — as ordinary arguments, so a Java
caller supplies them as lambdas or method references and needs to know nothing about Scala
given instances:
Map<String, List<String>> graph = Map.of(
"A", List.of("B", "C"),
"B", List.of("D"),
"C", List.of("D"),
"D", List.of());
TraversalResult<String, String> r =
Traversals.bfs("A", v -> graph.getOrDefault(v, List.of()));
r.visited(); // [A, B, C, D]
r.cameFrom(); // {B=A, C=A, D=B}
Each traversal comes in four forms: with and without an early-termination goal, and
with or without an Evaluator. The plain forms evaluate each node to itself, so
TraversalResult.results() equals TraversalResult.visited(); the
...Evaluating forms let the evaluator transform and filter.
A goal predicate halts the traversal after recording the first node it
accepts. That node is present in the result; nothing beyond it is visited.
Every method is a static method on a final class that cannot be instantiated.
-
Method Summary
Modifier and TypeMethodDescriptionstatic <V> TraversalResult<V, V> bfs(V start, NeighbourFunction<V, V> neighbours) Breadth-first traversal fromstart, running to exhaustion.static <V> TraversalResult<V, V> bfs(V start, NeighbourFunction<V, V> neighbours, Predicate<V> goal) Breadth-first traversal fromstart, halting after the first node that satisfiesgoal.static <V,R> TraversalResult <V, R> bfsEvaluating(V start, NeighbourFunction<V, V> neighbours, Evaluator<V, R> evaluator) Breadth-first traversal fromstart, evaluating each node as it is visited.static <V,R> TraversalResult <V, R> bfsEvaluating(V start, NeighbourFunction<V, V> neighbours, Evaluator<V, R> evaluator, Predicate<V> goal) Breadth-first traversal fromstart, evaluating each node and halting after the first node that satisfiesgoal.static <V> TraversalResult<V, V> dfs(V start, NeighbourFunction<V, V> neighbours, Order order) Depth-first traversal fromstart, running to exhaustion.static <V> TraversalResult<V, V> dfs(V start, NeighbourFunction<V, V> neighbours, Order order, Predicate<V> goal) Depth-first traversal fromstart, halting after the first node that satisfiesgoal.static <V,R> TraversalResult <V, R> dfsEvaluating(V start, NeighbourFunction<V, V> neighbours, Order order, Evaluator<V, R> evaluator) Depth-first traversal fromstart, evaluating each node as it is visited.static <V,R> TraversalResult <V, R> dfsEvaluating(V start, NeighbourFunction<V, V> neighbours, Order order, Evaluator<V, R> evaluator, Predicate<V> goal) Depth-first traversal fromstart, evaluating each node and halting after the first node that satisfiesgoal.static <H,V> TraversalResult <V, V> traverseTree(H root, NeighbourFunction<H, V> rootChildren, NeighbourFunction<V, V> children, Order order) Depth-first traversal of a tree whose root may have a different type from its descendants.static <H,V> TraversalResult <V, V> traverseTree(H root, NeighbourFunction<H, V> rootChildren, NeighbourFunction<V, V> children, Order order, Predicate<V> goal) Depth-first traversal of a tree, halting after the first node that satisfiesgoal.static <H,V, R> TraversalResult <V, R> traverseTreeEvaluating(H root, NeighbourFunction<H, V> rootChildren, NeighbourFunction<V, V> children, Order order, Evaluator<V, R> evaluator) Depth-first traversal of a tree, evaluating each node as it is visited.static <H,V, R> TraversalResult <V, R> traverseTreeEvaluating(H root, NeighbourFunction<H, V> rootChildren, NeighbourFunction<V, V> children, Order order, Evaluator<V, R> evaluator, Predicate<V> goal) Depth-first traversal of a tree, evaluating each node and halting after the first node that satisfiesgoal.
-
Method Details
-
bfs
Breadth-first traversal fromstart, running to exhaustion.- Type Parameters:
V- the node type- Parameters:
start- the node to start fromneighbours- the adjacency of the graph- Returns:
- the nodes in breadth-first order, with a came-from map
-
bfs
public static <V> TraversalResult<V,V> bfs(V start, NeighbourFunction<V, V> neighbours, Predicate<V> goal) Breadth-first traversal fromstart, halting after the first node that satisfiesgoal.- Type Parameters:
V- the node type- Parameters:
start- the node to start fromneighbours- the adjacency of the graphgoal- halts the traversal after recording the first node it accepts- Returns:
- the nodes in breadth-first order, with a came-from map
-
bfsEvaluating
public static <V,R> TraversalResult<V,R> bfsEvaluating(V start, NeighbourFunction<V, V> neighbours, Evaluator<V, R> evaluator) Breadth-first traversal fromstart, evaluating each node as it is visited.- Type Parameters:
V- the node typeR- the result type- Parameters:
start- the node to start fromneighbours- the adjacency of the graphevaluator- what to extract from each node- Returns:
- the visited nodes and the evaluator's results, both in breadth-first order
-
bfsEvaluating
public static <V,R> TraversalResult<V,R> bfsEvaluating(V start, NeighbourFunction<V, V> neighbours, Evaluator<V, R> evaluator, Predicate<V> goal) Breadth-first traversal fromstart, evaluating each node and halting after the first node that satisfiesgoal.- Type Parameters:
V- the node typeR- the result type- Parameters:
start- the node to start fromneighbours- the adjacency of the graphevaluator- what to extract from each nodegoal- halts the traversal after recording the first node it accepts- Returns:
- the visited nodes and the evaluator's results, both in breadth-first order
-
dfs
Depth-first traversal fromstart, running to exhaustion.- Type Parameters:
V- the node type- Parameters:
start- the node to start fromneighbours- the adjacency of the graphorder- whether a node is recorded before or after its descendants- Returns:
- the nodes in depth-first order, with a came-from map
-
dfs
public static <V> TraversalResult<V,V> dfs(V start, NeighbourFunction<V, V> neighbours, Order order, Predicate<V> goal) Depth-first traversal fromstart, halting after the first node that satisfiesgoal.- Type Parameters:
V- the node type- Parameters:
start- the node to start fromneighbours- the adjacency of the graphorder- whether a node is recorded before or after its descendantsgoal- halts the traversal after recording the first node it accepts- Returns:
- the nodes in depth-first order, with a came-from map
-
dfsEvaluating
public static <V,R> TraversalResult<V,R> dfsEvaluating(V start, NeighbourFunction<V, V> neighbours, Order order, Evaluator<V, R> evaluator) Depth-first traversal fromstart, evaluating each node as it is visited.- Type Parameters:
V- the node typeR- the result type- Parameters:
start- the node to start fromneighbours- the adjacency of the graphorder- whether a node is recorded before or after its descendantsevaluator- what to extract from each node- Returns:
- the visited nodes and the evaluator's results, both in depth-first order
-
dfsEvaluating
public static <V,R> TraversalResult<V,R> dfsEvaluating(V start, NeighbourFunction<V, V> neighbours, Order order, Evaluator<V, R> evaluator, Predicate<V> goal) Depth-first traversal fromstart, evaluating each node and halting after the first node that satisfiesgoal.- Type Parameters:
V- the node typeR- the result type- Parameters:
start- the node to start fromneighbours- the adjacency of the graphorder- whether a node is recorded before or after its descendantsevaluator- what to extract from each nodegoal- halts the traversal after recording the first node it accepts- Returns:
- the visited nodes and the evaluator's results, both in depth-first order
-
traverseTree
public static <H,V> TraversalResult<V,V> traverseTree(H root, NeighbourFunction<H, V> rootChildren, NeighbourFunction<V, V> children, Order order) Depth-first traversal of a tree whose root may have a different type from its descendants.The root itself is not visited:
rootChildrenyields the nodes the traversal begins from, andchildrencarries it down from there. Where the root is of the same type as its descendants, pass the same function twice.TraversalResult.cameFrom()is always empty for a tree traversal, because the engine does not record came-from where the parent is already evident from the tree's shape.- Type Parameters:
H- the root typeV- the node type- Parameters:
root- the root structurerootChildren- the children of the rootchildren- the children of each node below the rootorder- whether a node is recorded before or after its descendants- Returns:
- the nodes in depth-first order
-
traverseTree
public static <H,V> TraversalResult<V,V> traverseTree(H root, NeighbourFunction<H, V> rootChildren, NeighbourFunction<V, V> children, Order order, Predicate<V> goal) Depth-first traversal of a tree, halting after the first node that satisfiesgoal.- Type Parameters:
H- the root typeV- the node type- Parameters:
root- the root structurerootChildren- the children of the rootchildren- the children of each node below the rootorder- whether a node is recorded before or after its descendantsgoal- halts the traversal after recording the first node it accepts- Returns:
- the nodes in depth-first order
-
traverseTreeEvaluating
public static <H,V, TraversalResult<V,R> R> traverseTreeEvaluating(H root, NeighbourFunction<H, V> rootChildren, NeighbourFunction<V, V> children, Order order, Evaluator<V, R> evaluator) Depth-first traversal of a tree, evaluating each node as it is visited.- Type Parameters:
H- the root typeV- the node typeR- the result type- Parameters:
root- the root structurerootChildren- the children of the rootchildren- the children of each node below the rootorder- whether a node is recorded before or after its descendantsevaluator- what to extract from each node- Returns:
- the visited nodes and the evaluator's results, both in depth-first order
-
traverseTreeEvaluating
public static <H,V, TraversalResult<V,R> R> traverseTreeEvaluating(H root, NeighbourFunction<H, V> rootChildren, NeighbourFunction<V, V> children, Order order, Evaluator<V, R> evaluator, Predicate<V> goal) Depth-first traversal of a tree, evaluating each node and halting after the first node that satisfiesgoal.- Type Parameters:
H- the root typeV- the node typeR- the result type- Parameters:
root- the root structurerootChildren- the children of the rootchildren- the children of each node below the rootorder- whether a node is recorded before or after its descendantsevaluator- what to extract from each nodegoal- halts the traversal after recording the first node it accepts- Returns:
- the visited nodes and the evaluator's results, both in depth-first order
-