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

Graph connectivity analysis - finding connected components, bridges, articulation points,
strongly connected components, and k-core decomposition.

This module provides a unified API for analyzing the connectivity structure of graphs.

## Algorithms

### Connectivity Analysis
- `analyze/1` - Find bridges and articulation points (undirected).

### Strongly Connected Components (Directed)
- `strongly_connected_components/1` (alias `scc/1`) - Tarjan's algorithm.
- `kosaraju/1` - Kosaraju's two-pass algorithm.

### (Weakly) Connected Components
- `connected_components/1` - Standard CC (undirected).
- `weakly_connected_components/1` - WCC (directed).

### Higher-Order Connectivity
- `k_core/2` - Find maximal subgraphs with minimum degree k.
- `core_numbers/1` - Core number for all nodes.
- `degeneracy/1` - Maximum core number.

# `bridge`

```elixir
@type bridge() :: Yog.Connectivity.Analysis.bridge()
```

# `component`

```elixir
@type component() :: Yog.Connectivity.Components.component()
```

# `connectivity_results`

```elixir
@type connectivity_results() :: Yog.Connectivity.Analysis.connectivity_results()
```

# `reachability_direction`

```elixir
@type reachability_direction() :: Yog.Connectivity.Reachability.direction()
```

# `analyze`

```elixir
@spec analyze(keyword() | Yog.graph()) :: connectivity_results()
```

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

## 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: nil)
    ...> |> Yog.add_edge_ensure(from: 2, to: 3, with: nil)
    iex> results = Yog.Connectivity.analyze(in: graph)
    iex> results.bridges
    [{1, 2}, {2, 3}]
    iex> results.articulation_points
    [2]

# `connected_components`

```elixir
@spec connected_components(Yog.graph()) :: [component()]
```

Finds Connected Components in an **undirected graph**.

## Example

    iex> graph = Yog.undirected()
    ...> |> Yog.add_node(1, "A")
    ...> |> Yog.add_node(2, "B")
    ...> |> Yog.add_node(3, "C")
    ...> |> Yog.add_node(4, "D")
    ...> |> Yog.add_edge_ensure(from: 1, to: 2, with: 1)
    ...> |> Yog.add_edge_ensure(from: 3, to: 4, with: 1)
    iex> components = Yog.Connectivity.connected_components(graph)
    iex> Enum.map(components, &Enum.sort/1) |> Enum.sort()
    [[1, 2], [3, 4]]

# `core_numbers`

```elixir
@spec core_numbers(Yog.graph()) :: %{required(Yog.node_id()) => integer()}
```

Calculates all core numbers for all nodes in the graph.

# `degeneracy`

```elixir
@spec degeneracy(Yog.graph()) :: integer()
```

Finds the degeneracy of the graph, which is the maximum core number.

# `k_core`

```elixir
@spec k_core(Yog.graph(), integer()) :: Yog.graph()
```

Extracts the k-core of a graph (maximal subgraph with minimum degree k).

## Examples

    iex> graph = Yog.undirected()
    ...> |> Yog.add_edge_ensure(1, 2, 1, nil)
    ...> |> Yog.add_edge_ensure(2, 3, 1, nil)
    ...> |> Yog.add_edge_ensure(3, 4, 1, nil)
    ...> |> Yog.add_edge_ensure(4, 1, 1, nil)
    iex> core_2 = Yog.Connectivity.k_core(graph, 2)
    iex> Yog.node_count(core_2)
    4

# `kosaraju`

```elixir
@spec kosaraju(Yog.graph()) :: [[Yog.node_id()]]
```

Finds Strongly Connected Components (SCC) using Kosaraju's Algorithm.

## Example

    iex> graph = Yog.directed()
    ...> |> Yog.add_node(1, "A")
    ...> |> Yog.add_node(2, "B")
    ...> |> Yog.add_node(3, "C")
    ...> |> 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> sccs = Yog.Connectivity.kosaraju(graph)
    iex> hd(sccs) |> Enum.sort()
    [1, 2, 3]

# `reachability_counts`

```elixir
@spec reachability_counts(Yog.graph(), reachability_direction()) :: %{
  required(Yog.node_id()) => integer()
}
```

Counts the number of ancestors or descendants for every node in the graph.

## Example

    iex> graph = Yog.directed() |> Yog.add_edge_ensure(1, 2, 1, nil)
    iex> Yog.Connectivity.reachability_counts(graph, :descendants)[1]
    1

# `scc`

```elixir
@spec scc(Yog.graph()) :: [[Yog.node_id()]]
```

Alias for `strongly_connected_components/1`.

# `shell_decomposition`

```elixir
@spec shell_decomposition(Yog.graph()) :: %{required(integer()) => [Yog.node_id()]}
```

Groups nodes into their respective k-shells.

# `strongly_connected_components`

```elixir
@spec strongly_connected_components(Yog.graph()) :: [[Yog.node_id()]]
```

Finds Strongly Connected Components (SCC) using Tarjan's Algorithm.

# `weakly_connected_components`

```elixir
@spec weakly_connected_components(Yog.graph()) :: [component()]
```

Finds Weakly Connected Components in a **directed graph**.

## Example

    iex> graph = Yog.directed()
    ...> |> Yog.add_node(1, "A")
    ...> |> Yog.add_node(2, "B")
    ...> |> Yog.add_node(3, "C")
    ...> |> Yog.add_edge_ensure(from: 1, to: 2, with: 1)
    ...> |> Yog.add_edge_ensure(from: 3, to: 2, with: 1)
    iex> wccs = Yog.Connectivity.weakly_connected_components(graph)
    iex> hd(wccs) |> Enum.sort()
    [1, 2, 3]

---

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