Opened 8 years ago
Last modified 3 years ago
#17173 needs_work enhancement
Poset: faster is_distributive_lattice
Reported by:  Jori Mäntysalo  Owned by:  

Priority:  major  Milestone:  sage7.2 
Component:  combinatorics  Keywords:  
Cc:  Travis Scrimshaw  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 (15)
comment:1 Changed 8 years ago by
Cc:  Nathann Cohen 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:  sagewishlist → sage6.4 
Status:  new → needs_review 
comment:4 followup: 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 betterlooking:
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 followup: 6 Changed 8 years ago by
Replying to ncohen:
Please, try to make your code a bit betterlooking:
OK, I'll try. I was thinkig about some kind of "shortcircuit 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 indegree 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 followup: 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 meetirreducible elements, i.e. a meetirreducible element that is not greater than any other meetirreducible 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?
I forgot one place where minimal_elements()
was computed twice. Otherwise there is no unneeded lists generated in loop.
comment:8 followup: 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,...,n1
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 sagedevel.
comment:10 Changed 7 years ago by
Cc:  Travis Scrimshaw added; Nathann Cohen 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:  sage6.4 → sage7.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 rereading 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

Also deprecated same function from
hasse_diagram.py
.New commits:
Added O(n) recognition of distributive lattices to posets.
Unnecessary spaces removed.