Package org.dellroad.stuff.graph

Class TopologicalSorter<E>

java.lang.Object

org.dellroad.stuff.graph.TopologicalSorter<E>

public class TopologicalSorter<E>
extends Object

Topological sorting utility class.

Nested Class Summary

Nested Classes

Modifier and Type	Class	Description
static interface	TopologicalSorter.EdgeLister<E>	Implemented by classes that can enumerate the outgoing edges from a node in a graph.

Constructor Summary

Constructors

Constructor	Description
TopologicalSorter(Collection<E> nodes, TopologicalSorter.EdgeLister<E> edgeLister)	Convenience constructor for when ties should be broken based on the original ordering.
TopologicalSorter(Collection<E> nodes, TopologicalSorter.EdgeLister<E> edgeLister, Comparator<? super E> tieBreaker)	Primary constructor.

Method Summary

Modifier and Type	Method	Description
List<E>	sort()	Produce a total ordering of the nodes consistent with the partial ordering implied by the edge lister and tie breaker provided to the constructor.
List<E>	sortEdgesReversed()	Same as sort() but treats all edges as reversed.

Methods inherited from class java.lang.Object

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

Constructor Details

TopologicalSorter

public TopologicalSorter(Collection<E> nodes,
 TopologicalSorter.EdgeLister<E> edgeLister,
 Comparator<? super E> tieBreaker)

Primary constructor.

Parameters:

nodes - partially ordered nodes to be sorted

edgeLister - provides the edges defining the partial order

tieBreaker - used to sort nodes that are not otherwise ordered, or null to tie break based on the original ordering

TopologicalSorter

public TopologicalSorter(Collection<E> nodes,
 TopologicalSorter.EdgeLister<E> edgeLister)

Convenience constructor for when ties should be broken based on the original ordering.

Equivalent to:

TopologicalSorter(nodes, edgeLister, null);

Parameters:

nodes - set of nodes to sort

edgeLister - defines the edges between nodes

Method Details

sort

public List<E> sort()

Produce a total ordering of the nodes consistent with the partial ordering implied by the edge lister and tie breaker provided to the constructor.

The returned list will have the property that if there is an edge from X to Y, then X will appear before Y in the list. If there is no edge (or sequence of edges) from X to Y in either direction, then X will appear before Y if the tie breaker sorts X before Y.

Returns:

sorted, mutable list of nodes

Throws:

IllegalArgumentException - if the partial ordering relation contains a cycle

sortEdgesReversed

public List<E> sortEdgesReversed()

Same as sort() but treats all edges as reversed.

The returned list will have the property that if there is an edge from X to Y, then Y will appear before X in the list. If there is no edge (or sequence of edges) from X to Y in either direction, then X will appear before Y if the tie breaker sorts X before Y.

Returns:

sorted, mutable list of nodes

Throws:

IllegalArgumentException - if the partial ordering relation contains a cycle