Opened 5 years ago

Closed 5 years ago

#20727 closed defect (fixed)

LatticePoset: about complements

Reported by: jmantysalo Owned by:
Priority: major Milestone: sage-7.4
Component: combinatorics Keywords:
Cc: tscrim Merged in:
Authors: Jori Mäntysalo Reviewers: Travis Scrimshaw, Frédéric Chapoton
Report Upstream: N/A Work issues:
Branch: 89dbcf4 (Commits, GitHub, GitLab) Commit: 89dbcf480dbe452c0f9dcbde634777b3659c5a8d
Dependencies: Stopgaps:

Status badges

Description (last modified by jmantysalo)

There is a slight corner-case -error:

LatticePoset({1: []}).complements()

will give {1: [1, 1]}.

Change History (19)

comment:1 Changed 5 years ago by jmantysalo

  • Branch set to u/jmantysalo/hasse_complements

comment:2 Changed 5 years ago by jmantysalo

  • Cc tscrim added
  • Commit set to 2481a494167fa56b15742fd9b507559232517069
  • Status changed from new to needs_review

New commits:

2481a49Corner-case for complements and more.

comment:3 Changed 5 years ago by jmantysalo

Just a ping.

If wanted, I can make a patch that only corrects the corner case in lattices.py.

comment:4 follow-up: Changed 5 years ago by tscrim

  • Reviewers set to Travis Scrimshaw

This is essentially a positive review, but I don't know the definition of the complements of elements in a poset. I think it would be good to give this.

comment:5 in reply to: ↑ 4 Changed 5 years ago by jmantysalo

Replying to tscrim:

This is essentially a positive review, but I don't know the definition of the complements of elements in a poset. I think it would be good to give this.

(I guess you mean lattice and not poset, even if it is easy to extend the definition to every bounded poset.)

It is said in lattices.py at function complements() already: Elements x and y are complements if their meet and join are respectively the bottom and the top element of the lattice.

In how many places should it be said? In hasse_diagram.py? In is_complemented(), is_relatively_complemented(), and maybe later in is_sectionally_complemented()? This is a real question, and I can see arguments for both directions.

comment:6 follow-up: Changed 5 years ago by kdilks

I think it definitely needs to be defined in hasse_diagram.py, to distinguish between the inherited method of complement() coming from Digraphs, which is entirely different.

For the other ones, I would include a line at the end of each linking to similar/relevant methods (ie, is_complemented() would have a line at the end saying see: complements(), is_relatively_complemented(), etc..

comment:7 in reply to: ↑ 6 Changed 5 years ago by jmantysalo

First, thanks for reviews!

Replying to kdilks:

I think it definitely needs to be defined in hasse_diagram.py, to distinguish between the inherited method of complement() coming from Digraphs, which is entirely different.

This patch will do that. Althought I must admit that now lattices.py copies code from hasse_diagram.py, and that is not needed.

For the other ones, I would include a line at the end of each linking to similar/relevant methods (ie, is_complemented() would have a line at the end saying see: complements(), is_relatively_complemented(), etc..

True. I guess that #20940 will be last of this serie, so it is propably right place to add seealso-links. Before that I wait comment from Travis at #20972.

comment:8 Changed 5 years ago by git

  • Commit changed from 2481a494167fa56b15742fd9b507559232517069 to fcbf57e355d100bd2da269b5ffe474443fa56c6a

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

fcbf57eAdd definition of complement.

comment:9 Changed 5 years ago by jmantysalo

  • Milestone changed from sage-7.3 to sage-7.4

OK, I added the definition of complement directly to this function in hasse_diagram.py.

It feels good design to have "internals" in hasse_diagram.py and have "interface" at posets.py and lattices.py. But it means that some definitions and tests must be written twise, maybe with collisions (definitions of graded vs. ranked). Also some functions at hasse_diagram.py are only meaningfull for lattices.

Now we have certificate-option in is_relatively_complemented() and is_sectionally_complemented(). I think we should add the same to is_complemented(). But that's a task for another ticket.

comment:10 follow-up: Changed 5 years ago by kdilks

What makes you think it's good design? It seems like poor design to have the code for a single function spread across different files. If somebody is working with a poset/lattice and wants to figure out what this function is doing, instead of ?? giving them the code for the algorithm, they get the interface, and they have to try and hunt down the actual internals.

comment:11 Changed 5 years ago by jmantysalo

For example series-parallel decomposition should be doable without temporary posets, i.e. using connected_components() and vertical_summands() in Hasse diagram. Partly the problem is UniqueRepresentation, which means that every poset is saved to memory, and takes more time to create. And if we make a code to generate all lattices of given type (see #20516) we need test functions that does not need poset generation.

But even having all functions at posets.py and lattices.py would be simpler than current system where we internal code splitted without any logic.

comment:12 in reply to: ↑ 10 ; follow-up: Changed 5 years ago by tscrim

Replying to kdilks:

What makes you think it's good design? It seems like poor design to have the code for a single function spread across different files. If somebody is working with a poset/lattice and wants to figure out what this function is doing, instead of ?? giving them the code for the algorithm, they get the interface, and they have to try and hunt down the actual internals.

You're forgetting the fact that by working in HasseDiagram, you can assume the vertices are (0, 1, ..., n-1) and that is a linear extension. I agree that we loose a small bit of clarity (and an extra Python function call) for the indirection, but we often gain much more speed and code simplicity by utilizing these assumptions. One way you can think of Poset is that it adds the extra layer of the element labels.

I think we can remove all references to the deprecation because this function is no longer broken AFAIK.

comment:13 Changed 5 years ago by tscrim

  • Status changed from needs_review to positive_review

comment:14 Changed 5 years ago by tscrim

  • Status changed from positive_review to needs_work

Whoops, that's right, I wanted to the comment about the deprecation removed.

comment:15 in reply to: ↑ 12 Changed 5 years ago by jmantysalo

Replying to tscrim:

You're forgetting the fact that by working in HasseDiagram, you can assume the vertices are (0, 1, ..., n-1) and that is a linear extension. I agree that we loose a small bit of clarity (and an extra Python function call) for the indirection, but we often gain much more speed and code simplicity by utilizing these assumptions. One way you can think of Poset is that it adds the extra layer of the element labels.

But we could have it all in one file, without hasse_diagram.py. But OTOH this design is quite clear to me. Also I suppose that everything can be changed in that file, as long as "interfaces", i.e. mostly posets.py and lattices.py stays.

I think we can remove all references to the deprecation because this function is no longer broken AFAIK.

OK, I can remove them.

comment:16 Changed 5 years ago by git

  • Commit changed from fcbf57e355d100bd2da269b5ffe474443fa56c6a to 89dbcf480dbe452c0f9dcbde634777b3659c5a8d

Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:

89dbcf4Corner case for complements().

comment:17 Changed 5 years ago by jmantysalo

  • Description modified (diff)
  • Status changed from needs_work to needs_review

Hmm... There were no deprecations left in my code.

But anyway, I guess this can be thinked later. I changed this patch to only correct the corner case error and added tests for that.

comment:18 Changed 5 years ago by chapoton

  • Reviewers changed from Travis Scrimshaw to Travis Scrimshaw, Frédéric Chapoton
  • Status changed from needs_review to positive_review

ok, looks good to me

comment:19 Changed 5 years ago by vbraun

  • Branch changed from u/jmantysalo/hasse_complements to 89dbcf480dbe452c0f9dcbde634777b3659c5a8d
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.