# `Yog.Property.Bipartite`
[🔗](https://github.com/code-shoily/yog_ex/blob/v0.97.0/lib/yog/property/bipartite.ex#L1)

[Bipartite graph](https://en.wikipedia.org/wiki/Bipartite_graph) analysis and matching algorithms.

A graph is bipartite (2-colorable) if its vertices can be divided into two disjoint sets
such that every edge connects a vertex in one set to a vertex in the other set.
Equivalently, a bipartite graph contains no odd-length cycles.

## Algorithms

| Problem | Algorithm | Function | Complexity |
|---------|-----------|----------|------------|
| Bipartite check | [BFS 2-coloring](https://en.wikipedia.org/wiki/Bipartite_graph#Testing_bipartiteness) | `bipartite?/1`, `partition/1` | O(V + E) |
| Maximum matching | [Augmenting paths](https://en.wikipedia.org/wiki/Matching_(graph_theory)) | `maximum_matching/2` | O(VE) |
| Stable matching | [Gale-Shapley](https://en.wikipedia.org/wiki/Gale%E2%80%93Shapley_algorithm) | `stable_marriage/2` | O(V²) |

## Key Concepts

- **Bipartite Graph**: Vertices partitioned into two sets L and R, edges only go between sets
- **2-Coloring**: Adjacent vertices always have different colors (equivalent to bipartite)
- **Matching**: Set of edges without common vertices
- **Maximum Matching**: Matching with largest possible number of edges
- **Perfect Matching**: Every vertex is matched (requires |L| = |R|)
- **Stable Matching**: No unmatched pair prefers each other over current matches

## Characterizations of Bipartite Graphs

A graph is bipartite if and only if:
- It is 2-colorable
- It contains no odd-length cycles
- Its spectrum is symmetric about 0

## König's Theorem

In bipartite graphs, the size of the maximum matching equals the size of the
minimum vertex cover. This is a fundamental result that doesn't hold for general graphs.

## Use Cases

- **Job assignment**: Workers to tasks they can perform
- **Scheduling**: Time slots to events without conflicts
- **Recommendation systems**: Users to items they might like
- **Chemistry**: Matching molecules for reactions
- **Stable marriage**: Matching medical residents to hospitals

## Bipartite Visualization

<div class="graphviz">
graph G {
  rankdir=LR;
  bgcolor="transparent";
  node [shape=circle, fontname="inherit"];
  edge [fontname="inherit", fontsize=10];

  subgraph cluster_left {
    label="LeftSet"; color="#6366f1"; style=rounded;
    L1; L2; L3;
  }

  subgraph cluster_right {
    label="RightSet"; color="#f43f5e"; style=rounded;
    R1; R2; R3;
  }

  L1 -- R1; L1 -- R2;
  L2 -- R2; L2 -- R3;
  L3 -- R1;
}
</div>

    iex> alias Yog.Property.Bipartite
    iex> graph = Yog.from_edges(:undirected, [
    ...>   {"L1", "R1", 1}, {"L1", "R2", 1},
    ...>   {"L2", "R2", 1}, {"L2", "R3", 1},
    ...>   {"L3", "R1", 1}
    ...> ])
    iex> Bipartite.bipartite?(graph)
    true

## Maximum Matching

<div class="graphviz">
graph G {
  rankdir=LR;
  bgcolor="transparent";
  node [shape=circle, fontname="inherit"];
  edge [fontname="inherit", fontsize=10];

  subgraph cluster_workers {
    label="Workers"; color="#6366f1"; style=rounded;
    w1; w2; w3;
  }

  subgraph cluster_tasks {
    label="Tasks"; color="#f43f5e"; style=rounded;
    t1; t2; t3;
  }

  // Matching edges (Job Assignments)
  w1 -- t1 [color="#6366f1", penwidth=2.5];
  w2 -- t3 [color="#6366f1", penwidth=2.5];
  w3 -- t2 [color="#6366f1", penwidth=2.5];

  // Other potential matches
  w1 -- t2 [style=dashed, color="#94a3b8"];
  w2 -- t1 [style=dashed, color="#94a3b8"];
}
</div>

    iex> alias Yog.Property.Bipartite
    iex> graph = Yog.from_edges(:undirected, [
    ...>   {"w1", "t1", 1}, {"w1", "t2", 1},
    ...>   {"w2", "t1", 1}, {"w2", "t3", 1},
    ...>   {"w3", "t2", 1}
    ...> ])
    iex> {:ok, p} = Bipartite.partition(graph)
    iex> matching = Bipartite.maximum_matching(graph, p)
    iex> length(matching)
    3

## Examples

    # Check if a graph is bipartite
    iex> graph = Yog.undirected()
    ...> |> Yog.add_node(1, nil)
    ...> |> Yog.add_node(2, nil)
    ...> |> Yog.add_node(3, nil)
    ...> |> Yog.add_node(4, nil)
    ...> |> Yog.add_edge_ensure(from: 1, to: 2, with: 1)
    ...> |> Yog.add_edge_ensure(from: 2, to: 3, with: 1)
    ...> |> Yog.add_edge_ensure(from: 3, to: 4, with: 1)
    iex> Yog.Property.Bipartite.bipartite?(graph)
    true

    # Get the partition
    iex> graph =
    ...>   Yog.undirected()
    ...>   |> Yog.add_node(1, nil)
    ...>   |> Yog.add_node(2, nil)
    ...>   |> Yog.add_node(3, nil)
    ...>   |> Yog.add_node(4, nil)
    ...>   |> Yog.add_edge_ensure(from: 1, to: 2, with: 1)
    ...>   |> Yog.add_edge_ensure(from: 2, to: 3, with: 1)
    ...>   |> Yog.add_edge_ensure(from: 3, to: 4, with: 1)
    iex> {:ok, %{left: left, right: right}} = Yog.Property.Bipartite.partition(graph)
    iex> MapSet.size(left) + MapSet.size(right)
    4

## References

- [Wikipedia: Bipartite Graph](https://en.wikipedia.org/wiki/Bipartite_graph)
- [Wikipedia: Graph Coloring](https://en.wikipedia.org/wiki/Graph_coloring)
- [Wikipedia: Matching](https://en.wikipedia.org/wiki/Matching_(graph_theory))
- [Wikipedia: Gale-Shapley Algorithm](https://en.wikipedia.org/wiki/Gale%E2%80%93Shapley_algorithm)
- [CP-Algorithms: Bipartite Check](https://cp-algorithms.com/graph/bipartite-check.html)

# `partition`

```elixir
@type partition() :: %{left: MapSet.t(Yog.node_id()), right: MapSet.t(Yog.node_id())}
```

A partition of a bipartite graph into two independent sets.
In a bipartite graph, all edges connect vertices from `left` to `right`,
with no edges within `left` or within `right`.

# `bipartite?`

```elixir
@spec bipartite?(Yog.graph()) :: boolean()
```

Determines if a graph is bipartite (2-colorable).
Works for both directed and undirected graphs.

A graph is bipartite if its vertices can be divided into two disjoint sets
such that every edge connects a vertex in one set to a vertex in the other set.

## Examples

    iex> graph = 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> Yog.Property.Bipartite.bipartite?(graph)
    true

    # Odd cycle (triangle) is not bipartite
    iex> triangle = 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)
    ...> |> Yog.add_edge_ensure(from: 3, to: 1, with: 1)
    iex> Yog.Property.Bipartite.bipartite?(triangle)
    false

## Time Complexity

O(V + E)

# `coloring`

```elixir
@spec coloring(Yog.graph()) ::
  {:ok, %{required(Yog.node_id()) =&gt; 0 | 1}} | {:error, :not_bipartite}
```

Finds a 2-coloring of a graph if it is bipartite.

Returns a map where each node ID maps to either 0 or 1, representing the two colors.

## Examples

    iex> graph = 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> {:ok, coloring} = Yog.Property.Bipartite.coloring(graph)
    iex> # Adjacent nodes should have different colors
    ...> coloring[1] != coloring[2] and coloring[2] != coloring[3]
    true

    iex> triangle = 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)
    ...> |> Yog.add_edge_ensure(from: 3, to: 1, with: 1)
    iex> Yog.Property.Bipartite.coloring(triangle)
    {:error, :not_bipartite}

# `get_partner`

```elixir
@spec get_partner(%{required(k :: any()) =&gt; v :: any()}, any()) :: any() | nil
```

Gets the partner of a person in a stable matching.

Returns the partner if the person is matched, `nil` otherwise.

## Examples

    iex> residents = %{1 => [101, 102], 2 => [102, 101]}
    iex> hospitals = %{101 => [1, 2], 102 => [2, 1]}
    iex> matches = Yog.Property.Bipartite.stable_marriage(residents, hospitals)
    iex> partner = Yog.Property.Bipartite.get_partner(matches, 1)
    iex> partner in [101, 102]
    true
    iex> Yog.Property.Bipartite.get_partner(matches, 999)
    nil

# `maximum_matching`

```elixir
@spec maximum_matching(Yog.graph(), %{
  left: MapSet.t(Yog.node_id()),
  right: MapSet.t(Yog.node_id())
}) ::
  [{Yog.node_id(), Yog.node_id()}]
```

Finds a maximum matching in a bipartite graph.

A matching is a set of edges with no common vertices. A maximum matching
has the largest possible number of edges.

Uses the augmenting path algorithm (also known as the Hungarian algorithm
for unweighted bipartite matching).

Returns a list of matched pairs `{left_node, right_node}`.

## Examples

    # Complete bipartite graph K_{2,2}
    iex> graph = Yog.undirected()
    ...> |> Yog.add_node(1, nil)  # left
    ...> |> Yog.add_node(2, nil)  # left
    ...> |> Yog.add_node(3, nil)  # right
    ...> |> Yog.add_node(4, nil)  # right
    ...> |> Yog.add_edge_ensure(from: 1, to: 3, with: 1)
    ...> |> Yog.add_edge_ensure(from: 1, to: 4, with: 1)
    ...> |> Yog.add_edge_ensure(from: 2, to: 3, with: 1)
    ...> |> Yog.add_edge_ensure(from: 2, to: 4, with: 1)
    iex> {:ok, p} = Yog.Property.Bipartite.partition(graph)
    iex> matching = Yog.Property.Bipartite.maximum_matching(graph, p)
    iex> length(matching)
    2

## Time Complexity

O(V * E)

# `partition`

```elixir
@spec partition(Yog.graph()) ::
  {:ok, %{left: MapSet.t(Yog.node_id()), right: MapSet.t(Yog.node_id())}}
  | {:error, :not_bipartite}
```

Returns the two partitions of a bipartite graph, or an error if not bipartite.

Uses BFS with 2-coloring to detect bipartiteness and construct the partitions.
Handles disconnected graphs by checking all components.

## Examples

    iex> graph = Yog.undirected()
    ...> |> Yog.add_node(1, nil)
    ...> |> Yog.add_node(2, nil)
    ...> |> Yog.add_node(3, nil)
    ...> |> Yog.add_node(4, nil)
    ...> |> Yog.add_edge_ensure(from: 1, to: 2, with: 1)
    ...> |> Yog.add_edge_ensure(from: 2, to: 3, with: 1)
    ...> |> Yog.add_edge_ensure(from: 3, to: 4, with: 1)
    iex> {:ok, %{left: left, right: right}} = Yog.Property.Bipartite.partition(graph)
    iex> MapSet.size(left) == 2 and MapSet.size(right) == 2
    true

    # Not bipartite - odd cycle
    iex> triangle = 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)
    ...> |> Yog.add_edge_ensure(from: 3, to: 1, with: 1)
    iex> Yog.Property.Bipartite.partition(triangle)
    {:error, :not_bipartite}

## Time Complexity

O(V + E)

# `stable_marriage`

# `stable_marriage`

```elixir
@spec stable_marriage(
  %{required(k1 :: any()) =&gt; [k2 :: any()]},
  %{required(k2 :: any()) =&gt; [k1 :: any()]}
) :: %{
  required(k1 :: any()) =&gt; k2 :: any(),
  required(k2 :: any()) =&gt; k1 :: any()
}
```

Finds a stable matching given preference lists for two groups.

Uses the Gale-Shapley algorithm to find a stable matching where no two people
would both prefer each other over their current partners.

The algorithm is "proposer-optimal" - it finds the best stable matching for
the proposing group (left), and the worst stable matching for the receiving
group (right).

## Parameters

- `left_prefs` - Map where each key is a left person and the value is a list of
  right person preferences (most preferred first)
- `right_prefs` - Map where each key is a right person and the value is a list of
  left person preferences (most preferred first)

Returns a map of matched pairs (bidirectional).

## Examples

    # Medical residency matching
    iex> residents = %{1 => [101, 102], 2 => [102, 101]}
    iex> hospitals = %{101 => [1, 2], 102 => [2, 1]}
    iex> matches = Yog.Property.Bipartite.stable_marriage(residents, hospitals)
    iex> is_map(matches)
    true

## Time Complexity

O(n²) where n is the size of each group

---

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