How to efficiently generate all graph isomorphism classes of a given size?

[Shiyue Li]

Hi all, 

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. 

Thanks!

[David Joyner]

Since all the graphs you are counting are disconnected,
my guess is that there is a combinatorial argument to
determine their number, say L_n, in terms of the number of connected ones.
Assuming you know the number of connected graphs on
k vertices with n edges (where k<=n+1), call it M_{k,n}, my guess
is you should be able to derive a formula for L_n in terms of
the M_{k,n} without needing a computer.

You may need a computer to tabulate the M_{k,n} but maybe
this is done already for "small" n,k?

> --
> You received this message because you are subscribed to the Google Groups "sage-support" group.
> To unsubscribe from this group and stop receiving emails from it, send an email to sage-support...@googlegroups.com.
> To view this discussion on the web visit https://groups.google.com/d/msgid/sage-support/0acb6537-3fe9-42dc-ab1b-c5c79dd5fb5cn%40googlegroups.com.

[Dima Pasechnik]

We have a function to do this job very efficently:

graphs.nauty_geng()

it generates non-isomorphic graphs. E.g. list(graphs.nauty_geng("3
-c")) gives you the complete list
(of lengh 2) of all non-isomrphic connected graphs on 3 vertices
(remove "-c" there if you want all graphs,
not only connected)

HTH
Dima

[Shiyue Li]

Thank you. Do you know what is an efficient way of getting these non-isomorphic graphs with n edges? 

Using your answer. I can use nauty_geng(2 * n), and then filter out all the graphs with n edges. But even going through nauty_geng(2*n) is more memory and spaces needed.