Re: [sage-devel] Re: Suggestion to speed up nauty_geng()?
On Fri, 22 Mar 2019, Ai Bo wrote: > With 12, I can't write to a file, it is at least 1500G. I can write to a > file up to around 300G at most. > That is why I am thinking how to divide the output of "geng 12". So > far, I don't have any idea. Any suggestion? You can (and should) use A/B -notation to geng: $ ./local/bin/geng 9 > /dev/null >A ./local/bin/geng -d0D8 n=9 e=0-36 >Z 274668 graphs generated in 0.15 sec $ ./local/bin/geng 9 0/10 > /dev/null >A ./local/bin/geng -X0x200d0D8 n=9 e=0-36 class=0/10 >Z 30682 graphs generated in 0.02 sec $ ./local/bin/geng 9 1/10 > /dev/null >A ./local/bin/geng -X0x200d0D8 n=9 e=0-36 class=1/10 >Z 26300 graphs generated in 0.02 sec and to verify this: ./local/bin/geng 9 | wc -l outputs 274668, just like for x in $(seq 0 9); do ./local/bin/geng 9 $x/10; done | wc -l (But I guess you must use splitting number bigger than 10, maybe ~100.) I think that you can run this in parallel and get you computation done in a day or two. But n=13 might need a supercomputer. -- Jori Mäntysalo Tampereen yliopisto - Ihminen ratkaisee -- 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 post to this group, send email to sage-devel@googlegroups.com. Visit this group at https://groups.google.com/group/sage-devel. For more options, visit https://groups.google.com/d/optout.
Re: [sage-devel] Re: Suggestion to speed up nauty_geng()?
Thank you!
I have resolved for up to "geng 11". It is the 12 that I need a solution. I
am aware how many graphs it generates.
I used multi-core manually, i.e., I launched multiple(24) geng program on a
24-core machine.
There is no doubt that geng is much faster than using sagemath's
nauty_geng(python). Thank you for the suggestion.
With 12, I can't write to a file, it is at least 1500G. I can write to a
file up to around 300G at most.
That is why I am thinking how to divide the output of "geng 12". So far,
I don't have any idea. Any suggestion?
On Friday, March 22, 2019 at 1:37:42 AM UTC-7, Jori Mäntysalo (TAU) wrote:
>
> OK, more explanation.
>
> * * *
>
> First I compare time for generating graphs in Nauty and in Sage. As plain
> graphs(n) uses nauty, I have test.sage containing
>
> print(sum(1 for _ in graphs(9)))
>
> It takes about 11½ seconds to run. I tested this with
>
> time ./sage test.sage
>
> Then,
>
> ./local/bin/geng 9 > /dev/null
>
> says "274668 graphs generated in 0.12 sec". So, if we just want to sample
> few graphs, we can get the speedup of ~50x. In other words, it is slow to
> convert data to Python internal format.
>
> OTOH number of many finite structures up to isomorphism grows very fast.
> So you can for example test some hypothesis to n=10 on a mobile phone,
> n=11 on a desktop computer and n=13 on a supercomputer. Same happens when
> you optimize code.
>
> * * *
>
> Next, does geng use multiple cpu cores? No. There is no difference between
>
> time taskset -c 1 ./local/bin/geng 9 > /dev/null
> time taskset -c 1-4 ./local/bin/geng 9 > /dev/null
>
> (You could also use "top" to see cpu usage.)
>
> * * *
>
> Now, how to use geng, make a sample, and then get them to Sage? First I
> generated all graphs (here to n=9 for speed):
>
> $ ./local/bin/geng 9 > g9
> >A ./local/bin/geng -d0D8 n=9 e=0-36
> >Z 274668 graphs generated in 0.12 sec
>
> OK, now I have a big list of strings:
>
> $ head -3 g9 ; tail -3 g9
> H??
> HA?
> HB?
> H]~
> H^~
> H~~
>
> Every line is an encoded graph. I want to make a sample, lets say every
> 1000:th line. Every line is (HERE, not when n=12) 8 bytes long. So,
>
> $ i=0; while [[ i -lt 274668 ]]; do dd if=g9 bs=8 skip=$i count=1 >>
> g9sample 2> /dev/null; i=$((i+1000)); done
>
> will give you a file of 275 lines:
>
> $ wc -l g9sample
> 275 g9sample
>
> And now I did a test2.sage -file:
>
> with open('g9sample', 'r') as fp:
> c = 0
> n = 0
> for line in fp:
> g = Graph(line, format='graph6')
> n += 1
> if g.is_connected():
> c += 1
> print("About %s percent are connected" % round(100.0*c/n))
>
> and
>
> $ ./sage test2.sage
> About 95 percent are connected
>
> Of course there are many other ways for this. For example you could read
> the whole file with Python and just skip 99,9% of lines, or skip every
> line with propability of 0.999 etc. Hopefully you get the idea from this.
>
> --
> Jori Mäntysalo
>
> Tampereen yliopisto - Ihminen ratkaisee
--
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 post to this group, send email to sage-devel@googlegroups.com.
Visit this group at https://groups.google.com/group/sage-devel.
For more options, visit https://groups.google.com/d/optout.
Re: [sage-devel] Re: Suggestion to speed up nauty_geng()?
On Thu, 21 Mar 2019, Simon King wrote: > Does either of you plan to open a ticket and make the functionality > available, that according to Jori is present in nauty but according > to Ai isn't wrapped in Sage? At least I do not. -- Jori Mäntysalo Tampereen yliopisto - Ihminen ratkaisee -- 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 post to this group, send email to sage-devel@googlegroups.com. Visit this group at https://groups.google.com/group/sage-devel. For more options, visit https://groups.google.com/d/optout.
Re: [sage-devel] Re: Suggestion to speed up nauty_geng()?
OK, more explanation.
* * *
First I compare time for generating graphs in Nauty and in Sage. As plain
graphs(n) uses nauty, I have test.sage containing
print(sum(1 for _ in graphs(9)))
It takes about 11½ seconds to run. I tested this with
time ./sage test.sage
Then,
./local/bin/geng 9 > /dev/null
says "274668 graphs generated in 0.12 sec". So, if we just want to sample
few graphs, we can get the speedup of ~50x. In other words, it is slow to
convert data to Python internal format.
OTOH number of many finite structures up to isomorphism grows very fast.
So you can for example test some hypothesis to n=10 on a mobile phone,
n=11 on a desktop computer and n=13 on a supercomputer. Same happens when
you optimize code.
* * *
Next, does geng use multiple cpu cores? No. There is no difference between
time taskset -c 1 ./local/bin/geng 9 > /dev/null
time taskset -c 1-4 ./local/bin/geng 9 > /dev/null
(You could also use "top" to see cpu usage.)
* * *
Now, how to use geng, make a sample, and then get them to Sage? First I
generated all graphs (here to n=9 for speed):
$ ./local/bin/geng 9 > g9
>A ./local/bin/geng -d0D8 n=9 e=0-36
>Z 274668 graphs generated in 0.12 sec
OK, now I have a big list of strings:
$ head -3 g9 ; tail -3 g9
H??
HA?
HB?
H]~
H^~
H~~
Every line is an encoded graph. I want to make a sample, lets say every
1000:th line. Every line is (HERE, not when n=12) 8 bytes long. So,
$ i=0; while [[ i -lt 274668 ]]; do dd if=g9 bs=8 skip=$i count=1 >> g9sample
2> /dev/null; i=$((i+1000)); done
will give you a file of 275 lines:
$ wc -l g9sample
275 g9sample
And now I did a test2.sage -file:
with open('g9sample', 'r') as fp:
c = 0
n = 0
for line in fp:
g = Graph(line, format='graph6')
n += 1
if g.is_connected():
c += 1
print("About %s percent are connected" % round(100.0*c/n))
and
$ ./sage test2.sage
About 95 percent are connected
Of course there are many other ways for this. For example you could read
the whole file with Python and just skip 99,9% of lines, or skip every
line with propability of 0.999 etc. Hopefully you get the idea from this.
--
Jori Mäntysalo
Tampereen yliopisto - Ihminen ratkaisee
--
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 post to this group, send email to sage-devel@googlegroups.com.
Visit this group at https://groups.google.com/group/sage-devel.
For more options, visit https://groups.google.com/d/optout.
[sage-devel] Re: Suggestion to speed up nauty_geng()?
Hi David, On 2019-03-22, David Coudert wrote: > Our interface to nauty geng is in Python, but the difficulty is not here. > >- It takes time to build graphs from graph6 strings, and also to build >Sandpiles (12 for each graph) >- The number of biconnected graphs with 12 nodes is huge: 153.620.333.545 > >See https://oeis.org/A002218 > > Some parallelism could certainly help here, but there will be no miracle. If I understand correctly, this thread is about how to create an iterator for these graphs that does not try to generate all of them at once (and if I understand correctly, nauty/geng provides such iterator, it just isn't wrapped, but could easily be, since the output of geng, which is a stand-alone executable, can be read as a string [by a wrapper in Sage] and then translated into a graph). The miracle would be that in a doc test you could probably iterate over the first 10 graphs, demonstrating that you do not need to create the remaining 153,620,333,535. Best regards, Simon -- 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 post to this group, send email to sage-devel@googlegroups.com. Visit this group at https://groups.google.com/group/sage-devel. For more options, visit https://groups.google.com/d/optout.
[sage-devel] Re: Suggestion to speed up nauty_geng()?
I found it. Thank you. I also tried the command listed above. I am confused. Where is this "I]~~w"? Is it a file? How did Graph load this? In my program, my code looks like this: i=12 for G in graphs.nauty_geng(str(i) + " -C"): q = True for j in range (0,i): S = Sandpile(G,j) if S.identity() != S.max_stable(): q = False break If I use geng to generate graphs, how should I load them in my for loop so I can check with Sandpile? Sorry for being new in Sagemath. Thank you all for the help. On Wednesday, March 20, 2019 at 9:33:26 PM UTC-7, Ai Bo wrote: > > I am running a program with these lines: > i =12 > for G in graphs.nauty_geng(str(i) + " -C"): > > It is very slow. I know the returned generator is very large. Is there a > way to speed this up? > > Is there a way to "random access"? For example, access the nth element in > the "generator", instead of one by one? > > Thank you! > -- 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 post to this group, send email to sage-devel@googlegroups.com. Visit this group at https://groups.google.com/group/sage-devel. For more options, visit https://groups.google.com/d/optout.
[sage-devel] Re: Suggestion to speed up nauty_geng()?
Hi!
Does either of you plan to open a ticket and make the functionality
available, that according to Jori is present in nauty but according
to Ai isn't wrapped in Sage?
Best regards,
Simon
On 2019-03-21, Jori Mäntysalo wrote:
> On Thu, 21 Mar 2019, Ai Bo wrote:
>
>> Is there a way to "random access"? For example, access the nth element
>> in the "generator", instead of one by one?
>
> Kind of. As a most time is propably spent by creating Python data
> structures for SageMath, you can use nautygen directly to generate huge
> number of graphs.
>
> As an example, it takes below 5 seconds to generate all biconnected graphs
> on 10 vertices, and I took third last one:
>
> $ nauty26r7/geng 10 -C | tail -3 | head -1
>>A /home/jm58660/lat-koe/nauty26r7/geng -Cd2D9 n=10 e=10-45
>>Z 9743542 graphs generated in 4.59 sec
> I]~~w
>
> and now
>
> sage: g = Graph('I]~~w', format='graph6')
> sage: g.is_biconnected()
> True
>
>
> --
> Jori Mäntysalo
>
> Tampereen yliopisto - Ihminen ratkaisee
>
--
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 post to this group, send email to sage-devel@googlegroups.com.
Visit this group at https://groups.google.com/group/sage-devel.
For more options, visit https://groups.google.com/d/optout.
