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

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

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

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

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