Re: [sage-support] How to efficiently generate all graph isomorphism classes of a given size?
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 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-support" group.
To unsubscribe from this group and stop receiving emails from it, send an email
to sage-support+unsubscr...@googlegroups.com.
To view this discussion on the web visit
https://groups.google.com/d/msgid/sage-support/a068d628-793b-4abf-a80d-402fc8333661n%40googlegroups.com.
Re: [sage-support] How to efficiently generate all graph isomorphism classes of a given size?
On Tue, Jan 31, 2023 at 2:38 AM Shiyue Li 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+unsubscr...@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-support" group.
To unsubscribe from this group and stop receiving emails from it, send an email
to sage-support+unsubscr...@googlegroups.com.
To view this discussion on the web visit
https://groups.google.com/d/msgid/sage-support/CAAWYfq0EG%2BGhzJu%3D6iw%3DHmxe%2Bfwbd3%2BAEVdd%2BWtPnq_DO_8Bsg%40mail.gmail.com.
Re: [sage-support] How to efficiently generate all graph isomorphism classes of a given size?
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?
On Mon, Jan 30, 2023 at 9:38 PM Shiyue Li 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.
>
> 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+unsubscr...@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-support" group.
To unsubscribe from this group and stop receiving emails from it, send an email
to sage-support+unsubscr...@googlegroups.com.
To view this discussion on the web visit
https://groups.google.com/d/msgid/sage-support/CAEQuuAX8ApuYCD6Jxp3L3E8YsTNqjd%2BBCZU%3DW-b%3Dx%2BL0110tgA%40mail.gmail.com.
