On Thu, Nov 19, 2009 at 08:42:54PM -0600, Jason Grout wrote:
> Tom Boothby wrote:
> > On Thu, Nov 19, 2009 at 4:14 PM, Florent Hivert
> > <florent.hiv...@univ-rouen.fr> wrote:
> >> Hi Jason,
> >>
> >>>> I'd like to generate all partially ordered sets of a given cardinality
> >>>> upto
> >>>> isomorphisms... They are in bijection with aclyclic, transitively reduced
> >>>> directed graphs. Does anyone have an idea how to do that ? I can't
> >>>> manage to
> >>>> get this with nauty.
> >>>
> >>> I'm sure there's a smarter way, but you could generate acyclic directed
> >>> graphs and then transitively reduce them.
> >> Yep ! That's a solution... I'll need then nauty again to remove isomorphic
> >> duplicates. I'll probably go far enough for my problem with this methods
> >> since
> >> the algorithm I want to put behind seems to be vastly exponential in the
> >> size
> >> of the poset. I hope this will not break my conjecture...
> >>
> >> By the way, just to know, can this be achieved in plain sage without nauty
> >> ?
> >
> > Yes, it can. Read the documentation for digraphs().
> >
>
> Using the "augment" and "property" options might also speed up your
> generation quite a bit, as you can control how these things are
> generated (i.e., you can just generate acyclic transitively reduced
> graphs, maybe). Nauty has similar hooks in C too.
That's pretty cool indeed!
sage: def posets(n):
... return list(digraphs(n,
... augment = "edges",
... property = lambda g: g.is_directed_acyclic() and
g.is_transitively_reduced()))
sage: for n in range(20):
print len(list(digraphs(n, augment = "edges", property = lambda g:
g.is_directed_acyclic() and g.is_transitively_reduced())))
sage: [len(posets(n)) for n in range(8)]
[1, 1, 2, 5, 16, 63, 318, 2045]
sage: sloane_find([1, 1, 2, 5, 16, 63, 318, 2045])
Searching Sloane's online database...
[[112,
'Number of partially ordered sets ("posets") with n unlabeled elements.'
sage: %time len(posets(4))
CPU times: user 0.17 s, sys: 0.00 s, total: 0.17 s
Wall time: 0.19 s
sage: %time len(posets(5))
CPU times: user 0.64 s, sys: 0.00 s, total: 0.64 s
Wall time: 0.67 s
sage: %time len(posets(6))
CPU times: user 5.27 s, sys: 0.00 s, total: 5.27 s
Wall time: 5.28 s
sage: %time len(posets(7))
CPU times: user 54.54 s, sys: 0.12 s, total: 54.66 s
Wall time: 54.94 s
sage: %time l = len(posets(8))
CPU times: user 703.65 s, sys: 0.54 s, total: 704.19 s
Wall time: 707.64 s
So, the poset generation would be around: O(number_of_posets_of_size(n) * n^3)
which should be not that far from optimal:
sage: 0.19/16/4^3, 0.64/63/5^3, 5.28/318/6^3, 54.9/2045/7^3, 704.19/16999/8^3
(0.000185, 0.000081, 0.000076, 0.000078, 0.000080)
It would be good to have this example in the digraphs documentation,
and to use this to implement the enumerated set of all posets in the
posets library.
Florent?
Cheers,
Nicolas
--
Nicolas M. Thiéry "Isil" <nthi...@users.sf.net>
http://Nicolas.Thiery.name/
--
To post to this group, send an email to sage-devel@googlegroups.com
To unsubscribe from this group, send an email to
sage-devel-unsubscr...@googlegroups.com
For more options, visit this group at http://groups.google.com/group/sage-devel
URL: http://www.sagemath.org
