# `Yog.Operation`
[🔗](https://github.com/code-shoily/yog_ex/blob/v0.98.5/lib/yog/operation.ex#L1)

Graph operations - Set-theoretic operations, composition, and structural comparison.

This module implements binary operations that treat graphs as sets of nodes and edges,
following NetworkX's "Graph as a Set" philosophy. These operations allow you to combine,
compare, and analyze structural differences between graphs.

## Set-Theoretic Operations

| Function | Description | Use Case |
|----------|-------------|----------|
| `union/2` | All nodes and edges from both graphs | Combine graph data |
| `intersection/2` | Only nodes and edges common to both | Find common structure |
| `difference/2` | Nodes/edges in first but not second | Find unique structure |
| `symmetric_difference/2` | Edges in exactly one graph | Find differing structure |

## Composition & Joins

| Function | Description | Use Case |
|----------|-------------|----------|
| `disjoint_union/2` | Combine with automatic ID re-indexing | Safe graph combination |
| `cartesian_product/4` | Multiply graphs (grids, hypercubes) | Generate complex structures |
| `compose/2` | Merge overlapping graphs with combined edges | Layered systems |
| `power/2` | k-th power (connect nodes within distance k) | Reachability analysis |

## Structural Comparison

| Function | Description | Use Case |
|----------|-------------|----------|
| `subgraph?/2` | Check if first is subset of second | Validation, pattern matching |
| `isomorphic?/2` | Check if graphs are structurally identical | Graph comparison |

## Examples

    # Two triangle graphs with overlapping IDs
    iex> triangle1 = Yog.undirected()
    ...> |> Yog.add_node(0, nil)
    ...> |> Yog.add_node(1, nil)
    ...> |> Yog.add_node(2, nil)
    ...> |> Yog.add_edge_ensure(from: 0, to: 1, with: 1)
    ...> |> Yog.add_edge_ensure(from: 1, to: 2, with: 1)
    ...> |> Yog.add_edge_ensure(from: 2, to: 0, with: 1)
    iex> triangle2 = Yog.undirected()
    ...> |> Yog.add_node(0, nil)
    ...> |> Yog.add_node(1, nil)
    ...> |> Yog.add_node(2, nil)
    ...> |> Yog.add_edge_ensure(from: 0, to: 1, with: 1)
    ...> |> Yog.add_edge_ensure(from: 1, to: 2, with: 1)
    ...> |> Yog.add_edge_ensure(from: 2, to: 0, with: 1)
    iex> # disjoint_union re-indexes the second graph automatically
    ...> combined = Yog.Operation.disjoint_union(triangle1, triangle2)
    iex> # Result: 6 nodes (0-5), two separate triangles
    ...> Yog.Model.order(combined)
    6

    # Finding common structure
    iex> graph_a = Yog.undirected()
    ...> |> Yog.add_node(1, nil)
    ...> |> Yog.add_node(2, nil)
    ...> |> Yog.add_edge_ensure(from: 1, to: 2, with: 1)
    iex> graph_b = Yog.undirected()
    ...> |> Yog.add_node(1, nil)
    ...> |> Yog.add_node(2, nil)
    ...> |> Yog.add_edge_ensure(from: 1, to: 2, with: 1)
    iex> common = Yog.Operation.intersection(graph_a, graph_b)
    iex> Yog.Model.order(common)
    2

# `cartesian_product`

```elixir
@spec cartesian_product(Yog.Graph.t(), Yog.Graph.t(), any(), any()) :: Yog.Graph.t()
```

Returns the Cartesian product of two graphs.

Creates a new graph where each node represents a pair of nodes from the
input graphs. Useful for generating grids, hypercubes, and other
complex structures.

> [!WARNING]
> **Performance Warning:** The size of the resulting Cartesian product graph grows
> quadratically. The output graph contains $V_1 	imes V_2$ nodes and
> $E_1 	imes V_2 + E_2 	imes V_1$ edges. For larger graphs (e.g., $V_1, V_2 > 1,000$),
> this operation can consume substantial CPU time and memory.

**Time Complexity:** O(V₁ × V₂ + E₁ × V₂ + E₂ × V₁)

## Parameters

- `first` - First input graph
- `second` - Second input graph
- `default_first` - Default edge data for edges derived from `first`
- `default_second` - Default edge data for edges derived from `second`

## Examples

    iex> g1 = Yog.undirected()
    ...> |> Yog.add_node(0, nil)
    ...> |> Yog.add_node(1, nil)
    ...> |> Yog.add_edge_ensure(from: 0, to: 1, with: 1)
    iex> g2 = Yog.undirected()
    ...> |> Yog.add_node(0, nil)
    ...> |> Yog.add_node(1, nil)
    ...> |> Yog.add_edge_ensure(from: 0, to: 1, with: 1)
    iex> product = Yog.Operation.cartesian_product(g1, g2, 0, 0)
    iex> # 2x2 grid structure: 4 nodes
    ...> Yog.Model.order(product)
    4

# `compose`

```elixir
@spec compose(Yog.Graph.t(), Yog.Graph.t()) :: Yog.Graph.t()
```

Composes two graphs by merging overlapping nodes and combining their edges.

This is equivalent to `union/2` - both graphs are merged together with
`other`'s data taking precedence on conflicts.

**Time Complexity:** O(V₁ + V₂ + E₁ + E₂)

## Examples

    iex> g1 = Yog.undirected()
    ...> |> Yog.add_node(1, nil)
    ...> |> Yog.add_node(2, nil)
    ...> |> Yog.add_edge_ensure(from: 1, to: 2, with: 1)
    iex> g2 = Yog.undirected()
    ...> |> Yog.add_node(2, nil)
    ...> |> Yog.add_node(3, nil)
    ...> |> Yog.add_edge_ensure(from: 2, to: 3, with: 1)
    iex> composed = Yog.Operation.compose(g1, g2)
    iex> Yog.Model.order(composed)
    3

# `difference`

```elixir
@spec difference(Yog.Graph.t(), Yog.Graph.t()) :: Yog.Graph.t()
```

Returns a graph containing nodes and edges that exist in the first graph
but not in the second.

Any node that appears in `second` is removed from the result, along with
all its incident edges. Of the remaining nodes, only edges that do not
appear in `second` are kept.

**Time Complexity:** O(V + E)

## Examples

    iex> g1 = Yog.undirected()
    ...> |> Yog.add_node(1, nil)
    ...> |> Yog.add_node(2, nil)
    ...> |> Yog.add_edge_ensure(from: 1, to: 2, with: 1)
    iex> g2 = Yog.undirected()
    ...> |> Yog.add_node(3, nil)
    iex> diff = Yog.Operation.difference(g1, g2)
    iex> Yog.Model.order(diff)
    2
    iex> Yog.Model.has_edge?(diff, 1, 2)
    true

# `disjoint_union`

```elixir
@spec disjoint_union(Yog.Graph.t(), Yog.Graph.t()) :: Yog.Graph.t()
```

Computes the disjoint union of two graphs.

Unlike a simple join, this function guarantees that nodes from Graph A
and Graph B remain distinct by tagging their IDs as `{0, id}` and `{1, id}`,
even if they share the same original ID.

The resulting graph uses the kind (`:directed` or `:undirected`) from
`graph_a`. Combining graphs of different kinds may lead to unexpected
edge behavior.

**Time Complexity:** O(V₁ + V₂ + E₁ + E₂)

## Example
    iex> g1 = Yog.directed() |> Yog.add_node("root", "Data A")
    iex> g2 = Yog.directed() |> Yog.add_node("root", "Data B")
    iex> union = Yog.Operation.disjoint_union(g1, g2)
    iex> Yog.Model.node_count(union)
    2
    iex> Yog.Model.node(union, {0, "root"})
    "Data A"

# `intersection`

```elixir
@spec intersection(Yog.Graph.t(), Yog.Graph.t()) :: Yog.Graph.t()
```

Returns a graph containing only nodes and edges that exist in both input graphs.

For directed graphs, a directed edge must exist in both graphs to be kept.
For undirected graphs, an undirected edge must exist in both graphs.

**Time Complexity:** O(V + E)

## Examples

    iex> g1 = Yog.undirected()
    ...> |> Yog.add_node(1, nil)
    ...> |> Yog.add_node(2, nil)
    ...> |> Yog.add_node(3, nil)
    ...> |> Yog.add_edge_ensure(from: 1, to: 2, with: 1)
    ...> |> Yog.add_edge_ensure(from: 2, to: 3, with: 1)
    iex> g2 = Yog.undirected()
    ...> |> Yog.add_node(1, nil)
    ...> |> Yog.add_node(2, nil)
    ...> |> Yog.add_node(3, nil)
    ...> |> Yog.add_edge_ensure(from: 1, to: 2, with: 1)
    iex> intersection = Yog.Operation.intersection(g1, g2)
    iex> Yog.Model.order(intersection)
    3

# `isomorphic?`

```elixir
@spec isomorphic?(Yog.Graph.t(), Yog.Graph.t()) :: boolean()
```

Checks if two graphs are isomorphic (structurally identical).

Two graphs are isomorphic if there exists a bijection between their node sets
that preserves adjacency. This implementation uses degree sequence comparison
and backtracking to test for isomorphism.

> [!WARNING]
> **Performance Warning:** Graph isomorphism is a computationally hard problem.
> While this function includes fast heuristics (degree sequence matching), the worst-case
> backtracking complexity is exponential. It should not be used on graphs with more
> than a few dozen nodes, especially highly symmetric graphs (like strongly regular graphs)
> where degree heuristics fail.

**Time Complexity:** O(V log V + E) for the fast checks; exponential in the
worst case due to backtracking (not recommended for large graphs).

## Examples

    # Two identical triangles are isomorphic
    iex> g1 = Yog.undirected()
    ...> |> Yog.add_node(0, nil)
    ...> |> Yog.add_node(1, nil)
    ...> |> Yog.add_node(2, nil)
    ...> |> Yog.add_edge_ensure(from: 0, to: 1, with: 1)
    ...> |> Yog.add_edge_ensure(from: 1, to: 2, with: 1)
    ...> |> Yog.add_edge_ensure(from: 2, to: 0, with: 1)
    iex> g2 = Yog.undirected()
    ...> |> Yog.add_node(10, nil)
    ...> |> Yog.add_node(20, nil)
    ...> |> Yog.add_node(30, nil)
    ...> |> Yog.add_edge_ensure(from: 10, to: 20, with: 1)
    ...> |> Yog.add_edge_ensure(from: 20, to: 30, with: 1)
    ...> |> Yog.add_edge_ensure(from: 30, to: 10, with: 1)
    iex> Yog.Operation.isomorphic?(g1, g2)
    true
    iex> # Triangle is not isomorphic to a path
    iex> path = Yog.undirected()
    ...> |> Yog.add_node(0, nil)
    ...> |> Yog.add_node(1, nil)
    ...> |> Yog.add_node(2, nil)
    ...> |> Yog.add_edge_ensure(from: 0, to: 1, with: 1)
    ...> |> Yog.add_edge_ensure(from: 1, to: 2, with: 1)
    iex> Yog.Operation.isomorphic?(g1, path)
    false

# `lexicographic_product`

```elixir
@spec lexicographic_product(Yog.Graph.t(), Yog.Graph.t(), any(), any()) ::
  Yog.Graph.t()
```

Returns the Lexicographic product (composition) of two graphs.

The Lexicographic product $G_1[G_2]$ is a graph where the node set is the Cartesian product
$V(G_1) \times V(G_2)$. An edge exists between $(u_1, u_2)$ and $(v_1, v_2)$ if and only if:
- $u_1 \to v_1$ in $G_1$ (for all $u_2, v_2 \in V(G_2)$)
- $u_1 = v_1$ and $u_2 \to v_2$ in $G_2$

Edge weights are tuples:
- `{weight_first, default_first}` for edges derived from $G_1$
- `{default_second, weight_second}` for edges derived from $G_2$

> [!WARNING]
> **Performance Warning:** The size of the resulting Lexicographic product graph grows
> quadratically. The output graph contains $V_1 \times V_2$ nodes and $V_1 \times E_2 + E_1 \times V_2^2$
> edges. For larger or dense graphs, this operation can consume substantial CPU time and memory.

**Time Complexity:** O(V₁ × V₂ + E₁ × V₂² + V₁ × E₂)

## Examples

    iex> g1 = Yog.undirected()
    ...> |> Yog.add_node(0, nil)
    ...> |> Yog.add_node(1, nil)
    ...> |> Yog.add_edge_ensure(from: 0, to: 1, with: 10)
    iex> g2 = Yog.undirected()
    ...> |> Yog.add_node(0, nil)
    ...> |> Yog.add_node(1, nil)
    ...> |> Yog.add_edge_ensure(from: 0, to: 1, with: 20)
    iex> product = Yog.Operation.lexicographic_product(g1, g2, 0, 0)
    iex> Yog.Model.order(product)
    4
    iex> Yog.Model.edge_count(product)
    6

# `line_graph`

```elixir
@spec line_graph(Yog.Graph.t(), term()) :: Yog.Graph.t()
```

Returns the line graph of a graph.

The line graph L(G) is a graph where each node represents an edge of G,
and two nodes are adjacent if and only if their corresponding edges share
a common endpoint in G.

For **directed graphs**, two edges `(u, v)` and `(x, y)` are adjacent in the
line graph if and only if `v == x` (the head of the first edge matches the
tail of the second edge). This is the standard line digraph definition.

For **undirected graphs**, two edges `{u, v}` and `{x, y}` are adjacent if
and only if they share at least one endpoint.

Line graph nodes are represented as `{u, v}` tuples. For undirected graphs,
the tuple follows the same ordering convention as `Yog.Model.all_edges/1`
(`u <= v` using Erlang term ordering).

> [!WARNING]
> **Performance Warning:** Since each edge in the original graph becomes a node
> in the line graph, the line graph can grow extremely large. Specifically, it
> will have $E$ nodes and can have up to $O(E^2)$ edges in dense graphs.
> This operation has $O(E^2)$ time complexity and is not recommended for very dense or large graphs.

**Time Complexity:** O(E²) where E is the number of edges in the original graph

## Parameters

- `graph` - The input graph
- `default_weight` - Weight for edges in the line graph (default: 1)

## Examples

    iex> path = Yog.undirected()
    ...> |> Yog.add_node(0, nil)
    ...> |> Yog.add_node(1, nil)
    ...> |> Yog.add_node(2, nil)
    ...> |> Yog.add_edge_ensure(from: 0, to: 1, with: 10)
    ...> |> Yog.add_edge_ensure(from: 1, to: 2, with: 20)
    iex> lg = Yog.Operation.line_graph(path, 1)
    iex> # Line graph of a path has 2 nodes ({0,1} and {1,2}) and 1 edge
    iex> Yog.Model.order(lg)
    2
    iex> Yog.Model.has_edge?(lg, {0, 1}, {1, 2})
    true

# `power`

```elixir
@spec power(Yog.Graph.t(), integer(), any()) :: Yog.Graph.t()
```

Returns the k-th power of a graph.

The k-th power of a graph G, denoted G^k, is a graph where two nodes are
adjacent if and only if their distance in G is at most k.

Self-loops are never added.

> [!WARNING]
> **Performance Warning:** Computing the $k$-th power of a graph requires running BFS
> from every node. For larger $k$ or dense graphs, the resulting graph can approach
> a complete graph ($O(V^2)$ edges), causing high CPU and memory utilization.

**Time Complexity:** O(V × (V + E)) in the worst case

## Parameters

- `graph` - The input graph
- `k` - The power (distance threshold)
- `default_weight` - Weight for newly created edges

## Examples

    iex> path = Yog.undirected()
    ...> |> Yog.add_node(0, nil)
    ...> |> Yog.add_node(1, nil)
    ...> |> Yog.add_node(2, nil)
    ...> |> Yog.add_edge_ensure(from: 0, to: 1, with: 1)
    ...> |> Yog.add_edge_ensure(from: 1, to: 2, with: 1)
    iex> # G^2 connects nodes at distance <= 2
    ...> power = Yog.Operation.power(path, 2, 1)
    iex> # Node 0 and 2 should now be connected (distance 2 in original)
    ...> Yog.Model.has_edge?(power, 0, 2)
    true

# `strong_product`

```elixir
@spec strong_product(Yog.Graph.t(), Yog.Graph.t(), any(), any()) :: Yog.Graph.t()
```

Returns the Strong product of two graphs.

The Strong product $G_1 \boxtimes G_2$ is a graph where the node set is the Cartesian product
$V(G_1) \times V(G_2)$. An edge exists between $(u_1, u_2)$ and $(v_1, v_2)$ if and only if:
- $u_1 = v_1$ and $u_2 \to v_2$ in $G_2$ (vertical Cartesian edge)
- $u_2 = v_2$ and $u_1 \to v_1$ in $G_1$ (horizontal Cartesian edge)
- $u_1 \to v_1$ in $G_1$ and $u_2 \to v_2$ in $G_2$ (Tensor edge)

Edge weights are tuples:
- `{default_second, weight_second}` for vertical edges
- `{weight_first, default_first}` for horizontal edges
- `{weight_first, weight_second}` for tensor edges

> [!WARNING]
> **Performance Warning:** The size of the resulting Strong product graph grows
> quadratically. For larger or dense graphs, this operation can consume substantial CPU
> time and memory.

**Time Complexity:** O(V₁ × V₂ + E₁ × V₂ + E₂ × V₁ + E₁ × E₂)

## Examples

    iex> g1 = Yog.undirected()
    ...> |> Yog.add_node(0, nil)
    ...> |> Yog.add_node(1, nil)
    ...> |> Yog.add_edge_ensure(from: 0, to: 1, with: 10)
    iex> g2 = Yog.undirected()
    ...> |> Yog.add_node(0, nil)
    ...> |> Yog.add_node(1, nil)
    ...> |> Yog.add_edge_ensure(from: 0, to: 1, with: 20)
    iex> product = Yog.Operation.strong_product(g1, g2, 0, 0)
    iex> Yog.Model.order(product)
    4
    iex> Yog.Model.edge_count(product)
    6

# `subgraph?`

```elixir
@spec subgraph?(Yog.Graph.t(), Yog.Graph.t()) :: boolean()
```

Checks if the first graph is a subgraph of the second graph.

Returns `true` if all nodes and edges in the first graph exist in the second.

**Time Complexity:** O(Vₚ + Eₚ) where Vₚ and Eₚ are the nodes and edges of the potential subgraph

## Examples

    iex> container = Yog.undirected()
    ...> |> Yog.add_node(1, nil)
    ...> |> Yog.add_node(2, nil)
    ...> |> Yog.add_node(3, nil)
    ...> |> Yog.add_edge_ensure(from: 1, to: 2, with: 1)
    ...> |> Yog.add_edge_ensure(from: 2, to: 3, with: 1)
    iex> potential = Yog.undirected()
    ...> |> Yog.add_node(1, nil)
    ...> |> Yog.add_node(2, nil)
    ...> |> Yog.add_edge_ensure(from: 1, to: 2, with: 1)
    iex> Yog.Operation.subgraph?(potential, container)
    true
    iex> not_subgraph = Yog.undirected()
    ...> |> Yog.add_node(4, nil)
    ...> |> Yog.add_node(5, nil)
    ...> |> Yog.add_edge_ensure(from: 4, to: 5, with: 1)
    iex> Yog.Operation.subgraph?(not_subgraph, container)
    false

# `symmetric_difference`

```elixir
@spec symmetric_difference(Yog.Graph.t(), Yog.Graph.t()) :: Yog.Graph.t()
```

Returns a graph containing edges that exist in exactly one of the input graphs.

The result is the union of `difference(first, second)` and
`difference(second, first)`. Nodes that have no incident unique edges
will not appear in the result.

**Time Complexity:** O(V₁ + V₂ + E₁ + E₂)

## Examples

    iex> g1 = Yog.undirected()
    ...> |> Yog.add_node(1, nil)
    ...> |> Yog.add_node(2, nil)
    ...> |> Yog.add_node(3, nil)
    ...> |> Yog.add_edge_ensure(from: 1, to: 2, with: 1)
    iex> g2 = Yog.undirected()
    ...> |> Yog.add_node(2, nil)
    ...> |> Yog.add_node(3, nil)
    ...> |> Yog.add_edge_ensure(from: 2, to: 3, with: 1)
    iex> sym_diff = Yog.Operation.symmetric_difference(g1, g2)
    iex> Yog.Model.order(sym_diff)
    1
    iex> Yog.Model.edge_count(sym_diff)
    0

# `tensor_product`

```elixir
@spec tensor_product(Yog.Graph.t(), Yog.Graph.t()) :: Yog.Graph.t()
```

Returns the Tensor product (also known as Kronecker or direct product) of two graphs.

The Tensor product $G_1 \times G_2$ is a graph where the node set is the Cartesian product
$V(G_1) \times V(G_2)$, and an edge exists between $(u_1, u_2)$ and $(v_1, v_2)$ if and only if
$u_1 \to v_1$ is an edge in $G_1$ and $u_2 \to v_2$ is an edge in $G_2$.

Edge weights in the resulting graph are tuples of `{weight_first, weight_second}`.

> [!WARNING]
> **Performance Warning:** The size of the resulting Tensor product graph grows
> quadratically. The output graph contains $V_1 \times V_2$ nodes and $E_1 \times E_2$ edges
> (or $2 \times E_1 \times E_2$ for undirected graphs). For larger or dense graphs,
> this operation can consume substantial CPU time and memory.

**Time Complexity:** O(V₁ × V₂ + E₁ × E₂)

## Examples

    iex> g1 = Yog.undirected()
    ...> |> Yog.add_node(0, nil)
    ...> |> Yog.add_node(1, nil)
    ...> |> Yog.add_edge_ensure(from: 0, to: 1, with: 10)
    iex> g2 = Yog.undirected()
    ...> |> Yog.add_node(0, nil)
    ...> |> Yog.add_node(1, nil)
    ...> |> Yog.add_edge_ensure(from: 0, to: 1, with: 20)
    iex> product = Yog.Operation.tensor_product(g1, g2)
    iex> Yog.Model.order(product)
    4
    iex> Yog.Model.edge_count(product)
    2

# `union`

```elixir
@spec union(Yog.Graph.t(), Yog.Graph.t()) :: Yog.Graph.t()
```

Returns a graph containing all nodes and edges from both input graphs.

Node data and edge weights from `other` take precedence on conflicts.
Both graphs must have the same kind (`:directed` or `:undirected`);
the result inherits the kind from `base`.

**Time Complexity:** O(V₁ + V₂ + E₁ + E₂)

## Examples

    iex> g1 = Yog.undirected()
    ...> |> Yog.add_node(1, nil)
    ...> |> Yog.add_node(2, nil)
    ...> |> Yog.add_edge_ensure(from: 1, to: 2, with: 1)
    iex> g2 = Yog.undirected()
    ...> |> Yog.add_node(2, nil)
    ...> |> Yog.add_node(3, nil)
    ...> |> Yog.add_edge_ensure(from: 2, to: 3, with: 1)
    iex> union = Yog.Operation.union(g1, g2)
    iex> Yog.Model.order(union)
    3

---

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