# `Yog.Functional.Algorithms`
[🔗](https://github.com/code-shoily/yog_ex/blob/v1.0.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 | Return value |
|-----------|----------|-----------------|--------------|
| [Topological Sort](https://en.wikipedia.org/wiki/Topological_sorting) | `topsort/1` | O(V + E) | `{:ok, ids}` or `{:error, :cycle_detected}` |
| [Dijkstra's Shortest Path](https://en.wikipedia.org/wiki/Dijkstra%27s_algorithm) | `shortest_path/3` | O((V + E) log V) | `{:ok, path, distance}` or `{:error, :no_path}` |
| Distances | `distances/2` | O((V + E) log V) | `%{node_id => distance}` |
| [Prim's MST](https://en.wikipedia.org/wiki/Prim%27s_algorithm) | `mst_prim/1` | O(E log V) | `{:ok, [{from, to, weight}]}` |
| [Kosaraju's SCC](https://en.wikipedia.org/wiki/Kosaraju%27s_algorithm) | `scc/1` | O(V + E) | `[[node_id]]` |

## Semantics and Caveats

- Dijkstra-based functions assume non-negative numeric edge labels. `nil` edge
  labels are treated as weight `1`.
- `mst_prim/1` treats the graph as undirected by looking at both incoming and
  outgoing edge maps. It returns the minimum spanning tree for the connected
  component containing the first node encountered by map iteration, not a full
  spanning forest for disconnected graphs.
- `scc/1` is for directed graphs and raises `ArgumentError` for undirected graphs.
- These implementations favor the inductive/FGL model's clarity over raw
  throughput. For large production graphs, prefer the adjacency-based Yog
  algorithm modules.

## 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`

```elixir
@spec mst_prim(Yog.Functional.Model.t()) ::
  {:ok,
   [{Yog.Functional.Model.node_id(), Yog.Functional.Model.node_id(), number()}]}
```

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 incoming and outgoing edges
from each context. For disconnected graphs this returns a tree for one component,
not a spanning forest across all components.

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`

```elixir
@spec scc(Yog.Functional.Model.t()) :: [[Yog.Functional.Model.node_id()]]
```

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.
Raises `ArgumentError` for undirected graphs.

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`

```elixir
@spec shortest_path(
  Yog.Functional.Model.t(),
  Yog.Functional.Model.node_id(),
  Yog.Functional.Model.node_id()
) :: {:ok, [Yog.Functional.Model.node_id()], number()} | {:error, :no_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 (`nil` defaults to `1`). Weights should be
non-negative numbers; negative weights are outside Dijkstra's assumptions.

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`

```elixir
@spec topsort(Yog.Functional.Model.t()) ::
  {:ok, [Yog.Functional.Model.node_id()]} | {:error, :cycle_detected}
```

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*