com.facebook.buck.core.util.graph

Class AcyclicDepthFirstPostOrderTraversalWithPayload<T,P>

java.lang.Object

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

Type Parameters:

T - the type of node in the graph

public class AcyclicDepthFirstPostOrderTraversalWithPayload<T,P>
extends Object

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

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

Constructor Summary

Constructors

Constructor and Description
AcyclicDepthFirstPostOrderTraversalWithPayload(GraphTraversableWithPayload<T,P> traversable)

Method Summary

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

AcyclicDepthFirstPostOrderTraversalWithPayload

public AcyclicDepthFirstPostOrderTraversalWithPayload(GraphTraversableWithPayload<T,P> traversable)

Method Detail

traverse

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