Opened 7 months ago
Closed 5 months ago
#31725 closed enhancement (fixed)
Implement meet, join, etc. methods for posets
Reported by:  yzh  Owned by:  

Priority:  major  Milestone:  sage9.4 
Component:  combinatorics  Keywords:  poset, hasse_diagram 
Cc:  mkoeppe, chapoton, tscrim, slelievre  Merged in:  
Authors:  Yuan Zhou  Reviewers:  Travis Scrimshaw 
Report Upstream:  N/A  Work issues:  
Branch:  a19697f (Commits, GitHub, GitLab)  Commit:  a19697ff97092b9bd17bd4e01920a6cfa90b8d95 
Dependencies:  Stopgaps: 
Description (last modified by )
FinitePoset.meet(x, y)
computes the meet of two elements x
, y
in the poset, returning None
if the meet doesn't exist.
Similar for FinitePoset.join(x, y)
.
Currently, FinitePoset._hasse_diagram
has @lazy_attribute
_meet
(resp. _join
) and method meet_matrix
(resp. join_matrix
). However, they don't compute the matrix but raise an Error if the poset is not a meet/joinsemilattice.
sage: from sage.combinat.posets.hasse_diagram import HasseDiagram sage: h = HasseDiagram({0:[2], 1:[2,3], 2:[4], 3:[4], 4:[]}) sage: h._meet Traceback (most recent call last) ... ValueError: not a meetsemilattice: no bottom element
We propose to change HasseDiagram._meet
(resp. _join
), so that the (x,y)
entry of the matrix is 1
if the meet of x
and y
doesn't exist, instead of raising an Error. Defer the checks to HasseDiagram.meet_matrix()
(resp. join_matrix
).
For the poset h
above, we expect:
h._meet[2,3] 1 h._meet[0,1] 1 sage: h.meet_matrix() Traceback (most recent call last) ... ValueError: not a meetsemilattice: no bottom element
Then, we make the method FinitePoset.meet(x, y)
(resp. join(x, y)
) by applying the _element_to_vertex
and _vertex_to_element
conversions on poset._hasse_diagram._meet
.
This extends meet
of a pair x, y
in FiniteMeetSemilattice
to nonsemilattice finite poset.
sage: P = Poset({"a":["b", "c", "d"], "b":["e", "f"], "c":["f"], "d":["f", "g"]} ....: ) sage: M = MeetSemilattice(P) sage: M.meet("f","g") 'd' sage: P2 = Poset({"b":["e", "f"], "c":["f"], "d":["f", "g"]}) sage: M2 = MeetSemilattice(P) Traceback (most recent call last) ... ValueError: not a meetsemilattice: no bottom element
For the posets P
and P2
above, we expect:
sage: P.meet("f","g") 'd' sage: P2.meet("f","g") 'd'
In addition, FinitePoset
has the method common_upper_covers
. We propose to implement the method common_lower_covers
as well, for symmetry and completeness.
Change History (25)
comment:1 Changed 7 months ago by
 Description modified (diff)
comment:2 Changed 7 months ago by
 Description modified (diff)
comment:3 Changed 7 months ago by
 Branch set to u/yzh/implement_meet__join__etc__methods_for_posets
comment:4 followup: ↓ 5 Changed 7 months ago by
 Commit set to 287ec785acd6a520beae4f2f61523cc2e40ce9fa
comment:5 in reply to: ↑ 4 Changed 7 months ago by
Replying to tscrim:
I don't understand why we need a
_meet
and_join
method inFinitePoset
. Those are implementation details in the backend.+1 for adding a
common_lower_covers
method.
In fact, I meant FinitePoset.meet(x, y)
for two given elements x and y in the poset, even for poset such that poset.has_bottom()
is False
. Now reading the code more carefully, I realize that this is not exactly the same as poset._hasse_diagram._meet
, which gives the meet_matrix
in the case of a meetsemilattice and raises an error otherwise.
comment:6 Changed 7 months ago by
I'm also wondering if @lazy_attribute HasseDiagram._meet
(and also _join
) raises Error and refuses to compute the matrix too often. I think it would be better to set the xyentry of the meet matrix to None
when the meet of x, y doesn't exists, and then push the checks for the ValueError("not a meetsemilattice...")
and LatticeError('meet')
to where it needs.
comment:7 Changed 7 months ago by
 Description modified (diff)
comment:8 Changed 7 months ago by
 Description modified (diff)
comment:9 Changed 7 months ago by
 Description modified (diff)
comment:10 Changed 7 months ago by
 Description modified (diff)
comment:11 Changed 7 months ago by
 Description modified (diff)
comment:12 Changed 7 months ago by
 Commit changed from 287ec785acd6a520beae4f2f61523cc2e40ce9fa to a155f416e944ef7bc45e6e2751d2a0aaf07e5a8d
Branch pushed to git repo; I updated commit sha1. New commits:
a155f41  change HasseDiagram._meet/_join to allow non meet/joinsemilattice

comment:13 Changed 7 months ago by
 Description modified (diff)
comment:14 Changed 7 months ago by
 Description modified (diff)
comment:15 Changed 7 months ago by
 Description modified (diff)
comment:16 Changed 7 months ago by
Question: Why is the following not allowed?
sage: E = LatticePoset({}) sage: Poset({0: [1]}).is_lattice() True sage: P = MeetSemilattice({0: [1]}) sage: E.is_sublattice(P) Traceback (most recent call last): ... TypeError: other is not a lattice
comment:17 Changed 7 months ago by
 Commit changed from a155f416e944ef7bc45e6e2751d2a0aaf07e5a8d to e9a42fd01c05d4e892aa08ceadb26095aaf77f78
Branch pushed to git repo; I updated commit sha1. New commits:
04f153f  change calls of _meet/_join to meet_matrix()/join_matrix() which include checks

2a32c9d  implement meet/join methods for posets that are not meet/joinsemilattices

e9a42fd  change doctests regarding LatticePoset.is_sublattice(MeetSemilattice or JoinSemilattice)

comment:18 Changed 7 months ago by
 Status changed from new to needs_review
comment:19 Changed 7 months ago by
comment:20 Changed 7 months ago by
 Commit changed from e9a42fd01c05d4e892aa08ceadb26095aaf77f78 to fa07859f935f00630bdf5890e2e01a482a8e6cd4
Branch pushed to git repo; I updated commit sha1. New commits:
fa07859  add doctest allowing LatticePoset.is_sublattice(FinitePoset)

comment:21 Changed 7 months ago by
The semilattice check can be quite slow with your proposal as it is done every time the meet_matrix()
is called. I think you should define a new attribute _semilattice_failure = None
on initialization. Then when _meet
is called, it sets this attribute to an invalid pair (and perhaps ()
if successful). Then the check in meet_matrix()
becomes:
if (n != 0) and (not self.has_bottom()): raise ValueError("not a meetsemilattice: no bottom element") # call the attribute to build the matrix and sets _semilattice_failure mt = self._meet if self._semilattice_failure: x, y = self._is_meet_semilattice raise LatticeError('meet', x, y)
comment:22 Changed 7 months ago by
 Commit changed from fa07859f935f00630bdf5890e2e01a482a8e6cd4 to a19697ff97092b9bd17bd4e01920a6cfa90b8d95
Branch pushed to git repo; I updated commit sha1. New commits:
a19697f  new attributes HasseDiagram._meet/join_semilattice_failure

comment:23 Changed 7 months ago by
Thanks, Travis! I made the change according to your suggestion.
comment:24 Changed 7 months ago by
 Reviewers set to Travis Scrimshaw
 Status changed from needs_review to positive_review
I like your solution. Thank you. LGTM.
comment:25 Changed 5 months ago by
 Branch changed from u/yzh/implement_meet__join__etc__methods_for_posets to a19697ff97092b9bd17bd4e01920a6cfa90b8d95
 Resolution set to fixed
 Status changed from positive_review to closed
I don't understand why we need a
_meet
and_join
method inFinitePoset
. Those are implementation details in the backend.+1 for adding a
common_lower_covers
method.New commits:
implement common_lower_covers