Opened 4 years ago

Closed 3 years ago

#18511 closed enhancement (fixed)

LatticePoset: add is_sublattice()

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

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 4 years ago by jmantysalo

  • Branch set to u/jmantysalo/latticeposet__add_is_sublattice__

comment:2 follow-up: Changed 4 years ago by jmantysalo

  • Authors set to Jori Mäntysalo
  • Cc chapoton added
  • Commit set to c3e1c19e4e7c8c1a666a755c96bb5a23ea921b1a

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 and other? 2.2 If yes, should I change name from is_sublattice() to has_sublattice()? (Compare to is_subgraph() on generic graphs.)


New commits:

c3e1c19Added a function. Docs missing from Hasse diagram.

comment:3 in reply to: ↑ 2 Changed 4 years ago by ncohen

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 and other? 2.2 If yes, should I change name from is_sublattice() to has_sublattice()? (Compare to is_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 follow-up: Changed 4 years ago by ncohen

ARGGGGGGGGGGGGG. OKay, please merge those two functions into one.

Nathann

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

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 follow-up: Changed 4 years ago by ncohen

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 ; follow-up: Changed 4 years ago by jmantysalo

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 by Lattice.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 ; follow-up: Changed 4 years ago by ncohen

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 4 years ago by jmantysalo

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 4 years ago by ncohen

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 4 years ago by git

  • Commit changed from c3e1c19e4e7c8c1a666a755c96bb5a23ea921b1a to 9f1e2e7cff9151477fe8456cf041d8a5bd32cef6

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

9f1e2e7Now only lists are checked; correction to hasse_diagram.

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

  • 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 4 years ago by jmantysalo

  • Summary changed from LatticePoset: add is_sublattice() to LatticePoset: add has_sublattice()

comment:14 Changed 4 years ago by ncohen

The branch does not merge with the latest beta.

Nathann

comment:15 Changed 4 years ago by git

  • Commit changed from 9f1e2e7cff9151477fe8456cf041d8a5bd32cef6 to c52353a1148a0b59ddf57a76e402144e3bc86ea3

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

c52353aMerge branch 'rebase_git' into rebase_git_18511

comment:16 Changed 4 years ago by jmantysalo

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 4 years ago by darij

  • Branch changed from u/jmantysalo/latticeposet__add_is_sublattice__ to public/ticket/18511
  • Commit changed from c52353a1148a0b59ddf57a76e402144e3bc86ea3 to 0e885593b48db3891a78274e183af013788f1158
  • Milestone changed from sage-wishlist to sage-6.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:

0e88559doc improvements

comment:18 Changed 4 years ago by darij

  • Reviewers changed from Nathan Cohen, Darij Grinberg to Nathann Cohen, Darij Grinberg

comment:19 Changed 4 years ago by git

  • Commit changed from 0e885593b48db3891a78274e183af013788f1158 to a9c24c1d896b85204601d1993b9d5b8b86ebbbf3

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

a9c24c1more doc improvements

comment:20 Changed 4 years ago by jmantysalo

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 follow-up: Changed 4 years ago by ncohen

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 4 years ago by git

  • Commit changed from a9c24c1d896b85204601d1993b9d5b8b86ebbbf3 to 0ef0050b3b959c2115dc9a433d80c62dda905f8f

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

0392776add doctests in lattice has_sublattice method, and make the doctests in hasse-diagram has_sublattice method more direct
0ef0050handling outside elements in lattices.py

comment:23 follow-ups: Changed 4 years ago by darij

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 4 years ago by ncohen

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 ; follow-up: Changed 4 years ago by jmantysalo

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 4 years ago by jmantysalo

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://sphinx-doc.org/latest/ext/example_google.html which says "Do not include the self parameter in the Args section."

comment:27 in reply to: ↑ 25 ; follow-up: Changed 4 years ago by ncohen

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.

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 ; follow-up: Changed 4 years ago by jmantysalo

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 input O_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 ; follow-up: Changed 4 years ago by ncohen

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.

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 4 years ago by jmantysalo

Replying to ncohen:

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.

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 4 years ago by jmantysalo

  • Description modified (diff)
  • Milestone changed from sage-6.8 to sage-6.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 4 years ago by git

  • Commit changed from 0ef0050b3b959c2115dc9a433d80c62dda905f8f to 836e225da2ebe310468f29c8978bb6bb5c49b790

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

836e225Add function is_sublattice().

comment:33 Changed 4 years ago by jmantysalo

This is not ready, as I wait to see how should

L = LatticePoset({1:[2]})
P = Poset(L)
L == P

work.

comment:34 Changed 3 years ago by git

  • Commit changed from 836e225da2ebe310468f29c8978bb6bb5c49b790 to 50bda95dc76e82d9c79436a4a4f61685c27b064e

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

caa52edAdd is_orthocomplemented().
5dbda42Slight optimization.
80805abAdd is_orthocomplemented().
30e03fdRebase for beta1.
7470ca5Typo correction.
6f81728Py3-compliant next() for iterator.
50bda95Add backslash to wedge.

comment:35 Changed 3 years ago by git

  • Commit changed from 50bda95dc76e82d9c79436a4a4f61685c27b064e to 15885519638e632fd96185a61efcf66c91e0010a

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

1588551Add is_sublattice().

comment:36 Changed 3 years ago by git

  • Commit changed from 15885519638e632fd96185a61efcf66c91e0010a to a85965ad988539fc6cb2d477c10f30ac0c6462da

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

030ed7eAdd is_sublattice().
a85965aAdd empty line.

comment:37 Changed 3 years ago by jmantysalo

  • 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 3 years ago by jmantysalo

  • Milestone changed from sage-6.9 to sage-7.4

comment:39 follow-up: Changed 3 years ago by tscrim

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 3 years ago by git

  • Commit changed from a85965ad988539fc6cb2d477c10f30ac0c6462da to f922127be87eb4bf8a9cdc753071c02021f8df39

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

f922127Reviewer comment's.

comment:41 in reply to: ↑ 39 Changed 3 years ago by jmantysalo

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 3 years ago by tscrim

  • 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 3 years ago by vbraun

  • Branch changed from public/ticket/18511 to f922127be87eb4bf8a9cdc753071c02021f8df39
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.