#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 | Keywords:
Merged in: | Authors:
Reviewers: | Report Upstream: N/A
Work issues: | Branch:
Commit: | Dependencies:
Stopgaps: |
----------------------------+----------------------------
1. The documentation of `GenericGraph.__eq__` contains "For equality, ...,
output the same vertex list (in order), ...". However, since
[http://git.sagemath.org/sage.git/commit/?id=b59285e6f9b91f25ee2c77bfe940a45c51b58f80
b59285e6] (Trac #14806: Immutable graph backend), the order of the
vertices is no longer checked. So either that check should be
reintroduced, or the documentation should be updated.
The list returned by `.vertices()` is sorted, so that checking the
order only affects the result in rare cases. Hence I think updating the
documentation should be okay, even while it is technically backwards
incompatible.
2. While `GenericGraph.__eq__` no longer takes the ordering of vertices
into account, `GenericGraph.__hash__` still does. Consequently graphs that
compare equal can have different hashes.
3. For graphs that are not weighted, `GenericGraph.__eq__` ignores the
edge labels, while `GenericGraph.__hash__` does not.
Item 3 is most easily shown:
{{{
sage: G1 = Graph({0: {1: 'edge label A'}}, immutable=True)
sage: G2 = Graph({0: {1: 'edge label B'}}, immutable=True)
sage: G1 == G2
True
sage: G1.__hash__() == G2.__hash__()
False
}}}
For items 2 and 3, here is some contrived but deterministic code showing
that the order is not checked in `.__eq__`, while it is in `.__hash__`:
{{{
#!python
import functools
@functools.total_ordering
class C:
def __init__(self, val, reverse):
self.val = val
self.reverse = reverse
def __repr__(self):
return 'C(%r, %r)' % (self.val, self.reverse)
def __hash__(self):
return hash(self.val)
def __eq__(self, other):
return self.val == other.val
def __lt__(self, other):
if self.reverse:
return self.val > other.val
else:
return self.val < other.val
G1 = Graph({C(0, False): [], C(1, False): []}, immutable=True)
G2 = Graph({C(0, True ): [], C(1, True ): []}, immutable=True)
}}}
{{{
sage: [G1.vertices(), G2.vertices()]
[[C(0, False), C(1, False)], [C(1, True), C(0, True)]]
sage: G1 == G2
True
sage: hash(G1) == hash(G2)
False
}}}
The trick in the code above is to obtain tuples (x1, y1) and (x2, y2) that
compare equal but sort differently. Above this is achieved explicitly
using the argument `reverse`. However, this can also happen by
coincidence, as the code below shows. Here the inequality comparison falls
back to comparison of ids, so we just generate objects until the ids are
in an unlucky order.
{{{
#!python
from random import randint
from sage.graphs.graph import Graph
class Foo:
def __init__(self, b):
self.b = b
def __eq__(self, other):
return self.b == other.b
def __hash__(self):
return hash(self.b)
def __repr__(self):
return "foo(%r)" % (self.b,)
def gen(f):
print "* Trying to obtain res = ((f(0),f(1)), (f(0),f(1))) with\n" \
" (not res[0][0] < res[0][1]) and (res[1][0] < res[1][1])."
candidates = [[],[]]
res = [None, None]
while res[False] is None or res[True] is None:
bit = randint(0,1)
candidates[bit].append( f(bit) )
for x in candidates[0]:
for y in candidates[1]:
res[bool(x < y)] = (x,y)
print "* Succeeded after %i random picks." \
% (len(candidates[0]) + len(candidates[1]),)
print ("* res[0] = %r\n res[1] = %r") % (res[0], res[1])
return res
def doit(f):
print
print "* f = %r" % (f,)
res = gen(f)
print "* For i=0 and i=1 creating graph G[i] with vertices " \
"res[i] and no edges"
G = [Graph(dict((x, []) for x in res[bit]), immutable = True)
for bit in range(2)]
print "* G[0] = %r\n G[1] = %r" % (G[0], G[1])
print "* G[0].vertices() = %r\n G[1].vertices() = %r" % \
(G[0].vertices(), G[1].vertices())
print "* res[0] == res[1] : %r" % \
(res[0] == res[1],)
print "* sorted(res[0]) == sorted(res[1]) : %r" % \
(sorted(res[0]) == sorted(res[1]),)
print "* G[0] == G[1] : %r" % (G[0] == G[1],)
print "* hash(G[0]) == hash(G[1]) : %r" % \
(hash(G[0]) == hash(G[1]),)
print
}}}
{{{
sage: doit(Foo)
* f = <class __main__.Foo at 0xacb694ac>
* Trying to obtain res = ((f(0),f(1)), (f(0),f(1))) with
(not res[0][0] < res[0][1]) and (res[1][0] < res[1][1]).
* Succeeded after 6 random picks.
* res[0] = (foo(0), foo(1))
res[1] = (foo(0), foo(1))
* For i=0 and i=1 creating graph G[i] with vertices res[i] and no edges
* G[0] = Graph on 2 vertices
G[1] = Graph on 2 vertices
* G[0].vertices() = [foo(1), foo(0)]
G[1].vertices() = [foo(0), foo(1)]
* res[0] == res[1] : True
* sorted(res[0]) == sorted(res[1]) : False
* G[0] == G[1] : True
* hash(G[0]) == hash(G[1]) : False
}}}
The custom class `Foo` above is not necessary:
{{{
sage: doit(lambda x: sage.graphs.graph.Graph(x, immutable=True))
* f = <function <lambda> at 0xac556b1c>
* Trying to obtain res = ((f(0),f(1)), (f(0),f(1))) with
(not res[0][0] < res[0][1]) and (res[1][0] < res[1][1]).
* Succeeded after 4 random picks.
* res[0] = (Graph on 0 vertices, Graph on 1 vertex)
res[1] = (Graph on 0 vertices, Graph on 1 vertex)
* For i=0 and i=1 creating graph G[i] with vertices res[i] and no edges
* G[0] = Graph on 2 vertices
G[1] = Graph on 2 vertices
* G[0].vertices() = [Graph on 1 vertex, Graph on 0 vertices]
G[1].vertices() = [Graph on 0 vertices, Graph on 1 vertex]
* res[0] == res[1] : True
* sorted(res[0]) == sorted(res[1]) : False
* G[0] == G[1] : True
* hash(G[0]) == hash(G[1]) : False
}}}
--
Ticket URL: <http://trac.sagemath.org/ticket/17086>
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.
