connected_components

compas.topology.connected_components(adjacency)

Identify the connected components of a graph.

Parameters

adjacency (dict[hashable, dict[hashable, None]] | dict[hashable, sequence[hashable]]) – An adjacency dictionary representing the connectivity of the graph by mapping nodes identifiers to neighbour identifiers. Examples of valid adjacency dicts are

• {0: [1, 2, 3, 4], 1: [0], 2: [0], 3: [0], 4: [0]}

• {0: {1: None, 2: None, 3: None, 4: None}, 1: {0: None}, 2: {0: None}, 3: {0: None}, 4: {0: None}}

Returns

list[list[hashable]] – A list of connected components, with each component a list of connected nodes.

Examples

>>> adjacency = {0: [1, 2], 1: [0, 2], 2: [0, 1], 3: []}
>>> connected_components(adjacency)
[[0, 1, 2], [3]]