Opened 4 years ago

Closed 4 years ago

#18941 closed enhancement (fixed)

Poset documentation polishing: chains and antichains

Reported by: jmantysalo Owned by:
Priority: major Milestone: sage-6.9
Component: documentation Keywords:
Cc: tscrim, kdilks Merged in:
Authors: Jori Mäntysalo Reviewers: Kevin Dilks
Report Upstream: N/A Work issues:
Branch: 93f35e5 (Commits) Commit: 93f35e5dd1f134f072a84f8d08971207d64d8023
Dependencies: Stopgaps:

Description (last modified by jmantysalo)

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

Change History (39)

comment:1 Changed 4 years ago by jmantysalo

  • Description modified (diff)
  • Type changed from enhancement to defect

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."?

comment:2 Changed 4 years ago by jmantysalo

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?

comment:3 Changed 4 years ago by jmantysalo

  • Dependencies set to #18944
  • Description modified (diff)
  • Type changed from defect to enhancement

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

comment:4 Changed 4 years ago by jmantysalo

  • Branch set to u/jmantysalo/poset_polishing_chains
  • Commit set to 2e47dc2df348f80446c4724f6c8c066c2aa29d21

New commits:

2e47dc2Shorted doc for is_chain_of_poset().

comment:5 Changed 4 years ago by git

  • Commit changed from 2e47dc2df348f80446c4724f6c8c066c2aa29d21 to 041cf315cbec72a405b59e004e6a16d24474c9db

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

041cf31Minor changes in doc for chains().

comment:6 Changed 4 years ago by git

  • Commit changed from 041cf315cbec72a405b59e004e6a16d24474c9db to d185533c18017b13368fd37886fbfe98af909cfd

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

d185533Minor changes in doc for antichains().

comment:7 Changed 4 years ago by git

  • Commit changed from d185533c18017b13368fd37886fbfe98af909cfd to 9642c432505970dff49d647900ecd218596670ec

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

9642c43Minor addition to maximal_antichains().

comment:8 Changed 4 years ago by jmantysalo

  • Dependencies #18944 deleted
  • Milestone changed from sage-feature to sage-6.8
  • Status changed from new to needs_review
  • Summary changed from Poset documentation polishing: chains to Poset documentation polishing: chains and antichains

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

comment:9 Changed 4 years ago by git

  • Commit changed from 9642c432505970dff49d647900ecd218596670ec to df6d947928eda82b989a1fd104c7ed57e911cbd1

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

df6d947An example to antichains_iterator().

comment:10 Changed 4 years ago by kdilks

  • Cc kdilks added
  • Reviewers set to Kevin Dilks

comment:11 Changed 4 years ago by jmantysalo

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.

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

not combatible ?

comment:13 in reply to: ↑ 12 Changed 4 years ago by jmantysalo

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

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

typo: "combatible" is not an English word

comment:15 Changed 4 years ago by git

  • Commit changed from df6d947928eda82b989a1fd104c7ed57e911cbd1 to fc7d6a56de2a3dc24003adfa5fddfbb711ca143b

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

fc7d6a5Typo correction.

comment:16 in reply to: ↑ 14 Changed 4 years ago by jmantysalo

Replying to chapoton:

typo: "combatible" is not an English word

Ah, now I see the error. Corrected.

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

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

Nathann

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

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?

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

Nathann

comment:20 in reply to: ↑ 19 Changed 4 years ago by jmantysalo

  • Milestone changed from sage-6.8 to sage-6.9
  • Status changed from needs_review to needs_work

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.

comment:21 Changed 4 years ago by git

  • Commit changed from fc7d6a56de2a3dc24003adfa5fddfbb711ca143b to ecb16e648cdff2cb22bc88c7fd01f114af8006a5

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

ecb16e6Added tests to is_chain_of_poset().

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

  • Status changed from needs_work to needs_review

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.

comment:23 in reply to: ↑ 22 ; follow-ups: Changed 4 years ago by ncohen

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

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

  • Status changed from needs_review to needs_work

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.

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

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

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.

comment:27 in reply to: ↑ 26 Changed 4 years ago by ncohen

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

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

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?

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

? 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

comment:30 Changed 4 years ago by ncohen

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

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

comment:31 Changed 4 years ago by git

  • Commit changed from ecb16e648cdff2cb22bc88c7fd01f114af8006a5 to 93f35e5dd1f134f072a84f8d08971207d64d8023

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

93f35e5Removed a (failing) test of 'elms' being ordered.

comment:32 in reply to: ↑ 29 Changed 4 years ago by jmantysalo

  • Status changed from needs_work to needs_review

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

comment:33 follow-up: Changed 4 years ago by tscrim

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

comment:34 in reply to: ↑ 33 Changed 4 years ago by jmantysalo

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.

comment:35 Changed 4 years ago by jmantysalo

ping -c 1 kevin...

comment:36 follow-up: Changed 4 years ago by kdilks

  • Status changed from needs_review to positive_review

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.

comment:37 in reply to: ↑ 36 Changed 4 years ago by jmantysalo

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.

comment:38 Changed 4 years ago by kdilks

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.

comment:39 Changed 4 years ago by vbraun

  • Branch changed from u/jmantysalo/poset_polishing_chains to 93f35e5dd1f134f072a84f8d08971207d64d8023
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.