#17173: Poset: faster is_distributive_lattice
-----------------------------+---------------------------------
Reporter: jmantysalo | Owner:
Type: enhancement | Status: new
Priority: major | Milestone: sage-wishlist
Component: combinatorics | Keywords:
Merged in: | Authors:
Reviewers: | Report Upstream: N/A
Work issues: | Branch:
Commit: | Dependencies:
Stopgaps: |
-----------------------------+---------------------------------
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 .
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.
{{{
def join_irreducibles(self): return [e for e in self if
len(self.lower_covers(e))==1]
def meet_irreducibles(self): return [e for e in self if
len(self.upper_covers(e))==1]
def is_distributive_lattice(self):
if ( not self.is_graded() or not self.is_bounded() or not
self.rank() == len(join_irreducibles(self)) ==
len(meet_irreducibles(self)) ):
return False
return _is_distributive_lattice_workhorse(self)
def _is_distributive_lattice_workhorse(P):
# Real workhorse, a recursive algorithm.
# To show how the reduction goes:
P.show()
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():
return False
if P.cardinality() == 2:
if len(P.minimal_elements())==1:
return True
return "This should not happen!"
M=P.subposet([x for x in P if len(P.upper_covers(x))==1])
if len(M) == 0:
return "This should not happen!"
m=M.minimal_elements()[0]
if len(P.upper_covers(m)) > 1:
return "This should not happen!"
m_=P.upper_covers(m)[0]
M_=P.subposet([x for x in P if not x in P.closed_interval(P.bottom(),
m)])
if len(M_.minimal_elements()) > 1:
return False
j=M_.minimal_elements()
j=j[0]
# Does not really work, but counter-example must be quite big lattice.
Z1=P.interval(P.bottom(), m)
Z2=Set(P.interval(j, m_))
for z in Z1:
if len(Set(P.upper_covers(z)).difference(Z1)) != 1:
return False
if Set(P.upper_covers(z)).intersection(Z2).cardinality() != 1:
return False
Z2 = Z2.difference(P.upper_covers(z))
if Z2.cardinality() > 0:
return False
P_=P.subposet(x for x in P if not x in P.interval(P.bottom(), m))
return _is_distributive_lattice_workhorse(P_)
}}}
--
Ticket URL: <http://trac.sagemath.org/ticket/17173>
Sage <http://www.sagemath.org>
Sage: Creating a Viable Open Source Alternative to Magma, Maple, Mathematica,
and MATLAB
--
You received this message because you are subscribed to the Google Groups
"sage-trac" group.
To unsubscribe from this group and stop receiving emails from it, send an email
to [email protected].
To post to this group, send email to [email protected].
Visit this group at http://groups.google.com/group/sage-trac.
For more options, visit https://groups.google.com/d/optout.
