Opened 5 years ago
Closed 5 years ago
#19123 closed enhancement (fixed)
LatticePoset: add is_vertically_decomposable
Reported by:  jmantysalo  Owned by:  

Priority:  major  Milestone:  sage7.0 
Component:  combinatorics  Keywords:  
Cc:  ncohen, tscrim, kdilks  Merged in:  
Authors:  Jori Mäntysalo  Reviewers:  Kevin Dilks 
Report Upstream:  N/A  Work issues:  
Branch:  bf4d108 (Commits)  Commit:  bf4d108440d0533d57cd433d0f0432fab630d193 
Dependencies:  Stopgaps: 
Description (last modified by )
This patch adds a function is_vertically_decomposable
to finite lattices.
For testing see https://oeis.org/A058800 ; for example
sum([1 for L in Posets(6) if L.is_lattice() and not LatticePoset(L).is_vertically_decomposable()])
returns 7 as it should.
There is a place for possible optimization: If there is, say, covering relations bottom > 5
, 3 > 8
and 7 > top
, is suffices to show that the lattice is not vertically decomposable. This might be faster on average. Now the complexity is linear to number of covering relations.
Change History (53)
comment:1 Changed 5 years ago by
 Branch set to u/jmantysalo/vertically_decomposable
comment:2 Changed 5 years ago by
 Cc ncohen added
 Commit set to 0d472a68c9edf4ddea1404ff0cb6d2f508de55d0
 Status changed from new to needs_review
comment:3 followups: ↓ 4 ↓ 46 Changed 5 years ago by
Sounds good, but don't you think it may be useful to *know* where the poset splits? Also, why is it only defined for lattices? The algorithm works in all cases.
I did not test it, but from the code's look I am not sure that it works for the chain of length 2, as the docstring indicates. Could you add a doctest for that?
Nathann
comment:4 in reply to: ↑ 3 ; followup: ↓ 5 Changed 5 years ago by
 Status changed from needs_review to needs_work
Replying to ncohen:
Sounds good, but don't you think it may be useful to *know* where the poset splits?
Yes, I think that will be usefull. For posets we have is_connected()
, connected_components()
and disjoint_union()
. I guess we should have is_vertically_decomposable()
, vertically_indecomposable_parts()
and vertical_sum()
for lattices.
There are of course other options, like having a function (this one, with an argument?) returning list of "decomposition elements". The user could then run interval()
on them to get parts.
Also, why is it only defined for lattices? The algorithm works in all cases.
How should it be defined on nonconnected posets? And I am not sure if this works with nonbounded posets; I thinked about bounded ones when writing this.
I did not test it, but from the code's look I am not sure that it works for the chain of length 2, as the docstring indicates. Could you add a doctest for that?
Arghs! You are right, of course. I forget the special case when writing the code. I'll correct it.
(Btw, this would be nice exercise of (totally unneeded) optimization. One should not need to look for all edged of Hasse diagram to see that a poset is indecomposable.)
comment:5 in reply to: ↑ 4 ; followup: ↓ 6 Changed 5 years ago by
There are of course other options, like having a function (this one, with an argument?) returning list of "decomposition elements".
+1 to that.
How should it be defined on nonconnected posets? And I am not sure if this works with nonbounded posets; I thinked about bounded ones when writing this.
Hmmm, okay okay... I attempted to write a definition, but indeed for nonlattices you have 1000 different cornercases, and th definition would be a mess.
(Btw, this would be nice exercise of (totally unneeded) optimization. One should not need to look for all edged of Hasse diagram to see that a poset is indecomposable.)
What do you mean? Your algorithm looks very reliable. I do not see it waste much.
Nathann
comment:6 in reply to: ↑ 5 ; followup: ↓ 7 Changed 5 years ago by
Replying to ncohen:
There are of course other options, like having a function (this one, with an argument?) returning list of "decomposition elements".
+1 to that.
OK. What should be the name of the argument? certificate
? give_me_the_list=True
?
How should it be defined on nonconnected posets? And I am not sure if this works with nonbounded posets; I thinked about bounded ones when writing this.
Hmmm, okay okay... I attempted to write a definition, but indeed for nonlattices you have 1000 different cornercases, and th definition would be a mess.
Except for the 2element lattice there is one simple definition that generalizes this:
any(P.cover_relations_graph().is_cut_vertex(e) for e in P)
But in any case, it is easy to move this to posets later if we want so.
(Btw, this would be nice exercise of (totally unneeded) optimization. One should not need to look for all edged of Hasse diagram to see that a poset is indecomposable.)
What do you mean? Your algorithm looks very reliable. I do not see it waste much.
If the poset has coverings 2 > 6
and 4 > 9
, then no element 3..8
can be a decomposition element. After founding, say, 2 > 6
we could check 5 >
, 4 >
and so on. But after founding 4 > 9
we should have a somewhat complicated stack to skip rechecking biggest covers of 4
and 5
. I guess that the algorithm would be slower in reality, but I am quite sure that it would be better in some theoretical meaning.
comment:7 in reply to: ↑ 6 ; followup: ↓ 10 Changed 5 years ago by
OK. What should be the name of the argument?
certificate
?give_me_the_list=True
?
Isn't there a terminology for those points? If it is only for lattices, maybe you could have return_cutvertices=True
or something?
Except for the 2element lattice there is one simple definition that generalizes this:
any(P.cover_relations_graph().is_cut_vertex(e) for e in P)
Wouldn't work for a poset on three elements, one being greater than the two others (which are incomparable).
If the poset has coverings
2 > 6
and4 > 9
, then no element3..8
can be a decomposition element. After founding, say,2 > 6
we could check5 >
,4 >
and so on. But after founding4 > 9
we should have a somewhat complicated stack to skip rechecking biggest covers of4
and5
. I guess that the algorithm would be slower in reality, but I am quite sure that it would be better in some theoretical meaning.
HMmm... Skipping some edges without additional assumption on the order in which they are returned? I do not know... This is not so bad, for the moment :)
Nathann
comment:8 Changed 5 years ago by
 Commit changed from 0d472a68c9edf4ddea1404ff0cb6d2f508de55d0 to 893ecc133183398f0932e02c146f235230784915
Branch pushed to git repo; I updated commit sha1. New commits:
893ecc1  Added an option to get "decomposing elements".

comment:9 followup: ↓ 29 Changed 5 years ago by
You don't have to write this algorithm twice to make it work in all situations. Once is enough. And if you are worried of the cost of a 'if' inside of the loop, then you should not be writing Python code.
Furthermore, be careful with '::' as they are not needed after an INPUT block. Build the doc to check it.
Nathann
comment:10 in reply to: ↑ 7 Changed 5 years ago by
Now it should work with empty lattice, 1element lattice and 2element lattice. There is backend ready for extending the function in lattices.py
. I may modify it as suggested by Nathann at comment 9. But the more important question:
How should we exactly define "decomposing elements"? Let's start with
Posets.ChainPoset(2).ordinal_sum(Posets.BooleanLattice(3), labels='integers')
Is 0
a decomposing element? What are "components" for the lattice? Maybe 01
, 12
and 29
. But then, what are components of 2element lattice?
Replying to ncohen:
If the poset has coverings
2 > 6
and4 > 9
, then no element3..8
can be a decomposition element. After founding, say,2 > 6
we could check5 >
,4 >
and so on. But after founding4 > 9
we should have a somewhat complicated stack to skip rechecking biggest covers of4
and5
. I guess that the algorithm would be slower in reality, but I am quite sure that it would be better in some theoretical meaning.HMmm... Skipping some edges without additional assumption on the order in which they are returned?
I dont' mean that. If the lattice has 100
elements, then 0
is the bottom and 99
is the top. If the lattice has coverings 0 > 37
, 34 > 88
and 77 > 99
, then it is not vertically decomposable. There might be faster way to find those coverings than going throught all elements. But the code would be much more complicated.
comment:11 followup: ↓ 13 Changed 5 years ago by
Could you also add to your docstring a reference toward a textbook that defines this notion?
comment:12 Changed 5 years ago by
 Commit changed from 893ecc133183398f0932e02c146f235230784915 to ca909a0c05fee489a071ff672b9f3b5392ba8158
Branch pushed to git repo; I updated commit sha1. New commits:
ca909a0  Indentation of INPUT block.

comment:13 in reply to: ↑ 11 Changed 5 years ago by
 Cc tscrim added
 Description modified (diff)
Replying to ncohen:
Could you also add to your docstring a reference toward a textbook that defines this notion?
Duh. Counting Finite Lattices by Heitzig and Reinhold defines it "  contains an element which is neither the greatest not the least element of L but comparable to every element of L." On the other hand, On the number of distributive lattices by Erné and (same) Heitzig and Reinhold says "  if it is either a singleton or the vertical sum of two nonempty posets  ", and vertical sum on two twoelement lattice by their definition is the twoelement lattice.
I select tscrim as another random victim. Travis, should we define the twoelement lattice to be vertically decomposable or indecomposable?
(Or raise OtherError("developers don't know how to define this")
? :=)
)
comment:14 Changed 5 years ago by
OEIS uses the definition where the twoelement lattice is vertically indecomposable: https://oeis.org/A058800. Does this suffice as a base for the definition?
comment:15 Changed 5 years ago by
Helloooooooo !
Yeah yeah I guess. Could you just add a link in the doc toward a textbook/paper that defines it the way you use it?
(Or raise OtherError?("developers don't know how to define this")?
We have had very nonenlightening debates here about whether the empty graph is connected or not. In such a situation, I would add such a warning rather than have those stupid conversations :P
Nathann
comment:16 Changed 5 years ago by
 Commit changed from ca909a0c05fee489a071ff672b9f3b5392ba8158 to 667173c9117e910378f3bc959821a7922a1f9c39
Branch pushed to git repo; I updated commit sha1. New commits:
667173c  Options to is_vertically_decomposable().

comment:17 Changed 5 years ago by
 Description modified (diff)
This code should now work.
I still don't know how to make the user interface... For posets we have booleanvalued is_connected()
and subposetsvalued connected_components()
. But what should then be the function returning only "decomposing elements". I will ask in sagedevel.
Comments on documentation are welcome.
comment:18 followup: ↓ 20 Changed 5 years ago by
return_type vs return_elements.
comment:19 Changed 5 years ago by
 Commit changed from 667173c9117e910378f3bc959821a7922a1f9c39 to 5e7224a20d6341a09821779ebdeb38cbf0130817
Branch pushed to git repo; I updated commit sha1. New commits:
5e7224a  Check for 0 and 1element lattices.

comment:20 in reply to: ↑ 18 ; followup: ↓ 21 Changed 5 years ago by
Replying to ncohen:
return_type vs return_elements.
But they are different things. "Internal" function in hasse_diagram.py
has only one yes/no argument, so a Boolean seems right. "Interface" function in lattices.py
has three possible inputs.
comment:21 in reply to: ↑ 20 Changed 5 years ago by
But they are different things. "Internal" function in
hasse_diagram.py
has only one yes/no argument, so a Boolean seems right. "Interface" function inlattices.py
has three possible inputs.
Sorry, I removed my comment on the argument's type right after I posted it, it was a mistake. The one I left, however, is about the fact that the argument that appears in the doc is not the one that appears in the function's definition.
Nathann
comment:22 Changed 5 years ago by
 Commit changed from 5e7224a20d6341a09821779ebdeb38cbf0130817 to d42f0ab3e5bba8a005407f9e864ac6fa5f420318
Branch pushed to git repo; I updated commit sha1. New commits:
d42f0ab  Splitted function, added examples. Also categorized the index of function.

comment:23 Changed 5 years ago by
I will wait until #17226 gets to beta, and then rebase this. (Forgot that it was not there yet.) This will also categorize the index of functions.
I split the function to two parts. I will also wait if somebody comments this on sagedevel. I don't know what should be the name of argument for vertical_decomposition()
.
So this is open for comments and de facto ready for review, but not de iure in needs_review phase.
comment:24 Changed 5 years ago by
 Branch u/jmantysalo/vertically_decomposable deleted
 Commit d42f0ab3e5bba8a005407f9e864ac6fa5f420318 deleted
comment:25 Changed 5 years ago by
 Branch set to u/jmantysalo/vertically_decomposable2
comment:26 Changed 5 years ago by
 Commit set to c0455d6e94d30e62494888814bdea5c3c8f2be3f
Branch pushed to git repo; I updated commit sha1. New commits:
c0455d6  Added vertical decomposition of the lattice. Also change index of function.

comment:27 Changed 5 years ago by
 Status changed from needs_work to needs_review
OK, here is one possible way to split the functionality. Ready for review.
comment:28 Changed 5 years ago by
 Commit changed from c0455d6e94d30e62494888814bdea5c3c8f2be3f to abe1642631b63035568761fd34699929f8afdc8f
Branch pushed to git repo; I updated commit sha1. New commits:
abe1642  Simplification as suggested by ncohen.

comment:29 in reply to: ↑ 9 Changed 5 years ago by
 Status changed from needs_review to needs_work
Replying to ncohen:
You don't have to write this algorithm twice to make it work in all situations. Once is enough.
Done this. Compiling, will change to needs_review if this seems to work.
comment:30 Changed 5 years ago by
 Commit changed from abe1642631b63035568761fd34699929f8afdc8f to 0abc93861d121a172abfb11203821d34fecfd78e
Branch pushed to git repo; I updated commit sha1. New commits:
0abc938  Special cases for empty, one and twoelement lattices.

comment:31 Changed 5 years ago by
 Status changed from needs_work to needs_review
comment:32 Changed 5 years ago by
Nathann, what about this. You already read the code and the 2element lattice case is now documented. Hence there is two questions left:
 Is the thematic index of functions OK in lattices?
 Is this splitting of functionality OK?
comment:33 Changed 5 years ago by
Jori,
I thought a bit before answering your email, because the reason I had not done anything on the ticket during the last 6 days is that I had chosen to not work on it anymore. I do not often "forget" things like tickets in needs_review: my mail inbox contains all the things I must attend to, and they all remain there until I do what I think I should do with them.
Among the reasons that led me there is that nothing specific makes your code invalid, and I have no reason to ask you to change it just because it does not suit my taste. I like things short, simple, concise. Three functions for only one feature is beyond me, it angers me by itself.
If I were to write it, you would have one Lattice method which would directly
work on the hasse diagram, with a return_recomposition
boolean flag to return
lists instead of boolean answers. One function, 20 lines, end of the story.
Right now, the Lattice method vertical_decomposition
contains around 20 lines
of code, none of which has the slightest interest to me. It's just wrapping
things into other things, and testing things that are already tested elsewhere.
What I know, however, is that it is impossible for you to get any kind of code into Sage and to work with it unless you have somebody to review your code. I surely know that. Depending on what I work on, depending on the times, it is either easy or hard to get anything in there, and from time to time I think that it would be better if you were allowed to put any code that you like into Sage without needing reviewers like me who drag their feet at every occasion.
Also, I admit that I do not have the energy to discuss the implementation details endlessly, and I also hate that this process may require you to implement code only because the only reviewer you have has a different taste.
Truth is, I don't want to be the reason why you cannot work properly on Sage's code, and I don't have a lot of ways out as not many would do the reviewing job otherwise. So I will try this: I will implement this as is the most natural to me, and you can feel free to not use it if you do not like it. Let's see how it works.
Sorry for the painful reviews.
Nathann
P.S.: the code is at u/ncohen/19123
comment:34 Changed 5 years ago by
Hmm... I continue to think. Or hope that somebody else reviews this.
I hope that having this on hasse_diagram.py
is useful later  it can be a quick optimization before frattini_sublattice
.
comment:35 Changed 5 years ago by
 Status changed from needs_review to needs_work
does not apply, needs rebase
comment:36 Changed 5 years ago by
 Commit changed from 0abc93861d121a172abfb11203821d34fecfd78e to 1356d17b1bd124fa573767ee8b7e5d50798004c0
Branch pushed to git repo; I updated commit sha1. New commits:
1356d17  Rebasing.

comment:37 Changed 5 years ago by
Err. Terminology nazi here: what you did is a 'merge'. A rebase is a difference operation which moves the commits around.
Nathann
comment:38 Changed 5 years ago by
 Status changed from needs_work to needs_review
Merged. Sorry for wrong term.
comment:39 Changed 5 years ago by
 Cc kdilks added
Kevin, if you are interested in docs, you might want to review this. It does some polishing together with adding little new functionality.
comment:40 Changed 5 years ago by
I still think that formal definitions should come first, without being labelled as formal definitions, and then informal definitions can come after.
comment:41 followup: ↓ 42 Changed 5 years ago by
I'm not sure if I like the backend code living in hasse_diagram.py
. Even if the code applies to more than lattices, you seem to still be making assumptions about the poset being bounded. Plus the initial docstring there is written in a way that implies it only works for lattices.
comment:42 in reply to: ↑ 41 Changed 5 years ago by
Replying to kdilks:
I still think that formal definitions should come first, without being labelled as formal definitions, and then informal definitions can come after.
OK, I can change that.
Replying to kdilks:
I'm not sure if I like the backend code living in
hasse_diagram.py
. Even if the code applies to more than lattices, you seem to still be making assumptions about the poset being bounded. Plus the initial docstring there is written in a way that implies it only works for lattices.
I think that all code in hasse_diagram.py
is "internal", i.e. it is user's fault if something break for direct call to it.
If this is not in hasse_diagram.py
, then I guess it must be copied if I want to optimize frattini_sublattice()
with it. Or linear_extensions_number()
maybe?
comment:43 Changed 5 years ago by
 Commit changed from 1356d17b1bd124fa573767ee8b7e5d50798004c0 to b408d0c9dd34b9c07ca3472d7e12615dc7072457
Branch pushed to git repo; I updated commit sha1. New commits:
b408d0c  Change order of formal and informal definition.

comment:44 Changed 5 years ago by
Better docstring now?
If this seems hard one to decide, then I can split the (nonrelating) part that rearranges the index of functions.
comment:45 Changed 5 years ago by
ping c 1 Kevin
. This could be nice to have before #18511, as this modifies the index of function.
(Funny. I have a poset of dependencies between posetrelated tickets.)
comment:46 in reply to: ↑ 3 Changed 5 years ago by
comment:47 Changed 5 years ago by
 Milestone changed from sage6.9 to sage7.0
 Status changed from needs_review to needs_work
Documentation part (i.e. index of functions) done in #19854, so this one needs work.
Also this should be thinked about. There is also #19659 waiting, and in principle it is same thing as this one; a poset that is also a lattice can be expressed as an ordinal sum of two posets only if it vertically decomposable. At least http://users.cecs.anu.edu.au/~bdm/papers/posets.pdf by Brinkmann and McKay? uses term "vertically decomposable" with nonlattice posets.
(Actually after #19659 it is easy to make a simple function for #19215, and then use it as a "precompiler" for #14126. But that's another story.)
comment:48 Changed 5 years ago by
 Branch changed from u/jmantysalo/vertically_decomposable2 to public/19123
 Commit changed from b408d0c9dd34b9c07ca3472d7e12615dc7072457 to 0ee8b96dbb37a87c5c43b4fd0ad6c7ee8c8a97c4
 Status changed from needs_work to needs_review
New commits:
0ee8b96  Merge branch 'u/jmantysalo/vertically_decomposable2' into 7.1.rc0

comment:49 followup: ↓ 51 Changed 5 years ago by
Minor grammatical corrections:
 In
vertical_decomposition()
, 'Letd_1, \ldots , d_n
be elements comparable to every element of the lattice, excluding the top and bottom elements.' Should be rephrased as 'Letd_1, \ldots, d_n
be elements (excluding the top and bottom elements) comparable to every element of the lattice.' The original version makes it sound like the top and bottom elements are being excluded from the set of things thatd_1...d_n
need to be comparable to, instead of being excluded from the setd_1...d_n
itself.
 Immediately following that, 'Let
b
be THE bottom element andt
be the top element.'
 'Informally said, this returns the lattice SPLIT INTO parts AT every singleelement "cutting point".'
 Under
INPUT:
, 'return the list OF decomposing elements'.
 In the definition of
is_vertically_decomposable()
, 'A lattice is vertically decomposable if it has an element that is comparable to all elements and is NEITHER the bottom NOR the top element.'
Besides that, I think I'm happy with it. I'll just need to check the rendered documentation once those changes are made.
comment:50 Changed 5 years ago by
 Commit changed from 0ee8b96dbb37a87c5c43b4fd0ad6c7ee8c8a97c4 to bf4d108440d0533d57cd433d0f0432fab630d193
Branch pushed to git repo; I updated commit sha1. New commits:
bf4d108  Docstring corrections.

comment:51 in reply to: ↑ 49 Changed 5 years ago by
Replying to kdilks:
Minor grammatical corrections:
Thanks! Done those.
 'Informally said, this returns the lattice SPLIT INTO parts AT every singleelement "cutting point".'
These are hard ones... In Finnish 'hila'='lattice', 'hilassani'='in my lattice' etc.
comment:52 Changed 5 years ago by
 Reviewers set to Kevin Dilks
 Status changed from needs_review to positive_review
comment:53 Changed 5 years ago by
 Branch changed from public/19123 to bf4d108440d0533d57cd433d0f0432fab630d193
 Resolution set to fixed
 Status changed from positive_review to closed
Quite easy one. Nathann selected as a random victim for a possible reviewer.
:=)
New commits:
Added function is_vertically_decomposable().
Spaces on empty lines.