On Tue, Jan 31, 2023 at 4:59 PM Shiyue Li <shiyue...@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.
>
>
>
>
>
> On Tue, Jan 31, 2023 at 9:24 AM Dima Pasechnik <dimp...@gmail.com> wrote:
>>
>> 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/CAAWYfq1GfdhMd600RASkSmGD8t3qMgR6uwpfM9EWbPLcCuiThg%40mail.gmail.com.
