#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 aschilling):
> > 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.
That condition is fine, but the labeling of the "canonical" labeling is
still arbitrary and not unique (as you can see, it has changed).
> 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".
Why? Your isomorphism property is still satisfied:
{{{
sage: p1 = Poset(d, linear_extension=True)
sage: p2 = p1.relabel({1:1,2:3,3:2})
sage: q1 = p1.canonical_label()
sage: q2 = p2.canonical_label()
sage: q1.is_isomorphic(q2)
True
sage: q1._linear_extension
True
sage: q2._linear_extension
True
}}}
> I also believe that `is_isomorphic` should raise an exception in that
case.
No, it checks that the posets are isomorphic (which has nothing to do with
the linear extension chosen).
Anne
--
Ticket URL: <http://trac.sagemath.org/ticket/14019#comment:65>
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.
