id,summary,reporter,owner,description,type,status,priority,milestone,component,resolution,keywords,cc,merged,author,reviewer,upstream,work_issues,branch,commit,dependencies,stopgaps
15278,Hash and equality for graphs,SimonKing,,"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)`.",defect,closed,major,sage-6.1,graph theory,fixed,,ncohen,,Simon King,Nathann Cohen,N/A,,u/SimonKing/ticket/15278,2525d22a6b3a687bf932c2afaa8297e40c7af3d8,"#12601, #15491",