Ask Your Question
2

Twin reduction in Graph

asked 0 years ago

Erdos2 gravatar image

Two vertices in a graph are called twins if they have the same neighbourhood. Twin reduction is the process in which twin vertices are merged, until no twin vertices remain. Note that this process is independent of the order in which pair of twins are chosen and merged.

As far as I know, there is no inbuilt function in sage, which returns a twin reduced graph from a given graph G. Can anyone help me in defining one such function?

Preview: (hide)

3 Answers

Sort by » oldest newest most voted
3

answered 0 years ago

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.

Preview: (hide)
link
1

answered 0 years ago

vdelecroix gravatar image

updated 0 years ago

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
Preview: (hide)
link

Comments

Note that it is easy to modify my function to modify G in place.

vdelecroix gravatar imagevdelecroix ( 0 years ago )
1

answered 0 years ago

FrédéricC gravatar image

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(_)
Preview: (hide)
link

Comments

should it return G or newG finally?

Erdos2 gravatar imageErdos2 ( 0 years ago )

It returns G when it fails to simplify anything. You need to iterate that several times until there is no change.

FrédéricC gravatar imageFrédéricC ( 0 years ago )

Your Answer

Please start posting anonymously - your entry will be published after you log in or create a new account.

Add Answer

Question Tools

1 follower

Stats

Asked: 0 years ago

Seen: 273 times

Last updated: Jul 15 '24