Connected components in graph with numba: "native lowering" error

42 Views Asked by At

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...

0

There are 0 best solutions below