@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}

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.

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]]

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}

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]