#15278: Hash and equality for graphs
--------------------------------+-------------------------
Reporter: SimonKing | Owner:
Type: defect | Status: new
Priority: major | Milestone: sage-5.13
Component: graph theory | Resolution:
Keywords: | Merged in:
Authors: | Reviewers:
Report Upstream: N/A | Work issues:
Branch: | Commit:
Dependencies: #12601 | Stopgaps:
--------------------------------+-------------------------
Changes (by SimonKing):
* dependencies: => #12601
Comment:
Replying to [comment:2 SimonKing]:
> - In order to fix the hash, it must take into account precisely the data
that are used in `__eq__`.
Perhaps I am over-eager at this point. The hash is ''not'' broken. Being
broken means that two graphs that evaluate equal have distinct hash
values. But this can currently not happen. So, it's fine.
Therefore I modify the "easiest way to go":
- We keep equality test as it currently is. Here, I am being egoistic: As
long as the edge labels and the multiplicity of edges count in equality
testing, I simply don't care whether _weighted counts or not. I just need
immutable graphs ''with a fast hash''.
- We want that graphs using the immutable graph backend are immutable in
the sense stated above. Hence, we must disallow G.weighted(True/False) if
G is supposed to be immutable. Hence, G.weighted should check for the
G._immutable flag. Similarly, we must proceed with all other non-
underscore methods that could potentially change the ==-class of G.
- In particular, we want that that G._immutable is set when the immutable
backend is in use.
- The hash will of course keep raising an error if `G._immutable` does not
evaluate to True. However, we would not like that the hash of an immutable
graph is re-computed, since this is too slow. Hence, we should use
`@cached_method` on the `__hash__`. We thus use #12601.
Do you agree on using #12601?
--
Ticket URL: <http://trac.sagemath.org/ticket/15278#comment:3>
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.
