#17173: Poset: faster is_distributive_lattice
-------------------------------------+-------------------------------------
Reporter: jmantysalo | Owner:
Type: enhancement | Status: needs_review
Priority: major | Milestone: sage-6.4
Component: combinatorics | Resolution:
Keywords: | Merged in:
Authors: Jori Mäntysalo | Reviewers:
Report Upstream: N/A | Work issues:
Branch: | Commit:
u/jmantysalo/poset__faster_is_distributive_lattice|
d69e73a0a0a655e4e1595a77cda807ccb017fb02
Dependencies: | Stopgaps:
-------------------------------------+-------------------------------------
Changes (by {'newvalue': u'Jori M\xe4ntysalo', 'oldvalue': ''}):
* status: new => needs_review
* commit: => d69e73a0a0a655e4e1595a77cda807ccb017fb02
* author: => Jori Mäntysalo
* milestone: sage-wishlist => sage-6.4
Old description:
> 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_)
> }}}
New description:
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.
--
Comment:
Also deprecated same function from `hasse_diagram.py`.
----
New commits:
||[http://git.sagemath.org/sage.git/commit/?id=26e45c282ad073bc862c87b04f95696ebced5d48
26e45c2]||{{{Added O(n) recognition of distributive lattices to
posets.}}}||
||[http://git.sagemath.org/sage.git/commit/?id=d69e73a0a0a655e4e1595a77cda807ccb017fb02
d69e73a]||{{{Unnecessary spaces removed.}}}||
--
Ticket URL: <http://trac.sagemath.org/ticket/17173#comment:3>
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.
