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??????
H????A?
H????B?
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.
