# `Yog.Operation`
[🔗](https://github.com/code-shoily/yog_ex/blob/v0.97.0/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.

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

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

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

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

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

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

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