Class TopologicalSort

java.lang.Object
com.phasmidsoftware.gryphon.java.TopologicalSort

public class TopologicalSort extends Object
Java façade for topological sorting of directed acyclic graphs (DAGs).

A topological sort orders vertices such that for every directed edge u → v, vertex u appears before v in the ordering. Topological sort is only defined for DAGs — if the graph contains a cycle, sort(com.phasmidsoftware.gryphon.java.Graph<V>) returns Optional.empty().

The graph must be directed. Calling these methods on an undirected graph will throw IllegalStateException.

Usage example:


 Graph<String> g = Graph.directed();
 g.addEdge("A", "B");
 g.addEdge("A", "C");
 g.addEdge("B", "D");
 g.addEdge("C", "D");

 Optional<List<String>> order = TopologicalSort.sort(g);
 // order: Optional[A, B, C, D] or Optional[A, C, B, D] (both valid)

 // Cyclic graph:
 Graph<String> cyclic = Graph.directed();
 cyclic.addEdge("A", "B");
 cyclic.addEdge("B", "A");
 TopologicalSort.sort(cyclic);  // Optional.empty()
 
  • Method Details

    • sort

      public static <V> Optional<List<V>> sort(Graph<V> graph)
      Computes a topological ordering of the vertices in a directed graph.

      Uses post-order DFS — each vertex appears in the result only after all vertices reachable from it have been recorded.

      Type Parameters:
      V - the vertex type.
      Parameters:
      graph - a directed graph.
      Returns:
      Optional containing a topological ordering of all vertices, or Optional.empty() if the graph contains a cycle.
      Throws:
      IllegalStateException - if graph is undirected.
    • isDAG

      public static <V> boolean isDAG(Graph<V> graph)
      Returns true if the graph is a DAG (contains no directed cycle).

      Convenience method — equivalent to sort(graph).isPresent().

      Type Parameters:
      V - the vertex type.
      Parameters:
      graph - a directed graph.
      Returns:
      true if acyclic, false if cyclic.
      Throws:
      IllegalStateException - if graph is undirected.