Opened 6 years ago
Closed 6 years ago
#17361 closed enhancement (fixed)
Poset: Add ordinal_product
Reported by:  jmantysalo  Owned by:  

Priority:  major  Milestone:  sage6.5 
Component:  combinatorics  Keywords:  poset 
Cc:  ncohen  Merged in:  
Authors:  Frédéric Chapoton  Reviewers:  Nathann Cohen, Jori Mäntysalo 
Report Upstream:  N/A  Work issues:  
Branch:  5aced5a (Commits)  Commit:  5aced5adce233e4506799920dcd9c751b326bd91 
Dependencies:  Stopgaps: 
Description (last modified by )
Add the ordinal product (Enumerative combinatorics, p. 284) function of posets. In ordinal product of P
and Q
we have (p,q) <= (p',q')
if either p <= p'
or p == p'
and q <= q'
. This is easy one, just needs docstring etc. Direct example code:
def ordinal_product(P, Q): # Note: P*Q is not isomorphic to Q*P elms=[(s,t) for s in P for t in Q] rels_a=[((s,t),(s, t_)) for s in P for t in Q for t_ in Q if Q.lt(t, t_)] rels_b=[((s,t),(s_, t_)) for s in P for t in Q for s_ in P for t_ in Q if P.lt(s, s_)] return Poset((elms, rels_a+rels_b))
Change History (28)
comment:1 Changed 6 years ago by
 Keywords poset added
comment:2 Changed 6 years ago by
 Description modified (diff)
comment:3 Changed 6 years ago by
 Branch set to u/chapoton/17361
 Commit set to 950d9017287acc28bb240eea2679c97dbccf5843
Here is a first proposal, that still needs some polishing.
New commits:
950d901  trac #17361 first tentative to implement ordinal_product of posets

comment:4 Changed 6 years ago by
 Commit changed from 950d9017287acc28bb240eea2679c97dbccf5843 to 8b9b41de365d628074b17687490a7a510bb7a317
Branch pushed to git repo; I updated commit sha1. New commits:
8b9b41d  trac #17361 fixup commit

comment:5 Changed 6 years ago by
On #17129 I was told that strings for ValueError
should be incomplete sentences.
After #17053 it seems logical to have pairs
as a default value, not integers
.
If I am not mistaken, ordinal product of lattices is a lattice; compare to for example #17142.
I have been told that all input should be documented, i.e. also other
.
comment:6 Changed 6 years ago by
 Commit changed from 8b9b41de365d628074b17687490a7a510bb7a317 to 2ab2d62b69f9ee7a115c4db2bbbab8a8af1e637b
Branch pushed to git repo; I updated commit sha1. New commits:
2ab2d62  trac #17361 changes according to some of the reviewer's comments

comment:7 Changed 6 years ago by
When making SEEALSO
part it is good to also add reference of new function to old ones. I guess that most seealsoreferences should be bidirectional.
Sorry for forgotting to say this in first message.
comment:8 Changed 6 years ago by
 Commit changed from 2ab2d62b69f9ee7a115c4db2bbbab8a8af1e637b to abeef07ddd88246d8564692ff57ff17f62c5eb3f
Branch pushed to git repo; I updated commit sha1. New commits:
abeef07  trac #17361 crossreferences

comment:9 Changed 6 years ago by
Aarghs, we already have the function! It is lexicographic_product
on graphs, and I guess it must just be mapped to function of poset. (Like minimal_elements
on poset is actually sources
on digraphs.)
comment:10 Changed 6 years ago by
 Cc ncohen added
I cc Nathann to this, because he knows digraphs. I tested with product of BooleanLattice(5)
with itself. It took 14 seconds with code of this ticket, whereas lexicographic_product
took 18 seconds. This is interesting. Nathann has just corrected a slowdown on generating digraph from dict, maybe this is related?
comment:11 Changed 6 years ago by
Hello !
Well, first for the poset thing you can be MUCH more efficient. In Poset.ordinal_sum
you add only edges between the top elements of one and the bottom elements of the other. Why don't you do that here too ?
(please, cache the top/bottom elements of each poset).
Also, for s in self for s2 in self.lower_covers(s)
should probably be for s,s in cover_relations_iterator
.
For the graph code, it could be improved by replacing the calls to add_edge
by one call to add_edges
. The difference is that add_edge
supports many kind of inputs (a pair, or two points, or three points) and that add_edge
checks it at every call (while add_edges
does it once).
Nathann
comment:12 Changed 6 years ago by
 Commit changed from abeef07ddd88246d8564692ff57ff17f62c5eb3f to c7122b214135bbd7c77d840841753c94a05a9dac
Branch pushed to git repo; I updated commit sha1. New commits:
c7122b2  trac #17361 using cover iterator

comment:13 Changed 6 years ago by
 Commit changed from c7122b214135bbd7c77d840841753c94a05a9dac to 5686cc39d5e8ac58223b40f560de0d8812b623cb
Branch pushed to git repo; I updated commit sha1. New commits:
5686cc3  trac #17361 correct the failing doctest

comment:14 Changed 6 years ago by
(you can also use the min_elements/max_elements trick on the add_edge call which contains for t in other for t2 in other
. That is where it will save the most)
comment:15 Changed 6 years ago by
 Commit changed from 5686cc39d5e8ac58223b40f560de0d8812b623cb to c59047103bc9cf22d2526c7ae146492fec92b698
Branch pushed to git repo; I updated commit sha1. New commits:
c590471  trac #17361 using max and min elements for a better algorithm

comment:16 Changed 6 years ago by
 Reviewers set to Nathann Cohen
Hello !
Well, this patch looks good to me, and all tests pass. Jory: I tested the product of two BooleanLattice(5)
and it takes 2.5 seconds. It is still a lot, but better than 17s :/
sage: %timeit p.ordinal_product(p) 1 loops, best of 3: 2.46 s per loop
I do not understand much what the profiling says, though. It seems that 1.3s is used by the 'has_edge' function (Why ???? O_o
)
The code of transitive_reduction
can be rewritten more efficiently, though. Actually, this is a very important point since this function is called every time a poset is created, to build its hasse diagram.
Sorry guys, but I have to give up for tonight. 1am, and I will need my brain tomorrow again. Good night, and thanks for the patch !
Nathann
comment:17 Changed 6 years ago by
 Status changed from new to needs_review
comment:18 Changed 6 years ago by
 Status changed from needs_review to positive_review
comment:19 followup: ↓ 20 Changed 6 years ago by
Code seems to be clear. Just to clarify to Nathann: I reported this one, but have not written any of the code. So thanks goes to Frédéric!
I think that there is no need to have sorted
on examples. They are kind of automatically sorted, when are all same type. But this is of course a minor thing.
comment:20 in reply to: ↑ 19 Changed 6 years ago by
Yooooooo !
Code seems to be clear. Just to clarify to Nathann: I reported this one, but have not written any of the code. So thanks goes to Frédéric!
Right right, all the commits are his !
By the way, Jakob Kröker just sent me an email about Posets and I told him that you had a halfplan of adding some doc there.
God, I should be sleeping T_T
I think that there is no need to have
sorted
on examples. They are kind of automatically sorted, when are all same type. But this is of course a minor thing.
I don't know. Graphs+vertex labels mean dictionary somewhere, so I do not trust anything ^^;
Nathann
comment:21 Changed 6 years ago by
 Milestone changed from sagewishlist to sage6.5
 Status changed from positive_review to needs_work
Still one thing: Could this return a lattice instead of only poset when both this
and other
are lattices?
If not, that is OK: in that case, just mark this back to positive_review again.
comment:22 Changed 6 years ago by
 Commit changed from c59047103bc9cf22d2526c7ae146492fec92b698 to 56246c8f3abb1e66a2df1452f6016d8b288f37d7
Branch pushed to git repo; I updated commit sha1. New commits:
56246c8  trac #17361 ordinal_product of lattices as lattice

comment:23 Changed 6 years ago by
 Status changed from needs_work to needs_review
comment:24 Changed 6 years ago by
 Status changed from needs_review to needs_work
Poset({0:[1,2]})
is a meet semilattice, but it's ordinal product with itself is not a meet semilattice. (resp. for join semilattice). Hence we have only two options: both arguments are lattices and so is return type also lattice, or else return type is "only" poset.
comment:25 Changed 6 years ago by
 Commit changed from 56246c8f3abb1e66a2df1452f6016d8b288f37d7 to 5aced5adce233e4506799920dcd9c751b326bd91
Branch pushed to git repo; I updated commit sha1. New commits:
5aced5a  trac #17361 not for semilattices, only for lattices

comment:26 Changed 6 years ago by
 Status changed from needs_work to needs_review
comment:27 Changed 6 years ago by
 Reviewers changed from Nathann Cohen to Nathann Cohen, Jori Mäntysalo
 Status changed from needs_review to positive_review
Looks good. I tested for example empty poset, oneelement poset and products of chain and antichain.
comment:28 Changed 6 years ago by
 Branch changed from u/chapoton/17361 to 5aced5adce233e4506799920dcd9c751b326bd91
 Resolution set to fixed
 Status changed from positive_review to closed
Could you please recall the definition here ?