Opened 7 years ago
Closed 7 years ago
#18941 closed enhancement (fixed)
Poset documentation polishing: chains and antichains
Reported by:  Jori Mäntysalo  Owned by:  

Priority:  major  Milestone:  sage6.9 
Component:  documentation  Keywords:  
Cc:  Travis Scrimshaw, Kevin Dilks  Merged in:  
Authors:  Jori Mäntysalo  Reviewers:  Kevin Dilks 
Report Upstream:  N/A  Work issues:  
Branch:  93f35e5 (Commits, GitHub, GitLab)  Commit:  93f35e5dd1f134f072a84f8d08971207d64d8023 
Dependencies:  Stopgaps: 
Description (last modified by )
Do some polishing to is_chain_of_poset()
, maximal_antichains()
and so on at posets.py
.
Change History (39)
comment:1 Changed 7 years ago by
Description:  modified (diff) 

Type:  enhancement → defect 
comment:2 Changed 7 years ago by
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 7 years ago by
Dependencies:  → #18944 

Description:  modified (diff) 
Type:  defect → 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 7 years ago by
Branch:  → u/jmantysalo/poset_polishing_chains 

Commit:  → 2e47dc2df348f80446c4724f6c8c066c2aa29d21 
New commits:
2e47dc2  Shorted doc for is_chain_of_poset().

comment:5 Changed 7 years ago by
Commit:  2e47dc2df348f80446c4724f6c8c066c2aa29d21 → 041cf315cbec72a405b59e004e6a16d24474c9db 

Branch pushed to git repo; I updated commit sha1. New commits:
041cf31  Minor changes in doc for chains().

comment:6 Changed 7 years ago by
Commit:  041cf315cbec72a405b59e004e6a16d24474c9db → d185533c18017b13368fd37886fbfe98af909cfd 

Branch pushed to git repo; I updated commit sha1. New commits:
d185533  Minor changes in doc for antichains().

comment:7 Changed 7 years ago by
Commit:  d185533c18017b13368fd37886fbfe98af909cfd → 9642c432505970dff49d647900ecd218596670ec 

Branch pushed to git repo; I updated commit sha1. New commits:
9642c43  Minor addition to maximal_antichains().

comment:8 Changed 7 years ago by
Dependencies:  #18944 

Milestone:  sagefeature → sage6.8 
Status:  new → needs_review 
Summary:  Poset documentation polishing: chains → 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 7 years ago by
Commit:  9642c432505970dff49d647900ecd218596670ec → df6d947928eda82b989a1fd104c7ed57e911cbd1 

Branch pushed to git repo; I updated commit sha1. New commits:
df6d947  An example to antichains_iterator().

comment:10 Changed 7 years ago by
Cc:  Kevin Dilks added 

Reviewers:  → Kevin Dilks 
comment:11 Changed 7 years ago by
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:13 Changed 7 years ago by
comment:15 Changed 7 years ago by
Commit:  df6d947928eda82b989a1fd104c7ed57e911cbd1 → fc7d6a56de2a3dc24003adfa5fddfbb711ca143b 

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

comment:16 Changed 7 years ago by
comment:17 followup: 18 Changed 7 years ago by
Looks good to go, but why do you remove so many doctests of is_chain_of_poset
?
Nathann
comment:18 followup: 19 Changed 7 years ago by
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 followup: 20 Changed 7 years ago by
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 aTESTS
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 Changed 7 years ago by
Milestone:  sage6.8 → sage6.9 

Status:  needs_review → 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 aTESTS
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 7 years ago by
Commit:  fc7d6a56de2a3dc24003adfa5fddfbb711ca143b → ecb16e648cdff2cb22bc88c7fd01f114af8006a5 

Branch pushed to git repo; I updated commit sha1. New commits:
ecb16e6  Added tests to is_chain_of_poset().

comment:22 followup: 23 Changed 7 years ago by
Status:  needs_work → needs_review 

I added some tests. As Macaulay2 has function dilworthNumber
, I added the synonym to docstring of widht
; this is nonrelating change.
Ready for review. Nathann, remember to change name of the reviewer if you are going to do it.
comment:23 followups: 24 28 Changed 7 years ago by
I added some tests. As Macaulay2 has function
dilworthNumber
, I added the synonym to docstring ofwidht
; this is nonrelating 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 followup: 25 Changed 7 years ago by
Status:  needs_review → 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 followup: 26 Changed 7 years ago by
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 followup: 27 Changed 7 years ago by
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 Changed 7 years ago by
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 followup: 29 Changed 7 years ago by
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 followup: 32 Changed 7 years ago by
? 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 7 years ago by
(not to mention that you have to check whether it2.next()
yields a StopIterator
exception)
comment:31 Changed 7 years ago by
Commit:  ecb16e648cdff2cb22bc88c7fd01f114af8006a5 → 93f35e5dd1f134f072a84f8d08971207d64d8023 

Branch pushed to git repo; I updated commit sha1. New commits:
93f35e5  Removed a (failing) test of 'elms' being ordered.

comment:32 Changed 7 years ago by
Status:  needs_work → 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 followup: 34 Changed 7 years ago by
You could use sorted
to make deterministic output (in doctests?) (at least since integers has a nice total ordering)...
comment:34 Changed 7 years ago by
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:36 followup: 37 Changed 7 years ago by
Status:  needs_review → 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 Changed 7 years ago by
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 parameterstrict
, so that whenordered=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 7 years ago by
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 7 years ago by
Branch:  u/jmantysalo/poset_polishing_chains → 93f35e5dd1f134f072a84f8d08971207d64d8023 

Resolution:  → fixed 
Status:  positive_review → closed 
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."?