hash() on Graph objects changes as the object is mutated

[sagetrac-cwitty]

This is bad:

sage: foo = Graph()
sage: hash(foo)
1033452963
sage: foo.add_vertex(1)
sage: hash(foo)
1537218837

__hash__ on Graph objects should be overridden to raise a TypeError.

Component: combinatorics

Issue created by migration from https://trac.sagemath.org/ticket/911

[jasongrout]

comment:1

From the python docs for __hash__ at http://docs.python.org/ref/customization.html :

"If a class defines mutable objects and implements a cmp() or eq() method, it should not implement hash(), since the dictionary implementation requires that a key's hash value is immutable (if the object's hash value changes, it will be in the wrong hash bucket)."

Currently, a Graph object defines a __cmp__ method, but not a __hash__ method. This seems to be in accordance with the python docs. However, I guess we are inheriting the __hash__ method from SageObject, so we should redefine the __hash__ method?

Here's a patch:

diff -r 36489d2c9a2e sage/graphs/graph.py
--- a/sage/graphs/graph.py      Tue Oct 16 09:50:59 2007 -0500
+++ b/sage/graphs/graph.py      Wed Oct 17 10:19:53 2007 -0500
@@ -359,6 +359,20 @@ class GenericGraph(SageObject):
             return self._nxg.name
         else:
             return repr(self)
+
+    def __hash__(self):
+        """
+       Since graphs are mutable, they should not be hashable, so we return a type error.
+
+       EXAMPLE:
+           sage: hash(Graph())
+            Traceback (most recent call last):
+            ...
+            TypeError: graphs are mutable, and so therefore are unhashable
+    
+       """
+       raise TypeError, "graphs are mutable, and so therefore are unhashable"
+
 
     def _latex_(self):
         """

[sagetrac-ekirkman]

Attachment: graph_hash.patch.gz

[sagetrac-ekirkman]

comment:2

Defect resolved by attached patch. Ready to include in 2.8.8!

[sagetrac-mabshoff]

comment:3

Please see http://groups.google.com/group/sage-devel/t/72ca87d027fb3e63 regarding the

[tested by ...]

byline.

Cheers,

Michael