Implement meet, join, etc. methods for posets

Reported by: Owned by: yzh major sage-9.4 combinatorics poset, hasse_diagram mkoeppe, chapoton, tscrim, slelievre Yuan Zhou Travis Scrimshaw N/A a19697f a19697ff97092b9bd17bd4e01920a6cfa90b8d95

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

comment:1 Changed 16 months ago by yzh

• Description modified (diff)

comment:2 Changed 16 months ago by yzh

• Description modified (diff)

comment:3 Changed 16 months ago by yzh

• Branch set to u/yzh/implement_meet__join__etc__methods_for_posets

comment:4 follow-up: ↓ 5 Changed 16 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:

 ​287ec78 `implement common_lower_covers`

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

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 16 months ago by slelievre (previous) (diff)

comment:6 Changed 16 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 16 months ago by yzh

• Description modified (diff)

comment:8 Changed 16 months ago by yzh

• Description modified (diff)

comment:9 Changed 16 months ago by yzh

• Description modified (diff)

comment:10 Changed 16 months ago by yzh

• Description modified (diff)

comment:11 Changed 16 months ago by yzh

• Description modified (diff)

comment:12 Changed 16 months ago by git

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

• Description modified (diff)

comment:14 Changed 16 months ago by yzh

• Description modified (diff)

comment:15 Changed 16 months ago by slelievre

• Description modified (diff)

comment:16 Changed 16 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 16 months ago by git

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

• Status changed from new to needs_review

comment:19 Changed 16 months ago by yzh

• Authors set to Yuan Zhou

comment:20 Changed 16 months ago by git

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

• 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:24 Changed 16 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 14 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.