A faster way to obtain orbits of a partition of the verrtex set

asked 2012-12-29 02:44:09 -0500

Jernej gravatar image

I am given a graph $G$ a set $S \subseteq V(G)$ and a vertex $v.$ I want to compute the representatives for the orbits of the stabilizer of $v$ of $\rm{Aut}(G)$ whose equivalence classes contain elements of $S.$ Currently what I am doing is the following:

def compute_valid_orbit_reps(G,S,v):
    ret = []
    O = G.automorphism_group(return_group=False, orbits=True, 
    partition=[ [v], [el for el in G.vertices() if el != v]])

    for el in O:
        if S.intersection(set(el)):
            nb = el[0]
            G.add_edge(nb,v)
            if G.girth() >= 5:
                ret += [nb]
            G.delete_edge(nb,v)
    return ret

I am wondering if there is a more efficient way to do the same, perhaps using GAP directly?

Best,

Jernej

edit retag flag offensive close merge delete