#17086: GenericGraph's documentation, __eq__, and __hash__ out of sync
-------------------------------------+-------------------------------------
Reporter: emassop | Owner:
Type: defect | Status: new
Priority: major | Milestone: sage-6.4
Component: graph theory | Resolution:
Keywords: | Merged in:
Authors: | Reviewers:
Report Upstream: N/A | Work issues:
Branch: | Commit:
u/emassop/graph_hash | a207b85b076036104911b312aa5639a0b135a2e0
Dependencies: | Stopgaps:
-------------------------------------+-------------------------------------
Comment (by emassop):
Replying to [comment:6 ncohen]:
> > No, I do not have a counter example. I might look into it, or not.
Either way, I would like to restrict this ticket to the totally ordered
case where the axioms for ordering use {{{is}}} and not {{{==}}}.
> >
> > When an {{{is}}}-based ordering does not respect {{{==}}}, such as
Python's default ordering using {{{id}}}, you can have {{{a1==a2 and
b1==b2}}} and {{{a1<b1 and a2>b2}}} at the same time. Within a single
graph this cannot happen as there {{{a1==a2}}} implies {{{a1 is a2}}}
(assuming that the given vertex labels are `==`-distinct). However, it
''is'' possible to construct ''a pair'' of graphs using {{{==}}}-equal
vertex lists that nonetheless have distinct {{{.vertices()}}}. This is
what happens above.
>
> Okay, it took me a while to understand but it seems that to you a 'is-
based' ordering when comparison does not yield a total order, and is not
necessarily agreeing with '=='. Why not. It has to work in this case too,
anyway.
I can't understand "to you ... with '=='" here. The problem can occur when
an {{{is}}}-based ordering disagrees with {{{==}}}. This can still happen
when it is total.
To be precise, the problem occurs when
* there are {{{x}}}, {{{y}}}, and {{{z}}} with {{{x < y}}}, {{{y < z}}}
and {{{x == z}}}.
This does not contradict the following axioms of an {{{is}}}-based total
ordering:
* {{{x < y and y < z}}} implies {{{x < z}}} for all {{{x}}}, {{{y}}},
{{{z}}}
* for all {{{x}}} and {{{y}}} exactly one of {{{x < y}}}, {{{x is y}}},
and {{{y < x}}} holds.
> Despite that, I call a list L 'sorted' when applying 'sorted' to L does
not change L. Even if the ordering only makes sense to Python. And lists
returned by `.vertices()` should always be sorted in this way. I do not
think that it is very bad if it does not hold, but that is how it is meant
to work.
If sorted only uses {{{<}}} and not {{{==}}}, and if {{{<}}} is an
{{{is}}}-based total order, then {{{sorted(sorted(L)) == sorted(L)}}} is
indeed true. So someone should maybe check the implementation of
{{{sorted}}} to see what comparisons are used.
> > According to the documentation the labels are ignored. Let's defer
what is right(tm) to a different ticket.
>
> Well, I do not think it needs a different ticket. I was surprised, but
that's as bad as it got. If it is documented I don't see anything wrong
with it. Especially since `is_isomorphic` also ignores edges by default.
Okay... your punctuation was a bit strange then: "This is *REALLY* bad !
Graphs with different labels should be non-equal !!! `O_O;;;;;`"
> The only problem is this 'weighted' keyword. It does not have anything
to do with weights, so the keyword is ill-chosen. This can be fixed in
another ticket, but there is nothing really urgent to solve either.
Agreed.
--
Ticket URL: <http://trac.sagemath.org/ticket/17086#comment:8>
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.
