Opened 4 years ago

Closed 4 years ago

#19659 closed enhancement (fixed)

Poset: inverse function of ordinal_sum()

Reported by: jmantysalo Owned by:
Priority: major Milestone: sage-7.1
Component: combinatorics Keywords: poset
Cc: ncohen, chapoton Merged in:
Authors: Jori Mäntysalo, Nathann Cohen Reviewers: Nathann Cohen, Jori Mäntysalo, Frédéric Chapoton
Report Upstream: N/A Work issues:
Branch: be8c48e (Commits) Commit: be8c48e0bc992b99a7a9e94777689857a7570b40
Dependencies: Stopgaps:

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

Change History (67)

comment:1 Changed 4 years ago by jmantysalo

  • Branch set to u/jmantysalo/develop

comment:2 Changed 4 years ago by jmantysalo

  • Commit set to fcd68b964edd9abc071b32d49e90818f86073f01
  • Description modified (diff)
  • Status changed from new to needs_review

New commits:

d1d6f4bAdded ordinal_sum_decomposition().
fcd68b9Spaces removed.

comment:3 Changed 4 years ago by git

  • Commit changed from fcd68b964edd9abc071b32d49e90818f86073f01 to 4358a5a4574999015ccb9088bdb842dcc738d40c

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

4358a5aAdded a "front end"-function for ordinal splitting.

comment:4 Changed 4 years ago by jmantysalo

  • Cc dimpase added
  • Milestone changed from sage-6.10 to sage-7.0

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

comment:5 follow-up: Changed 4 years ago by dimpase

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

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

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

comment:7 Changed 4 years ago by jmantysalo

  • Cc ncohen added

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.)

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

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

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

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

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

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

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

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

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

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

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

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

comment:16 in reply to: ↑ 15 Changed 4 years ago by 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

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

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

comment:18 Changed 4 years ago by git

  • Commit changed from 4358a5a4574999015ccb9088bdb842dcc738d40c to 01f9e1c6bb502e6044181c856bcb8984718fd237

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

01f9e1cAn optimization.

comment:19 in reply to: ↑ 17 Changed 4 years ago by 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.

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

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

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

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

comment:24 in reply to: ↑ 23 Changed 4 years ago by 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

comment:25 Changed 4 years ago by 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.

comment:26 follow-up: Changed 4 years ago by jmantysalo

  • Cc dimpase removed

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.)

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

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

comment:29 in reply to: ↑ 28 Changed 4 years ago by 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

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

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

comment:31 in reply to: ↑ 30 ; follow-up: Changed 4 years ago by 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. :=)

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

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

comment:34 in reply to: ↑ 33 ; follow-up: Changed 4 years ago by ncohen

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

Sorry, I was talking of Poset.ordinal_components.

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

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

comment:36 in reply to: ↑ 35 ; follow-up: Changed 4 years ago by 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 ?

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

comment:38 Changed 4 years ago by 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?

comment:39 in reply to: ↑ 37 Changed 4 years ago by 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

comment:40 Changed 4 years ago by git

  • Commit changed from 01f9e1c6bb502e6044181c856bcb8984718fd237 to dc6ea77deba193bdf03e55ecf66a1ea1f7d3e90c

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

6b98cbfUnified to one function.
dc6ea77Spaces removed from end of lines.

comment:41 follow-up: Changed 4 years ago by jmantysalo

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

comment:42 in reply to: ↑ 41 ; follow-ups: Changed 4 years ago by 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

comment:43 Changed 4 years ago by ncohen

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

comment:44 in reply to: ↑ 42 ; follow-up: Changed 4 years ago by 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().

comment:45 in reply to: ↑ 44 Changed 4 years ago by ncohen

  • Cc chapoton added

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

comment:46 Changed 4 years ago by 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

Last edited 4 years ago by chapoton (previous) (diff)

comment:47 Changed 4 years ago by 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.

comment:48 Changed 4 years ago by jmantysalo

  • Branch changed from u/jmantysalo/develop to public/19659
  • Commit changed from dc6ea77deba193bdf03e55ecf66a1ea1f7d3e90c to 548b4eb8dcad4513c7f71b04c97a30b60035966c

New commits:

543c4a1Added ordinal_sum_decomposition().
548b4ebtrac #19659: Review

comment:49 Changed 4 years ago by git

  • Commit changed from 548b4eb8dcad4513c7f71b04c97a30b60035966c to 1385d69b99c5060821463ef513b0478a062db942

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

1385d69Added commas.

comment:50 in reply to: ↑ 42 ; follow-up: Changed 4 years ago by jmantysalo

  • Authors changed from Jori Mäntysalo to Jori Mäntysalo, Nathann Cohen
  • Reviewers set to Nathann Cohen, Jori Mäntysalo

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.

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

comment:52 in reply to: ↑ 51 ; follow-up: Changed 4 years ago by 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?

comment:53 in reply to: ↑ 52 Changed 4 years ago by 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

comment:54 Changed 4 years ago by 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.

comment:55 Changed 4 years ago by 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

comment:56 follow-up: Changed 4 years ago by 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.

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

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

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

comment:60 follow-up: Changed 4 years ago by chapoton

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

comment:61 Changed 4 years ago by git

  • Commit changed from 1385d69b99c5060821463ef513b0478a062db942 to 7f6e6b29649381942485fbfd5ac28bc0f4b4762f

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

7f6e6b2Change function name.

comment:62 in reply to: ↑ 59 Changed 4 years ago by 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.

comment:63 in reply to: ↑ 60 Changed 4 years ago by jmantysalo

Replying to chapoton:

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

Done this.

comment:64 Changed 4 years ago by git

  • Commit changed from 7f6e6b29649381942485fbfd5ac28bc0f4b4762f to be8c48e0bc992b99a7a9e94777689857a7570b40

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

be8c48eBroken seealso-link.

comment:65 Changed 4 years ago by chapoton

  • Milestone changed from sage-7.0 to sage-7.1
  • Reviewers changed from Nathann Cohen, Jori Mäntysalo to Nathann Cohen, Jori Mäntysalo, Frédéric ChapotonF
  • Status changed from needs_review to positive_review

ok, looks good. Patchbot failures seems not related.

comment:66 Changed 4 years ago by jmantysalo

  • Reviewers changed from Nathann Cohen, Jori Mäntysalo, Frédéric ChapotonF to Nathann Cohen, Jori Mäntysalo, Frédéric Chapoton

comment:67 Changed 4 years ago by vbraun

  • Branch changed from public/19659 to be8c48e0bc992b99a7a9e94777689857a7570b40
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.