Package com.google.mu.util.graph

Class GraphWalker<N>

java.lang.Object
com.google.mu.util.graph.Walker<N>
com.google.mu.util.graph.GraphWalker<N>
Type Parameters:
N - the graph node type
public abstract class GraphWalker<N> extends Walker<N>
Walker for graph topology (see Walker.inGraph()).

Besides pre-order, post-order and breadth-first traversals, also supports topologicalOrderFrom(), detectCycleFrom() and stronglyConnectedComponentsFrom().

Since:
4.3

  • Method Details

    • preOrderFrom

      public final Stream<N> preOrderFrom(Iterable<? extends N> startNodes)
      Description copied from class: Walker
      Starts from startNodes and walks depth first in pre-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 short-circuited to consume a limited number of nodes during traversal.

      Specified by:
      preOrderFrom in class Walker<N>

    • postOrderFrom

      public final Stream<N> postOrderFrom(Iterable<? extends N> startNodes)
      Description copied from class: Walker
      Starts from startNodes and walks depth first in post-order (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 short-circuited to consume a limited number of nodes during traversal.

      The stream may result in infinite loop when traversing through a node with infinite depth.

      Specified by:
      postOrderFrom in class Walker<N>

    • breadthFirstFrom

      public final Stream<N> breadthFirstFrom(Iterable<? extends N> startNodes)
      Description copied from class: Walker
      Starts from startNodes and walks in breadth-first 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 short-circuited to consume a limited number of nodes during traversal.

      Specified by:
      breadthFirstFrom in class Walker<N>

    • detectCycleFrom

      @SafeVarargs public final Optional<Stream<N>> detectCycleFrom(N... startNodes)
      Walking from startNodes, detects if the graph has any cycle.

      In the following cyclic graph, if starting from node a, the detected cyclic path will be: a -> b -> c -> e -> b, with b -> c -> e -> b being the cycle, and a -> b the prefix path leading to the cycle. 

      
 a -> b -> c -> d
      ^  /
      | /
      |/
      e

      This method will hang if the given graph is infinite without cycle (the sequence of natural numbers for instance).

      Parameters:
      startNodes - the entry point nodes to start walking the graph.
      Returns:
      The stream of nodes starting from the first of startNodes that leads to a cycle, ending with nodes along a cyclic path. The last node will also be the starting point of the cycle. That is, if A and B form a cycle, the stream ends with A -> B -> A. If there is no cycle, Optional.empty() is returned.
      Since:
      4.3

    • detectCycleFrom

      public final Optional<Stream<N>> detectCycleFrom(Iterable<? extends N> startNodes)
      Walking from startNodes, detects if the graph has any cycle.

      In the following cyclic graph, if starting from node a, the detected cyclic path will be: a -> b -> c -> e -> b, with b -> c -> e -> b being the cycle, and a -> b the prefix path leading to the cycle. 

      
 a -> b -> c -> d
      ^  /
      | /
      |/
      e

      This method will hang if the given graph is infinite with no cycles (the sequence of natural numbers for instance).

      Parameters:
      startNodes - the entry point nodes to start walking the graph.
      Returns:
      The stream of nodes starting from the first of startNodes that leads to a cycle, ending with nodes along a cyclic path. The last node will also be the starting point of the cycle. That is, if A and B form a cycle, the stream ends with A -> B -> A. If there is no cycle, Optional.empty() is returned.
      Since:
      4.3

    • topologicalOrderFrom

      @SafeVarargs public final List<N> topologicalOrderFrom(N... startNodes)
      Fully traverses the graph by starting from startNodes, and returns an immutable list of nodes in topological order.

      Unlike the other Walker utilities, this method is not lazy: it has to traverse the entire graph in order to figure out the topological order.

      Parameters:
      startNodes - the entry point nodes to start traversing the graph.
      Throws:
      CyclicGraphException - if the graph has cycles.
      Since:
      4.3

    • topologicalOrderFrom

      public final List<N> topologicalOrderFrom(Iterable<? extends N> startNodes)
      Fully traverses the graph by starting from startNodes, and returns an immutable list of nodes in topological order.

      Unlike the other Walker utilities, this method is not lazy: it has to traverse the entire graph in order to figure out the topological order.

      Parameters:
      startNodes - the entry point nodes to start traversing the graph.
      Throws:
      CyclicGraphException - if the graph has cycles.
      Since:
      4.3

    • stronglyConnectedComponentsFrom

      @SafeVarargs public final Stream<List<N>> stronglyConnectedComponentsFrom(N... startNodes)
      Walks the graph by starting from startNodes, and returns a lazy stream of strongly connected components found in the graph.

      Implements the Tarjan algorithm in linear time (O(V + E)).

      The strongly connected components (represented by the list of nodes in each component) are returned in a lazy stream, in depth-first post order. If you need topological order from the start nodes, convert it using: 

      
   List<List<N>> components = Walker.inGraph(...)
       .stronglyConnectedComponentsFrom(...)
       .peek(Collections::reverse)                      // reverse order within each component
       .collect(toListAndThen(Collections::reverse));   // reverse order of the components
      Parameters:
      startNodes - the entry point nodes to start traversing the graph.
      Since:
      4.4

    • stronglyConnectedComponentsFrom

      public final Stream<List<N>> stronglyConnectedComponentsFrom(Iterable<? extends N> startNodes)
      Walks the graph by starting from startNodes, and returns a lazy stream of strongly connected components found in the graph.

      Implements the Tarjan algorithm in linear time (O(V + E)).

      The strongly connected components (represented by the list of nodes in each component) are returned in a lazy stream, in depth-first post order. If you need topological order from the start nodes, convert it using: 

      
   List<List<N>> components = Walker.inGraph(...)
       .stronglyConnectedComponentsFrom(...)
       .peek(Collections::reverse)                      // reverse order within each component
       .collect(toListAndThen(Collections::reverse));   // reverse order of the components
      Parameters:
      startNodes - the entry point nodes to start traversing the graph.
      Since:
      4.4