Revision history [back]

A slightly improved solution.

def twin_reduced_graph(G):
    r"""
    Return a twin reduced graph.

    Vertices `u` and `v` are twins if `N(u) == N(v)`.
    This method merges twins until no twin vertices remain in `G`.
    """
    H = G.copy(immutable=False)
    while True:
        # Identify twins
        twins = {}
        best = None
        for v in H:
            neigh = frozenset(H.neighbor_iterator(v))
            if neigh in twins:
                twins[neigh].append(v)
                if best is None or len(best) < len(twins[neigh]):
                    best = twins[neigh]
            else:
                twins[neigh] = [v]

        # Merge the largest set of twins
        if best is None or len(best) == 1:
            break
        H.delete_vertices(best[1:])
    return H

A better approach might be to use the modular decomposition of the graph, but it's not easy with the current implementation.