com.facebook.buck.core.util.graph

Class AcyclicDepthFirstPostOrderTraversalWithPayloadAndDependencyStack<T,P>

java.lang.Object

com.facebook.buck.core.util.graph.AcyclicDepthFirstPostOrderTraversalWithPayloadAndDependencyStack<T,P>

Type Parameters:

T - the type of node in the graph

public class AcyclicDepthFirstPostOrderTraversalWithPayloadAndDependencyStack<T,P>
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 GraphTraversableWithPayloadAndDependencyStack callback and in result of traverse(Iterable) operation.

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

Constructor Summary

Constructors

Constructor and Description
AcyclicDepthFirstPostOrderTraversalWithPayloadAndDependencyStack(GraphTraversableWithPayloadAndDependencyStack<T,P> traversable, java.util.function.BiFunction<DependencyStack,T,DependencyStack> dependencyStackChild)

Method Summary

Modifier and Type	Method and Description
LinkedHashMap<T,Pair<P,DependencyStack>>	traverse(Iterable<? extends T> initialNodes) Performs a depth-first, post-order traversal over a DAG.
LinkedHashMap<T,Pair<P,DependencyStack>>	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

AcyclicDepthFirstPostOrderTraversalWithPayloadAndDependencyStack

public AcyclicDepthFirstPostOrderTraversalWithPayloadAndDependencyStack(GraphTraversableWithPayloadAndDependencyStack<T,P> 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 LinkedHashMap<T,Pair<P,DependencyStack>> traverse(Iterable<? extends T> initialNodes)
                                                  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.

Throws:

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

traverse

public LinkedHashMap<T,Pair<P,DependencyStack>> 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.