com.facebook.buck.core.util.graph

Class TopologicalSort

java.lang.Object

com.facebook.buck.core.util.graph.TopologicalSort

public class TopologicalSort
extends Object

Nested Class Summary

Nested Classes

Modifier and Type	Class and Description
static interface	TopologicalSort.Traversable<T> User provider callback used for walking the graph

Method Summary

Modifier and Type	Method and Description
static <T> com.google.common.collect.ImmutableList<? extends T>	snowflakeSort(Iterable<? extends T> roots, TopologicalSort.Traversable<T> traversable, Comparator<T> comparator) Deprecated. This is silly. You should just use the normal sort. This is here because c/c++ link command lines are sensitive to argument order, but aren't strict about it being correct. Since they aren't strict, code has evolved to depend on the specific order that Buck has been ordering link lines, and so this preserves that legacy behavior until code that depends on it is fixed.
static <T> com.google.common.collect.ImmutableList<? extends T>	sort(Iterable<? extends T> roots, TopologicalSort.Traversable<T> traversable) Returns a topologically sorted list of all nodes in the graph.
static <T> com.google.common.collect.ImmutableList<T>	sort(TraversableGraph<T> graph) Returns a topologically sorted list of the nodes in the graph.

Methods inherited from class java.lang.Object

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

Method Detail

sort

public static <T> com.google.common.collect.ImmutableList<T> sort(TraversableGraph<T> graph)

Returns a topologically sorted list of the nodes in the graph.

sort

public static <T> com.google.common.collect.ImmutableList<? extends T> sort(Iterable<? extends T> roots,
                                                                            TopologicalSort.Traversable<T> traversable)

Returns a topologically sorted list of all nodes in the graph.

snowflakeSort

@Deprecated
public static <T> com.google.common.collect.ImmutableList<? extends T> snowflakeSort(Iterable<? extends T> roots,
                                                                                                 TopologicalSort.Traversable<T> traversable,
                                                                                                 Comparator<T> comparator)

Deprecated. This is silly. You should just use the normal sort. This is here because c/c++ link command lines are sensitive to argument order, but aren't strict about it being correct. Since they aren't strict, code has evolved to depend on the specific order that Buck has been ordering link lines, and so this preserves that legacy behavior until code that depends on it is fixed.

This special form of topological sort returns items with each "level" sorted. The algorithm is basically this: identify all the leaves of the graph, sort them, add them to the list, remove them from the graph and proceed.