Opened 8 years ago

Last modified 5 months ago

#14110 new enhancement

Speed Up Poset Generation

Reported by: csar Owned by: csar
Priority: major Milestone: sage-9.4
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:

Status badges

Description (last modified by chapoton)

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.

  1. D. McKay? and G. Brinkmann, Posets on up to 16 points, Order, 19 (2002) 147-179

https://doi.org/10.1023/A:1016543307592

Attachments (2)

poset_package.zip (88.5 KB) - added by jmantysalo 7 years ago.
File from Brinkmann. Not GPL!
posetgen.spkg (40.0 KB) - added by jmantysalo 6 years ago.

Download all attachments as: .zip

Change History (38)

comment:1 Changed 8 years ago by csar

  • Type changed from PLEASE CHANGE to enhancement

comment:2 Changed 8 years ago by chapoton

  • Description modified (diff)
  • Keywords posets added

comment:3 Changed 8 years ago by jdemeyer

  • Milestone changed from sage-5.11 to sage-5.12

comment:4 Changed 7 years ago by vbraun_spam

  • Milestone changed from sage-6.1 to sage-6.2

comment:5 Changed 7 years ago by vbraun_spam

  • Milestone changed from sage-6.2 to sage-6.3

comment:6 Changed 7 years ago by vbraun_spam

  • Milestone changed from sage-6.3 to sage-6.4

comment:7 Changed 7 years ago by jmantysalo

  • Cc jmantysalo added

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?

comment:8 follow-up: Changed 7 years ago by 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.

comment:9 in reply to: ↑ 8 Changed 7 years ago by jmantysalo

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 7 years ago by jmantysalo

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.

Version 0, edited 7 years ago by jmantysalo (next)

Changed 7 years ago by jmantysalo

File from Brinkmann. Not GPL!

comment:11 Changed 7 years ago by jmantysalo

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: Changed 7 years ago by jmantysalo

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 7 years ago by jmantysalo

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: Changed 7 years ago by 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.

Another thing, somebody using Mac should check if this compiles. And answer my last question.

comment:15 follow-up: Changed 7 years ago by tmonteil

  • 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: Changed 7 years ago by jmantysalo

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: Changed 7 years ago by tmonteil

Note that nauty is already an optional Sage package

True, 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 jmantysalo

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 tmonteil

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 tmonteil

  • 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 6 years ago by jmantysalo

comment:21 Changed 6 years ago by jmantysalo

I changed package file. Hope it works now.

comment:22 Changed 6 years ago by ncohen

Just an update on 15: since then, nauty has become a new-style package (#18425).

comment:23 in reply to: ↑ 14 ; follow-up: Changed 6 years ago by 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.

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: Changed 6 years ago by jmantysalo

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: Changed 6 years ago by 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?

comment:26 in reply to: ↑ 24 Changed 6 years ago by jdemeyer

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: Changed 6 years ago by jmantysalo

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: Changed 6 years ago by 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? :-)

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 6 years ago by jmantysalo

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: Changed 6 years ago by jmantysalo

  • 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: Changed 6 years ago by 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? 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: Changed 6 years ago by 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.

comment:33 in reply to: ↑ 32 Changed 6 years ago by dimpase

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 jmantysalo

We can proceed to make posetgen a standard package, see https://groups.google.com/d/msg/sage-devel/VuNMvS9jyH8/fcUhKmraBAAJ

comment:35 Changed 5 months ago by chapoton

  • Description modified (diff)
  • Milestone changed from sage-6.4 to sage-9.4

comment:36 Changed 5 months ago by slelievre

Note: See TracTickets for help on using tickets.