#15278: Hash and equality for graphs
------------------------+--------------------------------
Reporter: SimonKing | Type: defect
Status: new | Priority: major
Milestone: sage-5.13 | Component: graph theory
Resolution: | Report Upstream: N/A
------------------------+--------------------------------
At #14806, an immutable graph backend has been introduced. However, the
resulting graphs are not known to be immutable.
{{{
sage: g = graphs.CompleteGraph(400)
sage: gi = Graph(g,data_structure="static_sparse")
sage: hash(gi)
Traceback (most recent call last):
...
TypeError: graphs are mutable, and thus not hashable
}}}
So, when the immutable graph backend is used, then the `._immutable`
attribute should be set to True.
But hang on: Does using the immutable graph backend really result in
immutable graphs? I.e., would it really be impossible to change the `==`-
and `cmp`-classes of a graph by "official" methods such as
"`add_vertex()`"? And is the current equality testing really what we want
to test?
Currently, `__eq__()` starts like this:
{{{
# inputs must be (di)graphs:
if not isinstance(other, GenericGraph):
raise TypeError("cannot compare graph to non-graph
(%s)"%str(other))
from sage.graphs.all import Graph
g1_is_graph = isinstance(self, Graph) # otherwise, DiGraph
g2_is_graph = isinstance(other, Graph) # otherwise, DiGraph
if (g1_is_graph != g2_is_graph):
return False
if self.allows_multiple_edges() != other.allows_multiple_edges():
return False
if self.allows_loops() != other.allows_loops():
return False
if self.order() != other.order():
return False
if self.size() != other.size():
return False
if any(x not in other for x in self):
return False
if self._weighted != other._weighted:
return False
}}}
1. Is it really a good idea to raise an error when testing equality of a
graph with a non-graph? Most likely not!
2. For sure, a graph that ''has'' multiple edges can not be equal to a
graph that does not have multiple edges. But should it really matter
whether a graph ''allows'' multiple edges when it actually doesn't
''have'' multiple edges?
3. Similarly for `.allows_loops()`.
4. Should `._weighted` be totally removed? Note the following comment in
the documentation of the `.weighted()` method: "edge weightings can still
exist for (di)graphs `G` where `G.weighted()` is `False`". Ouch.
Note the following annoying example from the docs of `.weighted()`:
{{{
sage: G = Graph({0:{1:'a'}}, sparse=True)
sage: H = Graph({0:{1:'b'}}, sparse=True)
sage: G == H
True
Now one is weighted and the other is not, and thus the graphs are
not equal::
sage: G.weighted(True)
sage: H.weighted()
False
sage: G == H
False
}}}
So, calling the method `weighted` with an argument changes the `==`-class,
even though I guess most mathematicians would agree that `G` has not
changed at all. And this would actually be the case even if `G` was using
the immutable graph backend!!!
The aim of this ticket is to sort these things out. To the very least,
graphs using the immutable graph backend should not be allowed to change
their `==`-class by calling `G.weighted(True)`. This would best be done by
banning `._weighted` from the equality test.
--
Ticket URL: <http://trac.sagemath.org/ticket/15278>
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.
