yog/topological_sort
Values
pub fn lexicographical_topological_sort(
graph: model.Graph(n, e),
compare_ids: fn(Int, Int) -> order.Order,
) -> Result(List(Int), Nil)Performs a topological sort that returns the lexicographically smallest sequence.
Uses a heap-based version of Kahn’s algorithm to ensure that when multiple
nodes have in-degree 0, the smallest one (according to compare_ids) is chosen first.
Returns Error(Nil) if the graph contains a cycle.
Time Complexity: O(V log V + E) due to heap operations
Example
// Get smallest numeric ordering
topological_sort.lexicographical_topological_sort(graph, int.compare)
// => Ok([1, 2, 3, 4]) // Always picks smallest available node
pub fn topological_sort(
graph: model.Graph(n, e),
) -> Result(List(Int), Nil)Performs a topological sort on a directed graph using Kahn’s algorithm.
Returns a linear ordering of nodes such that for every directed edge (u, v), node u comes before node v in the ordering.
Returns Error(Nil) if the graph contains a cycle.
Time Complexity: O(V + E) where V is vertices and E is edges
Example
topological_sort.topological_sort(graph)
// => Ok([1, 2, 3, 4]) // Valid ordering
// or Error(Nil) // Cycle detected