Twin reduction in Graph

edit

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.

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

Rough Tentative

sage: def remove_one(G):
....:     store = []
....:     newG = copy(G)
....:     for v in newG:
....:         neigh = set(newG.neighbors(v))
....:         if neigh in store:
....:             newG.delete_vertex(v)
....:             return newG
....:         store.append(neigh)
....:     return G
....:     
sage: G=graphs.CycleGraph(4)
sage: remove_one(G)
Cycle graph: Graph on 3 vertices
sage: remove_one(_)
Cycle graph: Graph on 2 vertices
sage: remove_one(_)
Cycle graph: Graph on 2 vertices
sage: remove_one(_)