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

static interface

TopologicalSorter.EdgeLister<E> Implemented by classes that can enumerate the outgoing edges from a node in a graph.

Constructor Summary

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

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 Detail

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);

Method Detail

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.

This implementation runs in linear time in the number of nodes in the graph.

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