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.
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];
}
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)
2Examples
# 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)
2Summary
Functions
Finds Strongly Connected Components (SCC) using Kosaraju's Algorithm.
Finds Strongly Connected Components (SCC) using Tarjan's Algorithm.
Functions
@spec kosaraju(Yog.graph()) :: [[Yog.node_id()]]
Finds Strongly Connected Components (SCC) using Kosaraju's Algorithm.
Kosaraju's algorithm performs two passes of DFS:
- First pass on the original graph to get finish order
- 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@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