Poset: inverse function of ordinal_sum()

[jmantysalo]

I suggest adding a function that decomposes a poset "vertically", i.e. has same relationship to ordinal_sum() as connected_components() has to disjoint_union(). This ticket contains code for the "backend", i.e. to hasse_diagram.py.

I am not sure about the name. Maybe ordinal_decomposition. Or maybe it could be ordinal_components or vertical_components.

Bonus question: What should be the name for inverse function of ordinal_product()?

[jmantysalo]

New commits:

​d1d6f4b	Added ordinal_sum_decomposition().
​fcd68b9	Spaces removed.

[git]

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

​4358a5a

Added a "front end"-function for ordinal splitting.

[jmantysalo]

Dime, do you got a spare time for quite easy(?) review?

[dimpase]

it's the 1st time I see "ordinal sum". So it's not going to be quick for me here...

[jmantysalo]

Replying to dimpase:

it's the 1st time I see "ordinal sum". So it's not going to be quick for me here...

OK. Ordinal sum is actually very simple thing: Just put one poset below another. (Defined in Enumerative Combinatorics section 3.2 paragraph 1.)

[jmantysalo]

Nathann, can you check this? This is quite similar to vertical decomposition code in lattices.

I think that this could be useful in it's own, hence "frontend" in posets.py. But this is also one way to get series-parallel decomposition. (Which is one way to get faster count of linear extensions.)

[ncohen]

Why do you think it should belong to the HasseDiagram class?

[jmantysalo]

Replying to ncohen:

Why do you think it should belong to the HasseDiagram class?

Other possibility would be posets.py. But then recursive ordinal_decomposition-connected_components would unnecessarily create intermediate posets instead of HasseDiagrams. It is slower.

And series-parallel decomposition is nothing more than just trying "ordinal and parallel decomposition" until there is nothing that can be done.

[ncohen]

Other possibility would be posets.py. But then recursive ordinal_decomposition-connected_components would unnecessarily create intermediate posets instead of HasseDiagrams. It is slower.

I don't see why. Can't you access _hasse_diagram directly?

Nathann

[jmantysalo]

Replying to ncohen:

I don't see why. Can't you access _hasse_diagram directly?

Without copying code? Then ordinal decomposition function in posets.py should return HasseDiagram, which sounds odd.

[ncohen]

Without copying code?

I do not understand this sentence.

What I meant is that your method could be a Poset method, which would access self._hasse_diagram directly.

Then ordinal decomposition function in posets.py should return HasseDiagram, which sounds odd.

Why do you insist on having it return a Hasse Diagram? If you want the decomposition feature without having to build posets, then you could have a 'as_posets=True` optional argument in the Poset method, which would either return a list of posets or return a partition of the elements.

Nathann

[jmantysalo]

Replying to ncohen:

Then ordinal decomposition function in posets.py should return HasseDiagram, which sounds odd.

Why do you insist on having it return a Hasse Diagram? If you want the decomposition feature without having to build posets, then you could have a 'as_posets=True` optional argument in the Poset method, which would either return a list of posets or return a partition of the elements.

This is true. But then, what's wrong with having functions at hasse_diagram.py?

(In general it makes possible to do a little optimization for advanced users. There is not always need to build poset object, if some filtering can be done in Hasse diagrams.)

[ncohen]

This is true. But then, what's wrong with having functions at hasse_diagram.py?

I don't believe that a designs that requires you to implement two functions every time you need one is a good thing.. Additionally, the docstring of the HasseDiagram function that currently appears in this branch starts with Return the ordinal decomposition of the poset. This method screams that it does not belong there.

(In general it makes possible to do a little optimization for advanced users. There is not always need to build poset object, if some filtering can be done in Hasse diagrams.)

You do not need to build posets even though you are a Poset method. Because you can access _hasse_diagram directly, and because there is no constraint whastoever on the type of what you should return. You can have optional arguments to return the result as whatever you want: posets, digraphs, partitions...

And if the Poset constructor was even remotely sensible you would have no reason to *fear* the time loss in the poset constructor.

Nathann

[jmantysalo]

Replying to ncohen:

This is true. But then, what's wrong with having functions at hasse_diagram.py?

I don't believe that a designs that requires you to implement two functions every time you need one is a good thing.. Additionally, the docstring of the HasseDiagram function that currently appears in this branch starts with Return the ordinal decomposition of the poset. This method screams that it does not belong there.

Hasse diagram is a poset with some constraints... I can change that docstring.

But the question remains: What is the meaning of hasse_diagram.py? Whole poset class could be implemented with just a digraph as one member variable. But then I guess we would have more internal functions starting with _. Or more functions returning something actually only useful for internal use.

An example: check (broken!) parameter partial at maximal_chains. It is needed for order_complex. I think that the whole concept of "partial maximal chain" is odd and should be removed. It could have placed in hasse_diagrams.py, which is meant for internal implementation. (Btw, see #18944 - my suggestion to drop partial-option was rejected.)

I think that I can generate something like all posets of size 7 in the same time as all Hasse diagrams of size 8. So it really loses some cpu time to make posets.

[ncohen]

But the question remains: What is the meaning of hasse_diagram.py? Whole poset class could be implemented with just a digraph as one member variable. But then I guess we would have more internal functions starting with _. Or more functions returning something actually only useful for internal use.

What we have now is Poset.X *and* HassDiagram?.X.

An example: check (broken!) parameter partial at maximal_chains. It is needed for order_complex. I think that the whole concept of "partial maximal chain" is odd and should be removed. It could have placed in hasse_diagrams.py, which is meant for internal implementation. (Btw, see #18944 - my suggestion to drop partial-option was rejected.)

The combinat guys have ther own view of the code. Perhaps something like "whatever was once useful to one must be a public method". In the case of very very specific functions, sometimes hard to document properly, I do not believe that it is a good choice.

I think that I can generate something like all posets of size 7 in the same time as all Hasse diagrams of size 8. So it really loses some cpu time to make posets.

I am tired to find ways to not call the constructor because it does things you never asked it to do.

Nathann

[ncohen]

About the algorithm: I don't know if it makes a big difference and if could help with your applications, but there may be something to gain by checking the *degree* of the minimum elements before doing some operations on the sets of neighbors themselves. Just before

+for l in lower:
+    if self.degree_out(l) != len(upper)
+        break
for l in lower:
    if set(self.neighbors_out(l)) != upper:
        break

[git]

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

​01f9e1c

An optimization.

[jmantysalo]

Replying to ncohen:

• - there may be something to gain by checking the *degree* of the minimum elements before doing some operations on the sets of neighbors themselves. - -

Of course. Done.

[ncohen]

Oh right, I had not noticed this 'for/else' problem. If you prefer, you can also do something like:

if (all(self.degree_out(l) == len(upper) for l in lower) and
    all(set(self.neighbors_out(l)) != upper for l in lower):
    cut_points.append(e)

Nathann

[jmantysalo]

Replying to ncohen:

Oh right, I had not noticed this 'for/else' problem. If you prefer, you can also do something like:

if (all(self.degree_out(l) == len(upper) for l in lower) and
    all(set(self.neighbors_out(l)) != upper for l in lower):
    cut_points.append(e)

Is this any more clear? I think that if the code needs clarification, first step would be adding comments. But at least the basic idea is quite clearly said in docstring.

If I do

all(self.degree_out(l) == len(upper) for l in lower)

then len(upper) will be called many times.

[ncohen]

Is this any more clear?

To me it is, but I won't be surprised if it is a matter of taste. It also avoids the 'for/else' trick that I never met anywhere except in Python.

If I do

all(self.degree_out(l) == len(upper) for l in lower)

then len(upper) will be called many times.

I see that you cached it in your code, and there is of course nothing wrong with that.

Nathann

[jmantysalo]

Replying to ncohen:

Is this any more clear?

To me it is, but I won't be surprised if it is a matter of taste. It also avoids the 'for/else' trick that I never met anywhere except in Python.

I can change that, if you want. But actually the code at one function level can always be optimized later. Real question is how to arrange this code. I think that it is fruitless to think about posets.py vs. hasse_diagram.py in context of one specific function. If we want to change it, then we would need to think those files (and lattices.py) as a whole.

So actually I want an answer to two questions: 1) Is Sage better with or without this patch? 2) Is there some trivial things that would make this patch better? Those two are my criteria for giving a positive review.

break-else is really a python special feature. Quite nice sometimes with this kind on mathematical code.

[ncohen]

I can change that, if you want.

I was just suggesting it. If you don't like it, then it's fine.

So actually I want an answer to two questions: 1) Is Sage better with or without this patch? 2) Is there some trivial things that would make this patch better? Those two are my criteria for giving a positive review.

Then it is likely that you would give your patch a positive review.

break-else is really a python special feature. Quite nice sometimes with this kind on mathematical code.

And it was not a problem at all with how it was used before you added the 'degree check'. Nesting two looks a bit unpleasant to me, which is why I suggested this 'all( ... )' thing but I can understand that it only matters to me.

What you need however, is a Poset class with a less wasteful constructor. You seem to use HasseDiagram to this end.

Nathann

[ncohen]

P.S.: From my point of view, there is a 'trivial' change that would make the code better, i.e. have everything inside the poset class. I consider that having it in nother class is only a workaround for the slow constructor.

[jmantysalo]

Of course I could change that, and for the "interface" for this function there would be no change.

But I ask a reverse question: What should be in hasse_diagram.py? What is the big picture of code structure in your vision?

(Dima dropped from cc.)

[ncohen]

But I ask a reverse question: What should be in hasse_diagram.py? What is the big picture of code structure in your vision?

I thought about it for a moment, and I don't even think that I can give you the name of a method that would be specific to the Hasse Diagram and not to the poset. Do you have one in mind?

Nathann

[jmantysalo]

Replying to ncohen:

But I ask a reverse question: What should be in hasse_diagram.py? What is the big picture of code structure in your vision?

I thought about it for a moment, and I don't even think that I can give you the name of a method that would be specific to the Hasse Diagram and not to the poset. Do you have one in mind?

That is why this specific ticket should not be rejected for doing what other similar code already does.

I think that actually almost all code could be at hasse_diagram.py! Hence posets and lattices would be mostly a lightweight (in a code, not in memory footprint...) wrapper handling element labels and checking input. And in longer future there could be cythonized internal implementation, something directly coded like your static sparse graphs backend has.

But I must admit that I have not been straight on this. See for example #19884.

[ncohen]

That is why this specific ticket should not be rejected for doing what other similar code already does.

I only click on positive_review when I am personally satsfied with the code.

I think that actually almost all code could be at hasse_diagram.py!

If Poset inherits from HasseDiagram then that wouldn't be a problem for me. Otherwise I do not see why you would insist on having two functions every time, one of which calls the other.

Nathann

[ncohen]

Actually, could you answer this very central question: why do you believe we should implement every function twice, once in Poset and once in HasseDiagram? Is it only because of the cost of the Poset constructor?

[jmantysalo]

Replying to ncohen:

Actually, could you answer this very central question: why do you believe we should implement every function twice, once in Poset and once in HasseDiagram? Is it only because of the cost of the Poset constructor?

Not only that. Earlier in this ticket you said

Perhaps something like "whatever was once useful to one must be a public method". In the case of very very specific functions, sometimes hard to document properly, I do not believe that it is a good choice.

I think that "visible" poset functions, i.e. those not starting with _, should give meaningful set of operations to do with posets. It does not always directly correspond with good structure for internal functions. So should I add a _-function to posets.py or add a strange option for ordinal_decomposition to be used just for series-parallel decomposition? Both options sounds strange, as the already have "internal" class.

I only click on positive_review when I am personally satsfied with the code.

I know. It's hard to get a positive_review from you, but easy to get performance tips etc. in the process. :=)

[ncohen]

Yooooooo,

I think that "visible" poset functions, i.e. those not starting with _, should give meaningful set of operations to do with posets. It does not always directly correspond with good structure for internal functions. So should I add a _-function to posets.py or add a strange option for ordinal_decomposition to be used just for series-parallel decomposition? Both options sounds strange, as the already have "internal" class.

You seem to say that implementing this function would have you implement a helper function, which you do not think would be user-friendly enough to deserve being public. Could you tell me what this function would do? I do not see what you have in mind. Surely you are not talking of the ordinal_sum_decomposition itself, as you made it publicly available in this branch?

Nathann

[jmantysalo]

Replying to ncohen:

You seem to say that implementing this function would have you implement a helper function, which you do not think would be user-friendly enough to deserve being public. Could you tell me what this function would do? I do not see what you have in mind. Surely you are not talking of the ordinal_sum_decomposition itself, as you made it publicly available in this branch?

It is "public", but in "private" class. Doc for Hasse diagram says "This should not be called directly, use Poset instead - -". (It should say it more clearly, but that's another thing.)

[ncohen]

It is "public", but in "private" class.

Sorry, I was talking of Poset.ordinal_components.

[jmantysalo]

Replying to ncohen:

It is "public", but in "private" class.

Sorry, I was talking of Poset.ordinal_components.

Yes, and it will give you subposets. Implementation is HasseDiagram returns just a list of numbers. And that is what I don't want to make public.

[ncohen]

Yes, and it will give you subposets. Implementation is HasseDiagram returns just a list of numbers. And that is what I don't want to make public.

In 12 I suggested a as_posets=True (or any other name you might prefer) to get a different output, i.e. as a partition of vertices for instance. Wouldn't that solve your problem ?

[jmantysalo]

Replying to ncohen:

Yes, and it will give you subposets. Implementation is HasseDiagram returns just a list of numbers. And that is what I don't want to make public.

In 12 I suggested a as_posets=True (or any other name you might prefer) to get a different output, i.e. as a partition of vertices for instance. Wouldn't that solve your problem ?

Then series-parallel decomposition would call that, and then... create a poset of them? So no luck.

With implementation at HasseDiagram we (read: I) can make a function to make a series-parallel decomposition that does not create Posets recursively.

[jmantysalo]

Example:

N = Poset({0:[2,3], 1:[3]})
P = N.ordinal_product(N)

How to make a series-parallel decomposition of P for counting linear extension, or to check if it has one?

[ncohen]

Then series-parallel decomposition would call that, and then... create a poset of them? So no luck.

With implementation at HasseDiagram we (read: I) can make a function to make a series-parallel decomposition that does not create Posets recursively.

I do not understand a word of what you are saying. Please, I try to make each of my sentences accurate to be sure that I do not get misunderstood, and as it is I can't get a straight answer. I assure you that I spend *minutes* over each of my comments.

I am trying to understand, as I asked in 30, if you need HasseDiagram only because of the slow Poset constructor or if there is another reason. You told me in 35 that you wanted to be able to return something which is *not* a poset, and I said in 36 that you could do so with Poset only. Now the two sentences to which I am replying right now say again that what you want to avoid is the Poset constructor.

Could you confirm that the cost of the Poset constructor is the only thing that bothers you, or else tell me what exactly is the problem? At the moment, I am convinced that the only reason for which you implement everything twice is because you want to avoid building posets. Tell me if I am wrong.

Nathann

[git]

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

​6b98cbf	Unified to one function.
​dc6ea77	Spaces removed from end of lines.

[jmantysalo]

OK, too hard to explain. I give up. Here is a version with only one function.

[ncohen]

OK, too hard to explain.

Then I guess we will have the same conversation again on the next ticket?...

I just went through your code and made small modifications, some to the code some to the doc. Most of the time by removing/shortening things. You are of course welcome to discuss any character of it. Also, you sometimes forget articles 'a/an': I am no expert in english but sometimes they really are necessary to the sentence.

My modifications have been pushed to public/19659.

Could you point me toward a book/paper that uses this "ordinal components" terminology?

Thanks,

Nathann

[ncohen]

(the branch has been rebased, and its history simplified)

[jmantysalo]

Replying to ncohen:

Could you point me toward a book/paper that uses this "ordinal components" terminology?

As I write in the description: I am not sure about the name.

"On the number of distributive lattices" by Marcel Erné, Jobst Heitzig and Jürgen Reinhold (​http://www.kurims.kyoto-u.ac.jp/EMIS/journals/EJC/Volume_9/PDF/v9i1r24.pdf) uses "vertical decomposition". I choose the name to be parallel to connected_components().

[ncohen]

As I write in the description: I am not sure about the name.

Okay okay. I don't trust myself when it comes to Posets, so let's ask.

Frédéric? Jori implemented here a function that decomposes a poset P into components P1,...,P_k such that P is the ordinal sum of the Pi. We are not sure which name should be picked for it, and right now the branch uses the name ordinal_components. What do you think of it? Should it be changed to something different, or is it what people would expect? If you are not sure and know somebody who would, could you add him in Cc?

Thanks,

Nathann

[chapoton]

I would suggest 'is_ordinal_sum', with boolean output, with a certificate option to see a decomposition.

Another possibility would be 'ordinal_sum_decomposition'.

'ordinal_components' is ambiguous because there exists also 'ordinal product' (not yet in sage maybe), besides ordinal sum.

EDIT: maybe 'ordinal_summands' would be ok

[jmantysalo]

Some thoughts, not a clear opinion yet:

We do have ordinal_product already. An "inverse function" of if would be ordinal_factors, I think. Compare to "factoring (undirected) graphs" (done be Nathann IIRC).

certificate=True sounds natural to for example dimension: there is not the set of realizers, just bunch of minimal sets and one of them is returned. For this function we do have exact "components", "parts" or something like that.

There is now is_connected and conneced_components. It would be orthogonal design to have two functions for this one also.

[jmantysalo]

New commits:

​543c4a1	Added ordinal_sum_decomposition().
​548b4eb	trac #19659: Review

[git]

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

​1385d69

Added commas.

[jmantysalo]

Replying to ncohen:

Then I guess we will have the same conversation again on the next ticket?...

This should really be discussed on sage-devel. Someone has originally implemented this, and I guess he/she have had a reason for this.

I just went through your code and made small modifications, some to the code some to the doc. Most of the time by removing/shortening things. You are of course welcome to discuss any character of it. Also, you sometimes forget articles 'a/an': I am no expert in english but sometimes they really are necessary to the sentence.

I am sure that you know "a"/"an"/"the" better than I do; my native language belongs to Uralic languages family. I just added commas to math blocks so that they are uniform.

Your code is, as usual, better than mine.

If I am right, now we just needs to decide the name.

[ncohen]

Hello,

This should really be discussed on sage-devel. Someone has originally implemented this, and I guess he/she have had a reason for this.

True, but it would be a mistake to value a reason that we do not know more than those we figured out ourselves. Maybe something smart may come from sage-devel indeed, though. I hope that we will hear something different from the frequent refusal to change things 'on principle'.

If I am right, now we just needs to decide the name.

Yep. I concur with Frédéric's proposal of a is_ordinal_sum with an optional certificate. The same is done differently for is_connected/connected_components, but there at least there is no doubt on which terminology should be used. Perhaps it's worth asking on sage-devel too if you prefer.

Nathann

[jmantysalo]

Replying to ncohen:

If I am right, now we just needs to decide the name.

Yep. I concur with Frédéric's proposal of a is_ordinal_sum with an optional certificate.

OK. Then, what should be the name of parameter (somehow certificate sounds odd to me)? And should it return the decomposition as a list of elements or as a list of subposets?

[ncohen]

OK. Then, what should be the name of parameter (somehow certificate sounds odd to me)?

'certificate' is a generic term that is used in some places already (mostly because of me I expect), but it is not a 'standard' at all. Is there another term you would prefer?

And should it return the decomposition as a list of elements or as a list of subposets?

Depends on what *you* plan to use it for. .is_ordinal_sum(as_posets=True) or .is_ordinal_sum(as_partition=True) would work for me, and either return an empty list (when it is not) or return a list of whatever is requested.

If you have a better idea, of course, just name it.

Nathann

[jmantysalo]

As I am not sure about this, I think that no Boolean-valued option is good. So it should be return_value='boolean' with options 'poset' and 'elements' or 'lists'. But is there something similar in other parts of Sage? I would like to re-use existing parameter name if possible.

[ncohen]

Hello,

I slowly used more and more booleans for these things as it reduces the risk of typoes. Any typo in the argument's name raises an automatic exception (that's Python), and the same goes for True/False (if you make a typo, that's an undefined variable). The code is also simpler as you don't have to do if x==A/elif x==B/else ValueError.

You will find many boolean functions with such a boolean argument: IncidenceStructure.is_t_design, Graph.is_strongly_regular, Graph.automorphism_group, Graph.is_isomorphic.

The use of a string argument is, in the graph library at least, more often used to select an algorithm/method to perform the requested computation (e.g. Graph.maximum_clique).

Nathann

[jmantysalo]

Still about the naming... Compare to #19123. These are kind of same thing, but for lattices it is more natural to think about making the top element of lattice 1 and the bottom element of lattice 2 to one common element.

A suggestion: What if I only make a function whose name starts with _? Then we could use the code to build more functions, and think later about the name.

[ncohen]

Still about the naming... Compare to #19123. These are kind of same thing, but for lattices it is more natural to think about making the top element of lattice 1 and the bottom element of lattice 2 to one common element.

What do you want us to compare in the naming of this function and the content of #19123?

A suggestion: What if I only make a function whose name starts with _? Then we could use the code to build more functions, and think later about the name.

Then that means that the function will not appear to the users, and that we will not even use it ourselves at the moment. I don't see the point.

Nathann

[jmantysalo]

Replying to ncohen:

What do you want us to compare in the naming of this function and the content of #19123?

These two functions do exactly same thing when they return a Boolean value. So should they have same name? OTOH when returning non-boolean values it is somewhat strange to return posets that are actually semilattices from decomposition of lattice.

A suggestion: What if I only make a function whose name starts with _? Then we could use the code to build more functions, and think later about the name.

Then that means that the function will not appear to the users, and that we will not even use it ourselves at the moment. I don't see the point.

It could be a building block for series-parallel decomposition.

[ncohen]

Then that means that the function will not appear to the users, and that we will not even use it ourselves at the moment. I don't see the point.

It could be a building block for series-parallel decomposition.

If you need a function to do that, keep it on your own computer. Patching Sage makes sense to *share* functions with others: if you want to have them hidden from the users and if Sage does not need them in any way, it can easily wait till you find a use for it.

Nathann

[chapoton]

I would be happy if you just change the name to ordinal_summands.

[git]

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

​7f6e6b2

Change function name.

[jmantysalo]

Replying to ncohen:

It could be a building block for series-parallel decomposition.

If you need a function to do that, keep it on your own computer.

I mean that I want to make series_parallel_decomposition to be a part of Sage.

[jmantysalo]

Replying to chapoton:

I would be happy if you just change the name to ordinal_summands.

Done this.

[git]

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

​be8c48e

Broken seealso-link.

[chapoton]

ok, looks good. Patchbot failures seems not related.