singular.eval('LIB "finvar.lib";')
def invariant_algebra_perm(G, verbose=False):
    """
    For a permutation group with domain {1,...,n}, return the minimal
    generators of the invariant ring.

    EXAMPLES::

        sage: G = graphs.CompleteGraph(4).relabel(range(1, 4+1), inplace=False).automorphism_group()
        sage: invariant_algebra_perm(G)
        [x0 + x1 + x2 + x3,
         x0^2 + x1^2 + x2^2 + x3^2,
         x0^3 + x1^3 + x2^3 + x3^3,
         x0^4 + x1^4 + x2^4 + x3^4]

    """
    assert min(G.domain()) == 1
    n = max(G.domain())
    v = "(" + ",".join("x%s" % i for i in range(n)) + ")"
    if verbose: print(v)
    singular.eval("ring R = 0,%s,dp;" % v)
    gens = G.gens()
    if verbose: print(gens)
    l = singular.list([singular.list(p.cycle_tuples(singletons=True))
                       for p in gens])
    if verbose:
        return singular.invariant_algebra_perm(l, 1).sage()
    return singular.invariant_algebra_perm(l, 0).sage().list()

def invariant_algebra(G, verbose=False):
    """
    Return the minimal generators of the invariant ring of a graph.

    EXAMPLES::

        sage: from sage.misc.lazy_list import lazy_list
        sage: l = lazy_list(lambda n: [] if not n else [(G.copy(immutable=True), invariant_algebra(G)) for G in graphs(n)])

    """
    n = G.num_verts()
    G = G.relabel(range(1, n+1), inplace=False).automorphism_group()
    return invariant_algebra_perm(G, verbose=verbose)

def statistic(G):
    return max(g.degree() for g in invariant_algebra(G))