pub fn connected_components<T: AsRef<[impl AsRef<[usize]>]>>(
data: T,
) -> Vec<usize>Expand description
Finds connected components using a Kruskal-like approach. Each input slice of usizes represents a set of nodes that form a complete subgraph (i.e., all of them are connected).
Returns a vector where each index corresponds to a graph node index and the value is the identifier of the connected component (the minimal node in that component).
use binius_utils::graph::connected_components;
assert_eq!(connected_components::<&[&Vec<usize>]>(&[]), vec![]);
assert_eq!(connected_components(&[&vec![0], &vec![1]]), vec![0, 1]);
assert_eq!(connected_components(&[&vec![0, 1], &vec![1, 2], &vec![2, 3], &vec![4]]), vec![0, 0, 0, 0, 4]);
assert_eq!(
connected_components(&[&vec![0, 1, 2], &vec![5, 6, 7, 8], &vec![9], &vec![2, 3, 9]]),
vec![0, 0, 0, 0, 4, 5, 5, 5, 5, 0]
);