Package com.phasmidsoftware.gryphon.java
Class TopologicalSort
java.lang.Object
com.phasmidsoftware.gryphon.java.TopologicalSort
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 Summary
-
Method Details
-
sort
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:
Optionalcontaining a topological ordering of all vertices, orOptional.empty()if the graph contains a cycle.- Throws:
IllegalStateException- ifgraphis undirected.
-
isDAG
Returnstrueif 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:
trueif acyclic,falseif cyclic.- Throws:
IllegalStateException- ifgraphis undirected.
-