shared_connected_components.py

def shared_connected_components(adj_mat_1, adj_mat_2):
    '''
    invariant: `adj_mat_1` and `adj_mat_2` have the same vertex set
    '''
    num_vertices = len(adj_mat_1)
    cc_id = 0
    vertex_to_cc = [None] * num_vertices
    cc_to_size = []
    num_shared = 0

    for i in range(num_vertices):
        if vertex_to_cc[i] is None:
            size = first_dfs(adj_mat_1, i, vertex_to_cc, cc_id)
            cc_to_size.append(size)
            cc_id += 1

    for i in range(num_vertices):
        cc_id = vertex_to_cc[i]
        if cc_id is not None:
            size = second_dfs(adj_mat_2, i, vertex_to_cc, cc_id)
            num_shared += (size == cc_to_size[cc_id])

    return num_shared


def first_dfs(adj_mat, start_index, vertex_to_cc, cc_id):
    vertex_to_cc[start_index] = cc_id
    size = 1
    for i in range(start_index + 1, len(adj_mat)):
        if adj_mat[start_index][i] and vertex_to_cc[i] is None:
            size += first_dfs(adj_mat, i, vertex_to_cc, cc_id)
    return size

def second_dfs(adj_mat, start_index, vertex_to_cc, cc_id):
    valid = vertex_to_cc[start_index] == cc_id
    vertex_to_cc[start_index] = None
    size = 1
    for i in range(start_index + 1, len(adj_mat)):
        if adj_mat[start_index][i] and vertex_to_cc[i] is not None:
            child_size = second_dfs(adj_mat, i, vertex_to_cc, cc_id)
            if child_size is None:
                valid = False
            else:
                size += child_size
    return size if valid else None