Poset: faster is_distributive_lattice

[jmantysalo]

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.

[jmantysalo]

Also deprecated same function from hasse_diagram.py.

---

New commits:

​26e45c2	Added O(n) recognition of distributive lattices to posets.
​d69e73a	Unnecessary spaces removed.

[ncohen]

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

[jmantysalo]

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.

[ncohen]

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 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?

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

[jmantysalo]

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?

[ncohen]

Hello !

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?

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

[jmantysalo]

Replying to ncohen:

Hello !

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?

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.

[jmantysalo]

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.

[tscrim]

Needs a rebase from the latest beta, but I will review this.

[git]

Branch pushed to git repo; I updated commit sha1. New commits:

​9a86b0a

Merged with latest beta

[jmantysalo]

Merged, but I am re-reading the code, compiling and testing. Not ready for review yet.

[chapoton]

New commits:

​4435835	Merge branch 'u/jmantysalo/poset__faster_is_distributive_lattice' in 9.0.b6
​db89e46	some enhancements

[git]

Branch pushed to git repo; I updated commit sha1. New commits:

​f5416f7

fix