Changes between Initial Version and Version 3 of Ticket #17173


Ignore:
Timestamp:
Oct 20, 2014, 6:41:14 AM (8 years ago)
Author:
jmantysalo
Comment:

Also deprecated same function from hasse_diagram.py.


New commits:

26e45c2Added O(n) recognition of distributive lattices to posets.
d69e73aUnnecessary spaces removed.

Legend:

Unmodified
Added
Removed
Modified
  • Ticket #17173

    • Property Status changed from new to needs_review
    • Property Authors changed from to Jori Mäntysalo
    • Property Cc ncohen added
    • Property Branch changed from to u/jmantysalo/poset__faster_is_distributive_lattice
    • Property Milestone changed from sage-wishlist to sage-6.4
    • Property Commit changed from to d69e73a0a0a655e4e1595a77cda807ccb017fb02
  • Ticket #17173 – Description

    initial v3  
    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 }}}
     1After #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.