LatticePoset: about complements

[jm58660]

There is a slight corner-case -error:

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

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

CC: @tscrim

Component: combinatorics

Author: Jori Mäntysalo

Branch/Commit: 89dbcf4

Reviewer: Travis Scrimshaw, Frédéric Chapoton

Issue created by migration from https://trac.sagemath.org/ticket/20727

[jm58660]

Branch: u/jmantysalo/hasse_complements

[jm58660]

Commit: 2481a49

[jm58660]

New commits:

2481a49

Corner-case for complements and more.

[jm58660]

comment:3

Just a ping.

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

[tscrim]

comment:4

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.

[tscrim]

Reviewer: Travis Scrimshaw

[jm58660]

comment:5

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.

[kevindilks]

comment:6

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..

[jm58660]

comment:7

First, thanks for reviews!

Replying to @kevindilks:

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.

[sagetrac-git]

Changed commit from 2481a49 to fcbf57e

[sagetrac-git]

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

fcbf57e

Add definition of complement.

[jm58660]

comment:9

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.

[kevindilks]

comment:10

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.

[jm58660]

comment:11

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.

[tscrim]

comment:12

Replying to @kevindilks:

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.

[tscrim]

comment:14

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

[jm58660]

comment:15

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.

[sagetrac-git]

Changed commit from fcbf57e to 89dbcf4

[sagetrac-git]

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

89dbcf4

Corner case for complements().

[jm58660]

comment:17

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.

[fchapoton]

comment:18

ok, looks good to me

[fchapoton]

Changed reviewer from Travis Scrimshaw to Travis Scrimshaw, Frédéric Chapoton

[vbraun]

Changed branch from u/jmantysalo/hasse_complements to 89dbcf4