#15322: Testing for antichains and chains in arbitrary posets
------------------------------------------------+--------------------------
Reporter: darij | Owner:
Type: enhancement | Status:
Priority: major | needs_review
Component: combinatorics | Milestone: sage-5.13
Keywords: posets, combinat, categories | Resolution:
Authors: Darij Grinberg | Merged in:
Report Upstream: N/A | Reviewers:
Branch: | Work issues:
Dependencies: #15283 | Commit:
| Stopgaps:
------------------------------------------------+--------------------------
Changes (by ncohen):
* cc: nthiery (added)
Comment:
Well, then if you insist on this `is_chain_of_poset` instead of `is_chain`
and as `_element_to_vertex` can be assumed to be a linear extension, this
patch looks right. What would you think of removing the second
implementation of `is_chain_of_posets` and merge it with the first one
though ? The docstrings are mostly similar, the documentation too. It
would be cool not to have copies of those.
The "ordered" version would be the same, and then you could just check for
the existence of this `._element_to_vertex` attribute. Would it also be
possible to add a comment like {{{# _element_to_vertex can be assumed to
be a linear extension of the poset}}} just before the call to `sorted` ? I
really wondered what was going on before remembering that this may be the
case `:-)`
Oh, and also : you use `Poset.le` from time to time, and the docstring
seem to indicate that it should be a `Poset.lt`. Plus in
`is_antichain_of_poset` you copy some part of the list in the second loop
(so manyyy many times) while you actually test `.gt` AND `.lt`.
This could be rewritten, I think more efficiently as :
{{{
return all(not self.lt(x,y) for x in o for y in o)
}}}
....
AND BY THE WAY (angry voice, right after wondering how `Poset.gt` was
implemented)
it looks like `Poset.lt` and `Poset.gt` actually call
`Poset.compare_elements`. And the code of `Poset.compare_elements` first
checks if `x<y` THEN if `x>y`.
As a result : any call to `.gt` or to `.lt` totally determines the
relationship between the two elements, and computing both `.lt` and `.gt`
actually computes TWICE whether the two elements are incomparable. As they
both call `.compare_elements`. When you compute if one is smaller than the
other Sage also wonder if it is not the opposite, or whether they are
incomparable. Only nobody asked it to.
Hence with the current implementation you should only call
`.compare_elements()` directly and use the full information it returns (as
`.lt` and `.gt` do the same and ignore some part of this information).
And these `.gt` and `.lt` functions will have to be patches eventually to
compute ONLY what they are asked to, and not twice as much.
Nathann
--
Ticket URL: <http://trac.sagemath.org/ticket/15322#comment:4>
Sage <http://www.sagemath.org>
Sage: Creating a Viable Open Source Alternative to Magma, Maple, Mathematica,
and MATLAB
--
You received this message because you are subscribed to the Google Groups
"sage-trac" group.
To unsubscribe from this group and stop receiving emails from it, send an email
to [email protected].
To post to this group, send email to [email protected].
Visit this group at http://groups.google.com/group/sage-trac.
For more options, visit https://groups.google.com/groups/opt_out.
