Opened 8 years ago
Last modified 6 weeks ago
#17173 needs_work enhancement
Poset: faster is_distributive_lattice
Reported by: | jmantysalo | Owned by: | |
---|---|---|---|
Priority: | major | Milestone: | |
Component: | combinatorics | Keywords: | |
Cc: | tscrim | Merged in: | |
Authors: | Jori Mäntysalo | Reviewers: | |
Report Upstream: | N/A | Work issues: | |
Branch: | public/poset__faster_is_distributive_lattice (Commits, GitHub, GitLab) | Commit: | f5416f799262d0540e61f0b337d900cc8e776bff |
Dependencies: | Stopgaps: |
Description (last modified by )
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.
Change History (16)
comment:1 Changed 8 years ago by
Cc: | ncohen added |
---|
comment:2 Changed 8 years ago by
Branch: | → u/jmantysalo/poset__faster_is_distributive_lattice |
---|
comment:3 Changed 8 years ago by
Authors: | → Jori Mäntysalo |
---|---|
Commit: | → d69e73a0a0a655e4e1595a77cda807ccb017fb02 |
Description: | modified (diff) |
Milestone: | sage-wishlist → sage-6.4 |
Status: | new → needs_review |
comment:4 follow-up: 5 Changed 8 years ago by
Status: | needs_review → needs_work |
---|
Hello Jori !
A couple of comments:
Please, try to make your code a bit better-looking:
-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
comment:5 follow-up: 6 Changed 8 years ago by
Replying to ncohen:
Please, try to make your code a bit better-looking:
OK, I'll try. I was thinkig about some kind of "short-circuit test" first: start with trivial ways to see that poset surely has not the property we are looking for. But your code example is cleaner.
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 need the list. It starts with x=give_an_array(y)
but if it's length is exactly one, then continues with z=x[0]
. Or do you mean optimizing it so that if code founds out that len(self.upper_covers(m)
is at least 2, it returns False?
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:
Uh, I somehow thinked that it would be optimized out. But of course it can not be done. I will correct this.
There is also a broken doctest in
hasse_diagram.py
?? I didn't touch it, just deprecated a function.
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)
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.
Hmm... First call to subposet
can be changed to subgraph and to search of element with in-degree zero.
And yes, this can be also changed to direct loop without recursion. Actually I just copied the algorithm without thinking speed; in any case this should now be almost O(n)
instead of O(n^3)
in current version.
But elements can not be removed from poset; vertices can be removed from graph (with right internal implementation). I guess it is faster that way; only code might seem slightly complicated.
Thanks for comments! I'll continue with these later.
comment:6 Changed 8 years ago by
I need the list.
Not there
len([e for e in self if len(self.lower_covers(e))==1])
nor there
if len(self.upper_covers(m))==1:
nor there
if len(M_.minimal_elements()) > 1:
It starts with
x=give_an_array(y)
but if it's length is exactly one, then continues withz=x[0]
. Or do you mean optimizing it so that if code founds out thatlen(self.upper_covers(m)
is at least 2, it returns False?
I have not read the algorithm closely yet, I do not know what it does exactly. There are places in the code, however, where those lists are created only to compute their length, e.g. above.
Uh, I somehow thinked that it would be optimized out. But of course it can not be done. I will correct this.
Python is the worst language ever. It is a script. I hate scripts.
?? I didn't touch it, just deprecated a function.
yes yes, but the deprecation breaks the tests. Run the tests and see ! It is trivial, however, you probably only need to fix the output (which now contains the deprecation warning).
Thanks for comments! I'll continue with these later.
Good luck ! :-)
Nathann
comment:7 follow-up: 8 Changed 8 years ago by
If I convert this to loop, I must have a working copy on Hasse diagram. Do I then still have linear extension? I must find a minimal element of subposet containing only meet-irreducible elements, i.e. a meet-irreducible element that is not greater than any other meet-irreducible element. For a poset P
I can found it just looping throught P
--- it will give elements by (some) linear extension.
In other words: If G.vertices()
prints ..., a, ..., b, ...
, can it after D.delete_edges(...)
print ..., b, ..., a, ...
? If not, is this guaranteed behaviour in following versions of Sage?
comment:8 follow-up: 9 Changed 8 years ago by
Hello !
In other words: If
G.vertices()
prints..., a, ..., b, ...
, can it afterD.delete_edges(...)
print..., b, ..., a, ...
? If not, is this guaranteed behaviour in following versions of Sage?
Hmmmmm... If the vertex set consists of integers this will not happens, but is that really a problem ? You can also store and manage the list of vertices yourself. Or rename the set of points.
I forgot one place where
minimal_elements()
was computed twice. Otherwise there is no unneeded lists generated in loop.
What about this ?
len([e for e in self if len(self.lower_covers(e))==1]) if len(self.upper_covers(m))==1: if len(M_.minimal_elements()) > 1:
nathann
comment:9 Changed 8 years ago by
Replying to ncohen:
Hello !
In other words: If
G.vertices()
prints..., a, ..., b, ...
, can it afterD.delete_edges(...)
print..., b, ..., a, ...
? If not, is this guaranteed behaviour in following versions of Sage?Hmmmmm... If the vertex set consists of integers this will not happens, but is that really a problem ? You can also store and manage the list of vertices yourself. Or rename the set of points.
Hasse diagram has always integers 0,...,n-1
as labels. But I don't quite get this: if I write code that manages list of vertex labels, I am doing code that posets code already does.
Actually I think that I will start discussion about this on sage-devel.
comment:10 Changed 7 years ago by
Cc: | tscrim added; ncohen removed |
---|
Travis: This is an old ticket that has been lying for two years. What you think about adding this as a recursive function? I think that it is still better than not having this at all.
comment:11 Changed 7 years ago by
Milestone: | sage-6.4 → sage-7.2 |
---|
Needs a rebase from the latest beta, but I will review this.
comment:12 Changed 7 years ago by
Commit: | d69e73a0a0a655e4e1595a77cda807ccb017fb02 → 9a86b0acba7649ecffe0c61bf6b4404bb72283e8 |
---|
Branch pushed to git repo; I updated commit sha1. New commits:
9a86b0a | Merged with latest beta
|
comment:13 Changed 7 years ago by
Merged, but I am re-reading the code, compiling and testing. Not ready for review yet.
comment:14 Changed 3 years ago by
Branch: | u/jmantysalo/poset__faster_is_distributive_lattice → public/poset__faster_is_distributive_lattice |
---|---|
Commit: | 9a86b0acba7649ecffe0c61bf6b4404bb72283e8 → db89e467f8ae6d7ce2c54b55c1737664ea7c5ce3 |
comment:15 Changed 3 years ago by
Commit: | db89e467f8ae6d7ce2c54b55c1737664ea7c5ce3 → f5416f799262d0540e61f0b337d900cc8e776bff |
---|
Branch pushed to git repo; I updated commit sha1. New commits:
f5416f7 | fix
|
comment:16 Changed 6 weeks ago by
Milestone: | sage-7.2 |
---|
Also deprecated same function from
hasse_diagram.py
.New commits:
Added O(n) recognition of distributive lattices to posets.
Unnecessary spaces removed.