#14110: Speed Up Poset Generation
---------------------------------+------------------------
Reporter: csar | Owner: csar
Type: enhancement | Status: new
Priority: major | Milestone: sage-6.4
Component: combinatorics | Resolution:
Keywords: posets | Merged in:
Authors: | Reviewers:
Report Upstream: N/A | Work issues:
Branch: | Commit:
Dependencies: | Stopgaps:
---------------------------------+------------------------
Comment (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.
--
Ticket URL: <http://trac.sagemath.org/ticket/14110#comment:11>
Sage <http://www.sagemath.org>
Sage: Creating a Viable Open Source Alternative to Magma, Maple, Mathematica,
and MATLAB
--
You received this message because you are subscribed to the Google Groups
"sage-trac" group.
To unsubscribe from this group and stop receiving emails from it, send an email
to [email protected].
To post to this group, send email to [email protected].
Visit this group at http://groups.google.com/group/sage-trac.
For more options, visit https://groups.google.com/d/optout.
