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

Strongly Connected Components (SCC) algorithms.

This module provides algorithms for finding strongly connected components in directed
graphs. A strongly connected component is a maximal subgraph where every node is
reachable from every other node via directed edges.

## Algorithms

- **Tarjan's Algorithm**: `strongly_connected_components/1` - Single-pass DFS with
  low-link values. Time complexity O(V + E).
- **Kosaraju's Algorithm**: `kosaraju/1` - Two-pass DFS on original and transposed
  graphs. Time complexity O(V + E).

## When to Use

- **Tarjan's**: Preferred for most use cases; single pass, slightly more efficient
- **Kosaraju's**: When you need the finish order for other algorithms, or prefer
  the conceptual simplicity of the two-pass approach

## Use Cases

- Finding cycles in dependency graphs
- Identifying mutually reachable regions in networks
- Condensing graphs for easier analysis
- Detecting bottlenecks in flow networks

## SCC Partition Visualization

In a strongly connected component, every node can reach every other node.

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

  subgraph cluster_scc1 {
    label="SCC 1 (Cycle)"; color="#6366f1"; style=rounded;
    A -> B; B -> C; C -> A;
  }

  subgraph cluster_scc2 {
    label="SCC 2 (Cycle)"; color="#f43f5e"; style=rounded;
    D -> E; E -> D;
  }

  // Bridge edge between SCCs
  B -> D [label="bridge", color="#94a3b8", style=dashed];
}
</div>

    iex> alias Yog.Connectivity.SCC
    iex> graph = Yog.from_edges(:directed, [
    ...>   {"A", "B", 1}, {"B", "C", 1}, {"C", "A", 1},
    ...>   {"D", "E", 1}, {"E", "D", 1}, {"B", "D", 1}
    ...> ])
    iex> sccs = SCC.strongly_connected_components(graph)
    iex> length(sccs)
    2

## Examples

    # Find SCCs in a graph with a cycle
    iex> graph = Yog.directed()
    ...> |> Yog.add_node(1, nil)
    ...> |> Yog.add_node(2, nil)
    ...> |> Yog.add_node(3, nil)
    ...> |> Yog.add_edges!([{1, 2, 1}, {2, 3, 1}, {3, 1, 1}])
    iex> Yog.Connectivity.SCC.strongly_connected_components(graph)
    [[1, 2, 3]]

    # Find SCCs in a graph with multiple cycles
    iex> graph = Yog.directed()
    ...> |> Yog.add_node(1, nil)
    ...> |> Yog.add_node(2, nil)
    ...> |> Yog.add_node(3, nil)
    ...> |> Yog.add_node(4, nil)
    ...> |> Yog.add_edges!([{1, 2, 1}, {2, 1, 1}, {3, 4, 1}, {4, 3, 1}])
    iex> sccs = Yog.Connectivity.SCC.strongly_connected_components(graph)
    iex> length(sccs)
    2

# `kosaraju`

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

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

Kosaraju's algorithm performs two passes of DFS:
1. First pass on the original graph to get finish order
2. Second pass on the transposed graph in reverse finish order

Time Complexity: O(V + E)

## Examples

    iex> graph = Yog.directed()
    ...> |> Yog.add_node(1, nil)
    ...> |> Yog.add_node(2, nil)
    ...> |> Yog.add_node(3, nil)
    ...> |> Yog.add_edges!([{1, 2, 1}, {2, 3, 1}, {3, 1, 1}])
    iex> sccs = Yog.Connectivity.SCC.kosaraju(graph)
    iex> length(sccs)
    1
    iex> hd(sccs) |> Enum.sort()
    [1, 2, 3]

    iex> # Acyclic graph - each node is its own SCC
    iex> graph = Yog.directed()
    ...> |> Yog.add_node(1, nil)
    ...> |> Yog.add_node(2, nil)
    ...> |> Yog.add_node(3, nil)
    ...> |> Yog.add_edges!([{1, 2, 1}, {2, 3, 1}])
    iex> sccs = Yog.Connectivity.SCC.kosaraju(graph)
    iex> length(sccs)
    3

# `strongly_connected_components`

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

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

A strongly connected component is a maximal subgraph where every node is
reachable from every other node via directed edges.

Time Complexity: O(V + E)

## Examples

    iex> graph = Yog.directed()
    ...> |> Yog.add_node(1, nil)
    ...> |> Yog.add_node(2, nil)
    ...> |> Yog.add_node(3, nil)
    ...> |> Yog.add_edges!([{1, 2, 1}, {2, 3, 1}, {3, 1, 1}])
    iex> sccs = Yog.Connectivity.SCC.strongly_connected_components(graph)
    iex> length(sccs)
    1
    iex> hd(sccs) |> Enum.sort()
    [1, 2, 3]

    iex> # Two separate cycles
    iex> graph = Yog.directed()
    ...> |> Yog.add_node(1, nil)
    ...> |> Yog.add_node(2, nil)
    ...> |> Yog.add_node(3, nil)
    ...> |> Yog.add_node(4, nil)
    ...> |> Yog.add_edges!([{1, 2, 1}, {2, 1, 1}, {3, 4, 1}, {4, 3, 1}])
    iex> sccs = Yog.Connectivity.SCC.strongly_connected_components(graph)
    iex> length(sccs)
    2

---

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