Opened 6 years ago

Closed 6 years ago

#17361 closed enhancement (fixed)

Poset: Add ordinal_product

Reported by: jmantysalo Owned by:
Priority: major Milestone: sage-6.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 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))

Change History (28)

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:

950d901trac #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:

8b9b41dtrac #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:

2ab2d62trac #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:

abeef07trac #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:

c7122b2trac #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:

5686cc3trac #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:

c590471trac #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: 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:

56246c8trac #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:

5aced5atrac #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.