Opened 6 years ago

Last modified 5 years ago

#20494 needs_info defect

Poset is_chain_of_poset(): error checking and saturated-keyword

Reported by: jmantysalo Owned by:
Priority: major Milestone: sage-7.3
Component: combinatorics Keywords:
Cc: Merged in:
Authors: Jori Mäntysalo Reviewers: Travis Scrimshaw
Report Upstream: N/A Work issues:
Branch: u/jmantysalo/saturated_chain (Commits, GitHub, GitLab) Commit: efe83f037d5ebbaec63549945c8b416df5d30326
Dependencies: Stopgaps:

Status badges

Description

This should be shown as an error

P = Posets.PentagonPoset()
P.is_chain_of_poset([1, 2, 4, 'junk'], ordered=True)

Also keyword saturated was asked to be added some time ago.

Change History (12)

comment:1 Changed 6 years ago by jmantysalo

  • Branch set to u/jmantysalo/saturated_chain

comment:2 Changed 6 years ago by jmantysalo

  • Commit set to efe83f037d5ebbaec63549945c8b416df5d30326
  • Status changed from new to needs_review

Frédéric, I think it was you who asked for saturated-option.


New commits:

efe83f0Added saturated-option.

comment:3 Changed 6 years ago by jmantysalo

Just pinging...

comment:4 Changed 6 years ago by jmantysalo

ping.

comment:5 Changed 6 years ago by tscrim

  • Milestone changed from sage-7.2 to sage-7.3
  • Reviewers set to Travis Scrimshaw

Two things:

-        - ``saturated`` -- a Boolean. If ``True``, then return ``True``
-          only if `elms` is a saturated chain. A chain `C` is saturated
-          when `a < b < c` and `a, c \in C` implies `b \in C`.
+        - ``saturated`` -- boolean; if ``True``, then return ``True``
+          only if `elms` is a saturated chain

and put

A chain `C` is saturated when `a < b < c` and `a, c \in C` implies `b \in C`.

in with the body of the docstring.

The other thing is I would also have the code be this like this:

# _element_to_vertex can be assumed to be a linear extension
# of the poset according to the documentation of class
# HasseDiagram.
H = self._hasse_diagram

if ordered:
    elms = [self._element_to_vertex(e) for e in elms]
else:
    elms = sorted(set([self._element_to_vertex(e) for e in elms]))

if saturated:
    return all(H.covers(a, b) for a, b in zip(elms, elms[1:]))
else:
    return all(H.is_lequal(a, b) for a, b in zip(elms, elms[1:]))
Last edited 6 years ago by tscrim (previous) (diff)

comment:6 Changed 6 years ago by jmantysalo

The code you suggests would mean that [1, 1, 2] is not a saturated chain of ChainPoset(42). Is this how you want it to be?

comment:7 follow-up: Changed 6 years ago by kdilks

It's my understanding that if repeated elements are allowed, then it's a multichain, and if repeated elements aren't allowed then it's just a chain. I don't know if Sage fully distinguishes between the two, so it might be worth having a separate ticket just dedicated to making that distinction clear in function names/documentation.

comment:8 in reply to: ↑ 7 ; follow-up: Changed 6 years ago by jmantysalo

Replying to kdilks:

It's my understanding that if repeated elements are allowed, then it's a multichain, and if repeated elements aren't allowed then it's just a chain. I don't know if Sage fully distinguishes between the two, so it might be worth having a separate ticket just dedicated to making that distinction clear in function names/documentation.

True. But currently

P = Posets.PentagonPoset()
P.is_chain_of_poset([2, 2, 3])

returns True. With suggested code it would still return True, but P.is_chain_of_poset([2,2,3], saturated=True) would return False.

How about third parameter allow_multichain with default value True to maintain current behaviour?

comment:9 in reply to: ↑ 8 Changed 6 years ago by jmantysalo

Replying to jmantysalo:

How about third parameter allow_multichain with default value True to maintain current behaviour?

Forget. Already ordered makes difference between multichain and chain.

Arghs. What to do? It sounds natural to have three different boolean options, as all 2^3 combinations are usable.

comment:10 Changed 6 years ago by jmantysalo

  • Status changed from needs_review to needs_info

Frédéric? How should this function work?

comment:11 follow-up: Changed 5 years ago by kdilks

I'm thinking we just find a way to make the code handle all three boolean options. Though I would call the third option strict=True, with strict=False corresponding to multichains.

Another thing to consider would be to add functions that take an unordered chain and return the ordered list, take a multichain and return the underlying strict chain, etc.

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

Replying to kdilks:

I'm thinking we just find a way to make the code handle all three boolean options. Though I would call the third option strict=True, with strict=False corresponding to multichains.

But how to resolve the problem with current ordered-option that makes two different things? We do not want to make an option that will change default value depending on other parameter? Or do we - have strict=None as a default. Sounds odd to me...

Another thing to consider would be to add functions that take an unordered chain and return the ordered list, take a multichain and return the underlying strict chain, etc.

I did #20934 for that.

Note: See TracTickets for help on using tickets.