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(aliasscc/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.
Summary
Functions
Analyzes an undirected graph to find all bridges and articulation points.
Finds Connected Components in an undirected graph.
Calculates all core numbers for all nodes in the graph.
Finds the degeneracy of the graph, which is the maximum core number.
Extracts the k-core of a graph (maximal subgraph with minimum degree k).
Finds Strongly Connected Components (SCC) using Kosaraju's Algorithm.
Alias for strongly_connected_components/1.
Finds Strongly Connected Components (SCC) using Tarjan's Algorithm.
Finds Weakly Connected Components in a directed graph.
Types
@type bridge() :: Yog.Connectivity.Analysis.bridge()
@type component() :: Yog.Connectivity.Components.component()
@type connectivity_results() :: Yog.Connectivity.Analysis.connectivity_results()
Functions
@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!(from: 1, to: 2, with: nil)
...> |> Yog.add_edge!(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]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!(from: 1, to: 2, with: 1)
...> |> Yog.add_edge!(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]]@spec core_numbers(Yog.graph()) :: %{required(Yog.node_id()) => integer()}
Calculates all core numbers for all nodes in the graph.
Finds the degeneracy of the graph, which is the maximum core number.
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@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!(from: 1, to: 2, with: 1)
...> |> Yog.add_edge!(from: 2, to: 3, with: 1)
...> |> Yog.add_edge!(from: 3, to: 1, with: 1)
iex> sccs = Yog.Connectivity.kosaraju(graph)
iex> hd(sccs) |> Enum.sort()
[1, 2, 3]@spec scc(Yog.graph()) :: [[Yog.node_id()]]
Alias for strongly_connected_components/1.
@spec strongly_connected_components(Yog.graph()) :: [[Yog.node_id()]]
Finds Strongly Connected Components (SCC) using Tarjan's Algorithm.
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!(from: 1, to: 2, with: 1)
...> |> Yog.add_edge!(from: 3, to: 2, with: 1)
iex> wccs = Yog.Connectivity.weakly_connected_components(graph)
iex> hd(wccs) |> Enum.sort()
[1, 2, 3]