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

Core multigraph data model and primitive operations.

A multigraph allows multiple (parallel) edges between the same pair of nodes.
Both directed and undirected variants are supported.

The internal representation maintains three synchronized indexes:
- `nodes`: NodeId → Data
- `edges`: EdgeId → {from, to, data} — canonical edge store
- `out_edge_ids`: NodeId → MapSet[EdgeId] — outgoing edge IDs per node
- `in_edge_ids`: NodeId → MapSet[EdgeId] — incoming edge IDs per node

All operations in this module operate on `%Yog.Multi.Graph{}` structs.

## Edge IDs

Every edge added to a multigraph is assigned a unique, sequential non-negative integer
`EdgeId` (starting from `0`). For undirected graphs, a single `EdgeId` is generated, and
the edge is indexed in both directions.

## Complexity Summary

- Node additions / queries / lookups: $\mathcal{O}(1)$ time.
- Edge additions / removals: $\mathcal{O}(1)$ time.
- Successors / predecessors / edges between nodes: $\mathcal{O}(\text{deg}(v))$ time.
- Collapsing multigraph to simple graph: $\mathcal{O}(V + E \log E)$ time.

# `edge_id`

```elixir
@type edge_id() :: Yog.Multi.Graph.edge_id()
```

# `t`

```elixir
@type t() :: Yog.Multi.Graph.t()
```

# `add_edge`

```elixir
@spec add_edge(t(), Yog.Model.node_id(), Yog.Model.node_id(), any()) ::
  {t(), edge_id()}
```

Adds an edge from `from` to `to` with the given data payload.

Returns `{updated_graph, new_edge_id}`.

If `from` or `to` nodes do not already exist in the graph, they are created automatically
with `nil` default data.

For undirected graphs, a single `EdgeId` is generated and indexed for both directions.

**Time Complexity:** $\mathcal{O}(1)$

## Examples

    iex> multi = Yog.Multi.directed()
    iex> {multi, eid} = Yog.Multi.Model.add_edge(multi, 1, 2, "link")
    iex> eid
    0
    iex> Yog.Multi.Model.has_edge(multi, 0)
    true

# `add_node`

```elixir
@spec add_node(t(), Yog.Model.node_id(), any()) :: t()
```

Adds a node with the given ID and data.
If the node already exists, its data is updated while preserving all incident edges.

**Time Complexity:** $\mathcal{O}(1)$

## Parameters

- `graph` - Multigraph struct
- `id` - Node ID
- `data` - Custom data associated with the node (default: `nil`)

## Errors

- Raises `ArgumentError` if `graph` is not a `%Yog.Multi.Graph{}` struct.

# `all_edge_ids`

```elixir
@spec all_edge_ids(t()) :: [edge_id()]
```

Returns all edge IDs in the multigraph.

**Time Complexity:** $\mathcal{O}(E)$

# `all_edges`

```elixir
@spec all_edges(t()) :: [{edge_id(), Yog.Model.node_id(), Yog.Model.node_id(), any()}]
```

Returns all edges in the multigraph as `[{edge_id, from, to, data}]` sorted by `edge_id`.

**Time Complexity:** $\mathcal{O}(E \log E)$

## Examples

    iex> multi = Yog.Multi.directed()
    ...> {multi, _e1} = Yog.Multi.Model.add_edge(multi, 1, 2, "a")
    iex> Yog.Multi.Model.all_edges(multi)
    [{0, 1, 2, "a"}]

# `all_nodes`

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

Returns all node IDs in the multigraph.

**Time Complexity:** $\mathcal{O}(V)$

# `degree`

```elixir
@spec degree(t(), Yog.Model.node_id()) :: non_neg_integer()
```

Returns the total degree of a node.

- For directed graphs: `in_degree + out_degree`.
- For undirected graphs: same as `out_degree`.

Self-loops contribute 2 to degree in undirected graphs (standard graph theory convention)
and 1 to each of in-degree and out-degree in directed graphs.

**Time Complexity:** $\mathcal{O}(\text{deg}(id))$

# `directed`

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

Creates a new, empty directed multigraph.

**Time Complexity:** $\mathcal{O}(1)$

# `edge`

```elixir
@spec edge(t(), edge_id()) :: {Yog.Model.node_id(), Yog.Model.node_id(), any()} | nil
```

Returns the `{from, to, data}` tuple for the specified `EdgeId`, or `nil` if not found.

**Time Complexity:** $\mathcal{O}(1)$

# `edge_count`

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

Synonym for `size/1`. Returns total number of edges in the multigraph.

# `edge_count`

```elixir
@spec edge_count(t(), Yog.Model.node_id(), Yog.Model.node_id()) :: non_neg_integer()
```

Returns the number of parallel edges between two nodes.

**Time Complexity:** $\mathcal{O}(\text{deg}(from))$

# `edge_data`

```elixir
@spec edge_data(t(), edge_id()) :: any()
```

Returns edge data for the specified `EdgeId`, or `nil` if not found.

**Time Complexity:** $\mathcal{O}(1)$

# `edges_between`

```elixir
@spec edges_between(t(), Yog.Model.node_id(), Yog.Model.node_id()) :: [
  {edge_id(), any()}
]
```

Returns all parallel edges between `from` and `to` as `[{edge_id, edge_data}]`.

**Time Complexity:** $\mathcal{O}(\text{deg}(from))$

# `fetch_edge`

```elixir
@spec fetch_edge(t(), edge_id()) ::
  {:ok, {Yog.Model.node_id(), Yog.Model.node_id(), any()}} | :error
```

Fetches details for the specified `EdgeId`.
Returns `{:ok, {from, to, data}}` if found, or `:error` otherwise.

**Time Complexity:** $\mathcal{O}(1)$

# `fetch_node`

```elixir
@spec fetch_node(t(), Yog.Model.node_id()) :: {:ok, any()} | :error
```

Fetches node data for the given node ID.
Returns `{:ok, data}` if the node exists, or `:error` otherwise.

**Time Complexity:** $\mathcal{O}(1)$

# `from_map`

```elixir
@spec from_map(map()) :: t()
```

Backward compatibility helper: converts legacy map representation to `%Yog.Multi.Graph{}`.

# `has_edge`

```elixir
@spec has_edge(t(), edge_id()) :: boolean()
```

Returns `true` if an edge with the specified `EdgeId` exists.

**Time Complexity:** $\mathcal{O}(1)$

# `has_edge?`

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

Predicate synonym for `has_edge/2`. Returns `true` if edge ID exists.

# `has_edge_between`

```elixir
@spec has_edge_between(t(), Yog.Model.node_id(), Yog.Model.node_id()) :: boolean()
```

Synonym for `has_edge_between?/3`.

# `has_edge_between?`

```elixir
@spec has_edge_between?(t(), Yog.Model.node_id(), Yog.Model.node_id()) :: boolean()
```

Returns `true` if there is at least one edge between `from` and `to`.

**Time Complexity:** $\mathcal{O}(\text{deg}(from))$

# `has_node?`

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

Returns `true` if the node exists in the multigraph.

**Time Complexity:** $\mathcal{O}(1)$

# `in_degree`

```elixir
@spec in_degree(t(), Yog.Model.node_id()) :: non_neg_integer()
```

Returns the in-degree of a node (number of incoming edges).
For undirected graphs, self-loops contribute 2 to degree.

**Time Complexity:** $\mathcal{O}(\text{deg}(id))$

# `kind`

```elixir
@spec kind(t()) :: Yog.graph_type()
```

Synonym for `type/1`. Returns the graph kind (`:directed` or `:undirected`).

# `new`

```elixir
@spec new(Yog.graph_type()) :: t()
```

Creates a new, empty multigraph of the given type (`:directed` or `:undirected`).

**Time Complexity:** $\mathcal{O}(1)$

## Examples

    iex> graph = Yog.Multi.Model.new(:directed)
    iex> Yog.Multi.Model.type(graph)
    :directed

    iex> graph = Yog.Multi.Model.new(:undirected)
    iex> Yog.Multi.Model.type(graph)
    :undirected

## Errors

- Raises `ArgumentError` if `graph_type` is not `:directed` or `:undirected`.

# `node`

```elixir
@spec node(t(), Yog.Model.node_id()) :: any()
```

Returns the data associated with a node, or `nil` if the node does not exist.

**Time Complexity:** $\mathcal{O}(1)$

# `node_count`

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

Synonym for `order/1`. Returns the number of nodes in the multigraph.

**Time Complexity:** $\mathcal{O}(1)$

# `node_data`

```elixir
@spec node_data(t(), Yog.Model.node_id()) :: any()
```

Synonym for `node/2`. Returns data associated with the given node.

# `order`

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

Returns the number of nodes in the multigraph (graph order).

**Time Complexity:** $\mathcal{O}(1)$

# `out_degree`

```elixir
@spec out_degree(t(), Yog.Model.node_id()) :: non_neg_integer()
```

Returns the out-degree of a node (number of outgoing edges).
For undirected graphs, self-loops contribute 2 to degree.

**Time Complexity:** $\mathcal{O}(\text{deg}(id))$

# `predecessors`

```elixir
@spec predecessors(t(), Yog.Model.node_id()) :: [
  {Yog.Model.node_id(), edge_id(), any()}
]
```

Returns all incoming edges to `id` as `[{from_node, edge_id, edge_data}]`.

**Time Complexity:** $\mathcal{O}(\text{deg}(id))$

# `remove_edge`

```elixir
@spec remove_edge(t(), edge_id()) :: t()
```

Removes a single edge by its `EdgeId`.

If the edge ID does not exist, the graph is returned unchanged.
For undirected graphs, both direction indexes are cleaned up.

**Time Complexity:** $\mathcal{O}(1)$

# `remove_node`

```elixir
@spec remove_node(t(), Yog.Model.node_id()) :: t()
```

Removes a node and all incident edges connected to it.

**Time Complexity:** $\mathcal{O}(\text{deg}(v))$

## Examples

    iex> multi = Yog.Multi.directed() |> Yog.Multi.add_node(1, "A")
    iex> multi = Yog.Multi.remove_node(multi, 1)
    iex> Yog.Multi.order(multi)
    0

# `size`

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

Returns the total number of physical edges in the multigraph (graph size).

**Time Complexity:** $\mathcal{O}(1)$

# `successors`

```elixir
@spec successors(t(), Yog.Model.node_id()) :: [
  {Yog.Model.node_id(), edge_id(), any()}
]
```

Returns all outgoing edges from `id` as `[{to_node, edge_id, edge_data}]`.

**Time Complexity:** $\mathcal{O}(\text{deg}(id))$

# `to_map`

```elixir
@spec to_map(t()) :: map()
```

Converts `%Yog.Multi.Graph{}` to legacy map representation.

# `to_simple_graph`

```elixir
@spec to_simple_graph(t()) :: Yog.graph()
```

Converts the multigraph to a simple graph deterministically.

When there are parallel edges, the edge with the lowest `edge_id` (the first added edge)
is preserved.

**Time Complexity:** $\mathcal{O}(V + E \log E)$

# `to_simple_graph`

```elixir
@spec to_simple_graph(t(), (any(), any() -> any())) :: Yog.graph()
```

Collapses the multigraph into a simple `Yog.graph()` by combining
parallel edges with `combine_fn(existing_data, new_data)`.

**Time Complexity:** $\mathcal{O}(V + E)$

## Errors

- Raises `ArgumentError` if `combine_fn` is not an arity-2 function.

## Example

Keep minimum weight among parallel edges:

    to_simple_graph(mg, fn a, b -> min(a, b) end)

# `to_simple_graph_max_edges`

```elixir
@spec to_simple_graph_max_edges(t()) :: Yog.graph()
```

Collapses parallel edges, keeping the maximum numerical weight.

**Time Complexity:** $\mathcal{O}(V + E)$

# `to_simple_graph_min_edges`

```elixir
@spec to_simple_graph_min_edges(t()) :: Yog.graph()
```

Collapses parallel edges, keeping the minimum numerical weight.

**Time Complexity:** $\mathcal{O}(V + E)$

# `to_simple_graph_sum_edges`

```elixir
@spec to_simple_graph_sum_edges(t()) :: Yog.graph()
```

Collapses parallel edges, summing weights using `&Kernel.+/2`.

**Time Complexity:** $\mathcal{O}(V + E)$

# `to_simple_graph_sum_edges`

```elixir
@spec to_simple_graph_sum_edges(t(), (any(), any() -> any())) :: Yog.graph()
```

Collapses parallel edges, combining weights with the provided `add` function.

**Time Complexity:** $\mathcal{O}(V + E)$

# `type`

```elixir
@spec type(t()) :: Yog.graph_type()
```

Returns the type of the multigraph (`:directed` or `:undirected`).

**Time Complexity:** $\mathcal{O}(1)$

# `undirected`

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

Creates a new, empty undirected multigraph.

**Time Complexity:** $\mathcal{O}(1)$

---

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