| 1 | | After #17121 it is faster to say `P.is_lattice() and LatticePoset(P).is_distibutive()` than `P._hasse_diagram.is_distributive_lattice()`. However, there exists also fast algorithm to directly check if a given poset is distributive lattice, see http://www.lirmm.fr/~nourine/Papiers/dist-recognition.ps . |
| 2 | | |
| 3 | | To show that algorithm works I did a small example code, which is not optimized at all. I will continue with this later. If someone is going to implement this, please add a note to this ticket. |
| 4 | | |
| 5 | | {{{ |
| 6 | | def join_irreducibles(self): return [e for e in self if len(self.lower_covers(e))==1] |
| 7 | | def meet_irreducibles(self): return [e for e in self if len(self.upper_covers(e))==1] |
| 8 | | |
| 9 | | def is_distributive_lattice(self): |
| 10 | | if ( not self.is_graded() or not self.is_bounded() or not |
| 11 | | self.rank() == len(join_irreducibles(self)) == len(meet_irreducibles(self)) ): |
| 12 | | return False |
| 13 | | return _is_distributive_lattice_workhorse(self) |
| 14 | | |
| 15 | | def _is_distributive_lattice_workhorse(P): |
| 16 | | # Real workhorse, a recursive algorithm. |
| 17 | | # To show how the reduction goes: |
| 18 | | P.show() |
| 19 | | if not len([x for x in P if len(P.upper_covers(x))==1])==len([x for x in P if len(P.lower_covers(x))==1])==P.rank(): |
| 20 | | return False |
| 21 | | if P.cardinality() == 2: |
| 22 | | if len(P.minimal_elements())==1: |
| 23 | | return True |
| 24 | | return "This should not happen!" |
| 25 | | M=P.subposet([x for x in P if len(P.upper_covers(x))==1]) |
| 26 | | if len(M) == 0: |
| 27 | | return "This should not happen!" |
| 28 | | m=M.minimal_elements()[0] |
| 29 | | if len(P.upper_covers(m)) > 1: |
| 30 | | return "This should not happen!" |
| 31 | | m_=P.upper_covers(m)[0] |
| 32 | | M_=P.subposet([x for x in P if not x in P.closed_interval(P.bottom(), m)]) |
| 33 | | if len(M_.minimal_elements()) > 1: |
| 34 | | return False |
| 35 | | j=M_.minimal_elements() |
| 36 | | j=j[0] |
| 37 | | # Does not really work, but counter-example must be quite big lattice. |
| 38 | | Z1=P.interval(P.bottom(), m) |
| 39 | | Z2=Set(P.interval(j, m_)) |
| 40 | | for z in Z1: |
| 41 | | if len(Set(P.upper_covers(z)).difference(Z1)) != 1: |
| 42 | | return False |
| 43 | | if Set(P.upper_covers(z)).intersection(Z2).cardinality() != 1: |
| 44 | | return False |
| 45 | | Z2 = Z2.difference(P.upper_covers(z)) |
| 46 | | if Z2.cardinality() > 0: |
| 47 | | return False |
| 48 | | P_=P.subposet(x for x in P if not x in P.interval(P.bottom(), m)) |
| 49 | | return _is_distributive_lattice_workhorse(P_) |
| 50 | | }}} |
| | 1 | After #17121 it is faster to say `P.is_lattice() and LatticePoset(P).is_distibutive()` than `P._hasse_diagram.is_distributive_lattice()`. However, there exists also fast algorithm to directly check if a given poset is distributive lattice. |
