<jupyter_start><jupyter_text>Connected Components The code in this notebook is based on the algorithm described in the following paper:* <NAME>, <NAME>, <NAME>: *Parallel algorithms for finding connected components using linear algebra*. J. Parallel Distributed Comput. 144: 14-27 (2020).A prevoius version of the algorithm is here (which might not be reflected in this code):* Zhang, Azad, Hu. *FastSV: A Distributed-Memory Connected Component Algorithm with Fast Convergence* (SIAM PP20)  Create and visualize a Matrix<jupyter_code># The input matrix A must be symmetric.  Self-edges (diagonal entries) are
# OK, and are ignored.  The values and type of A are ignored; just its
# pattern is accessed.
row_col = np.array([
    [0, 0, 0, 1, 2, 2, 3, 6, 6,  9,  9],
    [1, 2, 3, 2, 4, 5, 4, 7, 8, 10, 11],
])
rows, cols = row_col
data = np.full_like(rows, fill_value=1)
A = coo_matrix((data, (rows, cols)), shape=(12, 12)).tolil()
A[cols, rows] = A[rows, cols]                  # symmetrize matrix
A = A.tocoo()
# Draw A using spring layout which may even reveal the connected components
G = nx.convert_matrix.from_scipy_sparse_matrix(A)
layout = nx.drawing.layout.spring_layout(G, k=0.6, scale=1, threshold=1e-10)
nx.draw_networkx(G, with_labels=True, node_size=500, font_color='w', pos=layout)
rows_da = da.from_array(np.concatenate([rows, cols]))
cols_da = da.from_array(np.concatenate([cols, rows]))
data_da = da.from_array(np.concatenate([data, data]))
A = Matrix.from_values(rows_da, cols_da, data_da, nrows=12, ncols=12, chunks=4)
# Size of the sparse matrix is 12x12 with 22 non-zero elements of type INT64
A
(A.nrows, A.ncols)
A.nvals.compute()
A._delayed
A.compute()
# This is an adjacency matrix
# Reading along a row shows the out-nodes of a vertex
# Reading along a column shows the in-nodes of a vertex
# grblas.io.draw could do with a few more tunable options to improve pretty display
gio.draw(A.compute())
def fastSV(A, chunksz='auto'):
    n = A.nrows
    I = da.arange(n, chunks=chunksz)
    # The parent of each vertex is initialized to be the vertex itself:
    f = Vector.from_values(I, I, name='parents', chunks=chunksz)
    gp = f.dup()        # grandparent of each vertex initialized to parent
    gp_dup = gp.dup()   # duplicate grandparents
    mngp = f.dup()      # minimum grandparent of each star-vertex

    # boolean flag for each vertex
    mod = Vector.new(dtype=bool, size=n, name='modified?', chunks=chunksz)
    # flag to terminate FastSV algorithm
    change = Scalar.from_value(True, dtype=bool, name='changed?')
    
    # set checkpoint for task graph
    f = f.persist()
    I = I.persist()
    gp = gp.persist()
        
    while change:
        # Step 1: Hooking phase
        mngp << semiring.min_second(A @ gp)
        f(binary.min)[I] << mngp
        f << op.min(f | mngp)
        # Step 2: Shortcutting
        f << op.min(f | gp)
        # Step 3: Calculate grandparents
        _, I = f.to_values()
        gp << f[I]
        # set checkpoint for task graph
        f = f.persist()
        I = I.persist()
        gp = gp.persist()
        # Check termination
        mod << op.ne(gp_dup & gp)
        change << mod.reduce(binary.lor)
        gp_dup << gp

    return f
A = A.persist()
connected_components = fastSV(A, chunksz=4)
connected_components
connected_components._delayed
connected_components.compute()<jupyter_output><empty_output><jupyter_text>*connected_components* gives the label of the component to which each vertex belongs.Compare with the graph drawing to check result:<jupyter_code>nx.draw_networkx(G, with_labels=True, node_size=500, font_color='w', pos=layout)<jupyter_output><empty_output>
StarcoderdataJupyterStructuredCleanDedup