Opened 6 years ago

Last modified 14 months ago

#17173 needs_work enhancement

Poset: faster is_distributive_lattice

Reported by: jmantysalo Owned by:
Priority: major Milestone: sage-7.2
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) Commit: f5416f799262d0540e61f0b337d900cc8e776bff
Dependencies: Stopgaps:

Description (last modified by 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.

Change History (15)

comment:1 Changed 6 years ago by ncohen

  • Cc ncohen added

comment:2 Changed 6 years ago by jmantysalo

  • Branch set to u/jmantysalo/poset__faster_is_distributive_lattice

comment:3 Changed 6 years ago by jmantysalo

  • Authors set to Jori Mäntysalo
  • Commit set to d69e73a0a0a655e4e1595a77cda807ccb017fb02
  • Description modified (diff)
  • Milestone changed from sage-wishlist to sage-6.4
  • Status changed from new to needs_review

Also deprecated same function from hasse_diagram.py.


New commits:

26e45c2Added O(n) recognition of distributive lattices to posets.
d69e73aUnnecessary spaces removed.

comment:4 follow-up: Changed 6 years ago by ncohen

  • Status changed from needs_review to 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

Last edited 6 years ago by ncohen (previous) (diff)

comment:5 in reply to: ↑ 4 ; follow-up: Changed 6 years ago by 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.

comment:6 in reply to: ↑ 5 Changed 6 years ago by 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

comment:7 follow-up: Changed 6 years ago by 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?

I forgot one place where minimal_elements() was computed twice. Otherwise there is no unneeded lists generated in loop.

Last edited 6 years ago by jmantysalo (previous) (diff)

comment:8 in reply to: ↑ 7 ; follow-up: Changed 6 years ago by 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

comment:9 in reply to: ↑ 8 Changed 6 years ago by 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.

comment:10 Changed 5 years ago by jmantysalo

  • 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 5 years ago by tscrim

  • Milestone changed from sage-6.4 to sage-7.2

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

comment:12 Changed 5 years ago by git

  • Commit changed from d69e73a0a0a655e4e1595a77cda807ccb017fb02 to 9a86b0acba7649ecffe0c61bf6b4404bb72283e8

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

9a86b0aMerged with latest beta

comment:13 Changed 5 years ago by jmantysalo

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

comment:14 Changed 14 months ago by chapoton

  • Branch changed from u/jmantysalo/poset__faster_is_distributive_lattice to public/poset__faster_is_distributive_lattice
  • Commit changed from 9a86b0acba7649ecffe0c61bf6b4404bb72283e8 to db89e467f8ae6d7ce2c54b55c1737664ea7c5ce3

New commits:

4435835Merge branch 'u/jmantysalo/poset__faster_is_distributive_lattice' in 9.0.b6
db89e46some enhancements

comment:15 Changed 14 months ago by git

  • Commit changed from db89e467f8ae6d7ce2c54b55c1737664ea7c5ce3 to f5416f799262d0540e61f0b337d900cc8e776bff

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

f5416f7fix
Note: See TracTickets for help on using tickets.