Opened 16 months ago
Closed 14 months ago
#31725 closed enhancement (fixed)
Implement meet, join, etc. methods for posets
Reported by: | yzh | Owned by: | |
---|---|---|---|
Priority: | major | Milestone: | sage-9.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/join-semilattice.
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 meet-semilattice: 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 meet-semilattice: 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 non-semilattice 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 meet-semilattice: 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 16 months ago by
- Description modified (diff)
comment:2 Changed 16 months ago by
- Description modified (diff)
comment:3 Changed 16 months ago by
- Branch set to u/yzh/implement_meet__join__etc__methods_for_posets
comment:4 follow-up: ↓ 5 Changed 16 months ago by
- Commit set to 287ec785acd6a520beae4f2f61523cc2e40ce9fa
comment:5 in reply to: ↑ 4 Changed 16 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 meet-semilattice and raises an error otherwise.
comment:6 Changed 16 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 xy-entry 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 meet-semilattice...")
and LatticeError('meet')
to where it needs.
comment:7 Changed 16 months ago by
- Description modified (diff)
comment:8 Changed 16 months ago by
- Description modified (diff)
comment:9 Changed 16 months ago by
- Description modified (diff)
comment:10 Changed 16 months ago by
- Description modified (diff)
comment:11 Changed 16 months ago by
- Description modified (diff)
comment:12 Changed 16 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/join-semilattice
|
comment:13 Changed 16 months ago by
- Description modified (diff)
comment:14 Changed 16 months ago by
- Description modified (diff)
comment:15 Changed 16 months ago by
- Description modified (diff)
comment:16 Changed 16 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 16 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/join-semilattices
|
e9a42fd | change doctests regarding LatticePoset.is_sublattice(MeetSemilattice or JoinSemilattice)
|
comment:18 Changed 16 months ago by
- Status changed from new to needs_review
comment:19 Changed 16 months ago by
comment:20 Changed 16 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 16 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 meet-semilattice: 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 16 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 16 months ago by
Thanks, Travis! I made the change according to your suggestion.
comment:24 Changed 16 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 14 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