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 <shiyue...@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.
--
You received this message because you are subscribed to the Google Groups
"sage-devel" group.
To unsubscribe from this group and stop receiving emails from it, send an email
to sage-devel+unsubscr...@googlegroups.com.
To view this discussion on the web visit
https://groups.google.com/d/msgid/sage-devel/CAAWYfq03MFopCBPxWD0ZJQ%2BD5sU6WYmvNhCu4qK2YiXu2deayQ%40mail.gmail.com.
