Opened 6 years ago

Last modified 5 years ago

#18944 needs_info defect

Posets: maximal_chains() partial-option broken

Reported by: jmantysalo Owned by:
Priority: major Milestone: sage-6.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:

Status badges

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 jmantysalo

  • Branch set to u/jmantysalo/maximal_chains
  • Commit set to eeefd9d2c4184a3f60f505a7851ec3ff16eb7bf0

New commits:

eeefd9dCorrection to maximal_chains.

comment:2 follow-up: Changed 6 years ago by jmantysalo

  • 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 child-ticket of #18941.)

comment:3 in reply to: ↑ 2 Changed 6 years ago by ncohen

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 jmantysalo

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 kdilks

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 jmantysalo

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 git

  • Commit changed from eeefd9d2c4184a3f60f505a7851ec3ff16eb7bf0 to e6a4ae2b1f7f887b58a49af5c1607640c7821dde

Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:

e6a4ae2Removed broken partial-option from maximal_chains().

comment:8 Changed 6 years ago by jmantysalo

  • 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 follow-up: Changed 6 years ago by tscrim

  • Milestone changed from sage-6.8 to sage-6.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 jmantysalo

  • 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 follow-up: Changed 6 years ago by tscrim

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

comment:12 in reply to: ↑ 11 Changed 6 years ago by jmantysalo

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

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[i-1]]

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 follow-up: Changed 6 years ago by tscrim

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 jmantysalo

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 follow-up: Changed 5 years ago by jmantysalo

I am still wondering about this... Other parts of Sage relies on broken or non-defined behaviour of partial argument. It feels bad design.

comment:16 in reply to: ↑ 15 ; follow-up: Changed 5 years ago by tscrim

Replying to jmantysalo:

I am still wondering about this... Other parts of Sage relies on broken or non-defined 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 jmantysalo

Replying to tscrim:

Replying to jmantysalo:

I am still wondering about this... Other parts of Sage relies on broken or non-defined 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 follow-up: Changed 5 years ago by tscrim

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 jmantysalo

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 follow-up: Changed 5 years ago by tscrim

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 jmantysalo

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.

Note: See TracTickets for help on using tickets.