Re: Private message regarding: [sage-support] How to efficiently generate all graph isomorphism classes of a given size?

[Dima Pasechnik]

There are infinitely many graphs with n edges (just keep throwing in
more isolated vertices)
That is, you basically need to restrict to connected ones only (as a
variation, only ones without isolated vertices).

sage: graphs.nauty_geng?

will tell you

The possible options, obtained as output of "geng --help":

n : the number of vertices
mine:maxe : <int>:<int> a range for the number of edges
<int>:0 means '<int> or more' except in the case 0:0

that 2nd positional parameter to pass can be used to say how many
edges you need. E.g.


sage: [list(graphs.nauty_geng(str(n)+" 5:5 -c")) for n in range(4,7)]
[[Graph on 4 vertices],
[Graph on 5 vertices,
Graph on 5 vertices,
Graph on 5 vertices,
Graph on 5 vertices,
Graph on 5 vertices],
[Graph on 6 vertices,
Graph on 6 vertices,
Graph on 6 vertices,
Graph on 6 vertices,
Graph on 6 vertices,
Graph on 6 vertices]]

lists all connected graphs with exactly 5 edges.

HTH
Dima

On Tue, Jan 31, 2023 at 1:52 PM Shiyue Li <shiy...@brown.edu> wrote:
>
> 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.
>
>
> On Tuesday, January 31, 2023 at 6:49:03 AM UTC-5 dim...@gmail.com wrote:
> On Tue, Jan 31, 2023 at 2:38 AM Shiyue Li <shiy...@brown.edu> wrote:
> >
> > 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.
>
> 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
>
> >
> > Thanks!
> >
> > --
> > 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]

On Tue, Jan 31, 2023 at 4:59 PM Shiyue Li <shiy...@brown.edu> wrote:
>
> I agree that I don’t want isolated vertices. But putting “-c” would eliminate all graphs of the given edge size n that have more than 1 connected components. I would still want to consider those. For example, a tree of 4 edges together with a disjoint edge is a graph that I want for n = 5.

For n=5 it's

[list(graphs.nauty_geng(str(n)+" 5:5")) for n in range(4,11)]

In general, if e is the number of edges, n should vary from min(n:
n(n-1)>=2e) to 2e.


>
> Would there be a simpler way of doing this?
>
> One way is List(graphs.nauty_geng(str(2*n) + “ n:n”)).
>
> The reason for the 2*n is because the maximum number of vertices a (possibly disconnected, without isolated vertices) graph can possess is 2*n.
>
> But this is still slower than I desired as n = 8, for example.