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: 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:

Status badges

Description (last modified by slelievre)

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 7 months ago by yzh

  • Description modified (diff)

comment:2 Changed 7 months ago by yzh

  • Description modified (diff)

comment:3 Changed 7 months ago by yzh

  • Branch set to u/yzh/implement_meet__join__etc__methods_for_posets

comment:4 follow-up: Changed 7 months ago by tscrim

  • Commit set to 287ec785acd6a520beae4f2f61523cc2e40ce9fa

I don't understand why we need a _meet and _join method in FinitePoset. Those are implementation details in the backend.

+1 for adding a common_lower_covers method.


New commits:

287ec78implement common_lower_covers

comment:5 in reply to: ↑ 4 Changed 7 months ago by yzh

Replying to tscrim:

I don't understand why we need a _meet and _join method in FinitePoset. 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.

Last edited 7 months ago by slelievre (previous) (diff)

comment:6 Changed 7 months ago by yzh

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 7 months ago by yzh

  • Description modified (diff)

comment:8 Changed 7 months ago by yzh

  • Description modified (diff)

comment:9 Changed 7 months ago by yzh

  • Description modified (diff)

comment:10 Changed 7 months ago by yzh

  • Description modified (diff)

comment:11 Changed 7 months ago by yzh

  • Description modified (diff)

comment:12 Changed 7 months ago by git

  • Commit changed from 287ec785acd6a520beae4f2f61523cc2e40ce9fa to a155f416e944ef7bc45e6e2751d2a0aaf07e5a8d

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

a155f41change HasseDiagram._meet/_join to allow non meet/join-semilattice

comment:13 Changed 7 months ago by yzh

  • Description modified (diff)

comment:14 Changed 7 months ago by yzh

  • Description modified (diff)

comment:15 Changed 7 months ago by slelievre

  • Description modified (diff)

comment:16 Changed 7 months ago by yzh

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 git

  • Commit changed from a155f416e944ef7bc45e6e2751d2a0aaf07e5a8d to e9a42fd01c05d4e892aa08ceadb26095aaf77f78

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

04f153fchange calls of _meet/_join to meet_matrix()/join_matrix() which include checks
2a32c9dimplement meet/join methods for posets that are not meet/join-semilattices
e9a42fdchange doctests regarding LatticePoset.is_sublattice(MeetSemilattice or JoinSemilattice)

comment:18 Changed 7 months ago by yzh

  • Status changed from new to needs_review

comment:19 Changed 7 months ago by yzh

  • Authors set to Yuan Zhou

comment:20 Changed 7 months ago by git

  • Commit changed from e9a42fd01c05d4e892aa08ceadb26095aaf77f78 to fa07859f935f00630bdf5890e2e01a482a8e6cd4

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

fa07859add doctest allowing LatticePoset.is_sublattice(FinitePoset)

comment:21 Changed 7 months ago by tscrim

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 7 months ago by git

  • Commit changed from fa07859f935f00630bdf5890e2e01a482a8e6cd4 to a19697ff97092b9bd17bd4e01920a6cfa90b8d95

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

a19697fnew attributes HasseDiagram._meet/join_semilattice_failure

comment:23 Changed 7 months ago by yzh

Thanks, Travis! I made the change according to your suggestion.

comment:24 Changed 7 months ago by tscrim

  • 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 vbraun

  • 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
Note: See TracTickets for help on using tickets.