#17173: Poset: faster is_distributive_lattice
-------------------------------------+-------------------------------------
Reporter: jmantysalo | Owner:
Type: enhancement | Status: needs_work
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 ncohen):
* status: needs_review => needs_work
Comment:
Hello Jori !
A couple of comments:
Please, try to make your code a bit better-looking:
{{{
#!diff
-if ( not self.is_graded() or not self.is_bounded() or not
- self.rank() == len([e for e in self if
len(self.lower_covers(e))==1]) ==
- len([e for e in self if len(self.upper_covers(e))==1]) ):
- return False
-return self._is_distributive_lattice_recursion()
return (self.is_graded() and
self.is_bounded() and
(self.rank() == len([e for e in self if
len(self.lower_covers(e))==1])
== len([e for e in self if
len(self.upper_covers(e))==1])) and
self._is_distributive_lattice_recursion())
}}}
By the way it is very unpleasant to build the list of upper covers when
all you want to do is count its length. This is just a call to `in_degree`
in the hasse diagram !
I also see that you compute 'subposet' very often, and I wonder if you
should not compute subgraphs instead, as I expect that it is much more
efficient (I beware of the `UniqueRepresentation` stuff)
Also, you cannot write things like that in Sage code
{{{
[x for x in self if not x in self.closed_interval(self.bottom(), m)]
}}}
Here is why:
{{{
sage: def a():
....: print "Hey"
....: return [1]
....: [x for x in range(5) if x in a()]
....:
Hey
Hey
Hey
Hey
Hey
[1]
}}}
What you want to do is something like
{{{set(self).difference(self.closed_interval(self.bottom(), m))}}}
There is also a broken doctest in `hasse_diagram.py`
Oh. And I am just noticing that your function does not seem to be
recursive at all: you can replace the recursion by a loop ! First create a
copy of self, and at each turn of the loop remove some vertices from the
copy you work on.
Nathann
--
Ticket URL: <http://trac.sagemath.org/ticket/17173#comment:4>
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.
