Hash and equality for graphs

[simon-king-jena]

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).

Depends on #12601
Depends on #15491

CC: @nathanncohen

Component: graph theory

Author: Simon King

Branch/Commit: u/SimonKing/ticket/15278 @ 2525d22

Reviewer: Nathann Cohen

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

[simon-king-jena]

comment:1

Shouldn't the hash of graphs be cached, for efficiency? Currently it does return hash((tuple(self.vertices()), tuple(self.edges()))), which seems rather expensive.

Note that #12601 makes it possible to comfortably turn the hash (and other special methods) into a cached method.

[simon-king-jena]

comment:2

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.

[simon-king-jena]

Dependencies: #12601

[simon-king-jena]

comment:3

Replying to @simon-king-jena:

• In order to fix the hash, it must take into account precisely the data that are used in __eq__.

Perhaps I am over-eager at this point. The hash is not broken. Being broken means that two graphs that evaluate equal have distinct hash values. But this can currently not happen. So, it's fine.

Therefore I modify 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 a fast hash.
• 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.
• The hash will of course keep raising an error if G._immutable does not evaluate to True. However, we would not like that the hash of an immutable graph is re-computed, since this is too slow. Hence, we should use @cached_method on the __hash__. We thus use @cached_method does not work for special methods #12601.

Do you agree on using #12601?

[simon-king-jena]

comment:4

A related question: Shouldn't copy(G) return G, if G is immutable? Currently, we have

sage: g = graphs.CompleteGraph(400)
sage: gi = Graph(g,data_structure="static_sparse")
sage: copy(gi) is gi
False

Moreover, copy(gi) takes a lot of time.

[simon-king-jena]

comment:5

Moreover, copying a graph currently erases the _immutable flag:

sage: gi._immutable = True
sage: hash(gi)
1186925161
sage: copy(gi) is gi
False
sage: copy(gi)._immutable
---------------------------------------------------------------------------
AttributeError                            Traceback (most recent call last)
<ipython-input-8-7ee33a4c939a> in <module>()
----> 1 copy(gi)._immutable

AttributeError: 'Graph' object has no attribute '_immutable'

[simon-king-jena]

Branch: u/SimonKing/ticket/15278

[ghost]

Commit: c774057

[ghost]

New commits:

[changeset:c774057]	Prepare hash and copy for immutable graphs. Let .weighted() respect mutability.
[changeset:6cf1fad]	Faster and more thorough detection of special method names
[changeset:fe1e739]	Remove trailing whitespace
[changeset:13b500b]	#12601: Cached special methods

[nathanncohen]

New commits:

[changeset:c774057]	Prepare hash and copy for immutable graphs. Let .weighted() respect mutability.
[changeset:6cf1fad]	Faster and more thorough detection of special method names
[changeset:fe1e739]	Remove trailing whitespace
[changeset:13b500b]	#12601: Cached special methods

[simon-king-jena]

New commits:

[changeset:c774057]	Prepare hash and copy for immutable graphs. Let .weighted() respect mutability.
[changeset:6cf1fad]	Faster and more thorough detection of special method names
[changeset:fe1e739]	Remove trailing whitespace
[changeset:13b500b]	#12601: Cached special methods

[simon-king-jena]

Author: Simon King

[simon-king-jena]

comment:10

I have uploaded a preliminary "patch" (or branch, actually). The existing tests pass.

What it already does:

• If a graph is immutable then the __copy__ method returns the graph---unless of course optional arguments are passed to the __copy__ method. This is standard behaviour for immutable things, IIRC.
• If .weighted(...) is used to modify an immutable graph, then an error is raised.
• The __hash__ became a cached method

So far, I am not setting the ._immutable flag for the immutable graph backend. I did not add tests for the new code. And I did not verify that all "official" methods will be unable to alter an immutable graph (so far, I only fixed .weighted()). This shall be done in the next commits.

[nathanncohen]

comment:11

• About not requiring allows_multiple_edges and allows_loops to be equal :
  there is actually a technical problem there I just noticed : the
  get_edge_label function behaves differently according to the value of
  allow_multiple_edges(). It returns either a label, or a list of labels. And
  that complicates things.

  sage: g = graphs.PetersenGraph()
  sage: print g.edge_label(0,1)
  None
  sage: g.allow_multiple_edges(True)
  sage: print g.edge_label(0,1)
  [None]
  

  (I hate labels and multiple edges)

  Besides, testing whether the graph containts multiple edges is currently a bit
  costly. I think we actually go over all edges, and test it.

• About .weighted() : looks like the meaning of "weighted" is only used in
  spanning_tree.pyx. And I'd say that this can easily be replaced by an
  additional argument to the methods (as it is already the case in many others,
  like flow of traveling_salesman_problem)

• I believe (note sure, never used it) that .weighted() only indicates whether
  the labels on the edges are to be understood as weights. That's all. Multiple
  edges are handled by the backend, and each edge can have a different label,
  it's unrelated.

• I don't see any problem with using @cached_method does not work for special methods #12601. Do you see one ?

• copy(gi) takes a lot of time : indeed, returning self makes sense. If one
  actually wants to copy the immutable copy of the graph, i.e. the underlying C
  data and arrays, this can be made MUCH faster than the current
  implementation. Two calls to memcpy and it's settled :-P

• Why didn't you use the decorators from your first immutable graph patch to
  deal with immutability in .weighted() ?

• If you want to check that current functions act well on immutable graphs, you
  may be interested by the decorator named _run_it_on_static_instead in
  sage.graphs.backends.static_sparse_backend. It makes the function take the
  graph as input, create an immutable copy of it, and run the code and the
  immutable copy instead. It's still a lot of manual work to do, but it's easier
  than trying the functions hand by hand. Just add the decorator to the graph
  functions you want to test, and run the doctests ;-)

Sorry for the delay. I moved a lot through Paris with my backpack during the
last days :-P

Nathann

[simon-king-jena]

comment:12

This has a branch, but its status is "new", not "needs review". Is it ready for review, Nathann?

[simon-king-jena]

comment:13

Oooops. I just notice that I am the author. So, I should read my own code in order to see whether it is ready for review or not...

[simon-king-jena]

comment:14

Back at questions on the static graph backend...

In __eq__, the following data play a role:

• .allows_multiple_edges()
• .allows_loops()
• .order()
• .size()
• ._weighted
• vertex and edge labels, and of course start and endpoints of the edges.

For immutability, it is thus essential that these methods do not change the answers after applying non-underscore methods.

• ._weighted may be changed by the .weighted(new) method, which I thus made respectful against mutability. So, that is settled.
• The methods mentioned above call the backend, namely:
  1. `._backend.multiple_edges(None)
  2. ._backend.loops(None)
  3. ._backend.num_verts()
  4. ._backend.num_edges(self._directed)

So, my question boils down to this, Nathann: Is it possible for the static backend that the return value of the above methods 1.--4. changes, if the user is only using non-underscore methods on the graph? If it is not possible, then the __eq__ classes won't change when using the static graph backend, and I am happy.

The hash only takes into account the tuple of vertices and edges (which includes their labels). You have already confirmed that this is fine with the static backend.

[simon-king-jena]

comment:15

Replying to @nathanncohen:

• About not requiring allows_multiple_edges and allows_loops to be equal :

It will probably be fine to keep them in __eq__, as they simply ask for the backend's opinion, and the static backend hopefully has no changeable mind.

• About .weighted() : looks like the meaning of "weighted" is only used in
  spanning_tree.pyx. And I'd say that this can easily be replaced by an
  additional argument to the methods (as it is already the case in many others,
  like flow of traveling_salesman_problem)

OK, but removing ".weighted()" from __eq__ could be done later, I believe.

• I don't see any problem with using @cached_method does not work for special methods #12601. Do you see one ?

Nope.

• Why didn't you use the decorators from your first immutable graph patch to
  deal with immutability in .weighted() ?

With the decorator, an error would be raised whenever .weighted() is called on a mutable graph. However, .weighted only mutates the graph if it has an argument. G.weighted() will not change G, but will only tell whether G is weighted or not. I am not using the decorator in order to preserve this behaviour.

Best regards,

Simon

[nathanncohen]

comment:16

Yooooooooo !!!

• The methods mentioned above call the backend, namely:
  1. `._backend.multiple_edges(None)
  2. ._backend.loops(None)
  3. ._backend.num_verts()
  4. ._backend.num_edges(self._directed)

So, my question boils down to this, Nathann: Is it possible for the static backend that the return value of the above methods 1.--4. changes, if the user is only using non-underscore methods on the graph?

Nope. multiple_edges and loops will give you the list of multiple edges and loops, and that cannot change if the adjacencies do not change, so that's ok. Aaaaand the same goes with the number of vertices and edges, so you're fine !

If it is not possible, then the __eq__ classes won't change when using the static graph backend, and I am happy.

You can't be Happy. This guy is already named Happy, and there can't be two.
http://fairytail.wikia.com/wiki/Happy

The hash only takes into account the tuple of vertices and edges (which includes their labels). You have already confirmed that this is fine with the static backend.

While saying each time that the labels CAN change if they are lists and that the users append/remove things from them. But indeed :-P

Nathann

[simon-king-jena]

comment:17

Replying to @nathanncohen:

Nope. multiple_edges and loops will give you the list of multiple edges and loops, and that cannot change if the adjacencies do not change, so that's ok. Aaaaand the same goes with the number of vertices and edges, so you're fine !

Honorary!

While saying each time that the labels CAN change if they are lists and that the users append/remove things from them. But indeed :-P

While replying each time that I consider this a misuse, and if a user mutates labels manually (without using "official" methods) then (s)he should be ready to bear the consequences. So, I don't care about mutable labels :-P

[simon-king-jena]

comment:18

Replying to @simon-king-jena:

Honorary!

To my automatic spell checker: "Hooray", not "honorary"...

[nathanncohen]

comment:19

Honorary!

Indeed, indeed.

While replying each time that I consider this a misuse, and if a user mutates labels manually (without using "official" methods) then (s)he should be ready to bear the consequences. So, I don't care about mutable labels :-P

Ahahahah. Yeah yeah we understand each other. I'm just making it impossible for you to quote me saying that there will never be such problems in the future :-P

It should all work fine. I just looked at these multiple_edges and loops booleans in the backend and they won't move. Thoug we will need to add some docstrings in the final patch to check that there is nothing wrong with that, just in case. I'll do that during the review.

Have fuuuuuuuuuuuuuuuuuuuuun !

Nathann

[simon-king-jena]

comment:20

Is this a bug?

sage: import networkx
sage: g = networkx.Graph({0:[1,2,3], 2:[4]})
sage: G = DiGraph(g, data_structure="static_sparse")
sage: H = DiGraph(g)
sage: G==H
False
sage: G.size()
16
sage: H.size()
8

[nathanncohen]

comment:21

Replying to @simon-king-jena:

Is this a bug?

It is ! My mistake ! And it is fixed by #15491, which removes the ten characters that shouldn't have been there ^^;

Nathann

[nathanncohen]

Changed dependencies from #12601 to #12601, #15491

[nathanncohen]

comment:67

Oh. I see. Hacks.

Well, that makes sense indeed. Looks like a proof that we shouldn't rely on this _immutable flag. Especially when none of us knows who exactly uses it :-P

Is there an usual "is_immutable" function in immutable objects ? Perhaps we should do this. This function would check the actual backend, and return its answer accordingly.

This being said, checking the backend does not exactly mean that all other properties of graphs are "protected", like the embedding and everything.

Hmmm...

Okay, I just read your latest post : the point is that this ._immutable flag is a hack. Shouldn't we just make their code use the new backend, so that their code is not hacked anymore ? Right now they claim their graphs are immutable, though they aren't. Seems like the way to go, isn't it ?

Nathann

[sagetrac-git]

Changed commit from 51d6328 to fcf9e30

[sagetrac-git]

Branch pushed to git repo; I updated commit sha1. New commits:

fcf9e30	Trac 15278: Only graphs that use the static backend are identical with their copy
8fc9c94	Merge branch 'develop' into ticket/15278

[simon-king-jena]

comment:69

Argh! It happened again!!! I merged "develop" into my branch and forgot to remove it before pushing. Did I mention that I don't like git?

Anyway, the commit that is now being pushed should solve the problem.

---

New commits:

fcf9e30	Trac 15278: Only graphs that use the static backend are identical with their copy
8fc9c94	Merge branch 'develop' into ticket/15278

[nathanncohen]

comment:70

Well the problem it solves is making this ticket compatible with beta2. So the hack stays ?

Nathann

[simon-king-jena]

comment:71

Replying to @nathanncohen:

This being said, checking the backend does not exactly mean that all other properties of graphs are "protected", like the embedding and everything.

That's why both the flag and the type of the backend are checked before returning "self" as a copy.

Okay, I just read your latest post : the point is that this ._immutable flag is a hack. Shouldn't we just make their code use the new backend, so that their code is not hacked anymore ? Right now they claim their graphs are immutable, though they aren't. Seems like the way to go, isn't it ?

In a way, yes. In a different way: Are we supposed to clean up their mess? If they use the static backend, as they should, then the should also let copy() create a mutable copy; hence, each usage of copy() should be decorated with an optional argument (such as: sparse=True) which makes the copy be an actual mutable copy of the graph. So, it is more to do than just changing the backend, since in some places they pretend to have immutable graphs, but in others they want to mutate a copy of the graph.

[simon-king-jena]

comment:72

Replying to @nathanncohen:

Well the problem it solves is making this ticket compatible with beta2. So the hack stays ?

I only see one place where combinat uses bla._immutable = True:

src/sage/combinat/posets/posets.py:        G._immutable = True

So, perhaps it would not be too much of a problem to change this to using the static sparse backend. But then, we also need to identify where stuff is copied.

[nathanncohen]

comment:73

That's why both the flag and the type of the backend are checked before returning "self" as a copy.

Okay.

In a way, yes. In a different way: Are we supposed to clean up their mess?

...
We are not supposed to clean up their mess, only they never give a fuck. So unless somebody else does it it's still broken code. Okay, let's fix it as you do right now as we do not know what lies ahead, and try to fix it in a different ticket.

You say that it may be easy in the end, but let's not take chances with this patch either. I'll check it again, give it a positive review, and we'll move on to another ticket.

By the way, as we are talking about all we hate : does it take you several minutes to load that page each time you want to answer to a comment on this ticket ? This is a major source of frustration too O_O

Nathann

[nathanncohen]

comment:74

I get a doctest error in generic_graph.py :

+            sage: P = Poset(([1,2,3,4], [[1,3],[1,4],[2,3]]),
+            linear_extension=True, facade = False)

Nathann

[simon-king-jena]

comment:75

Meanwhile I see at what point the copy is taken: It is

    def transitive_reduction(self):
        r"""
        Returns a transitive reduction of a graph. The original graph is
        not modified.

        A transitive reduction H of G has a path from x to y if and only if
        there was a path from x to y in G. Deleting any edge of H destroys
        this property. A transitive reduction is not unique in general. A
        transitive reduction has the same transitive closure as the
        original graph.

        A transitive reduction of a complete graph is a tree. A transitive
        reduction of a tree is itself.

        EXAMPLES::

            sage: g=graphs.PathGraph(4)
            sage: g.transitive_reduction()==g
            True
            sage: g=graphs.CompleteGraph(5)
            sage: edges = g.transitive_reduction().edges(); len(edges)
            4
            sage: g=DiGraph({0:[1,2], 1:[2,3,4,5], 2:[4,5]})
            sage: g.transitive_reduction().size()
            5
        """
        from copy import copy
        from sage.rings.infinity import Infinity
        G = copy(self)
        for e in self.edge_iterator():
            # Try deleting the edge, see if we still have a path
            # between the vertices.
            G.delete_edge(e)
            if G.distance(e[0],e[1])==Infinity:
                # oops, we shouldn't have deleted it
                G.add_edge(e)
        return G

Hence, it seems that we indeed want a mutable copy here. And perhaps it isn't their mess after all, as this method is broken for all truely immutable graphs.

[nathanncohen]

comment:76

Ahahaha. Well, given that there are no immutable graphs in Sage at the moment, this function can't really be said to be broken :-D

They needed immutable graphs and didn't want to implement them, i.e. to deal with this kind of things. So well, that's our job now and we have to find out when they need immutable graphs and when they don't :-P

This copy has to be flagged with "immutable=False" (but that's only available in my patch) or with a specific data structure.

So let's finish this patch with your fix, I'll give it a positive review once it passes the tests. Then there is my patch that enables "copy" (that I will have to rebase), then on top of it there will be a patch to use immutable graphs in posets as they should be.

Aaaaaaaand now I have to go eat T_T

Nathann

[nathanncohen]

comment:77

I'm back ! If you can fix your last commit we can set this patch to positive review again. And considering how fast Volker merges them it could be available soon ;-)

Nathann

[sagetrac-git]

Branch pushed to git repo; I updated commit sha1. New commits:

2525d22

Trac 15278: Fix syntax error in doc test

[sagetrac-git]

Changed commit from fcf9e30 to 2525d22

[simon-king-jena]

comment:79

Fixed the syntax error, and checked that the failing test passes.

So, with the last two commits, we counter-hacked the hack with the ._immutable attribute. Next step will be to make #15603 ready (can you merge the missing commits from here into #15603, please?), and in a third step, we will properly remove the hack and perhaps the counter-hack too.

[nathanncohen]

comment:80

Fixed the syntax error, and checked that the failing test passes.

Yep. And they just passed on my computer too in graph/ combinat/ and misc/. Soooo positive_review again !

So, with the last two commits, we counter-hacked the hack with the ._immutable attribute.

Nod.

Next step will be to make #15603 ready (can you merge the missing commits from here into #15603, please?)

Nod. Plus I will probably have some conflicts because of what I do in .__copy__. Shouldn't be very long.

and in a third step, we will properly remove the hack and perhaps the counter-hack too.

Nod.

I fear that there may be nasty surprises hiding, though. For instance, I'm rather convinced that the static backend will produce a HUGE slowdown in their code, because right now distance computations (which translates as comparison in posets) is done by some code specific to the sparse backend. And thus does not exist for the static backend. So this will have to be written too. And then it should be much faster ;-)

Nathann

P.S. : it takes a lifetime to add a comment on a ticket.

[simon-king-jena]

comment:81

Question, after some off-ticket discussion: Pickling of immutable graphs does not work. Should we remove the positive review and implement it here, or shall we open a new ticket?

[nathanncohen]

comment:82

Well. What's the difference with implementing it in the ticket that will use it as the default backend for posets ? Nobody will use it in the meantime, and if you want to get technical it's not related to "hash and equality for graphs" either.

And this patch will be in needs_review in a couple of days at most anyway. It may be so this very evening if I can get around that bug i told you about :-P

Nathann

[simon-king-jena]

comment:83

Replying to @nathanncohen:

Well. What's the difference with implementing it in the ticket that will use it as the default backend for posets ? Nobody will use it in the meantime, and if you want to get technical it's not related to "hash and equality for graphs" either.

Good point. But I think it isn't in the "poset" ticket either". Would you mind if I created a new ticket "pickling of immutable graphs", that will end up to be a dependency for the poset ticket?

[nathanncohen]

comment:84

Ahahahah... Okay, if you think you would sleep better this way, no problem. I just created ticket #15619 for that, with part of the patch I was writing for the immutable backend of posets.

Nathann