I am trying to compute all connected components in a graph using numba.
The graph is given as a 2D numpy array (E, 2), where each edge is specified by two node identifiers (integer).
I have written the following code
@nb.njit(nb.types.List(nb.types.Set(nb.int64))(nb.int64[::1, :]))
def connected_components(edges: npt.NDArray[np.int_]) -> List[Set[int]]:
"""
Compute largest connected component of a graph
:param edges: (n, 2) array of edges (node indices)
:type edges: npt.NDArray[np.int_]
:return: list of node indices (len == m) in largest connected component
where m <= n and m == n only for connected graphs
:rtype: Tuple[npt.NDArray[np.int_], List[int]]
"""
node_sets = [set(edges[0])]
edge_sets = [{0}]
for i, e in enumerate(edges[1:], 1):
in_sets_nodes = []
in_sets_edges = []
ls_idx = list(range(len(node_sets)))
ls_idx.reverse()
for j in ls_idx:
if node_sets[j].intersection(set(e)):
in_sets_nodes.append(node_sets.pop(j))
in_sets_edges.append(edge_sets.pop(j))
if len(in_sets_nodes) == 0:
node_sets.append(set(e))
edge_sets.append({i})
else:
merged_set_nodes = in_sets_nodes[0]
merged_set_edges = in_sets_edges[0]
for k in range(1, len(in_sets_nodes)):
merged_set_nodes = merged_set_nodes.union(in_sets_nodes[k])
merged_set_edges = merged_set_edges.union(in_sets_edges[k])
merged_set_nodes.update(e)
merged_set_edges.update((i,))
node_sets.append(merged_set_nodes)
edge_sets.append(merged_set_edges)
return node_sets
However, it fails with this error: AssertionError: Failed in nopython mode pipeline (step: native lowering)
I do not know, how to gain further insights to this issue, nor do I know how to fix it. Any help (fixes, hints) appreciated. The code above is already the result of fixing several other issues, I had with numba before...