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. A
faster method for the tests on Sandpile is needed.
Le jeudi 21 mars 2019 19:47:37 UTC+1, Dima Pasechnik a écrit :
>
>
>
> On Thu, 21 Mar 2019 18:42 Ai Bo, <boai...@gmail.com <javascript:>> wrote:
>
>> I found it. Thank you.
>> I also tried the command listed above.
>> I am confused. Where is this "I]~~~~~~w"?
>>
>
> This is a particular way to encode graph as a string of characters (8 bits
> per character).
> Read Sage docs on Graph for details.
>
> 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?
>>
>
> Ideally one should create a fast interface from Python to geng, probably
> using Cython, if it is not already done.
>
>
>> On Thursday, March 21, 2019 at 8:46:56 AM UTC-7, Dima Pasechnik wrote:
>>>
>>> On Thu, Mar 21, 2019 at 3:03 PM Ai Bo <boai...@gmail.com> wrote:
>>>
>>> > is this "nauty26r7/geng" a program available?
>>>
>>> geng is installed in local/bin/ sub-directory of your Sage
>>> installation, as a part of Sage's standard package nauty.
>>>
>>> > Also, as Python is slow, any part of the nautygen can be written in
>>> other language, such as C/C++?
>>>
>>> it is written in C, so it's quite fast in this sense.
>>>
>>> >
>>> > Thanks,
>>> > Laura
>>> >
>>> > On Wednesday, March 20, 2019 at 11:48:38 PM UTC-7, Jori Mäntysalo
>>> (TAU) 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+...@googlegroups.com.
>>> > To post to this group, send email to sage-...@googlegroups.com.
>>> > Visit this group at https://groups.google.com/group/sage-devel.
>>> > For more options, visit https://groups.google.com/d/optout.
>>>
>> --
>> 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+...@googlegroups.com <javascript:>.
>> To post to this group, send email to sage-...@googlegroups.com
>> <javascript:>.
>> Visit this group at https://groups.google.com/group/sage-devel.
>> For more options, visit https://groups.google.com/d/optout.
>>
>
--
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.
