Revision history [back]

A slightly 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)`.
    """
    twins = set()
    to_delete = []
    for v in G:
        neigh = frozenset(G.neighbor_iterator(v))
        if neigh in twins:
            to_delete.append(v)
        twins.add(neigh)

    H = G.copy(immutable=False)
    H.delete_vertices(to_delete)
    return H

A slightly 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)`.
    """
    twins = set()
    to_delete = []
    for v in G:
        neigh = frozenset(G.neighbor_iterator(v))
        if neigh in twins:
            to_delete.append(v)
        else:
            twins.add(neigh)

    H = G.copy(immutable=False)
    H.delete_vertices(to_delete)
    return H