Poset documentation polishing: chains and antichains

[Jori Mäntysalo]

Do some polishing to is_chain_of_poset(), maximal_antichains() and so on at posets.py.

[Jori Mäntysalo]

Found a bug -> type changed to defect.

Which one is correct: "Return the chains of the poset.", "Return all the chains of the poset.", "Return all chains of the poset." or "Return chains of the poset."?

[Jori Mäntysalo]

Code for maximal_chains() seems complicated. Why not just something like

list(P.hasse_diagram().all_paths_iterator(starting_vertices=P.minimal_elements(),
ending_vertices=P.maximal_elements()))

Argument partial does not seem to used in anywhere, it is just an implementation detail exposed to the user. Can it be removed?

[Jori Mäntysalo]

As deprecation needs a ticket number, it is best to make correction at a new ticket. I opened #18944 for that.

[Jori Mäntysalo]

New commits:

​2e47dc2

Shorted doc for is_chain_of_poset().

[git]

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

​041cf31

Minor changes in doc for chains().

[git]

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

​d185533

Minor changes in doc for antichains().

[git]

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

​9642c43

Minor addition to maximal_antichains().

[Jori Mäntysalo]

Ready for review, because I can look at #18944 later. Besides documentation there is one minor code change in is_chain_of_poset: I added

if not hasattr(elms, '__getitem__'):
    raise TypeError("ordered=True not combatible with type %s for elms" % type(elms))

[git]

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

​df6d947

An example to antichains_iterator().

[Jori Mäntysalo]

Thanks Kevin.

As a side note, there should be a link to is_antichain_of_poset() (on [all, including infinite] posets category) in the index of posets.py. But I can add it later, when we see if #18534 gets accepted or not.

[Frédéric Chapoton]

not combatible ?

[Jori Mäntysalo]

Replying to chapoton:

not combatible ?

Isn't it a clash if patch A modifies lines N and N+1, and patch B adds a line between the same lines?

But in any case, I can do this later if somebody wants to review #18534. It is two lines long, should I split it to make it easier for reviewers to read...?

[Frédéric Chapoton]

typo: "combatible" is not an English word

[git]

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

​fc7d6a5

Typo correction.

[Jori Mäntysalo]

Replying to chapoton:

typo: "combatible" is not an English word

Ah, now I see the error. Corrected.

[Nathann Cohen]

Looks good to go, but why do you remove so many doctests of is_chain_of_poset?

Nathann

[Jori Mäntysalo]

Replying to ncohen:

Looks good to go, but why do you remove so many doctests of is_chain_of_poset?

Because I (as always...) didn't think about the code but about the user. They were on EXAMPLES-part, and I think they were not all needed to show the idea of the function. Do you want me to add a TESTS-part?

[Nathann Cohen]

Because I (as always...) didn't think about the code but about the user. They were on EXAMPLES-part, and I think they were not all needed to show the idea of the function. Do you want me to add a TESTS-part?

Yep yep, you can move them to a "TESTS" section if you think they do not bring anything to the user.

Nathann

[Jori Mäntysalo]

Replying to ncohen:

Because I (as always...) didn't think about the code but about the user. They were on EXAMPLES-part, and I think they were not all needed to show the idea of the function. Do you want me to add a TESTS-part?

Yep yep, you can move them to a "TESTS" section if you think they do not bring anything to the user.

OK, I'll do that. (And hope that TESTS will be foldable or hidden part some day.)

I should also add is_antichain_of_poset() to SEEALSO. As #19078 shows red, I can do this now and correct it later.

[git]

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

​ecb16e6

Added tests to is_chain_of_poset().

[Jori Mäntysalo]

I added some tests. As Macaulay2 has function dilworthNumber, I added the synonym to docstring of widht; this is non-relating change.

Ready for review. Nathann, remember to change name of the reviewer if you are going to do it.

[Nathann Cohen]

I added some tests. As Macaulay2 has function dilworthNumber, I added the synonym to docstring of widht; this is non-relating change.

Okay.

• You must add a 'the' before 'given' in the description of 'is_chain_of_poset', in the index.

• This should work, and it does not:

  sage: posets.DiamondPoset(4).is_chain_of_poset(iter([3]),ordered=True)
  ...
  TypeError: ordered=True not compatible with type <type 'listiterator'> for elms
  

You cannot rely on things like the existence of __getitem__ to deduce something unrelated, like whether the ordering "matters" or not. You can rely on existing standards, but defining one in a patch won't make it true. In particular:

sage: Set([1,2,3])[0]
1

Say that it only take a list as input or do nothing. TIf the user provides a set and says that the order matters, well, I say that (s)he should be bitten as a result.

Nathann

[Jori Mäntysalo]

Replying to ncohen:

In particular:

sage: Set([1,2,3])[0]
1

Duh. So there is no way at all in Python to check if a given container item has fixed order? And in theory (Set([1,2,3])[1], Set([1,2,3])[1]) could return (3,2). In reality after P=Poset({'a':[1]}) the command P.is_chain_of_poset({'a', 1}, ordered=True) will return True or False depending on the machine that runs Python.

[Nathann Cohen]

Duh. So there is no way at all in Python to check if a given container item has fixed order?

What is a 'fixed order' from the point of view of the computer? What you want to know is if the order given is the one *intended* by the user. I don't think that there is a way to do that, neither in this language nor in another. If you want something reliable, test that input is a list, or just trust the user to not do anything stupid.

Nathann

[Jori Mäntysalo]

Replying to ncohen:

Duh. So there is no way at all in Python to check if a given container item has fixed order?

What is a 'fixed order' from the point of view of the computer? What you want to know is if the order given is the one *intended* by the user.

By fixed order I meant deterministic output. After x=['a',1] we always have x[1]==1 in every implementation of Python. After y={'a', 1} we always get error from y[1]. After z=Set(x) we don't know the output of z[1]. (Which sounds odd... "second item of a set"?)

But anyway, thanks. I will change the code. As all kinds of iterables were accepted before, I guess that is the way to continue. And it makes no sense to pick out most common "wrong" types, as it would give false impression of security to the user.

[Nathann Cohen]

And it makes no sense to pick out most common "wrong" types, as it would give false impression of security to the user.

+1. We should do what we can to help them avoid mistakes, but we can't protect them against themselves.

Nathann

[Jori Mäntysalo]

Replying to ncohen:

• This should work, and it does not:

  sage: posets.DiamondPoset(4).is_chain_of_poset(iter([3]),ordered=True)
  ...
  TypeError: ordered=True not compatible with type <type 'listiterator'> for elms
  

Arghs. Just noticed that this does not work in Sage even before this patch. It the right correction

if not hasattr(elms, '__getitem__'):
    sorted_o = elms
else:
    sorted_o = list(elms)

? Or is there still something more to think about?

[Nathann Cohen]

? Or is there still something more to think about?

If you want to support any iterable as input, I guess that the best is this

sage: elms = range(10)
sage: it1 = iter(elms)
sage: it2 = iter(elms)
sage: it2.next()
0
sage: zip(it1,it2)
[(0, 1), (1, 2), (2, 3), (3, 4), (4, 5), (5, 6), (6, 7), (7, 8), (8, 9)]

But that's really a lot of infrastructure for a very small impact.

Nathann

[Nathann Cohen]

(not to mention that you have to check whether it2.next() yields a StopIterator exception)

[git]

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

​93f35e5

Removed a (failing) test of 'elms' being ordered.

[Jori Mäntysalo]

Replying to ncohen:

But that's really a lot of infrastructure for a very small impact.

True. Feels lazy today -> put to needs_review without this. And after all, this ticket was about documentation, which is now polished. (Or at least one more pair of eyes have read it throught.)

[Travis Scrimshaw]

You could use sorted to make deterministic output (in doctests?) (at least since integers has a nice total ordering)...

[Jori Mäntysalo]

Replying to tscrim:

You could use sorted to make deterministic output (in doctests?) (at least since integers has a nice total ordering)...

No no, this is different thing. The problem is that Set([1,2])[1] might return 1 or 2. Hence it is not meaningful to ask if Set([1,2]) is an ordered chain of for example ChainPoset(4). But we have no way to check when the user asks something not meaningful.

[Jori Mäntysalo]

ping -c 1 kevin...

[Kevin Dilks]

All the changes you made look good to me, positive review.

Two comments related to things I saw while looking through the code (which should probably go in separate tickets):

1) Somebody should finally implement the wrapper that gives you all antichains of a specified size.

2) In is_chain_of_poset, I think there should be an additional optional parameter strict, so that when ordered=True, you can test whether a given list of elements is a weakly increasing chain or a strictly increasing chain. Right now it only tests for strict chains.

[Jori Mäntysalo]

Replying to kdilks:

All the changes you made look good to me, positive review.

Thanks!

Two comments related to things I saw while looking through the code (which should probably go in separate tickets):

1) Somebody should finally implement the wrapper that gives you all antichains of a specified size.

True. Same applies to chains of specified size.

2) In is_chain_of_poset, I think there should be an additional optional parameter strict, so that when ordered=True, you can test whether a given list of elements is a weakly increasing chain or a strictly increasing chain. Right now it only tests for strict chains.

?? Isn't it just another way? Name of the parameter should propably be saturated.

[Kevin Dilks]

saturated is something that only applies to strict chains, and it means that all of your elements differ by a covering relation. Using the standard partial (well...total) order on the integers,

[1,1,2,2,3,3] is a weak chain. [1,3,5,7] is a strict but not saturated chain. [2,3,4,5] is a strict and saturated chain.

Right now, if ordered=True, then it will tell you if your list of elements is a strict but not necessarily saturated chain (in the order given). If ordered=False, then it tells you whether the set of elements you give it can be ordered in some way to make a chain.