Opened 5 years ago
Closed 4 years ago
#20727 closed defect (fixed)
LatticePoset: about complements
Reported by:  jmantysalo  Owned by:  

Priority:  major  Milestone:  sage7.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)  Commit:  89dbcf480dbe452c0f9dcbde634777b3659c5a8d 
Dependencies:  Stopgaps: 
Description (last modified by )
There is a slight cornercase error:
LatticePoset({1: []}).complements()
will give {1: [1, 1]}
.
Change History (19)
comment:1 Changed 5 years ago by
 Branch set to u/jmantysalo/hasse_complements
comment:2 Changed 5 years ago by
 Cc tscrim added
 Commit set to 2481a494167fa56b15742fd9b507559232517069
 Status changed from new to needs_review
comment:3 Changed 5 years ago by
Just a ping
.
If wanted, I can make a patch that only corrects the corner case in lattices.py
.
comment:4 followup: ↓ 5 Changed 5 years ago by
 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
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 followup: ↓ 7 Changed 5 years ago by
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
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 ofcomplement()
coming fromDigraphs
, 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 sayingsee: complements(), is_relatively_complemented(), etc.
.
True. I guess that #20940 will be last of this serie, so it is propably right place to add seealsolinks. Before that I wait comment from Travis at #20972.
comment:8 Changed 4 years ago by
 Commit changed from 2481a494167fa56b15742fd9b507559232517069 to fcbf57e355d100bd2da269b5ffe474443fa56c6a
Branch pushed to git repo; I updated commit sha1. New commits:
fcbf57e  Add definition of complement.

comment:9 Changed 4 years ago by
 Milestone changed from sage7.3 to sage7.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 followup: ↓ 12 Changed 4 years ago by
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 4 years ago by
For example seriesparallel 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 ; followup: ↓ 15 Changed 4 years ago by
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, ..., n1)
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 4 years ago by
 Status changed from needs_review to positive_review
comment:14 Changed 4 years ago by
 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 4 years ago by
Replying to tscrim:
You're forgetting the fact that by working in
HasseDiagram
, you can assume the vertices are(0, 1, ..., n1)
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 ofPoset
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 4 years ago by
 Commit changed from fcbf57e355d100bd2da269b5ffe474443fa56c6a to 89dbcf480dbe452c0f9dcbde634777b3659c5a8d
Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:
89dbcf4  Corner case for complements().

comment:17 Changed 4 years ago by
 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 4 years ago by
 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 4 years ago by
 Branch changed from u/jmantysalo/hasse_complements to 89dbcf480dbe452c0f9dcbde634777b3659c5a8d
 Resolution set to fixed
 Status changed from positive_review to closed
New commits:
Cornercase for complements and more.