Re: [sage-devel] Re: how does the res/mod in "geng" work?
On Mon, Mar 25, 2019 at 10:58 AM Jori Mäntysalo (TAU) wrote: > > Btw, what is most simple way in SageMath to run parallel independent jobs > without dependencies? > > For example, let G() be a generator outputting 1000 objects and let there > be four cpu cores available. Now it would be nice if we could just fork > four processes, each basically saying for example "Get an object o from > G(), compute f(o), and if it is 42, save o to the list F." This needs an > atomic way to call G(), and an atomic way to append a list. > > This seems so common form of computation that I suppose there is some nice > way for this. For most cases you can try multiprocessing.Pool.map_async, and it works pretty nicely. It's biggest flaw for use in Sage is that it has a shortcoming where if an exception occurs in one of the worker processes, it only properly handles exceptions that inherit from Exception, and there are a few kinds of Python exceptions (e.g. KeyboardError) that do not. In conjunction with that, there's a bug (fixed in Python 3 though) that the map_async call would never return a result if one of the worker processes died unexpectedly (e.g. due to an unhandled segfault). But modulo those cases of crappy error handling, multiprocessing.Pool is exactly what you just described. -- 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: how does the res/mod in "geng" work?
There is the parallel decorator [1]. For even less dependencies there is the multiprocessing module [2] in Python's standard library. Regards, TB [1] https://doc.sagemath.org/html/en/reference/parallel/index.html [2] https://docs.python.org/2/library/multiprocessing.html On 25/03/2019 11:58, Jori Mäntysalo (TAU) wrote: Btw, what is most simple way in SageMath to run parallel independent jobs without dependencies? For example, let G() be a generator outputting 1000 objects and let there be four cpu cores available. Now it would be nice if we could just fork four processes, each basically saying for example "Get an object o from G(), compute f(o), and if it is 42, save o to the list F." This needs an atomic way to call G(), and an atomic way to append a list. This seems so common form of computation that I suppose there is some nice way for this. -- 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: how does the res/mod in "geng" work?
Btw, what is most simple way in SageMath to run parallel independent jobs without dependencies? For example, let G() be a generator outputting 1000 objects and let there be four cpu cores available. Now it would be nice if we could just fork four processes, each basically saying for example "Get an object o from G(), compute f(o), and if it is 42, save o to the list F." This needs an atomic way to call G(), and an atomic way to append a list. This seems so common form of computation that I suppose there is some nice way for 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: how does the res/mod in "geng" work?
I usually take the approach of splitting further. If you split in 10 parts, and part 3 took too long. You can split this part in two more parts by splitting into 20 and running part 3 and 13. (In reality I usually split into more parts, but for the example this seemed enough). It's always the symmetric graphs that 'break' these things. There are hardly any graphs with a non-trivial symmetry group, but when you're writing generation algorithms they tend to take up a significant percentage of the time, so you have to take them into account. Things are much nicer with graphs with a trivial symmetry group. :-) Nico Op zo 24 mrt. 2019 om 10:47 schreef Jori Mäntysalo (TAU) < jori.mantys...@tuni.fi>: > On Sun, 24 Mar 2019, Nico Van Cleemput wrote: > > > If you use the normal splitting with geng, it might become more even if > you go to a higher number of > > parts. However, it will never be completely even. > > We could also use geng to split output to for example 100 parts and then > combine parts so that we get 10 almost equal sized part. > > But then, it may be that in following computation almost all time is used > for only few graphs. As an example: take all posets on 10 elements and > compute the dimension. Now exactly one poset, the standard example of 2 × > 5 elements, will take very long time. Of course similar does not always > occur, it depends on what we are computing. > > -- > 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. > -- 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: how does the res/mod in "geng" work?
On Sun, 24 Mar 2019, Nico Van Cleemput wrote: > If you use the normal splitting with geng, it might become more even if you > go to a higher number of > parts. However, it will never be completely even. We could also use geng to split output to for example 100 parts and then combine parts so that we get 10 almost equal sized part. But then, it may be that in following computation almost all time is used for only few graphs. As an example: take all posets on 10 elements and compute the dimension. Now exactly one poset, the standard example of 2 × 5 elements, will take very long time. Of course similar does not always occur, it depends on what we are computing. -- 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: how does the res/mod in "geng" work?
If you use the normal splitting with geng, it might become more even if you
go to a higher number of parts. However, it will never be completely even.
If you want to split he output of geng evenly than all graphs will have to
be generated anyway, because there is no other way to guarantee this.
Therefore it is simpler to split the output after it has been generated by
geng. The code below is a possibility, but I would strongly advice you the
focus on the second part of your computations. As was mentioned by other
people as well: the thing that is slowing everything down is Sandpile and
not geng.
geng 12 | awk "NR % 6000 == 0 {print $1}"
This splits the output of geng in 6000 parts and outputs part 0 (i.e. the
first part). Replace the 0 by a number in the range 0-5999 to get all
parts. This will be split as evenly as possible.
Op vr 22 mrt. 2019 om 16:38 schreef Ai Bo :
> It is very true that I am not familiar with geng, nor sagemath. I just
> installed on my machine a few days ago.
>
> The reason I want to modify geng.c is I don't have a way to partition the
> output of "geng 12". I have finished up to "geng 11" so far, mostly with
> manual work. I know how many "geng 12" generates.
>
> With "geng 12", the output, if written to a file, is too large for my
> machine to handle. I can write to about 300G, not anything like 1500G.
>
> That is why I am looking at res/mod, but it seems I can't easily control
> how large the output will be (or I just don't know how).
>
> So if I can modify "geng" program, I can control the output range. Any
> other suggestion?
>
>
>
> On Friday, March 22, 2019 at 12:28:32 AM UTC-7, nvcleemp wrote:
>>
>> Why would you want to modify geng.c? From your previous comments I get
>> the impression that you are not familiar with the algorithm that geng uses.
>> You're not even familiar with the way geng encodes graphs. In that case it
>> is almost guaranteed that you will break something if you modify it.
>>
>> So again, why would you want to modify it? If it is to obtain an even
>> split, then you can only do this by generating all graphs and then
>> splitting the output. The commands to do this without translating the
>> intermediate graphs to the Sage data structure have been shown in the other
>> thread. For anything larger than 12 this will still be too slow since there
>> are just so many graphs.
>>
>> The builtin splitting in geng works by generating the graphs and at a
>> certain depth in the generation tree counting the branches and only
>> proceeding if the number modulo mod is equal to res. This way not
>> everything is generated and if this is done at a suitable depth then the
>> splitting will be fairly equal.
>>
>> Cheers
>> Nico
>>
>> Op vr 22 mrt. 2019 om 06:06 schreef Ai Bo :
>>
>>> Sorry for not being clear.
>>> I meant I used geng —help.
>>> Apparently, the equal divide doesn’t help in my example case.
>>> Where is this geng.c file? If I modify geng.c, how should I build geng?
>>>
>>> On Thu, Mar 21, 2019 at 9:58 PM John H Palmieri
>>> wrote:
>>>
On Thursday, March 21, 2019 at 9:38:03 PM UTC-7, Ai Bo wrote:
>
> Saw this in the document:
> res/mod : only generate subset res out of subsets 0..mod-1
>
It would help if you gave some context for this. I'm guessing that most
Sage users won't know what "geng" is. I certainly didn't. I found by
searching the source code that you found this help message in the method
"nauty_geng" in graph_generators.py: you should have said this at the start
instead of just "saw this in the document". This makes it look like the
program "geng" comes from nauty. Now look at the nauty source code (there
is a tar file in the "upstream" directory, if you have a source code
version of Sage, also available at
http://files.sagemath.org/spkg/upstream/nauty/index.html). The nauty
manual says
res/mod : only generate subset res out of subsets 0..mod-1
and
See program text for much more information.
The file geng.c says
mod, res = a way to restrict the output to a subset.
All the graphs in G(n,mine..maxe) are divided
into
disjoint classes C(0,mod),C(1,mod),...,C(mod-1,
mod),
of very approximately equal size.
Only the class C(res,mod) is written.
If the -x or -X switch is used, they must have
the
same value for different values of res;
otherwise
the partitioning may not be valid. In this
case
(-x,-X with constant value), the usual
relationships
between modulo classes are obeyed; for example
C(3,4) = C(3,8) union C(7,8). This is not true
if 3/8 and 7/8 are
Re: [sage-devel] Re: how does the res/mod in "geng" work?
It is very true that I am not familiar with geng, nor sagemath. I just installed on my machine a few days ago. The reason I want to modify geng.c is I don't have a way to partition the output of "geng 12". I have finished up to "geng 11" so far, mostly with manual work. I know how many "geng 12" generates. With "geng 12", the output, if written to a file, is too large for my machine to handle. I can write to about 300G, not anything like 1500G. That is why I am looking at res/mod, but it seems I can't easily control how large the output will be (or I just don't know how). So if I can modify "geng" program, I can control the output range. Any other suggestion? On Friday, March 22, 2019 at 12:28:32 AM UTC-7, nvcleemp wrote: > > Why would you want to modify geng.c? From your previous comments I get the > impression that you are not familiar with the algorithm that geng uses. > You're not even familiar with the way geng encodes graphs. In that case it > is almost guaranteed that you will break something if you modify it. > > So again, why would you want to modify it? If it is to obtain an even > split, then you can only do this by generating all graphs and then > splitting the output. The commands to do this without translating the > intermediate graphs to the Sage data structure have been shown in the other > thread. For anything larger than 12 this will still be too slow since there > are just so many graphs. > > The builtin splitting in geng works by generating the graphs and at a > certain depth in the generation tree counting the branches and only > proceeding if the number modulo mod is equal to res. This way not > everything is generated and if this is done at a suitable depth then the > splitting will be fairly equal. > > Cheers > Nico > > Op vr 22 mrt. 2019 om 06:06 schreef Ai Bo > >: > >> Sorry for not being clear. >> I meant I used geng —help. >> Apparently, the equal divide doesn’t help in my example case. >> Where is this geng.c file? If I modify geng.c, how should I build geng? >> >> On Thu, Mar 21, 2019 at 9:58 PM John H Palmieri > > wrote: >> >>> >>> >>> On Thursday, March 21, 2019 at 9:38:03 PM UTC-7, Ai Bo wrote: Saw this in the document: res/mod : only generate subset res out of subsets 0..mod-1 >>> >>> It would help if you gave some context for this. I'm guessing that most >>> Sage users won't know what "geng" is. I certainly didn't. I found by >>> searching the source code that you found this help message in the method >>> "nauty_geng" in graph_generators.py: you should have said this at the start >>> instead of just "saw this in the document". This makes it look like the >>> program "geng" comes from nauty. Now look at the nauty source code (there >>> is a tar file in the "upstream" directory, if you have a source code >>> version of Sage, also available at >>> http://files.sagemath.org/spkg/upstream/nauty/index.html). The nauty >>> manual says >>> >>> res/mod : only generate subset res out of subsets 0..mod-1 >>> >>> and >>> >>> See program text for much more information. >>> >>> The file geng.c says >>> >>> mod, res = a way to restrict the output to a subset. >>> All the graphs in G(n,mine..maxe) are divided >>> into >>> disjoint classes C(0,mod),C(1,mod),...,C(mod-1, >>> mod), >>> of very approximately equal size. >>> Only the class C(res,mod) is written. >>> >>> If the -x or -X switch is used, they must have >>> the >>> same value for different values of res; >>> otherwise >>> the partitioning may not be valid. In this case >>> (-x,-X with constant value), the usual >>> relationships >>> between modulo classes are obeyed; for example >>> C(3,4) = C(3,8) union C(7,8). This is not true >>> if 3/8 and 7/8 are done with -x or -X values >>> different from those used for 3/4. >>> >>> >>> How is the output divided? I tried with : ../sage-8.6/local/bin/geng 6 -C 0/7 and then I iterated from 0/7, 1/7, 2/7, 3/7 Why the output is 27, 21, 7, 1, 0, 0, ... How is the subset generated? Thank you. >>> -- >>> You received this message because you are subscribed to a topic in the >>> Google Groups "sage-devel" group. >>> To unsubscribe from this topic, visit >>> https://groups.google.com/d/topic/sage-devel/FJZoODSZK3Q/unsubscribe. >>> To unsubscribe from this group and all its topics, 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 me
Re: [sage-devel] Re: how does the res/mod in "geng" work?
Why would you want to modify geng.c? From your previous comments I get the impression that you are not familiar with the algorithm that geng uses. You're not even familiar with the way geng encodes graphs. In that case it is almost guaranteed that you will break something if you modify it. So again, why would you want to modify it? If it is to obtain an even split, then you can only do this by generating all graphs and then splitting the output. The commands to do this without translating the intermediate graphs to the Sage data structure have been shown in the other thread. For anything larger than 12 this will still be too slow since there are just so many graphs. The builtin splitting in geng works by generating the graphs and at a certain depth in the generation tree counting the branches and only proceeding if the number modulo mod is equal to res. This way not everything is generated and if this is done at a suitable depth then the splitting will be fairly equal. Cheers Nico Op vr 22 mrt. 2019 om 06:06 schreef Ai Bo : > Sorry for not being clear. > I meant I used geng —help. > Apparently, the equal divide doesn’t help in my example case. > Where is this geng.c file? If I modify geng.c, how should I build geng? > > On Thu, Mar 21, 2019 at 9:58 PM John H Palmieri > wrote: > >> >> >> On Thursday, March 21, 2019 at 9:38:03 PM UTC-7, Ai Bo wrote: >>> >>> Saw this in the document: >>> res/mod : only generate subset res out of subsets 0..mod-1 >>> >> >> It would help if you gave some context for this. I'm guessing that most >> Sage users won't know what "geng" is. I certainly didn't. I found by >> searching the source code that you found this help message in the method >> "nauty_geng" in graph_generators.py: you should have said this at the start >> instead of just "saw this in the document". This makes it look like the >> program "geng" comes from nauty. Now look at the nauty source code (there >> is a tar file in the "upstream" directory, if you have a source code >> version of Sage, also available at >> http://files.sagemath.org/spkg/upstream/nauty/index.html). The nauty >> manual says >> >> res/mod : only generate subset res out of subsets 0..mod-1 >> >> and >> >> See program text for much more information. >> >> The file geng.c says >> >> mod, res = a way to restrict the output to a subset. >> All the graphs in G(n,mine..maxe) are divided >> into >> disjoint classes C(0,mod),C(1,mod),...,C(mod-1, >> mod), >> of very approximately equal size. >> Only the class C(res,mod) is written. >> >> If the -x or -X switch is used, they must have >> the >> same value for different values of res; >> otherwise >> the partitioning may not be valid. In this case >> (-x,-X with constant value), the usual >> relationships >> between modulo classes are obeyed; for example >> C(3,4) = C(3,8) union C(7,8). This is not true >> if 3/8 and 7/8 are done with -x or -X values >> different from those used for 3/4. >> >> >> >>> >>> How is the output divided? >>> >>> I tried with : ../sage-8.6/local/bin/geng 6 -C 0/7 >>> and then I iterated from 0/7, 1/7, 2/7, 3/7 >>> Why the output is 27, 21, 7, 1, 0, 0, ... >>> >>> How is the subset generated? >>> >>> Thank you. >>> >> -- >> You received this message because you are subscribed to a topic in the >> Google Groups "sage-devel" group. >> To unsubscribe from this topic, visit >> https://groups.google.com/d/topic/sage-devel/FJZoODSZK3Q/unsubscribe. >> To unsubscribe from this group and all its topics, 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. >> > -- > 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. > -- 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: how does the res/mod in "geng" work?
On Thursday, March 21, 2019 at 10:06:26 PM UTC-7, Ai Bo wrote: > > Sorry for not being clear. > I meant I used geng —help. > Apparently, the equal divide doesn’t help in my example case. > Where is this geng.c file? If I modify geng.c, how should I build geng? > It's part of nauty. > On Thu, Mar 21, 2019 at 9:58 PM John H Palmieri > wrote: > >> >> >> On Thursday, March 21, 2019 at 9:38:03 PM UTC-7, Ai Bo wrote: >>> >>> Saw this in the document: >>> res/mod : only generate subset res out of subsets 0..mod-1 >>> >> >> It would help if you gave some context for this. I'm guessing that most >> Sage users won't know what "geng" is. I certainly didn't. I found by >> searching the source code that you found this help message in the method >> "nauty_geng" in graph_generators.py: you should have said this at the start >> instead of just "saw this in the document". This makes it look like the >> program "geng" comes from nauty. Now look at the nauty source code (there >> is a tar file in the "upstream" directory, if you have a source code >> version of Sage, also available at >> http://files.sagemath.org/spkg/upstream/nauty/index.html). The nauty >> manual says >> >> res/mod : only generate subset res out of subsets 0..mod-1 >> >> and >> >> See program text for much more information. >> >> The file geng.c says >> >> mod, res = a way to restrict the output to a subset. >> All the graphs in G(n,mine..maxe) are divided >> into >> disjoint classes C(0,mod),C(1,mod),...,C(mod-1, >> mod), >> of very approximately equal size. >> Only the class C(res,mod) is written. >> >> If the -x or -X switch is used, they must have >> the >> same value for different values of res; >> otherwise >> the partitioning may not be valid. In this case >> (-x,-X with constant value), the usual >> relationships >> between modulo classes are obeyed; for example >> C(3,4) = C(3,8) union C(7,8). This is not true >> if 3/8 and 7/8 are done with -x or -X values >> different from those used for 3/4. >> >> >> >>> >>> How is the output divided? >>> >>> I tried with : ../sage-8.6/local/bin/geng 6 -C 0/7 >>> and then I iterated from 0/7, 1/7, 2/7, 3/7 >>> Why the output is 27, 21, 7, 1, 0, 0, ... >>> >>> How is the subset generated? >>> >>> Thank you. >>> >> -- >> You received this message because you are subscribed to a topic in the >> Google Groups "sage-devel" group. >> To unsubscribe from this topic, visit >> https://groups.google.com/d/topic/sage-devel/FJZoODSZK3Q/unsubscribe. >> To unsubscribe from this group and all its topics, 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+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: how does the res/mod in "geng" work?
Sorry for not being clear. I meant I used geng —help. Apparently, the equal divide doesn’t help in my example case. Where is this geng.c file? If I modify geng.c, how should I build geng? On Thu, Mar 21, 2019 at 9:58 PM John H Palmieri wrote: > > > On Thursday, March 21, 2019 at 9:38:03 PM UTC-7, Ai Bo wrote: >> >> Saw this in the document: >> res/mod : only generate subset res out of subsets 0..mod-1 >> > > It would help if you gave some context for this. I'm guessing that most > Sage users won't know what "geng" is. I certainly didn't. I found by > searching the source code that you found this help message in the method > "nauty_geng" in graph_generators.py: you should have said this at the start > instead of just "saw this in the document". This makes it look like the > program "geng" comes from nauty. Now look at the nauty source code (there > is a tar file in the "upstream" directory, if you have a source code > version of Sage, also available at > http://files.sagemath.org/spkg/upstream/nauty/index.html). The nauty > manual says > > res/mod : only generate subset res out of subsets 0..mod-1 > > and > > See program text for much more information. > > The file geng.c says > > mod, res = a way to restrict the output to a subset. > All the graphs in G(n,mine..maxe) are divided into > disjoint classes C(0,mod),C(1,mod),...,C(mod-1,mod > ), > of very approximately equal size. > Only the class C(res,mod) is written. > > If the -x or -X switch is used, they must have > the > same value for different values of res; otherwise > the partitioning may not be valid. In this case > (-x,-X with constant value), the usual > relationships > between modulo classes are obeyed; for example > C(3,4) = C(3,8) union C(7,8). This is not true > if 3/8 and 7/8 are done with -x or -X values > different from those used for 3/4. > > > >> >> How is the output divided? >> >> I tried with : ../sage-8.6/local/bin/geng 6 -C 0/7 >> and then I iterated from 0/7, 1/7, 2/7, 3/7 >> Why the output is 27, 21, 7, 1, 0, 0, ... >> >> How is the subset generated? >> >> Thank you. >> > -- > You received this message because you are subscribed to a topic in the > Google Groups "sage-devel" group. > To unsubscribe from this topic, visit > https://groups.google.com/d/topic/sage-devel/FJZoODSZK3Q/unsubscribe. > To unsubscribe from this group and all its topics, 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. > -- 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: how does the res/mod in "geng" work?
On Thursday, March 21, 2019 at 9:38:03 PM UTC-7, Ai Bo wrote: > > Saw this in the document: > res/mod : only generate subset res out of subsets 0..mod-1 > It would help if you gave some context for this. I'm guessing that most Sage users won't know what "geng" is. I certainly didn't. I found by searching the source code that you found this help message in the method "nauty_geng" in graph_generators.py: you should have said this at the start instead of just "saw this in the document". This makes it look like the program "geng" comes from nauty. Now look at the nauty source code (there is a tar file in the "upstream" directory, if you have a source code version of Sage, also available at http://files.sagemath.org/spkg/upstream/nauty/index.html). The nauty manual says res/mod : only generate subset res out of subsets 0..mod-1 and See program text for much more information. The file geng.c says mod, res = a way to restrict the output to a subset. All the graphs in G(n,mine..maxe) are divided into disjoint classes C(0,mod),C(1,mod),...,C(mod-1,mod), of very approximately equal size. Only the class C(res,mod) is written. If the -x or -X switch is used, they must have the same value for different values of res; otherwise the partitioning may not be valid. In this case (-x,-X with constant value), the usual relationships between modulo classes are obeyed; for example C(3,4) = C(3,8) union C(7,8). This is not true if 3/8 and 7/8 are done with -x or -X values different from those used for 3/4. > > How is the output divided? > > I tried with : ../sage-8.6/local/bin/geng 6 -C 0/7 > and then I iterated from 0/7, 1/7, 2/7, 3/7 > Why the output is 27, 21, 7, 1, 0, 0, ... > > How is the subset generated? > > 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.
