Opened 5 years ago
Closed 4 years ago
#18511 closed enhancement (fixed)
LatticePoset: add is_sublattice()
Reported by:  jmantysalo  Owned by:  

Priority:  major  Milestone:  sage7.4 
Component:  combinatorics  Keywords:  
Cc:  chapoton  Merged in:  
Authors:  Jori Mäntysalo  Reviewers:  Nathann Cohen, Darij Grinberg, Travis Scrimshaw 
Report Upstream:  N/A  Work issues:  
Branch:  f922127 (Commits)  Commit:  f922127be87eb4bf8a9cdc753071c02021f8df39 
Dependencies:  Stopgaps: 
Description (last modified by )
Add function to check if a given lattice is a sublattice of the lattice. There should be nothing complicated with this.
Change History (43)
comment:1 Changed 5 years ago by
 Branch set to u/jmantysalo/latticeposet__add_is_sublattice__
comment:2 followup: ↓ 3 Changed 5 years ago by
 Cc chapoton added
 Commit set to c3e1c19e4e7c8c1a666a755c96bb5a23ea921b1a
comment:3 in reply to: ↑ 2 Changed 5 years ago by
Yo,
I would like to get some comments about this. 1) Should it be at all possible to check if given list of elements form a sublattice of the lattice? 2.1) If not, should I change the order of
self
andother
? 2.2 If yes, should I change name fromis_sublattice()
tohas_sublattice()
? (Compare tois_subgraph()
on generic graphs.)
the way it is implemented, your function works for both. And I do not personally mind if is_sublattice
also works on lists.
On the other hand, with the current implementation the antichain on 5 elements is a sublattice of the chain on 5 elements.
Nathann
comment:4 followup: ↓ 5 Changed 5 years ago by
ARGGGGGGGGGGGGG. OKay, please merge those two functions into one.
Nathann
comment:5 in reply to: ↑ 4 Changed 5 years ago by
Replying to ncohen:
ARGGGGGGGGGGGGG. OKay, please merge those two functions into one.
This and sublattice()
? Why? For example for sets we have a function to get subsets and another checking if a set is a subset of another set.
comment:6 followup: ↓ 7 Changed 5 years ago by
NOnono. I mean the hasse_diagram.is_sublattice
which is called by Lattice.is_sublattice
but does not check that 'other' is a subposet of self.
comment:7 in reply to: ↑ 6 ; followup: ↓ 8 Changed 5 years ago by
Replying to ncohen:
the way it is implemented, your function works for both. And I do not personally mind if
is_sublattice
also works on lists.
OK. How about the name of the function?
On the other hand, with the current implementation the antichain on 5 elements is a sublattice of the chain on 5 elements.
??
sage: L=Posets.ChainPoset(5) sage: M=Posets.AntichainPoset(5) sage: L.is_sublattice(M) False
Replying to ncohen:
I mean the
hasse_diagram.is_sublattice
which is called byLattice.is_sublattice
but does not check that 'other' is a subposet of self.
But that is checked on lattices.py
. Isn't it slower to access elements of _hasse_diagram on a loop from another file?
comment:8 in reply to: ↑ 7 ; followup: ↓ 12 Changed 5 years ago by
Yo !
OK. How about the name of the function?
I'd say that it is fine. You think it's wrong in some way?
On the other hand, with the current implementation the antichain on 5 elements is a sublattice of the chain on 5 elements.
After that comment I added a big 'ARGGGGGGG' which indicated that for the tenth time I had only read the code of the undocumented is_sublattice
function from hasse_diagram.py
. Could you please merge the two? The second function, by itself, is incorrect.
But that is checked on
lattices.py
. Isn't it slower to access elements of _hasse_diagram on a loop from another file?
I do not see why. To say it differently, I do not think that Python is smart enough to optimize anything due to the fact that everything is in the same file :P
Nathann
comment:9 Changed 5 years ago by
About the name: If A
and B
are graphs, then A.is_subgraph(B)
means "A is a subgraph of B". If they are lattices, then A.is_sublattice(B)
means "B is a sublattice of A". So it is somewhat surprising difference. But of course we can't add is_sublattice()
to all iterables.
comment:10 Changed 5 years ago by
Well, it's up to you. For as long as B
can be a Lattice object, I'd say that we are fine.
Nathann
comment:11 Changed 5 years ago by
 Commit changed from c3e1c19e4e7c8c1a666a755c96bb5a23ea921b1a to 9f1e2e7cff9151477fe8456cf041d8a5bd32cef6
Branch pushed to git repo; I updated commit sha1. New commits:
9f1e2e7  Now only lists are checked; correction to hasse_diagram.

comment:12 in reply to: ↑ 8 Changed 5 years ago by
 Status changed from new to needs_review
Replying to ncohen:
OK. How about the name of the function?
I'd say that it is fine. You think it's wrong in some way?
Semantics are wrong if A.is_sublattice(B) means that B is a sublattice of A. Changed to has_sublattice
. I also removed possibility to check of being a really sublattice, i.e. input is only assumed to be a list or like.
Could you please merge the two? The second function, by itself, is incorrect.
I corrected the (stupid) bug in hasse_diagram.
If I constantly call meet()
it will slow down computation. If I directly reference to _meet
, I'll break encapsulation. Then for example changing hasse_diagram to use list of lists instead of matrix will break the function.
comment:13 Changed 5 years ago by
 Summary changed from LatticePoset: add is_sublattice() to LatticePoset: add has_sublattice()
comment:14 Changed 5 years ago by
The branch does not merge with the latest beta.
Nathann
comment:15 Changed 5 years ago by
 Commit changed from 9f1e2e7cff9151477fe8456cf041d8a5bd32cef6 to c52353a1148a0b59ddf57a76e402144e3bc86ea3
Branch pushed to git repo; I updated commit sha1. New commits:
c52353a  Merge branch 'rebase_git' into rebase_git_18511

comment:16 Changed 5 years ago by
Now it should work again. It was sublattice()
at the end of file that made a conflict with this is_sublattice()
also added to end of file.
comment:17 Changed 5 years ago by
 Branch changed from u/jmantysalo/latticeposet__add_is_sublattice__ to public/ticket/18511
 Commit changed from c52353a1148a0b59ddf57a76e402144e3bc86ea3 to 0e885593b48db3891a78274e183af013788f1158
 Milestone changed from sagewishlist to sage6.8
 Reviewers set to Nathan Cohen, Darij Grinberg
Uploading my review patch. If you're fine with it, feel free to mark as pos_rev.
New commits:
0e88559  doc improvements

comment:18 Changed 5 years ago by
 Reviewers changed from Nathan Cohen, Darij Grinberg to Nathann Cohen, Darij Grinberg
comment:19 Changed 5 years ago by
 Commit changed from 0e885593b48db3891a78274e183af013788f1158 to a9c24c1d896b85204601d1993b9d5b8b86ebbbf3
Branch pushed to git repo; I updated commit sha1. New commits:
a9c24c1  more doc improvements

comment:20 Changed 5 years ago by
There has been discussion about not using self
in docstrings. For example "  of the lattice
self
." should be just "  of the lattice." That's because we don't expect all users to know about python.
comment:21 followup: ↓ 25 Changed 5 years ago by
Hello !
Could you add an example when the 'lattice' is given as a Lattice
object? Logically, it could even be the first kind of examples you give, and you could then add that "it also works when 'other' is any iterable'".
Also, it seems that the code does not work as expected when 'other' contains points which are not in self
. That's a trivial 'no', but it should not be an exception.
Nathann
comment:22 Changed 5 years ago by
 Commit changed from a9c24c1d896b85204601d1993b9d5b8b86ebbbf3 to 0ef0050b3b959c2115dc9a433d80c62dda905f8f
comment:23 followups: ↓ 24 ↓ 26 Changed 5 years ago by
Nathann: done and done, although I'm not sure if I've done it the way you've liked (please check).
Jori: I don't believe in this being of any help to users. Pronouns like "this" become ambiguous very quickly when several objects are involved. Here we have two lattices floating around and it's more or less clear which one is meant, but I'd say that self
makes it clearer. And when the situation is more complicated, it is downright impossible to circumlocute self
. And the ugly truth is, users who don't know about Python are screwed when they try to use our poset infrastructure anyway...
comment:24 in reply to: ↑ 23 Changed 5 years ago by
Nathann: done and done, although I'm not sure if I've done it the way you've liked (please check).
Right right. Thanks for adding this warning in HasseDiagram.is_has_sublattice
.
Jori also mentionned that there was now an index of Lattice functions. In this case, this method should be added to it.
Nathann
comment:25 in reply to: ↑ 21 ; followup: ↓ 27 Changed 5 years ago by
Replying to ncohen:
Also, it seems that the code does not work as expected when 'other' contains points which are not in
self
. That's a trivial 'no', but it should not be an exception.
I guess that it is mostly an error from the user if he/she ask if {1,2}
is a sublattice of a lattice containing a
, b
and a
. So raising an exceptions sounds better.
But totally another thing is a list vs. a lattice as a parameter. They feels two different things.
comment:26 in reply to: ↑ 23 Changed 5 years ago by
Replying to darij:
Jori: I don't believe in this being of any help to users. Pronouns like "this" become ambiguous very quickly when several objects are involved.
Sometimes, maybe. It I think it's good to at least try. I a recent discussion vbraun referred to
http://sphinxdoc.org/latest/ext/example_google.html which says "Do not include the self
parameter in the Args
section."
comment:27 in reply to: ↑ 25 ; followup: ↓ 28 Changed 5 years ago by
I guess that it is mostly an error from the user if he/she ask if
{1,2}
is a sublattice of a lattice containinga
,b
anda
. So raising an exceptions sounds better.
That's an inconsistency between graphs and posets
sage: p = Poset() sage: p.le(1,3) ... ValueError: element (=1) not in poset sage: g = Graph() sage: g.has_edge(1,3) False
Soooooo okay for an exception!
But totally another thing is a list vs. a lattice as a parameter. They feels two different things.
Well, a Lattice
is an iterable container of vertices, isn't it? And you just can't have a .has_sublattice(X)
function that does not accept a lattice as input O_o
Nathann
comment:28 in reply to: ↑ 27 ; followup: ↓ 29 Changed 5 years ago by
Replying to ncohen:
That's an inconsistency between graphs and posets
Duh.
Well, a
Lattice
is an iterable container of vertices, isn't it? And you just can't have a.has_sublattice(X)
function that does not accept a lattice as inputO_o
But it would mean that after L1=LatticePoset({1:[2]}); L2=L2.dual()
we would have L2
not a subposet of L1 but L1.has_sublattice(L2)
would return True
.
comment:29 in reply to: ↑ 28 ; followup: ↓ 30 Changed 5 years ago by
But it would mean that after
L1=LatticePoset({1:[2]}); L2=L2.dual()
we would haveL2
not a subposet of L1 butL1.has_sublattice(L2)
would returnTrue
.
Right, right. And returning True
is precisely what your branch does:
sage: L1=LatticePoset({1:[2]}) sage: L2=L1.dual() sage: L1.has_sublattice(L2) True
Nathann
comment:30 in reply to: ↑ 29 Changed 5 years ago by
Replying to ncohen:
But it would mean that after
L1=LatticePoset({1:[2]}); L2=L2.dual()
we would haveL2
not a subposet of L1 butL1.has_sublattice(L2)
would returnTrue
.Right, right. And returning
True
is precisely what your branch does:
True. Hence my branch needs correcting.
I think that this relates also with sublattice()
and random_maximal_sublattice()
(see #18562). Should there be "public" functions on lattices.py
returning lists? This would be kind of optimization for some computations. Other way is to have them on hasse_diagram.py
, so that advanced user might use them directly.
comment:31 Changed 5 years ago by
 Description modified (diff)
 Milestone changed from sage6.8 to sage6.9
 Status changed from needs_review to needs_work
 Summary changed from LatticePoset: add has_sublattice() to LatticePoset: add is_sublattice()
Returning to this one... We have is_subgraph
and there is is_subposet
on #15875 waiting for review. So I guess this should be also is_sublattice()
.
On the other hand, then testing if a list l
of elements of L
is closed under meet and join must be done like LatticePoset(L.subposet(l)).is_sublattice(L)
. But maybe we can live with it.
comment:32 Changed 5 years ago by
 Commit changed from 0ef0050b3b959c2115dc9a433d80c62dda905f8f to 836e225da2ebe310468f29c8978bb6bb5c49b790
Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:
836e225  Add function is_sublattice().

comment:33 Changed 5 years ago by
This is not ready, as I wait to see how should
L = LatticePoset({1:[2]}) P = Poset(L) L == P
work.
comment:34 Changed 4 years ago by
 Commit changed from 836e225da2ebe310468f29c8978bb6bb5c49b790 to 50bda95dc76e82d9c79436a4a4f61685c27b064e
Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:
caa52ed  Add is_orthocomplemented().

5dbda42  Slight optimization.

80805ab  Add is_orthocomplemented().

30e03fd  Rebase for beta1.

7470ca5  Typo correction.

6f81728  Py3compliant next() for iterator.

50bda95  Add backslash to wedge.

comment:35 Changed 4 years ago by
 Commit changed from 50bda95dc76e82d9c79436a4a4f61685c27b064e to 15885519638e632fd96185a61efcf66c91e0010a
Branch pushed to git repo; I updated commit sha1. New commits:
1588551  Add is_sublattice().

comment:36 Changed 4 years ago by
 Commit changed from 15885519638e632fd96185a61efcf66c91e0010a to a85965ad988539fc6cb2d477c10f30ac0c6462da
comment:37 Changed 4 years ago by
 Status changed from needs_work to needs_review
Had some errors with git, but now this old ticket should be ready for (easy) review.
comment:38 Changed 4 years ago by
 Milestone changed from sage6.9 to sage7.4
comment:39 followup: ↓ 41 Changed 4 years ago by
Could you add a test for when other
is not a lattice? I'm slightly worried about
if not hasattr(other, 'meet') or not hasattr(other, 'join'): raise TypeError('other is not a lattice')
Somewhat independent, I think it would be better to do something like:
try: M, J = other.meet, other.join except (AttributeError): raise TypeError('other is not a lattice')
which is more Pythonic and easily extends if meet
and join
end up raising other errors at some point.
comment:40 Changed 4 years ago by
 Commit changed from a85965ad988539fc6cb2d477c10f30ac0c6462da to f922127be87eb4bf8a9cdc753071c02021f8df39
Branch pushed to git repo; I updated commit sha1. New commits:
f922127  Reviewer comment's.

comment:41 in reply to: ↑ 39 Changed 4 years ago by
Replying to tscrim:
Could you add a test for when
other
is not a lattice? I'm slightly worried about 
Done this.
comment:42 Changed 4 years ago by
 Reviewers changed from Nathann Cohen, Darij Grinberg to Nathann Cohen, Darij Grinberg, Travis Scrimshaw
 Status changed from needs_review to positive_review
comment:43 Changed 4 years ago by
 Branch changed from public/ticket/18511 to f922127be87eb4bf8a9cdc753071c02021f8df39
 Resolution set to fixed
 Status changed from positive_review to closed
I would like to get some comments about this. 1) Should it be at all possible to check if given list of elements form a sublattice of the lattice? 2.1) If not, should I change the order of
self
andother
? 2.2 If yes, should I change name fromis_sublattice()
tohas_sublattice()
? (Compare tois_subgraph()
on generic graphs.)New commits:
Added a function. Docs missing from Hasse diagram.