Opened 18 months ago
Closed 16 months ago
#31725 closed enhancement (fixed)
Implement meet, join, etc. methods for posets
Reported by:  Yuan Zhou  Owned by:  

Priority:  major  Milestone:  sage9.4 
Component:  combinatorics  Keywords:  poset, hasse_diagram 
Cc:  Matthias Köppe, Frédéric Chapoton, Travis Scrimshaw, Samuel Lelièvre  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 18 months ago by
Description:  modified (diff) 

comment:2 Changed 18 months ago by
Description:  modified (diff) 

comment:3 Changed 18 months ago by
Branch:  → u/yzh/implement_meet__join__etc__methods_for_posets 

comment:4 followup: 5 Changed 18 months ago by
Commit:  → 287ec785acd6a520beae4f2f61523cc2e40ce9fa 

comment:5 Changed 18 months ago by
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.
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.
New commits:
287ec78 implement common_lower_covers
comment:6 Changed 18 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 18 months ago by
Description:  modified (diff) 

comment:8 Changed 18 months ago by
Description:  modified (diff) 

comment:9 Changed 18 months ago by
Description:  modified (diff) 

comment:10 Changed 18 months ago by
Description:  modified (diff) 

comment:11 Changed 18 months ago by
Description:  modified (diff) 

comment:12 Changed 18 months ago by
Commit:  287ec785acd6a520beae4f2f61523cc2e40ce9fa → 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 18 months ago by
Description:  modified (diff) 

comment:14 Changed 18 months ago by
Description:  modified (diff) 

comment:15 Changed 18 months ago by
Description:  modified (diff) 

comment:16 Changed 18 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 18 months ago by
Commit:  a155f416e944ef7bc45e6e2751d2a0aaf07e5a8d → 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 18 months ago by
Status:  new → needs_review 

comment:19 Changed 18 months ago by
Authors:  → Yuan Zhou 

comment:20 Changed 18 months ago by
Commit:  e9a42fd01c05d4e892aa08ceadb26095aaf77f78 → fa07859f935f00630bdf5890e2e01a482a8e6cd4 

Branch pushed to git repo; I updated commit sha1. New commits:
fa07859  add doctest allowing LatticePoset.is_sublattice(FinitePoset)

comment:21 Changed 18 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 18 months ago by
Commit:  fa07859f935f00630bdf5890e2e01a482a8e6cd4 → a19697ff97092b9bd17bd4e01920a6cfa90b8d95 

Branch pushed to git repo; I updated commit sha1. New commits:
a19697f  new attributes HasseDiagram._meet/join_semilattice_failure

comment:24 Changed 18 months ago by
Reviewers:  → Travis Scrimshaw 

Status:  needs_review → positive_review 
I like your solution. Thank you. LGTM.
comment:25 Changed 16 months ago by
Branch:  u/yzh/implement_meet__join__etc__methods_for_posets → a19697ff97092b9bd17bd4e01920a6cfa90b8d95 

Resolution:  → fixed 
Status:  positive_review → 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