Opened 6 years ago
Last modified 5 years ago
#18944 needs_info defect
Posets: maximal_chains() partialoption broken
Reported by:  jmantysalo  Owned by:  

Priority:  major  Milestone:  sage6.9 
Component:  combinatorics  Keywords:  posets 
Cc:  ncohen  Merged in:  
Authors:  Jori Mäntysalo  Reviewers:  
Report Upstream:  N/A  Work issues:  
Branch:  u/jmantysalo/maximal_chains (Commits, GitHub, GitLab)  Commit:  e6a4ae2b1f7f887b58a49af5c1607640c7821dde 
Dependencies:  Stopgaps: 
Description
partial
argument on maximal_chains()
of finite posets is broken. The error is at posets.py
.
P = Posets.BooleanLattice(2) P.maximal_chains(partial=[1, 2])
outputs [[1, 2, 3]]
which is not a chain at all. Best correction is to remove the option.
Change History (21)
comment:1 Changed 6 years ago by
 Branch set to u/jmantysalo/maximal_chains
 Commit set to eeefd9d2c4184a3f60f505a7851ec3ff16eb7bf0
comment:2 followup: ↓ 3 Changed 6 years ago by
 Cc ncohen added
Nathann, some questions: 1) Can you confirm that this is right way to get maximal chains of a poset? 2) What you think about this kind of "deprecation", where I removed broken functionality with warning?
And for most important part, 3) what about chain_polytope
? This brokes doctest. Who knows if it has been broken all the time? Should I just let it be, and move (broken) old version on maximal_chains
inside chain_polytope
?
(This is kind of childticket of #18941.)
comment:3 in reply to: ↑ 2 Changed 6 years ago by
Hello,
1) Can you confirm that this is right way to get maximal chains of a poset?
Hmmmmm... Well it *would*, if all_paths_iterator
actually did only what it claimed (it actually returns path sorted by distance, and you do not want that nor should you pay for that). This being said, this is precisely the function that you should call, and if it does not do what it should, well, that's a problem interal to all_paths_iterator
.
2) What you think about this kind of "deprecation", where I removed broken functionality with warning?
I do not see the point of displaying a warning before raising an exception. Better to only raise an exception, or to remove the optiona flag directly.
Not that "by Sage standards" this should not be done. My usual procedure is to write to Sage devel to ask if I can remove it, have 50 persons who usually never show up yell a me, and do nothing in the end because the community disagrees. Pick your path.
And for most important part, 3) what about
chain_polytope
?
I don't understand what you are talking about.
Nathann
comment:4 Changed 6 years ago by
As for question 3, just run sage t
to posets.py
.
About 1: How it does that on iterator? But yes, with BooleanLattice(8)
it seems to be about 3 times slower to use the function from digraphs.
comment:5 Changed 6 years ago by
As best I can tell, this isn't a broken function, it's bad input. [1,2]
represents the two incomparable elements of BooleanLattice(2)
, so they'll never be the start of a maximal chain. I think the better course of action would be to implement a check to ensure that partial
is a saturated chain in the poset, starting with a minimal element.
I think the description also needs to be clarified, because it's not clear just from reading it whether partial=[0,1]
means listing all maximal chains with minimal element 0 or minimal element 1 (which is not what this does), or if it it means listing all maximal chains that have 0 as the minimal element and 1 as it's second element (which is what it does).
comment:6 Changed 6 years ago by
But in any case, if we just add a check for input to be comparable elements, then chain_polytope
will broke. It relies on this (odd / buggy?) behavior.
And who will want "partial maximal chains" in first place? To compare: there is exclude
option in chains()
.
comment:7 Changed 6 years ago by
 Commit changed from eeefd9d2c4184a3f60f505a7851ec3ff16eb7bf0 to e6a4ae2b1f7f887b58a49af5c1607640c7821dde
Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:
e6a4ae2  Removed broken partialoption from maximal_chains().

comment:8 Changed 6 years ago by
 Status changed from new to needs_review
Also chain_polytope()
(not only order_complex()
) relies on this (IMO) broken maximal_chains()
function. Hence I made an internal copy of it with name _max_chains()
. At least all doctests pass now. For a user perspective everything should be as before, except that partial
option is gone.
comment:9 followup: ↓ 10 Changed 6 years ago by
 Milestone changed from sage6.8 to sage6.9
 Status changed from needs_review to needs_work
I agree with Kevin, bad input is bad input and you should not expect correct behavior. So there is no counterexample to the function working as documented, but we should raise an error when not given a saturated chain.
comment:10 in reply to: ↑ 9 Changed 6 years ago by
 Status changed from needs_work to needs_info
Replying to tscrim:
I agree with Kevin, bad input is bad input and you should not expect correct behavior. So there is no counterexample to the function working as documented, but we should raise an error when not given a saturated chain.
Should partial
be a saturated chain starting from some minimal element? Should it be ordered?
And why it should be saturated? If a
, b
and c
are comparable, then maximal_chains(partial=[a,b,c])
can be well defined: return every maximal chain that contains all three elements. On the other hand, chains()
have exclude
option, not include
. (Of course there are FOUR ways to have argument like this: include some element, include all elements, do not include all elements, do not include any of elements.)
I am quite sure that this function has been made just as a helper function, without thinking someone to use partial
directly.
comment:11 followup: ↓ 12 Changed 6 years ago by
The code seems to be assuming that it is ordered:
sage: P.maximal_chains(partial=[0,1]) [[0, 1, 3]] sage: P.maximal_chains(partial=[1,0]) [[1, 0, 1, 3], [1, 0, 2, 3]]
The documentation says "begins with", that is the saturated part. I'm not opposed to changing the behavior to removing the saturated condition, but it would make the code a lot more complex (i.e., likely nonrecursive).
comment:12 in reply to: ↑ 11 Changed 6 years ago by
Replying to tscrim:
I'm not opposed to changing the behavior to removing the saturated condition, but it would make the code a lot more complex (i.e., likely nonrecursive).
Not necessarily, as digraphs already have all_paths(start, end)
. A PoC:
P = Posets.BooleanLattice(5) g = P.hasse_diagram() k = [1,11,31] for x in [flatten(c) for c in CartesianProduct(*[g.all_paths(k[i],k[i+1]) for i in range(len(k)1)])]: print [x[i] for i in range(len(x)) if x[i] != x[i1]]
But in that case the name of the parameter should be include
, not partial
.
I still think that we could remove it. Maybe with deprecation that mentions _max_chains()
?
comment:13 followup: ↓ 14 Changed 6 years ago by
If it's easy and fast enough, then let's do it.
I don't think we should remove partial
as that just pushes useful (evident it is used in other parts of sage) functionality to a hidden place.
comment:14 in reply to: ↑ 13 Changed 6 years ago by
Replying to tscrim:
I don't think we should remove
partial
as that just pushes useful (evident it is used in other parts of sage) functionality to a hidden place.
This argument fails: use in other places (there is two) needs the broken behavior. But I guess we are not keeping public funtion maximal_chains()
that returns trees that are not chains.
comment:15 followup: ↓ 16 Changed 5 years ago by
I am still wondering about this... Other parts of Sage relies on broken or nondefined behaviour of partial
argument. It feels bad design.
comment:16 in reply to: ↑ 15 ; followup: ↓ 17 Changed 5 years ago by
Replying to jmantysalo:
I am still wondering about this... Other parts of Sage relies on broken or nondefined behaviour of
partial
argument. It feels bad design.
We will probably need to make adjustments to the other parts the break. I haven't checked (and/or don't remember) how much the other behavior relies on the current functionality. Also I still think we should not remove the partial
, but maybe we should just have some checks on that input.
comment:17 in reply to: ↑ 16 Changed 5 years ago by
Replying to tscrim:
Replying to jmantysalo:
I am still wondering about this... Other parts of Sage relies on broken or nondefined behaviour of
partial
argument. It feels bad design.We will probably need to make adjustments to the other parts the break. I haven't checked (and/or don't remember) how much the other behavior relies on the current functionality. Also I still think we should not remove the
partial
, but maybe we should just have some checks on that input.
There are two places that depends on this broken behaviour. They are not hard to fix, if we do that in ugly but working way.
Can you give examples of what you mean by "partial maximal chain"?
For chains()
we have exclude
option. This partial
option would be something like include
, I guess.
comment:18 followup: ↓ 19 Changed 5 years ago by
My guess is like you said, that it that every maximal chain must contain elements (i.e., this partial maximal chain).
comment:19 in reply to: ↑ 18 Changed 5 years ago by
Replying to tscrim:
My guess is like you said, that it that every maximal chain must contain elements (i.e., this partial maximal chain).
Then it conflicts with current behaviour. Try
P = Posets.BooleanLattice(3) P.maximal_chains([1])
Hence we would need a deprecation in any case.
comment:20 followup: ↓ 21 Changed 5 years ago by
So the documentation indicates that this method should find all maximal chains that beings with partial
. Hence, a priori, we don't actually require the result when given partial
to be a maximal chain of the poset (or at least, whether that is a requirement is vague). We might just have to actually update the documentation and maybe deal with the cases when the partial is not some interval.
comment:21 in reply to: ↑ 20 Changed 5 years ago by
Replying to tscrim:
We might just have to actually update the documentation and maybe deal with the cases when the partial is not some interval.
But two other functions require that the function gives list of elements that are not a chain.
New commits:
Correction to maximal_chains.