# `Yog.Functional.Model`
[🔗](https://github.com/code-shoily/yog_ex/blob/v0.98.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
defined recursively: a graph is either empty, or a node context "patched" into
an existing graph.

## 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 its edges from
  the graph. This enables recursive algorithms that naturally terminate without
  explicit visited sets.
- **Embed**: The inverse of `match` — restores a node and its edges into a graph.

## Example Use Cases

- **Recursive algorithms**: DFS, BFS, Dijkstra, SCC — all 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.

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

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

This operation restores the node and all the incident edges described in the
provided context. Note that it assumes the neighbors referenced in the context
already exist in the target graph.

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

# `get_node!`

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

Gets a node's context from the graph, raising 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.

# `match`

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

This operation extracts the node and all its incident edges (both incoming and
outgoing). If the node is found, it returns `{:ok, context, remaining_graph}`.
Otherwise, it returns `{:error, :not_found}`.

# `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 (both incoming and outgoing) of a node.

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

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

# `remove_edge!`

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

Removes an edge, raising on error.

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

# `remove_undirected_edge!`

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

Removes an undirected edge, raising on error.

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