@spec analyze(Zog.SoA.t()) :: %{
  bridges: [bridge()],
  articulation_points: [Zog.SoA.label()]
}

Analyzes an undirected graph natively to find all bridges and articulation points.

@spec bipartite_check(Zog.SoA.t()) :: boolean()

Checks whether a graph is bipartite (2-colourable) natively.

Treats all edges as undirected; works correctly for graphs that store undirected edges as symmetric directed pairs.

Returns true when the graph is bipartite, false otherwise.

Examples

iex> builder = Zog.undirected() |> Zog.add_edge(:a, :b, 1.0) |> Zog.add_edge(:b, :c, 1.0)
iex> Zog.Connectivity.bipartite_check(builder)
true

iex> builder = Zog.undirected() |> Zog.add_edge(:a, :b, 1.0) |> Zog.add_edge(:b, :c, 1.0) |> Zog.add_edge(:c, :a, 1.0)
iex> Zog.Connectivity.bipartite_check(builder)
false

@spec bipartite_partition(Zog.SoA.t()) ::
  {:ok, MapSet.t(Zog.SoA.label()), MapSet.t(Zog.SoA.label())}
  | {:error, :not_bipartite}

Returns the bipartite partition of a graph as two sets of node labels, or {:error, :not_bipartite} if the graph is not 2-colourable.

The partition is returned as {:ok, set_a, set_b} where set_a and set_b are MapSets of node labels. The assignment is deterministic (BFS from the lowest-ID uncoloured node) but arbitrary in terms of which partition is "A" vs "B".

Examples

iex> builder = Zog.undirected() |> Zog.add_edge(:a, :b, 1.0) |> Zog.add_edge(:b, :c, 1.0)
iex> {:ok, set_a, set_b} = Zog.Connectivity.bipartite_partition(builder)
iex> MapSet.member?(set_a, :a) or MapSet.member?(set_b, :a)
true
iex> MapSet.disjoint?(set_a, set_b)
true

@spec blossom_maximum_matching(Zog.SoA.t()) :: %{
  required(Zog.SoA.label()) => Zog.SoA.label()
}

Computes maximum cardinality matching on general (non-bipartite) graphs using Edmonds' Blossom algorithm.

Returns matching map %{u => v, v => u}.

@spec core_numbers(Zog.SoA.t()) :: %{required(Zog.SoA.label()) => integer()}

Calculates all core numbers for all nodes in the graph natively.

@spec detect(Zog.SoA.t(), integer()) :: Zog.SoA.t()

Detects the k-core of a graph natively.

@spec hungarian(
  Zog.SoA.t(),
  keyword()
) :: {float(), %{required(Zog.SoA.label()) => Zog.SoA.label()}}

Calculates weighted bipartite matching using the O(V³) Hungarian (Kuhn-Munkres) algorithm.

Returns {cost, matching} where matching is a map of {u => v, v => u}. Raises ArgumentError if the graph is not bipartite.

Options

• :optimization - :min (default) or :max.

@spec maximum_bipartite_matching(Zog.SoA.t()) ::
  {:ok, [{Zog.SoA.label(), Zog.SoA.label()}]} | {:error, :not_bipartite}

Computes a maximum bipartite matching natively using the Hopcroft-Karp algorithm.

Returns {:ok, pairs} where pairs is a list of {left_label, right_label} tuples representing matched edges. Returns {:error, :not_bipartite} if the graph is not bipartite.

Examples

iex> builder = Zog.undirected()
...> |> Zog.add_edge(:a, :b, 1.0)
...> |> Zog.add_edge(:b, :c, 1.0)
...> |> Zog.add_edge(:c, :d, 1.0)
iex> {:ok, pairs} = Zog.Connectivity.maximum_bipartite_matching(builder)
iex> length(pairs)
2

@spec strongly_connected_components(Zog.SoA.t()) :: [[Zog.SoA.label()]]

Finds strongly connected components in the graph natively. Returns a list of lists of node labels.

@spec weakly_connected_components(Zog.SoA.t()) :: [[Zog.SoA.label()]]

Finds weakly connected components in the graph natively. Returns a list of lists of node labels.