#14019: equality is broken for Posets
-------------------------------------+-------------------------------------
Reporter: ncohen | Owner: sage-combinat
Type: defect | Status: needs_work
Priority: major | Milestone: sage-6.4
Component: combinatorics | Resolution:
Keywords: posets | Merged in:
Authors: Travis Scrimshaw, | Reviewers: Travis Scrimshaw,
Anne Schilling | Anne Schilling
Report Upstream: N/A | Work issues:
Branch: | Commit:
public/combinat/poset/fix_equality-14019|
8dddb16ee9bce94fab03989228cf83dd567f8ac0
Dependencies: #17059 | Stopgaps: #14185
-------------------------------------+-------------------------------------
Comment (by ncohen):
Hello !
> Ok. Why does the documentation say *unique* though? It does not make
sense to me.
Take two digraphs `D1,D2` labelled on whatever you want, and such that
`D1.is_isomorphic(D2)` is True. Then
`D1.canonical_label()==D2.canonical_label()` is True. In such a way, the
output of `canonical_label` is unique on its isomorphism class.
To me this is a sufficient reason to raise an exception in
`canonical_label` when an linear extension is defined:
`DiGraph.canonical_label` ignores the linear extension, and so the output
is not unique for a pair "Poset, linear extension".
I also believe that `is_isomorphic` should raise an exception in that
case.
> I think so. The documentation says that `canonical_label` is supposed to
label the poset with elements `\{0,1,\ldots,n-1\}`. I changed the code
slightly, so that [0,1,2,...]
> is a linear extension of the canonical relabeled poset.
Okay, but now the code totally ignores the linear extension that may be
stored within the poset. I have nothing against that, but it would be more
honest to raise an exception in that case, to say to the
"PosetWithLinearExtension" users that they should first explicitly convert
their poset to a 'normal one' before computing that. We are unable to
compute a canonical label for a pair "Poset, linear extension" right now.
Nathann
--
Ticket URL: <http://trac.sagemath.org/ticket/14019#comment:64>
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/d/optout.
