#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 ncohen):
Yoooooooo !
> It's shiny new Python 2.7 material :).
Niiiiiiiiiice `:-P`
> Indeed you can set edge labels on unweighted graphs, but the documented
behaviour is that they are ignored in `__eq__`: "Note that graphs must be
considered weighted, or Sage will not pay attention to edge label data in
equality testing".
Weird. I had no idea and expected something different. Well. Nothing wrong
if it works as claimed, then `:-P`
> Whether edge labels ''should'' be checked or not, is a different
question, that I would like to keep outside the scope of this ticket.
Right right. I just did not expect that and I thought it was a bug. I
don't mind it if it is not.
> Either way, when `__eq__` is true, the hashes have to be the same. So if
`__eq__` ignores labels, then so should `__hash__`. I really see no point
in ignoring edge labels in `__hash__` when they are not ignored in
`__eq__`. I think that would just makes the hash weaker.
Of course, what you do makes sense in that case.
> 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.
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.
> Since Python's default ordering depends on {{{id}}} over which you have
no control, you need a bit of luck.
I would not have complained even if you had build a class for which `<=`
returns a random value `:-P`
> In {{{hash(..., self._is_weighted, ...)}}} I indeed included it
redundantly.
You were right.
> 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.
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.
Nathann
----
New commits:
||[http://git.sagemath.org/sage.git/commit/?id=06a3a12c358e74c3b02931350e1f42981a400b4e
06a3a12]||{{{fix typo}}}||
||[http://git.sagemath.org/sage.git/commit/?id=a207b85b076036104911b312aa5639a0b135a2e0
a207b85]||{{{Use more illustrative test}}}||
--
Ticket URL: <http://trac.sagemath.org/ticket/17086#comment:6>
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.
