Opened 9 years ago
Last modified 7 weeks ago
#14110 new enhancement
Speed Up Poset Generation
Reported by: | csar | Owned by: | csar |
---|---|---|---|
Priority: | major | Milestone: | sage-9.7 |
Component: | combinatorics | Keywords: | posets |
Cc: | kdilks, rowland, ahmorales, jmantysalo, jason, ncohen, dimpase | Merged in: | |
Authors: | Reviewers: | Thierry Monteil | |
Report Upstream: | N/A | Work issues: | |
Branch: | Commit: | ||
Dependencies: | Stopgaps: |
Description (last modified by )
Currently (sage 5.6), Sage generates the posets on n elements by generating all digraphs with n vertices and checking which of those give posets. A paper of Brinkmann and McKay? gives an algorithm for generating posets which they used to generate posets up to 16. Sage uses a related algorithm of McKay? to generate the digraphs.
- D. McKay? and G. Brinkmann, Posets on up to 16 points, Order, 19 (2002) 147-179
Attachments (2)
Change History (41)
comment:1 Changed 9 years ago by
- Type changed from PLEASE CHANGE to enhancement
comment:2 Changed 9 years ago by
- Description modified (diff)
- Keywords posets added
comment:3 Changed 9 years ago by
- Milestone changed from sage-5.11 to sage-5.12
comment:4 Changed 8 years ago by
- Milestone changed from sage-6.1 to sage-6.2
comment:5 Changed 8 years ago by
- Milestone changed from sage-6.2 to sage-6.3
comment:6 Changed 8 years ago by
- Milestone changed from sage-6.3 to sage-6.4
comment:7 Changed 8 years ago by
- Cc jmantysalo added
comment:8 follow-up: ↓ 9 Changed 8 years ago by
Since you have (working) specialized C-code, I'd just glue it to Sage using cython (guaranteed to be faster than a pure python implementation). Anyways, that's my opinion.
comment:9 in reply to: ↑ 8 Changed 8 years ago by
Replying to tscrim:
Since you have (working) specialized C-code, I'd just glue it to Sage using cython (guaranteed to be faster than a pure python implementation). Anyways, that's my opinion.
For that I first have to learn how to do glueing... Somewhere in the net should be simple example of making python data structure from C code.
comment:10 Changed 8 years ago by
As a quick test: len(Posets(6).list())
took about 10 seconds, reading binary output from Brinkmann's code for posets of size 7 took about 12 seconds. Maybe going to cython will make n=8 to took about same time.
E: About 90% of time is used in making posets from digraphs.
comment:11 Changed 8 years ago by
I attached the code I got from Brinkmann. It contains a slightly modified version of nauty; hence copyright is free "- - with the exception of sale for profit or application with nontrivial military significance." So it must be made to an optional package.
It compiles with gcc -O4 -o /tmp/posets posets.c nauty_poset.c nautil_poset.c
. Code to use it in non-optimal way seems to be quite easy:
import subprocess def generate_posets(n): # Add check for the argument etc. cmd=["/tmp/posets"] args=[str(n), 'o'] sp=subprocess.Popen(cmd+args, shell=False, stdin=subprocess.PIPE, stdout=subprocess.PIPE, stderr=subprocess.PIPE, close_fds=True) reader=iter(lambda: sp.stdout.read(2+2*n), '') while True: bin=reader.next()[2:] L=[] for i in range(0, n): t=ord(bin[1+2*i])*256+ord(bin[2*i]) for j in range(0, n): if (t << j) & 32768: L.append((i,j)) G=DiGraph() G.add_vertices(range(0, n)) G.add_edges(L) yield Poset(G, facade = True)
There is much to make it even faster: for example to check linear extension and use FinitePoset? directly, or even add to static sparse graphs an initializer that takes plain list as argument.
comment:12 follow-up: ↓ 20 Changed 8 years ago by
First test of packing files to .spkg is now attached to this ticket. Needs to add license information etc. Also I will do a test file and one line test script to check output.
However, now somebody could test if also 32-bit Linux and Mac OS X are able to install this.
Line cmd=["/tmp/posets"]
must be changed to cmd=[sage.env.SAGE_LOCAL+"/bin/genposets"]
.
comment:13 Changed 8 years ago by
What should be the interface for this? If the package is installed, should Posets(n)
use it automatically? What if we later got algorithm for generating for example all lattices or all modular lattices? Maybe this could be something like
Posets.PosetGenerator(n, properties='all')
And then later we could have something like properties='lattice'
. Same arguments could be available also on Posets.RandomPoset()
. Plain Posets(n)
could be modified to use this, if the package is available.
comment:14 follow-ups: ↓ 23 ↓ 25 Changed 8 years ago by
I asked from Brendan McKay? "Nauty.h contains copyright with 'exception of sale for profit or application with nontrivial military significance.' Does this apply to whole package?" and he answered: "It applies to all of the nauty files, but for incorporation into Sage you can ignore it.
Another thing, somebody using Mac should check if this compiles. And answer my last question.
comment:15 follow-up: ↓ 16 Changed 7 years ago by
- Cc jason ncohen added
Note that nauty
is already an optional Sage package, in old-spkg-style format : http://sagemath.org/packages/optional/
comment:16 in reply to: ↑ 15 ; follow-up: ↓ 17 Changed 7 years ago by
Replying to tmonteil:
Note that
nauty
is already an optional Sage package
True, but I think that it does not contain a code for generating posets.
Or do you mean to append this poset generation to nauty package?
comment:17 in reply to: ↑ 16 ; follow-up: ↓ 18 Changed 7 years ago by
Note that
nauty
is already an optional Sage packageTrue, but I think that it does not contain a code for generating posets.
Indeed. Do you think is is possible to rely on the existing nauty package for the nauty-part, and only add the poset-specific stuff ? Maybe it does not worth the work if the nauty part is too modified and is a small part of posetgen.
Also, do you think upstream could officially distribute its poset code (within nauty or in a separate tarball) ?
Or do you mean to append this poset generation to nauty package?
Definitely not, i think we should keep upstream tarball's integrity as much as possible (in particular moving nauty to the new spkg layout could be nice).
comment:18 in reply to: ↑ 17 Changed 7 years ago by
Replying to tmonteil:
Do you think is is possible to rely on the existing nauty package for the nauty-part, and only add the poset-specific stuff ? Maybe it does not worth the work if the nauty part is too modified and is a small part of posetgen.
nauty_poset.c
starts with "modified by Gunnar Brinkmann for use with posets." Hence I guess it is inpractical to merge.
Whole code for poset generation is about 7000 lines, so there is not much space to save.
Also, do you think upstream could officially distribute its poset code (within nauty or in a separate tarball) ?
I haven't asked that. But if they are not going to maintain poset code, then what difference would that do?
comment:19 Changed 7 years ago by
Replying to jmantysalo:
nauty_poset.c
starts with "modified by Gunnar Brinkmann for use with posets." Hence I guess it is inpractical to merge.Whole code for poset generation is about 7000 lines, so there is not much space to save.
OK, i was just asking to avoid code duplication (especially if was have to patch it).
Also, do you think upstream could officially distribute its poset code (within nauty or in a separate tarball) ?
I haven't asked that. But if they are not going to maintain poset code, then what difference would that do?
Upstream will be that trac ticket. And each modified version (e.g. to compile on particular architecture) will become the next upstream without clear distinction.
Having a well identified upstream source whose checksum can be checked by anyone is preferable. If i come with a modified code that is attributed to someone else, there is no way to check my modifications (disclaimer: i am not insinuating anything with respect to the current package !). The new layout upstream-unmodified-checkable-source + downstream-readable-patches makes things more clear.
comment:20 in reply to: ↑ 12 Changed 7 years ago by
- Reviewers set to Thierry Monteil
Replying to jmantysalo:
However, now somebody could test if also 32-bit Linux and Mac OS X are able to install this.
This works for me (in the sense : i can compile and run the program, i did not check the results) on Linux 32 bits (Debian wheezy).
However, i can not run the tests because of the #!/usr/bin/sh
at the beginning of spkg-check
(note that you used #!/bin/sh
in spkg-install
). Perhaps could you use #!/usr/bin/env sh
instead.
Also, it is unlikely this test will work since spkg-install
creates a binary named posetgen
and spkg-check
calls a binary named genposets
.
Changed 7 years ago by
comment:21 Changed 7 years ago by
I changed package file. Hope it works now.
comment:22 Changed 7 years ago by
comment:23 in reply to: ↑ 14 ; follow-up: ↓ 24 Changed 7 years ago by
Replying to jmantysalo:
I asked from Brendan McKay? "Nauty.h contains copyright with 'exception of sale for profit or application with nontrivial military significance.' Does this apply to whole package?" and he answered: "It applies to all of the nauty files, but for incorporation into Sage you can ignore it.
Any idea what "It applies to all of the nauty files, but for incorporation into Sage you can ignore it" actually means? The problem is that it really needs to be GPL v3 to be standard in Sage. And once it's GPL, it's GPL for everybody, not just for Sage.
The "sale for profit" isn't an unlikely scenario given William Stein's plans to make money from SMC.
Final remark: it's allowed by the GPL to run Sage and nauty as separate programs (using Python's subprocess
for example), but not to link nauty as a library.
comment:24 in reply to: ↑ 23 ; follow-up: ↓ 26 Changed 7 years ago by
Replying to jdemeyer:
Any idea what "It applies to all of the nauty files, but for incorporation into Sage you can ignore it" actually means? The problem is that it really needs to be GPL v3 to be standard in Sage. And once it's GPL, it's GPL for everybody, not just for Sage.
The "sale for profit" isn't an unlikely scenario given William Stein's plans to make money from SMC.
And even restriction to non-military applications is a problem. Who can be sure that there will never be any military application for posets?
Do we have someone who is better to discuss with McKay? about these license issues?
comment:25 in reply to: ↑ 14 ; follow-up: ↓ 27 Changed 7 years ago by
Replying to jmantysalo:
I asked from Brendan McKay? "Nauty.h contains copyright with 'exception of sale for profit or application with nontrivial military significance.' Does this apply to whole package?" and he answered: "It applies to all of the nauty files, but for incorporation into Sage you can ignore it.
Can you give the complete contents of this email exchange with McKay?
comment:26 in reply to: ↑ 24 Changed 7 years ago by
Replying to jmantysalo:
Do we have someone who is better to discuss with McKay? about these license issues?
There is not really that much to discuss. Either McKay wants to relicense nauty under GPL v3 or he does not want that. Only in the former case can we include it as standard Sage package.
comment:27 in reply to: ↑ 25 ; follow-up: ↓ 28 Changed 7 years ago by
Replying to jdemeyer:
Replying to jmantysalo:
I asked from Brendan McKay? "Nauty.h contains copyright with 'exception of sale for profit or application with nontrivial military significance.' Does this apply to whole package?" and he answered: "It applies to all of the nauty files, but for incorporation into Sage you can ignore it.
Can you give the complete contents of this email exchange with McKay?
I already gave... (Except a trivial ping-message and a start "Sorry, I forgot to answer.")
comment:28 in reply to: ↑ 27 ; follow-up: ↓ 29 Changed 7 years ago by
The sentence "It applies to all of the nauty files, but for incorporation into Sage you can ignore it." really is the whole answer? :-)
Given that he is OK with Nauty being in Sage and given that people might use Sage commercially or for military applications, this should logically mean that he would agree to license Nauty under the GPL v3. Somebody just needs to ask...
comment:29 in reply to: ↑ 28 Changed 7 years ago by
Replying to jdemeyer:
The sentence "It applies to all of the nauty files, but for incorporation into Sage you can ignore it." really is the whole answer? :-)
Yes.
Given that he is OK with Nauty being in Sage and given that people might use Sage commercially or for military applications, this should logically mean that he would agree to license Nauty under the GPL v3. Somebody just needs to ask...
And what is more: Sage is free, so I can take any part of Sage and use it as a part of some other (free) program that is used to prepare against another shelling of Mainila. Free software can be splitted, not only combined.
I am quite sure that he did not think about that. Not in a way or another.
comment:30 follow-up: ↓ 31 Changed 7 years ago by
- Cc dimpase added
About license: Dima has asked McKay?, who said that it is ok for him, IF Brinkmann do not complain. So we still wait to see if this can be added as a standard package.
comment:31 in reply to: ↑ 30 ; follow-up: ↓ 32 Changed 7 years ago by
Replying to jmantysalo:
About license: Dima has asked McKay?, who said that it is ok for him, IF Brinkmann do not complain. So we still wait to see if this can be added as a standard package.
Jeroen, isn't Brinkmann your colleague at UGent? Could you perhaps buy him a biertje so that he releases his related code under GPL, too?
comment:32 in reply to: ↑ 31 ; follow-up: ↓ 33 Changed 7 years ago by
Replying to dimpase:
Replying to jmantysalo:
About license: Dima has asked McKay?, who said that it is ok for him, IF Brinkmann do not complain. So we still wait to see if this can be added as a standard package.
Jeroen, isn't Brinkmann your colleague at UGent?
Well, he's in a different department, but I could ask him, yes.
comment:33 in reply to: ↑ 32 Changed 7 years ago by
Replying to jdemeyer:
Replying to dimpase:
Replying to jmantysalo:
About license: Dima has asked McKay?, who said that it is ok for him, IF Brinkmann do not complain. So we still wait to see if this can be added as a standard package.
Jeroen, isn't Brinkmann your colleague at UGent?
Well, he's in a different department, but I could ask him, yes.
I forwarded you my latest email to him.
comment:34 Changed 6 years ago by
We can proceed to make posetgen a standard package, see https://groups.google.com/d/msg/sage-devel/VuNMvS9jyH8/fcUhKmraBAAJ
comment:35 Changed 17 months ago by
- Description modified (diff)
- Milestone changed from sage-6.4 to sage-9.4
comment:36 Changed 17 months ago by
Recently active topic on Math Overflow.
comment:37 Changed 10 months ago by
- Milestone changed from sage-9.4 to sage-9.5
comment:38 Changed 5 months ago by
- Milestone changed from sage-9.5 to sage-9.6
comment:39 Changed 7 weeks ago by
- Milestone changed from sage-9.6 to sage-9.7
Brinkmann was kind and send me C-code that he used. However, on sage-devel list Nathann Cohen said that at least Nauty is not available as GPL and can not be directly added to Sage. As an optional package it should be fine.
To glue C code to Sage or to read the paper and make same code in [c|p]ython?