# `Yog.Traversal.Sort`
[🔗](https://github.com/code-shoily/yog_ex/blob/v0.97.0/lib/yog/traversal/sort.ex#L1)

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.

<div class="graphviz">
digraph G {
  rankdir=LR;
  bgcolor="transparent";
  node [shape=circle, fontname="inherit"];
  edge [fontname="inherit", fontsize=10];

  subgraph cluster_dag {
    label="Directed Acyclic Graph (DAG)"; color="#6366f1"; style=rounded;
    A -> B; A -> C;
    B -> D;
    C -> D;
    D -> E;
  }
}
</div>

    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]

# `lexicographical_topological_sort`

```elixir
@spec lexicographical_topological_sort(Yog.graph(), (term(), term() -&gt;
                                                 :lt | :eq | :gt)) ::
  {:ok, [Yog.node_id()]} | {:error, :contains_cycle}
```

Performs a lexicographically smallest topological sort. Compares by node_data. Breaks tie
by ID.

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

# `topological_sort`

```elixir
@spec topological_sort(Yog.graph()) ::
  {:ok, [Yog.node_id()]} | {:error, :contains_cycle}
```

Performs a topological sort on a directed graph using Kahn's algorithm.

Time Complexity: O(V + E)

---

*Consult [api-reference.md](api-reference.md) for complete listing*