Yog.Connectivity.Components (YogEx v0.70.0)

Copy Markdown View Source

Algorithms for finding (weakly) connected components in graphs.

Summary

Functions

Finds Connected Components in an undirected graph.

Finds Weakly Connected Components in a directed graph.

Types

component()

@type component() :: [Yog.node_id()]

Functions

connected_components(graph)

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

Finds Connected Components in an undirected graph.

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

Time Complexity: O(V + E)

weakly_connected_components(graph)

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

Finds Weakly Connected Components in a directed graph.

A weakly connected component is a maximal subgraph where, if you ignore edge directions, all nodes are reachable from each other.

Time Complexity: O(V + E)