Connected components algorithms for undirected and directed graphs.

This module provides algorithms for finding connected components:

• Connected Components: For undirected graphs, finds maximal subgraphs where every node is reachable from every other node.
• Weakly Connected Components: For directed graphs, finds maximal subgraphs where nodes are connected when edge directions are ignored.

Algorithm Characteristics

• Time Complexity: O(V + E) for both algorithms
• Space Complexity: O(V) for the visited set
• Implementation: DFS-based traversal with tail recursion

When to Use

• Connected Components: Use on undirected graphs to find disjoint subgraphs
• Weakly Connected Components: Use on directed graphs when you care about connectivity regardless of direction

Use Cases

• Identifying isolated subgraphs in social networks
• Finding disconnected regions in network topology
• Analyzing graph structure and connectivity
• Preprocessing for other graph algorithms

Disjoint Components Visualization

A graph is partitioned into disjoint components if no path exists between nodes across the partition.

iex> alias Yog.Connectivity.Components
iex> graph = Yog.from_edges(:undirected, [
...>   {"A1", "A2", 1}, {"A2", "A3", 1}, {"A3", "A1", 1},
...>   {"B1", "B2", 1}
...> ])
iex> components = Components.connected_components(graph)
iex> length(components)
2

Examples

# Find connected components in an undirected graph
iex> graph = Yog.undirected()
...> |> Yog.add_node(1, "A")
...> |> Yog.add_node(2, "B")
...> |> Yog.add_node(3, "C")
...> |> Yog.add_edges!([{1, 2, 1}, {2, 3, 1}])
iex> Yog.Connectivity.Components.connected_components(graph)
[[3, 2, 1]]

# Find weakly connected components in a directed graph
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> Yog.Connectivity.Components.weakly_connected_components(graph)
[[3, 2, 1]]