com.facebook.buck.core.util.graph

Class AcyclicDepthFirstPostOrderTraversalWithDependencyStack<T>

java.lang.Object

com.facebook.buck.core.util.graph.AcyclicDepthFirstPostOrderTraversalWithDependencyStack<T>

Type Parameters:

T - the type of node in the graph

public class AcyclicDepthFirstPostOrderTraversalWithDependencyStack<T>
extends Object

Performs a depth-first, post-order traversal over a DAG.

This version of algorithm tracks traversal path in DependencyStack structure and provides it to user in GraphTraversableWithDependencyStack callback.

If a cycle is encountered, a CycleException is thrown by traverse(Iterable).

Constructor Summary

Constructors

Constructor and Description
AcyclicDepthFirstPostOrderTraversalWithDependencyStack(GraphTraversableWithDependencyStack<T> traversable, java.util.function.BiFunction<DependencyStack,T,DependencyStack> dependencyStackChild)

Method Summary

Modifier and Type	Method and Description
Iterable<T>	traverse(Iterable<? extends T> initialNodes)
Iterable<T>	traverse(Iterable<? extends T> initialNodes, java.util.function.Predicate<T> shouldExploreChildren) Performs a depth-first, post-order traversal over a DAG.

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Constructor Detail

AcyclicDepthFirstPostOrderTraversalWithDependencyStack

public AcyclicDepthFirstPostOrderTraversalWithDependencyStack(GraphTraversableWithDependencyStack<T> traversable,
                                                              java.util.function.BiFunction<DependencyStack,T,DependencyStack> dependencyStackChild)

Parameters:

dependencyStackChild - a function to construct a child stack from a stack and a new graph node. In the most cases it is just an invocation of DependencyStack.child(DependencyStack.Element).

Method Detail

traverse

public Iterable<T> traverse(Iterable<? extends T> initialNodes)
                     throws CycleException

Throws:

CycleException

traverse

public Iterable<T> traverse(Iterable<? extends T> initialNodes,
                            java.util.function.Predicate<T> shouldExploreChildren)
                     throws CycleException

Performs a depth-first, post-order traversal over a DAG.

Parameters:

initialNodes - The nodes from which to perform the traversal. Not allowed to contain null.

shouldExploreChildren - Whether or not to explore a particular node's children. Used to support short circuiting in the traversal.

Throws:

CycleException - if a cycle is found while performing the traversal.