Implement meet, join, etc. methods for posets

[yzh]

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.

[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.

---

New commits:

​287ec78

implement common_lower_covers

[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.

[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.

[git]

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

​a155f41

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

[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

[git]

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)

[git]

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

​fa07859

add doctest allowing LatticePoset.is_sublattice(FinitePoset)

[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)

[git]

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

​a19697f

new attributes HasseDiagram._meet/join_semilattice_failure

[yzh]

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

[tscrim]

I like your solution. Thank you. LGTM.