@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)

@spec coloring(Yog.graph()) ::
  {:ok, %{required(Yog.node_id()) => 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}

@spec get_partner(%{required(k :: any()) => 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

@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)

@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)

@spec stable_marriage(
  %{required(k1 :: any()) => [k2 :: any()]},
  %{required(k2 :: any()) => [k1 :: any()]}
) :: %{
  required(k1 :: any()) => k2 :: any(),
  required(k2 :: any()) => 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