LatticePoset: add function to get all sublattices

[jmantysalo]

This patch will add a function that gives all sublattices of a lattice.

[jmantysalo]

Travis selected as a random victim for review.

---

New commits:

​1bb87bd

Add sublattices().

[tscrim]

I think you should use a backtracking algorithm instead of a recursion. It will be faster (and you don't have to constantly get things like self.cardinality()), never run up against the Python maximum recursion limit, and have better input (which set() and 0 should be defaults anyways).

[jmantysalo]

Replying to tscrim:

I think you should use a backtracking algorithm instead of a recursion. It will be faster (and you don't have to constantly get things like self.cardinality()), never run up against the Python maximum recursion limit, and have better input (which set() and 0 should be defaults anyways).

Maximun recursion limit is 999 by default, and that is too small only if we have a ChainPoset(n) with n > 999; recursion stack will have at most as many steps as the lattice has elements. And it will have 2^999 sublattices anyway, so this is not valid argument.

For example after B4 = Posets.BooleanLattice(4) it takes 0,02 seconds to count 732 sublattices with len(list(B4._hasse_diagram.sublattices_iterator(set(), 0))), whereas it took 1,13 seconds with len(B4.sublattices()). So if one wants to optimize lattices, then bottleneck is usually not in hasse_diagram.py but in lattices.py.

Of course I can change this to use backtracking, but... Then why not move this to static sparce graphs class, if we really want as fast code as possible?

[tscrim]

Replying to jmantysalo:

Replying to tscrim:

I think you should use a backtracking algorithm instead of a recursion. It will be faster (and you don't have to constantly get things like self.cardinality()), never run up against the Python maximum recursion limit, and have better input (which set() and 0 should be defaults anyways).

Maximun recursion limit is 999 by default, and that is too small only if we have a ChainPoset(n) with n > 999; recursion stack will have at most as many steps as the lattice has elements. And it will have 2^999 sublattices anyway, so this is not valid argument.

People could want to do some partial tests on some really big example of a lattice or wanted to run a month-long-type computation on a big lattice (of which, there are a number of examples of finite exceptional cases that I come across in my research where the easiest way to prove things can be to do long computations).

For example after B4 = Posets.BooleanLattice(4) it takes 0,02 seconds to count 732 sublattices with len(list(B4._hasse_diagram.sublattices_iterator(set(), 0))), whereas it took 1,13 seconds with len(B4.sublattices()). So if one wants to optimize lattices, then bottleneck is usually not in hasse_diagram.py but in lattices.py.

I don't disagree with this, but you should not be creating the lattice by using the LatticePoset but directly creating the necessary data and passing it to FiniteLatticePoset. This avoids the extra overhead and checks that is in the Poset code.

Of course I can change this to use backtracking, but... Then why not move this to static sparce graphs class, if we really want as fast code as possible?

I have no inherent objects to this, but does the static sparse digraph code have the capacity to do the meet and joins?

[jmantysalo]

Replying to tscrim:

Replying to jmantysalo:

Replying to tscrim:

I think you should use a backtracking algorithm instead of a recursion. It will be faster (and you don't have to constantly get things like self.cardinality()), never run up against the Python maximum recursion limit, and have better input (which set() and 0 should be defaults anyways).

Maximun recursion limit is 999 by default, and that is too small only if we have a ChainPoset(n) with n > 999; recursion stack will have at most as many steps as the lattice has elements. And it will have 2^999 sublattices anyway, so this is not valid argument.

People could want to do some partial tests on some really big example of a lattice or wanted to run a month-long-type computation on a big lattice (of which, there are a number of examples of finite exceptional cases that I come across in my research where the easiest way to prove things can be to do long computations).

Well, now it took only 20 seconds to make ChainPoset(1000). So yes, it is theoretically possible to run this kind of computations. But then, recursion limit can be changed.

Of course I can change this to use backtracking, but... Then why not move this to static sparce graphs class, if we really want as fast code as possible?

I have no inherent objects to this, but does the static sparse digraph code have the capacity to do the meet and joins?

No, but that could be added. Or actually copied from current file. For Frattini sublattices that would actually make sense.

---

Basic questions about all reviews: 1) Is Sage better with this or without? 2) If with, is there some easy steps to make it still better?

[tscrim]

Replying to jmantysalo:

Replying to tscrim:

Replying to jmantysalo:

Of course I can change this to use backtracking, but... Then why not move this to static sparce graphs class, if we really want as fast code as possible?

I have no inherent objects to this, but does the static sparse digraph code have the capacity to do the meet and joins?

No, but that could be added. Or actually copied from current file. For Frattini sublattices that would actually make sense.

However, meet and join doesn't quite make sense to have it there mathematically AFAIK. Although by cythonizing hasse_diagram.py, we should get most of possible speed without doing really much in the way of changes.

Basic questions about all reviews: 1) Is Sage better with this or without? 2) If with, is there some easy steps to make it still better?

I am going to treat this as you telling me your process for reviewing. Otherwise I would take that a very insulting comment to me which you are telling me how to do my review.

[jmantysalo]

Replying to tscrim:

I have no inherent objects to this, but does the static sparse digraph code have the capacity to do the meet and joins?

No, but that could be added.

However, meet and join doesn't quite make sense to have it there mathematically AFAIK. Although by cythonizing hasse_diagram.py, we should get most of possible speed without doing really much in the way of changes.

True, but I think that there was obstackle for cythonizing. Something with inheritance, I think; I discussed about this with Nathann Cohen maybe a two years ago.

Basic questions about all reviews: 1) Is Sage better with this or without? 2) If with, is there some easy steps to make it still better?

I am going to treat this as you telling me your process for reviewing. Otherwise I would take that a very insulting comment to me which you are telling me how to do my review.

Sorry. I don't intend to insult. (But also I does not so much english words to make my expressions smoother.)

I was just trying to say what developer guide says: "Please refrain from additional feature requests or open-ended discussion about alternative implementations."

[tscrim]

Replying to jmantysalo:

Replying to tscrim:

However, meet and join doesn't quite make sense to have it there mathematically AFAIK. Although by cythonizing hasse_diagram.py, we should get most of possible speed without doing really much in the way of changes.

True, but I think that there was obstackle for cythonizing. Something with inheritance, I think; I discussed about this with Nathann Cohen maybe a two years ago.

I don't see anything that would prevent a cythonization; the HasseDiagram class only has single inheritance (and cython probably has improved since when you discussed this).

Basic questions about all reviews: 1) Is Sage better with this or without? 2) If with, is there some easy steps to make it still better?

I am going to treat this as you telling me your process for reviewing. Otherwise I would take that a very insulting comment to me which you are telling me how to do my review.

Sorry. I don't intend to insult. (But also I does not so much english words to make my expressions smoother.)

I know you didn't, but it first seemed like you were trying to tell me how to review this. My reply was condescending, to which I apologize as well.

I was just trying to say what developer guide says: "Please refrain from additional feature requests or open-ended discussion about alternative implementations."

I don't think we are in an open-ended discussion because I am proposing a (single) concrete/explicit alternative implementation. While I am not strictly opposed to the current implementation, I think there is a relatively easy way to improve it. I might have some time to change the algorithm today, if you're okay with it (I'm on French time for this week and the next).

[jmantysalo]

Replying to tscrim:

I might have some time to change the algorithm today, if you're okay with it (I'm on French time for this week and the next).

Of course. I can review it then, and hopefully you can check docstrings I wrote.

Btw, I plan to add lattice_of_sublattices(). Hence the function in hasse_diagram.py should return something like sets, tuples etc.

[jmantysalo]

Just pinging...

[jmantysalo]

ping.

[tscrim]

So, I just haven't had time to do the algorithm change that I wanted. This works as claimed (although I was not able to completely prove its correctness). Thus this works as a first implementation, and so positive review (I can change it to a backtrak on a follow-up ticket if and when I have more time).

PS - Sorry it took so long.

[jmantysalo]

Thanks Travis!

Here is the followup: #20921.