Class Traversals

java.lang.Object
com.phasmidsoftware.visitor.java.Traversals

public final class Traversals extends Object
The Java entry points to Visitor's traversal engine.

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 Details

    • bfs

      public static <V> TraversalResult<V,V> bfs(V start, NeighbourFunction<V,V> neighbours)
      Breadth-first traversal from start, running to exhaustion.
      Type Parameters:
      V - the node type
      Parameters:
      start - the node to start from
      neighbours - 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 from start, halting after the first node that satisfies goal.
      Type Parameters:
      V - the node type
      Parameters:
      start - the node to start from
      neighbours - the adjacency of the graph
      goal - 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 from start, evaluating each node as it is visited.
      Type Parameters:
      V - the node type
      R - the result type
      Parameters:
      start - the node to start from
      neighbours - the adjacency of the graph
      evaluator - 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 from start, evaluating each node and halting after the first node that satisfies goal.
      Type Parameters:
      V - the node type
      R - the result type
      Parameters:
      start - the node to start from
      neighbours - the adjacency of the graph
      evaluator - what to extract from each node
      goal - 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

      public static <V> TraversalResult<V,V> dfs(V start, NeighbourFunction<V,V> neighbours, Order order)
      Depth-first traversal from start, running to exhaustion.
      Type Parameters:
      V - the node type
      Parameters:
      start - the node to start from
      neighbours - the adjacency of the graph
      order - 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 from start, halting after the first node that satisfies goal.
      Type Parameters:
      V - the node type
      Parameters:
      start - the node to start from
      neighbours - the adjacency of the graph
      order - whether a node is recorded before or after its descendants
      goal - 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 from start, evaluating each node as it is visited.
      Type Parameters:
      V - the node type
      R - the result type
      Parameters:
      start - the node to start from
      neighbours - the adjacency of the graph
      order - whether a node is recorded before or after its descendants
      evaluator - 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 from start, evaluating each node and halting after the first node that satisfies goal.
      Type Parameters:
      V - the node type
      R - the result type
      Parameters:
      start - the node to start from
      neighbours - the adjacency of the graph
      order - whether a node is recorded before or after its descendants
      evaluator - what to extract from each node
      goal - 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: rootChildren yields the nodes the traversal begins from, and children carries 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 type
      V - the node type
      Parameters:
      root - the root structure
      rootChildren - the children of the root
      children - the children of each node below the root
      order - 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 satisfies goal.
      Type Parameters:
      H - the root type
      V - the node type
      Parameters:
      root - the root structure
      rootChildren - the children of the root
      children - the children of each node below the root
      order - whether a node is recorded before or after its descendants
      goal - halts the traversal after recording the first node it accepts
      Returns:
      the nodes in depth-first order
    • traverseTreeEvaluating

      public 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.
      Type Parameters:
      H - the root type
      V - the node type
      R - the result type
      Parameters:
      root - the root structure
      rootChildren - the children of the root
      children - the children of each node below the root
      order - whether a node is recorded before or after its descendants
      evaluator - 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, 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 satisfies goal.
      Type Parameters:
      H - the root type
      V - the node type
      R - the result type
      Parameters:
      root - the root structure
      rootChildren - the children of the root
      children - the children of each node below the root
      order - whether a node is recorded before or after its descendants
      evaluator - what to extract from each node
      goal - halts the traversal after recording the first node it accepts
      Returns:
      the visited nodes and the evaluator's results, both in depth-first order