Ask Your Question

Generate the list of all graph isomorphism classes of a given size n

asked 2023-01-31 03:32:55 +0200

octoberbear gravatar image

I am hoping to generate a list of all graph isomorphism classes of a given size. The current code that I have first generate all the graphs on 2n, and then take all the isomorphism class representatives of size n. But the first step of generating all graphs on 2n vertices can take a really long time and huge amount of memory (run 10 days on my university's research computing cloud) and crashes.

See the following for my code:

def iso_graphs(n):
    '''returns all isomorphism classes of simple graphs on n edges on 2*n vertices'''
    L = list(graphs(2 * n, loops=False, size=n))
    print("Do we ever reach this point?")
    L = [G.canonical_label().copy(immutable=True) for G in L if G.size() == n]
    return L

I wonder if what is a correct and efficient way of doing it.


edit retag flag offensive close merge delete


What value of $n$ do you take here? If $n$ is really big, maybe it's this slow.

licheng gravatar imagelicheng ( 2023-02-01 04:04:19 +0200 )edit

1 Answer

Sort by ยป oldest newest most voted

answered 2023-01-31 18:48:42 +0200

Max Alekseyev gravatar image

updated 2023-01-31 19:02:11 +0200

Do you really need a list of all graphs? This is what takes huge amount of memory.

If you need a generator of canonical labels then it can be obtained as

gen_cl = ( G.canonical_label().copy(immutable=True) for G in graphs(2 * n, loops=False, size=n) )

It will generate you canonical labels one at a time - like:

for mycl in gen_cl:
     print( mycl.graph6_string() )

PS. It may be the case that graphs generated by graphs() are already canonically labeled, and if so .canonical_label() is not needed.

edit flag offensive delete link more

Your Answer

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

Add Answer

Question Tools


Asked: 2023-01-31 03:32:55 +0200

Seen: 30 times

Last updated: Jan 31