# very silly code, see Petkovšek for a characterisation
def letter_graph(w, D):
    """
    INPUT:

    - w, a word of length n with letters being vertices of D

    - D, a digraph, loops allowed

    OUTPUT:

    - a k-letter graph with n vertices
    """
    n = len(w)
    E = [(i,j) for i in range(n) for j in range(i) if D.has_edge(w[i], w[j])]
    return Graph([list(range(n)), E])

from sage.misc.lazy_list import lazy_list
from sage.databases.findstat import FindStatCollection


@cached_function
def letter_graphs(n, k):
    """
    The set of all k-letter graphs with n vertices.
    """
    n_graphs = FindStatCollection(20).levels_with_sizes()
    c_graphs = set()
    def graph_iterator():
        c_digraphs = set()
        for L in subsets(range(k)):
            for Ds in digraphs(k):
                D = DiGraph([Ds.vertices(), Ds.edges() + [(l,l) for l in L]], loops = True)
                D = D.canonical_label().copy(immutable=True)
                if D in c_digraphs:
                    continue
                c_digraphs.add(D)
                for w in Words(alphabet=D.vertices(), length=n):
                    G = letter_graph(w, D).canonical_label().copy(immutable=True)
                    if G not in c_graphs:
                        c_graphs.add(G)
                        yield(G)
                        if n in n_graphs and len(c_graphs) == n_graphs[n]:
                            return
                
    return lazy_list(graph_iterator())

def statistic(G):
    G = G.canonical_label().copy(immutable=True)
    n = G.num_verts()
    for k in range(1, n+1):
        if G in letter_graphs(n, k):
            return k