Class TopologicalSorter<E>

java.lang.Object
org.dellroad.stuff.graph.TopologicalSorter<E>

public class TopologicalSorter<E> extends Object
Topological sorting utility class.
  • 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