Opened 6 years ago

Closed 6 years ago

# Poset: Add ordinal_product

Reported by: Owned by: jmantysalo major sage-6.5 combinatorics poset ncohen Frédéric Chapoton Nathann Cohen, Jori Mäntysalo N/A 5aced5a (Commits) 5aced5adce233e4506799920dcd9c751b326bd91

### Description (last modified by jmantysalo)

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))
```

### comment:1 Changed 6 years ago by chapoton

• Keywords poset added

Could you please recall the definition here ?

### comment:2 Changed 6 years ago by jmantysalo

• Description modified (diff)

### comment:3 Changed 6 years ago by chapoton

• Authors set to Frédéric Chapoton
• 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 git

• 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 jmantysalo

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 git

• 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 jmantysalo

When making `SEEALSO`-part it is good to also add reference of new function to old ones. I guess that most seealso-references should be bidirectional.

Sorry for forgotting to say this in first message.

### comment:8 Changed 6 years ago by git

• Commit changed from 2ab2d62b69f9ee7a115c4db2bbbab8a8af1e637b to abeef07ddd88246d8564692ff57ff17f62c5eb3f

Branch pushed to git repo; I updated commit sha1. New commits:

 ​abeef07 `trac #17361 cross-references`

### comment:9 Changed 6 years ago by jmantysalo

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 jmantysalo

• 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 ncohen

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 git

• 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 git

• 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 ncohen

(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 git

• 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 ncohen

• 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 ncohen

• Status changed from new to needs_review

### comment:18 Changed 6 years ago by ncohen

• Status changed from needs_review to positive_review

### comment:19 follow-up: ↓ 20 Changed 6 years ago by jmantysalo

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 ncohen

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 half-plan 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 jmantysalo

• Milestone changed from sage-wishlist to sage-6.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 git

• 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 chapoton

• Status changed from needs_work to needs_review

### comment:24 Changed 6 years ago by jmantysalo

• 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 git

• 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 chapoton

• Status changed from needs_work to needs_review

### comment:27 Changed 6 years ago by jmantysalo

• 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, one-element poset and products of chain and antichain.

### comment:28 Changed 6 years ago by vbraun

• Branch changed from u/chapoton/17361 to 5aced5adce233e4506799920dcd9c751b326bd91
• Resolution set to fixed
• Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.