# `Yog.Functional.Algorithms`
[🔗](https://github.com/code-shoily/yog_ex/blob/v0.98.0/lib/yog/functional/algorithms.ex#L1)

Classic graph algorithms using purely functional inductive decomposition.

Each algorithm leverages `Yog.Functional.Model.match/2` as its core operation.
By extracting a node and working with the resulting *shrunken* graph, these
implementations avoid mutable state and explicit "visited" sets. Correctness
and termination follow naturally from the inductive structure.

## Available Algorithms

| Algorithm | Function | Time Complexity |
|-----------|----------|-----------------|
| [Topological Sort](https://en.wikipedia.org/wiki/Topological_sorting) | `topsort/1` | O(V + E) |
| [Dijkstra's Shortest Path](https://en.wikipedia.org/wiki/Dijkstra%27s_algorithm) | `shortest_path/3` | O((V + E) log V) |
| Distances | `distances/2` | Compute all-node distances from source |
| [Prim's MST](https://en.wikipedia.org/wiki/Prim%27s_algorithm) | `mst_prim/1` | O(E log V) |
| [Kosaraju's SCC](https://en.wikipedia.org/wiki/Kosaraju%27s_algorithm) | `scc/1` | O(V + E) |

## Key Principle

Every algorithm consumes the graph structurally: `match/2` removes a node and
all its incident edges, so already-processed nodes simply won't be found in the
remaining graph. No external "visited" bookkeeping is needed.

## References

- [Original FGL Paper (Erwig, 2001)](https://web.engr.oregonstate.edu/~erwig/papers/InductiveGraphs_JFP01.pdf)
- [Wikipedia: Graph Algorithms](https://en.wikipedia.org/wiki/Graph_algorithm)

# `distances`

```elixir
@spec distances(Yog.Functional.Model.t(), Yog.Functional.Model.node_id()) :: %{
  required(Yog.Functional.Model.node_id()) => number()
}
```

Computes the distance from a start node to all reachable nodes using Dijkstra's algorithm.
Returns `%{node_id => distance}`.

## Examples

    iex> alias Yog.Functional.{Model, Algorithms}
    iex> graph = Model.empty() |> Model.put_node(1, "A") |> Model.put_node(2, "B")
    ...> |> Model.add_edge!(1, 2, 10)
    iex> Algorithms.distances(graph, 1)
    %{1 => 0, 2 => 10}

# `mst_prim`

Finds the Minimum Spanning Tree of the connected component containing the first node.
Returns `{:ok, [{from, to, weight}]}` or `{:ok, []}` for empty graphs.

Treats the graph as undirected by extracting both in and out edges from each context.

Inductive approach (Prim's): start from any node (extracted via `match/2`),
insert its adjacent edges into a sorted priority queue, then repeatedly
dequeue the minimum-weight edge whose target is still in the unvisited graph.
`match/2` is used to extract the target: if it's already been visited,
`match/2` returns `{:error, :not_found}` and we skip to the next candidate.

# `scc`

Finds the Strongly Connected Components (SCCs) of a directed graph.
Returns a list of lists, where each inner list contains the node IDs of one SCC.

Uses Kosaraju's two-pass algorithm, adapted for functional inductive graphs:
1. Pass 1: compute the DFS finishing order of all nodes.
2. Reverse the graph's edges.
3. Pass 2: extract components by running DFS on the reversed graph in the compute order.

Due to the inductive `match/2` operations, nodes visited in one component
are naturally removed from the graph, preventing them from bleeding into
subsequent components.

## Examples

    iex> alias Yog.Functional.{Model, Algorithms}
    iex> graph = Model.empty() |> Model.put_node(1, "A") |> Model.put_node(2, "B")
    ...> |> Model.add_edge!(1, 2) |> Model.add_edge!(2, 1)
    iex> sccs = Algorithms.scc(graph)
    iex> Enum.map(sccs, &Enum.sort/1) |> Enum.sort()
    [[1, 2]]

# `shortest_path`

Finds the shortest path between two nodes using Dijkstra's algorithm.
Returns `{:ok, [node_ids], total_distance}` or `{:error, :no_path}`.

Edge labels are used as weights (defaults to 1 if `nil`).

Inductive approach: we maintain a sorted priority queue of `{dist, node, path}`
entries. Each step extracts the minimum-distance frontier node using `match/2`.
Because `match/2` removes the node from the graph, we naturally skip
already-settled nodes — they simply won't be found anymore.

## Examples

    iex> alias Yog.Functional.{Model, Algorithms}
    iex> graph = Model.empty() |> Model.put_node(1, "A") |> Model.put_node(2, "B")
    ...> |> Model.add_edge!(1, 2, 10)
    iex> Algorithms.shortest_path(graph, 1, 2)
    {:ok, [1, 2], 10}

# `topsort`

Performs a Topological Sort by repeatedly extracting nodes with 0 in-degree.
Returns `{:ok, [node_ids]}` or `{:error, :cycle_detected}`.

Inductive approach: each round, we scan for a node whose `in_edges` map is
empty in the current (shrunken) graph, extract it with `match/2`, and recurse.
When an edge is removed by `match/2`, affected neighbours' `in_edges` are
automatically updated by the inductive model, so the in-degree invariant is
always up to date without a separate tracking structure.

## Examples

    iex> alias Yog.Functional.{Model, Algorithms}
    iex> graph = Model.empty() |> Model.put_node(1, "A") |> Model.put_node(2, "B")
    ...> |> Model.add_edge!(1, 2)
    iex> {:ok, order} = Algorithms.topsort(graph)
    iex> order
    [1, 2]

---

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