# `Yog.Functional.Model`
[🔗](https://github.com/code-shoily/yog_ex/blob/v1.0.0/lib/yog/functional/model.ex#L1)

Inductive graph representation based on Martin Erwig's
[Functional Graph Library](https://web.engr.oregonstate.edu/~erwig/fgl/) (FGL).

Unlike the adjacency-list representation in `Yog.Graph`, an inductive graph is
viewed recursively: a graph is either empty, or a node context "patched" into
a smaller graph.

The central operation is `match/2`: it removes one node from the graph and
returns both that node's full context and the remaining graph. Recursing on the
remaining graph gives algorithms a natural "visited set": a matched node is no
longer present and cannot be matched again.

## Core Operations

| Operation | Function | Description |
|-----------|----------|-------------|
| **Decompose** | `match/2` | Extract a node + its edges, returning the *shrunken* graph |
| **Compose** | `embed/2` | Insert a node context back into a graph |
| **Inspect** | `match_any/1` | Decompose an arbitrary node |
| **Interop** | `from_adjacency_graph/1` | Convert from adjacency-based `Yog.Graph` |
| **Interop** | `to_adjacency_graph/1` | Convert back to adjacency-based `Yog.Graph` |

## Key Concepts

- **Context**: A node's identity, label, and its incident edges (`in_edges`, `out_edges`).
- **Match**: The primary operation — extracts a node and removes all incident
  references to it from the remaining graph. This enables recursive algorithms
  that naturally terminate without an external visited set for matched nodes.
- **Embed**: The inverse of `match` when used with the matching remaining graph —
  restores a node context and reconnects it to neighbors that are present.

## Example Use Cases

- **Recursive algorithms**: DFS, BFS, Dijkstra, SCC — implemented via repeated
  `match/2` calls that shrink the graph at each step
- **Functional transformations**: Map over nodes/edges, filter, reverse
- **Teaching**: The inductive structure makes graph algorithm correctness proofs
  straightforward

## References

- [Original FGL Paper (Erwig, 2001)](https://web.engr.oregonstate.edu/~erwig/papers/InductiveGraphs_JFP01.pdf)
- [Haskell FGL Library](https://hackage.haskell.org/package/fgl)

# `direction`

```elixir
@type direction() :: :directed | :undirected
```

# `edge_label`

```elixir
@type edge_label() :: any()
```

# `node_id`

```elixir
@type node_id() :: any()
```

# `node_label`

```elixir
@type node_label() :: any()
```

# `t`

```elixir
@type t() :: %Yog.Functional.Model{
  direction: direction(),
  nodes: %{required(node_id()) => Yog.Functional.Model.Context.t()}
}
```

# `add_edge`

```elixir
@spec add_edge(t(), node_id(), node_id(), edge_label()) ::
  {:ok, t()} | {:error, :source_not_found | :target_not_found}
```

Adds an edge, respecting the graph's directionality.

For directed graphs, only `from_id -> to_id` is added. For undirected graphs,
both directions are represented internally so neighbor queries remain simple.

Returns `{:error, :source_not_found}` or `{:error, :target_not_found}` if either
endpoint is missing.

# `add_edge!`

```elixir
@spec add_edge!(t(), node_id(), node_id(), edge_label()) :: t()
```

Adds an edge, raising on error.

# `add_undirected_edge`

```elixir
@spec add_undirected_edge(t(), node_id(), node_id(), edge_label()) ::
  {:ok, t()} | {:error, :source_not_found | :target_not_found}
```

Adds an undirected edge between two nodes.

# `add_undirected_edge!`

```elixir
@spec add_undirected_edge!(t(), node_id(), node_id(), edge_label()) :: t()
```

Adds an undirected edge, raising on error.

# `degree`

```elixir
@spec degree(t(), node_id()) :: {:ok, non_neg_integer()} | {:error, :not_found}
```

Returns the total degree of a node (in_degree + out_degree).

# `edges`

```elixir
@spec edges(t()) :: [{node_id(), node_id(), edge_label()}]
```

Returns all edges in the graph as a list of tuples `{from_id, to_id, label}`.

# `embed`

```elixir
@spec embed(Yog.Functional.Model.Context.t(), t()) :: t()
```

Embeds (patches) a node context back into a graph.

This is the inverse of `match/2` when used with the remaining graph returned by
that same match. It restores the node and reconnects incident edges to neighbor
nodes that are present in the target graph.

If the context references neighbors that are absent from the target graph, those
reverse references are not recreated, but the context itself is still inserted.

## Examples

    iex> graph =
    ...>   Yog.Functional.Model.empty()
    ...>   |> Yog.Functional.Model.put_node(1, "A")
    ...>   |> Yog.Functional.Model.put_node(2, "B")
    ...>   |> Yog.Functional.Model.add_edge!(1, 2, :edge)
    iex> {:ok, ctx, remaining} = Yog.Functional.Model.match(graph, 1)
    iex> restored = Yog.Functional.Model.embed(ctx, remaining)
    iex> Yog.Functional.Model.has_edge?(restored, 1, 2)
    true

# `empty`

```elixir
@spec empty() :: t()
```

Creates an empty directed graph.

## Examples

    iex> graph = Yog.Functional.Model.empty()
    iex> Yog.Functional.Model.empty?(graph)
    true

# `empty?`

```elixir
@spec empty?(t()) :: boolean()
```

Checks if the graph is empty.

# `ensure_node`

```elixir
@spec ensure_node(t(), node_id(), node_label()) :: t()
```

Ensures a node exists in the graph.

# `from_adjacency_graph`

```elixir
@spec from_adjacency_graph(Yog.Graph.t()) :: t()
```

Converts an adjacency-based `Yog.Graph` into a functional inductive model.

## Examples

    iex> alias Yog.Functional.Model
    iex> eg = Yog.Model.new(:directed) |> Yog.Model.add_node(1, "A")
    iex> fg = Model.from_adjacency_graph(eg)
    iex> Model.size(fg)
    1

# `get_edge`

```elixir
@spec get_edge(t(), node_id(), node_id()) ::
  {:ok, edge_label()} | {:error, :not_found}
```

Gets the label of an edge between two nodes.

## Examples

    iex> graph = Yog.Functional.Model.empty()
    ...> |> Yog.Functional.Model.put_node(1, "A")
    ...> |> Yog.Functional.Model.put_node(2, "B")
    ...> |> Yog.Functional.Model.add_edge!(1, 2, "weight")
    iex> Yog.Functional.Model.get_edge(graph, 1, 2)
    {:ok, "weight"}

# `get_node`

```elixir
@spec get_node(t(), node_id()) ::
  {:ok, Yog.Functional.Model.Context.t()} | {:error, :not_found}
```

Gets a node's context from the graph.

Returns `{:ok, context}` when the node exists, or `{:error, :not_found}` when it
does not.

# `get_node!`

```elixir
@spec get_node!(t(), node_id()) :: Yog.Functional.Model.Context.t()
```

Gets a node's context from the graph, raising `KeyError` if not found.

# `has_edge?`

```elixir
@spec has_edge?(t(), node_id(), node_id()) :: boolean()
```

Checks if an edge exists between two nodes.

# `has_node?`

```elixir
@spec has_node?(t(), node_id()) :: boolean()
```

Checks if a node exists in the graph.

## Examples

    iex> graph = Yog.Functional.Model.empty() |> Yog.Functional.Model.put_node(1, "A")
    iex> Yog.Functional.Model.has_node?(graph, 1)
    true
    iex> Yog.Functional.Model.has_node?(graph, 2)
    false

# `in_degree`

```elixir
@spec in_degree(t(), node_id()) :: {:ok, non_neg_integer()} | {:error, :not_found}
```

Returns the in-degree of a node.

# `in_neighbors`

```elixir
@spec in_neighbors(t(), node_id()) ::
  {:ok, %{required(node_id()) => edge_label()}} | {:error, :not_found}
```

Returns the incoming neighbors of a node as `%{neighbor_id => edge_label}`.

Returns `{:error, :not_found}` if the target node is missing.

# `match`

```elixir
@spec match(t(), node_id()) ::
  {:ok, Yog.Functional.Model.Context.t(), t()} | {:error, :not_found}
```

Matches a node in the graph, returning its context and the remaining graph.

This is the defining inductive operation. It extracts the node's `Context` and
removes the node plus all incident edge references from the returned graph.
Recursing on the remaining graph means this node cannot be visited again.

If the node is found, returns `{:ok, context, remaining_graph}`. Otherwise,
returns `{:error, :not_found}`.

## Examples

    iex> graph =
    ...>   Yog.Functional.Model.empty()
    ...>   |> Yog.Functional.Model.put_node(1, "A")
    ...>   |> Yog.Functional.Model.put_node(2, "B")
    ...>   |> Yog.Functional.Model.add_edge!(1, 2, :edge)
    iex> {:ok, ctx, remaining} = Yog.Functional.Model.match(graph, 1)
    iex> ctx.id
    1
    iex> Yog.Functional.Model.has_node?(remaining, 1)
    false
    iex> Yog.Functional.Model.has_edge?(remaining, 1, 2)
    false
    iex> Yog.Functional.Model.has_node?(remaining, 2)
    true

# `match_any`

```elixir
@spec match_any(t()) ::
  {:ok, Yog.Functional.Model.Context.t(), t()} | {:error, :empty}
```

Matches an arbitrary node from the graph.

## Examples

    iex> graph = Yog.Functional.Model.empty() |> Yog.Functional.Model.put_node(1, "A")
    iex> {:ok, ctx, remaining} = Yog.Functional.Model.match_any(graph)
    iex> ctx.id
    1
    iex> Yog.Functional.Model.empty?(remaining)
    true

# `neighbors`

```elixir
@spec neighbors(t(), node_id()) :: {:ok, [node_id()]} | {:error, :not_found}
```

Returns all unique neighbors of a node, combining incoming and outgoing edges.

For directed graphs this is the union of predecessors and successors. For
undirected graphs the incoming and outgoing maps are symmetric by convention.

# `new`

```elixir
@spec new(direction()) :: t()
```

Creates a new graph with specified direction (defaults to :directed).

## Examples

    iex> graph = Yog.Functional.Model.new(:directed)
    iex> graph.direction
    :directed

# `node_ids`

```elixir
@spec node_ids(t()) :: [node_id()]
```

Returns all node IDs in the graph.

# `nodes`

```elixir
@spec nodes(t()) :: [Yog.Functional.Model.Context.t()]
```

Returns all nodes (contexts) in the graph.

# `out_degree`

```elixir
@spec out_degree(t(), node_id()) :: {:ok, non_neg_integer()} | {:error, :not_found}
```

Returns the out-degree of a node.

# `out_neighbors`

```elixir
@spec out_neighbors(t(), node_id()) ::
  {:ok, %{required(node_id()) => edge_label()}} | {:error, :not_found}
```

Returns the outgoing neighbors of a node as `%{neighbor_id => edge_label}`.

Returns `{:error, :not_found}` if the source node is missing.

# `put_node`

```elixir
@spec put_node(t(), node_id(), node_label()) :: t()
```

Adds or updates a node in the graph.

# `remove_edge`

```elixir
@spec remove_edge(t(), node_id(), node_id()) :: {:ok, t()}
```

Removes an edge, respecting graph directionality.

Missing endpoints or missing edges are ignored; the function always returns
`{:ok, graph}`.

# `remove_edge!`

```elixir
@spec remove_edge!(t(), node_id(), node_id()) :: t()
```

Removes an edge and returns the updated graph.

# `remove_node`

```elixir
@spec remove_node(t(), node_id()) :: {:ok, t()}
```

Removes a node and all its edges from the graph.

# `remove_node!`

```elixir
@spec remove_node!(t(), node_id()) :: t()
```

Removes a node and all its edges from the graph, raising on error.

# `remove_undirected_edge`

```elixir
@spec remove_undirected_edge(t(), node_id(), node_id()) :: {:ok, t()}
```

Removes an undirected edge between two nodes.

Missing endpoints or missing edges are ignored; the function always returns
`{:ok, graph}`.

# `remove_undirected_edge!`

```elixir
@spec remove_undirected_edge!(t(), node_id(), node_id()) :: t()
```

Removes an undirected edge and returns the updated graph.

# `size`

```elixir
@spec size(t()) :: non_neg_integer()
```

Returns the number of nodes in the graph.

## Examples

    iex> graph = Yog.Functional.Model.empty() |> Yog.Functional.Model.put_node(1, "A")
    iex> Yog.Functional.Model.size(graph)
    1

# `to_adjacency_graph`

```elixir
@spec to_adjacency_graph(t()) :: Yog.Graph.t()
```

Converts a functional inductive model into an adjacency-based `Yog.Graph`.

## Examples

    iex> alias Yog.Functional.Model
    iex> fg = Model.empty() |> Model.put_node(1, "A")
    iex> eg = Model.to_adjacency_graph(fg)
    iex> eg.nodes[1]
    "A"

---

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