Topological sorting algorithms for directed acyclic graphs (DAGs).

This module provides algorithms for producing a topological ordering of nodes in a DAG. A topological ordering is a linear ordering of nodes such that for every directed edge (u, v), node u comes before v in the ordering.

Algorithms

• Kahn's Algorithm: topological_sort/1 - BFS-based approach using in-degrees. Time complexity O(V + E). Preferred for most use cases.
• Lexicographical Topological Sort: lexicographical_topological_sort/2 - Kahn's algorithm with a priority queue for deterministic ordering. Time complexity O((V + E) log V).

Algorithm Characteristics

• Time Complexity: O(V + E) for standard, O((V + E) log V) for lexicographical
• Space Complexity: O(V) for the in-degree map and queue
• Cycle Detection: Both algorithms detect cycles and return {:error, :contains_cycle}

When to Use

• Standard: Use when you just need any valid topological ordering
• Lexicographical: Use when you need a deterministic ordering (e.g., alphabetical)

Use Cases

• Task scheduling with dependencies
• Resolving symbol dependencies in compilers
• Ordering of formula calculations in spreadsheets
• Determining instruction sequences in dataflow programming

Topological Order Visualization

A topological sort flattens a DAG into a linear sequence where all directed edges point from left to right.

iex> alias Yog.Traversal.Sort
iex> graph = Yog.from_edges(:directed, [
...>   {"A", "B", 1}, {"A", "C", 1},
...>   {"B", "D", 1}, {"C", "D", 1},
...>   {"D", "E", 1}
...> ])
iex> {:ok, order} = Sort.topological_sort(graph)
iex> # Check if order is valid (A before B,C; B,C before D; D before E)
...> Enum.find_index(order, &(&1 == "A")) < Enum.find_index(order, &(&1 == "B"))
true

Examples

# Standard topological sort
iex> graph = Yog.directed()
...> |> Yog.add_node(1, "A")
...> |> Yog.add_node(2, "B")
...> |> Yog.add_node(3, "C")
...> |> Yog.add_edges!([{1, 2, 1}, {2, 3, 1}])
iex> {:ok, order} = Yog.Traversal.Sort.topological_sort(graph)
iex> order
[1, 2, 3]

# Lexicographical topological sort
iex> graph = Yog.directed()
...> |> Yog.add_node(1, "c")
...> |> Yog.add_node(2, "a")
...> |> Yog.add_node(3, "b")
...> |> Yog.add_edges!([{1, 3, 1}, {2, 3, 1}])
iex> {:ok, order} = Yog.Traversal.Sort.lexicographical_topological_sort(graph, &<=/2)
iex> order
[2, 1, 3]