from sage.graphs.independent_sets import IndependentSets

def toggle_set(g, indep, vertex):
    """toggle vertex v in independent set indep wrt graph g"""
    # FIXME gotta be a better way to toggle an element
    s1 = indep.symmetric_difference(Set([vertex]))
    if g.is_independent_set(s1):
        return s1
    else:
        return indep

def toggle_lis(g, indep, lis):
    """toggle a list of vertices in order"""
    for i in lis:
        indep = toggle_set(g, indep, i)
    return indep

def toggle_orbit_lis(g, indep, lis):
    """return a list of the elements in an orbit"""
    s0 = Set([i for i in indep])
    tot = [s0]
    s1 = toggle_lis(g, s0, lis)
    while s1 != s0:
        tot.append(s1)
        s1 = toggle_lis(g, s1, lis)
    return tot

def orbs(g, lis):
    """return all orbits for a given toggle order"""
    iset = Set(Set(i) for i in IndependentSets(g))
    orbs = []
    while not iset.is_empty():
        st = iset.an_element()
        orb = toggle_orbit_lis(g, st, lis)
        orbs.append(orb)
        iset = iset.difference(Set(orb))
    return orbs

def avg_weights(g, lis):
    """return a list of the average weights of the orbits"""
    return [Integer(sum(len(i) for i in s))/len(s) for s in orbs(g,lis)]

def rand_range(n):
    """generate a random permuation of range(n)"""
    a = range(n)
    sage.misc.prandom.shuffle(a)
    return a

def find_homomesic(n, k):
    """find homomesic graphs of order n.  Try k random orderings"""
    l = []
    count = 0
    for g in graphs.nauty_geng("{0} -c".format(n)):
        if len(set(avg_weights(g, range(n)))) == 1:
            if all(len(set(avg_weights(g, rand_range(n)))) == 1 for i in range(k)):
                count += 1
                print count, g.to_dictionary()
                g.show()
                l.append(g)
    return l

find_homomesic(5, 30)

find_homomesic(6,30)

find_homomesic(7,30)

find_homomesic(8, 30)