Opened 8 years ago
Closed 8 years ago
#17216 closed enhancement (fixed)
Poset / LatticePoset: [meetjoin]matrix algorithm
Reported by:  Jori Mäntysalo  Owned by:  

Priority:  major  Milestone:  sage6.4 
Component:  combinatorics  Keywords:  
Cc:  Nathann Cohen  Merged in:  
Authors:  Jori Mäntysalo  Reviewers:  Nathann Cohen, Travis Scrimshaw 
Report Upstream:  N/A  Work issues:  
Branch:  391c03b (Commits, GitHub, GitLab)  Commit:  391c03bcc290824c78f165d1623baaf1d921734d 
Dependencies:  Stopgaps: 
Description (last modified by )
Because join()
and meet()
are defined on [meetjoin]lattices, not on posets, it is logical to also move join_matrix()
and meet_matrix()
there.
On hasse_diagram.py
there is for example
le = copy(self.lequal_matrix()) for i in range(n): le[i,i] = 1
This is unneeded, because lequal_matrix()
already contains ones at diagonal. We can use _leq_matrix
directly. There are also few other places to small optimization.
At the same time I suggesg moving is_lattice()
to posets.py
from category code, because is_[meetjoin]_semilattice()
already is there.
Change History (24)
comment:1 Changed 8 years ago by
Branch:  → u/jmantysalo/poset___latticeposet___meet_join_matrix_algorithm 

comment:2 Changed 8 years ago by
Authors:  → Jori Mäntysalo 

Cc:  Nathann Cohen added 
Commit:  → 8b2ab93a44970afc31a12dc0df57883f4b27eda6 
comment:3 Changed 8 years ago by
Commit:  8b2ab93a44970afc31a12dc0df57883f4b27eda6 → aa6db231af42197ba9a4daccf904c126dad87204 

Branch pushed to git repo; I updated commit sha1. New commits:
aa6db23  Slight simplifying to _join.

comment:4 Changed 8 years ago by
Commit:  aa6db231af42197ba9a4daccf904c126dad87204 → a7d2dd08623026a269f5fd7700b9e659985e7579 

Branch pushed to git repo; I updated commit sha1. New commits:
a7d2dd0  Moved [meetjoin]_matrix from posets to lattices and is_lattice from

comment:5 Changed 8 years ago by
Description:  modified (diff) 

Milestone:  sagewishlist → sage6.4 
Status:  new → needs_review 
comment:6 Changed 8 years ago by
Status:  needs_review → needs_work 

Hello !
Thanks you for this branch, it is nice code.
A couple of comments and it can go:
1) The tests do not pass in the combinat/poset/ folder.
2) The code of _join
would be simpled if you called "min(T)" instead of relabelling all points as n1y
.
Nathann
comment:7 Changed 8 years ago by
Commit:  a7d2dd08623026a269f5fd7700b9e659985e7579 → a649be931b249028ff1e5961fc948c2daf50c695 

Branch pushed to git repo; I updated commit sha1. New commits:
a649be9  Let empty poset has [meetjoin]matrix with 0 rows and columns.

comment:8 followup: 9 Changed 8 years ago by
Reviewers:  → Nathann Cohen 

Status:  needs_work → needs_review 
1) Should empty set be a lattice? Anyways, this is now corrected. Should have a test suite containing tests for empty semilattices too. Actually a test suite should test all properties for 0 and 1element posets. (How about is_chain()
, for example?)
2) Hmm... I think I'll think about this on next round iterating throught the code.
comment:9 Changed 8 years ago by
Yo !
1) Should empty set be a lattice? Anyways, this is now corrected. Should have a test suite containing tests for empty semilattices too. Actually a test suite should test all properties for 0 and 1element posets. (How about
is_chain()
, for example?)
Well. I just asked a friend, and as usual it depends on the definition that you prefer. He told me that a lattice should have a maximum and minimum element. The definition I prefer is that "any two guys have both a meet and a join", which hold for an empty set. I do not mind much to be honest, I always suspect other to use different conventions than I, so I usually do not trust softwares for that :P
2) Hmm... I think I'll think about this on next round iterating throught the code.
Oh, I had not seen that the code was already like that before you modified it. Well, looks good to go !
Nathann
comment:10 Changed 8 years ago by
Status:  needs_review → positive_review 

comment:11 followup: 14 Changed 8 years ago by
Status:  positive_review → needs_info 

Has anyone checked that we do get speedups in meet/join matrix?
For the definition of a lattice, I've also been told you want a unique meet and join. Otherwise just the existence is something like regular poset, sorry I forget the exact term right now.
Also could you make the very minor change:
 return matrix(ZZ, [[n1join[n1x][n1y] for y in range(n)] for  x in range(n)]) + return matrix(ZZ, [[n1join[n1x][n1y] for y in range(n)] + for x in range(n)])
IMO it makes the code easier to read, but feel free to disregard.
comment:12 followup: 15 Changed 8 years ago by
Actually, you can't remove that function from the category without deprecating it.
comment:13 followup: 16 Changed 8 years ago by
About speedup: For example after P7=Posets(7).list()
it took 630 ms to run sum([P.is_lattice() for P in P7])
, after this patch 280 ms. Same can be seen in several test runs.
Suggestion of code formatting is good.
When is is_lattice()
on category tried to run? I don't quite understand  what happens if both finite_posets.py
on categories and posets.py
on combinats define same function?
comment:14 followup: 18 Changed 8 years ago by
Has anyone checked that we do get speedups in meet/join matrix?
Look at the code, and you will see that the algorithm never changed. It is only code simplification. For instance a call to 'max' instead of computing the max by hand, for instance listcomprehension instead of successive calls to 'append'. And a copy of a matrix is avoided too.
For the definition of a lattice, I've also been told you want a unique meet and join. Otherwise just the existence is something like regular poset, sorry I forget the exact term right now.
Travis, please read the code for your question is answered there.
Also could you make the very minor change:
Please don't change the status of a ticket that has been reviewed unless you see something which is actually wrong. Something more important than moving a 'for' around.
Nathann
comment:15 Changed 8 years ago by
Actually, you can't remove that function from the category without deprecating it.
If such an object exists somewhere in Sage then we should not move the function from the category file to the lattice file, for that would be a regression.
If such an object does not exist there is no reason to add a deprecation.
Bear in mind that an object that currently belongs to the category of Lattices
and is not a FiniteLattice
must implement its own is_meet_semilattice
and is_join_semilattice
.
Nathann
comment:16 Changed 8 years ago by
When is
is_lattice()
on category tried to run? I don't quite understand  what happens if bothfinite_posets.py
on categories andposets.py
on combinats define same function?
Here is the thing: some guys in Sage rewrote method inheritance and call that "categories". A Lattice belongs to several "categories" by default:
sage: LatticePoset(Poset()).category() Join of Category of finite lattice posets and Category of finite enumerated sets and Category of facade sets
Now, you can create any class and make it belong to the category of Lattices
. It will consequently inherit from the methods defined in the "lattices" category file. This being said, is_lattice
called is_join_semilattice
and is_meet_semilattice
which are defined in the usual poset/lattices.py
file.
Which means that if you want the is_lattice
method to work on an object which is not an instance of FiniteLattice
, then it must implement its own is_join_semilattice
and is_meet_semilattice
.
And chances are that nobody ever did that, for removing that function from the category while reimplementing it in the poset files did not break any doctest.
Nathann
comment:17 Changed 8 years ago by
Status:  needs_info → needs_work 

First off, I changed the status because there was no evidence that people had run any timings. This is why I changed it to needs_info
. I never trust code that should be faster to really be faster; overhead and idiosyncrasies of python can make things slower, even if asymptotically it is a better algorithm (my goto example is sorting, for (very) small lists, we just use bubble sort because of overhead). Also the algorithm to check that the finite poset is a lattice has changed (using has_top
and has_bottom
instead of the matrix).
Categories also can carry mathematical information as well, in particular for morphisms. The issue I'm raising about why the method needs to be deprecated is this. Suppose I have some personal code for a finite poset that does not inherit from FinitePoset
, but is a parent belonging to the category of FinitePosets
. Thus I have is_lattice
from the category. However, with this patch, all of a sudden my code is (horribly) broken because I no longer have the is_lattice
method.
There is likely some duplication from things in FinitePoset
that should be up in the category coming from the initial implementation of the class and when we transitioned to using categories. So what should happen is you should delete the method in the FinitePoset
class (which doesn't need a deprecation because you get it from the category).
comment:18 followup: 19 Changed 8 years ago by
Replying to ncohen:
Please don't change the status of a ticket that has been reviewed unless you see something which is actually wrong. Something more important than moving a 'for' around.
But Travis had also other points. It does not bother me, because this is an enhancement, not a bug (and nothing like changing O(2^n)
to O(n^2)
or similar).
I don't quite get this category thing. For example there is no category for semilattices, but there is for lattices if I remember correctly. But anyways, I'll put a deprecation to categories code.
comment:19 Changed 8 years ago by
Replying to jmantysalo:
I don't quite get this category thing. For example there is no category for semilattices, but there is for lattices if I remember correctly.
Well, no one currently has a need for those categories, or at least could put any generic code in them.
But anyways, I'll put a deprecation to categories code.
I think you're better off removing the one in FinitePoset
and reinstating the category one; no deprecation needed. (It's like moving the method up in the class hierarchy.)
comment:20 Changed 8 years ago by
Commit:  a649be931b249028ff1e5961fc948c2daf50c695 → 391c03bcc290824c78f165d1623baaf1d921734d 

Branch pushed to git repo; I updated commit sha1. New commits:
391c03b  Rollback: is_lattice() to categories.

comment:21 followup: 22 Changed 8 years ago by
Status:  needs_work → needs_review 

Rollback done, for
moved to other line.
Is it so that function on "real" class overrides function with same name in category? If so, then in principle there could be meet_matrix()
defined on category  it would loop over elements and construct a matrix. Basic implementation of lattice would only have meet()
, but better on could have it's own and better meet_matrix()
(?) This is basically what could be done in good old C++.
Anyways, this is now ready for review. Another thing is making documentation better. There is simply no point to make user to look different places for is_meet_semilattice()
and is_lattice()
.
comment:22 Changed 8 years ago by
Replying to jmantysalo:
Rollback done,
for
moved to other line.
Thanks.
Is it so that function on "real" class overrides function with same name in category? If so, then in principle there could be
meet_matrix()
defined on category  it would loop over elements and construct a matrix. Basic implementation of lattice would only havemeet()
, but better on could have it's own and bettermeet_matrix()
(?) This is basically what could be done in good old C++.
Yes, that's correct. Such a method would be a good benefit, although it might be good for it to also be an enumerated set. However a lattice morphism is stronger than a poset morphism, in that we must also have f(a ^ b) = f(a) ^ f(b)
and similarly for joins. See http://en.wikipedia.org/wiki/Lattice_(order). So for two lattices L,P
, we have Hom(L, P) <= Hom(L, P, category=Posets())
(the first one is the category of Lattices
).
Anyways, this is now ready for review. Another thing is making documentation better. There is simply no point to make user to look different places for
is_meet_semilattice()
andis_lattice()
.
How most (from my experience) people get documentation is interactively (i.e. P.is_lattice?
), so it doesn't make a difference where the method is located.
comment:23 Changed 8 years ago by
Reviewers:  Nathann Cohen → Nathann Cohen, Travis Scrimshaw 

Status:  needs_review → positive_review 
comment:24 Changed 8 years ago by
Branch:  u/jmantysalo/poset___latticeposet___meet_join_matrix_algorithm → 391c03bcc290824c78f165d1623baaf1d921734d 

Resolution:  → fixed 
Status:  positive_review → closed 
A slightly better(?) version for
_meet()
is done. Somebody could check if I did something stupid.It seems to already have a complexity on
O(n^2.5)
. I'm not sure if it would be much faster to just check if a poset is meetsemilattice. Probably no.New commits:
Slight simplification for meetmatrix.