#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: | Stopgaps:
--------------------------------+-------------------------
Old description:
> 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.
New description:
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)`.
--
Comment (by SimonKing):
Concerning "weighted": What exactly is the semantics? Is it the case that
a weighted graph has positive integral edge weights, that could be taken
as the multiplicity of this edge? But then, do we want that a weighted
graph is equal to a multigraph with the corresponding multiplicity of
edges?
In any case, the hash is currently broken, since it does not take into
account weightedness, but equality check does.
It seems to me that the following is 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 an unbroken hash.
- In order to fix the hash, it must take into account precisely the data
that are used in `__eq__`.
- 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.
--
Ticket URL: <http://trac.sagemath.org/ticket/15278#comment:2>
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.
