yog/topological_sort

Values

lexicographical_topological_sort

pub fn lexicographical_topological_sort(
  graph: model.Graph(n, e),
  compare_nodes: fn(n, n) -> 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_nodes) is chosen first.

The comparison function operates on node data, not node IDs, allowing intuitive comparisons like string.compare for alphabetical ordering.

Returns Error(Nil) if the graph contains a cycle.

Time Complexity: O(V log V + E) due to heap operations

Example

// Get alphabetical ordering by node data
topological_sort.lexicographical_topological_sort(graph, string.compare)
// => Ok([0, 1, 2])  // Node IDs ordered by their string data

// Custom comparison by priority
topological_sort.lexicographical_topological_sort(graph, fn(a, b) {
  int.compare(a.priority, b.priority)
})

topological_sort

</>

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