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

[SimonKing]

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.

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

[SimonKing]

Replying to SimonKing:

• 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 #12601.

Do you agree on using #12601?

[SimonKing]

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.

[SimonKing]

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'

[anonymous]

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

[ncohen]

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

[SimonKing]

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

[SimonKing]

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.

[ncohen]

• 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 #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

[SimonKing]

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

[SimonKing]

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

[SimonKing]

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.

[SimonKing]

Replying to ncohen:

• 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 #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

[ncohen]

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

[SimonKing]

Replying to ncohen:

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

[SimonKing]

Replying to SimonKing:

Honorary!

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

[ncohen]

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

[SimonKing]

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

[ncohen]

Replying to SimonKing:

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

[git]

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

​07bad46	Merge branch 'u/ncohen/15491' of ​git://trac.sagemath.org/sage into ticket/15278
​020cc82	trac #15491: addressing the reviewer's comments
​cd97926	trac #15491: directed immutable graphs report twice too many edges
​126b036	Merge branch 'master' into ticket/15278

[SimonKing]

I think we need to take care of another detail:

If the static graph backend is used, then self.delete_vertex(vertex) and similar mutating methods will result in an error raised by the backend.

However, the problem is that the backend is only called in the very end, after doing damage to attributes that the graph takes care of in addition to the backend:

        if in_order:
            vertex = self.vertices()[vertex]
        if vertex not in self:
            raise RuntimeError("Vertex (%s) not in the graph."%str(vertex))

        attributes_to_update = ('_pos', '_assoc', '_embedding')
        for attr in attributes_to_update:
            if hasattr(self, attr) and getattr(self, attr) is not None:
                getattr(self, attr).pop(vertex, None)
        self._boundary = [v for v in self._boundary if v != vertex]

        self._backend.del_vertex(vertex)

Shouldn't this better be

        if in_order:
            vertex = self.vertices()[vertex]
        if vertex not in self:
            raise RuntimeError("Vertex (%s) not in the graph."%str(vertex))

        self._backend.del_vertex(vertex)
        attributes_to_update = ('_pos', '_assoc', '_embedding')
        for attr in attributes_to_update:
            if hasattr(self, attr) and getattr(self, attr) is not None:
                getattr(self, attr).pop(vertex, None)
        self._boundary = [v for v in self._boundary if v != vertex]

[ncohen]

If the static graph backend is used, then self.delete_vertex(vertex) and similar mutating methods will result in an error raised by the backend.

If this thing is the code of .delete_vertex then we have a lot of things to worry about. WHY THE HELL is this thing building a list of size number_of_vertices for the _boundary operation EACH TIME A VERTEX IS REMOVED ? O_O

Anyway. What you want to do is a good way out. Adding a decorator to set_boundary and making it called by this function would do the job too. But the first important thing to do is to replace this stupid creation of a new list with a call to list.remove or something, in order to NOT create a list each time a vertex is deleted.

Fortunately this list is always empty. I should deprecate and remove this thing, that's what I should do. Nobody know why it's here for, it's awfully undocumented. This thing should be removed >_<

So yeah, you can fix your problem by relying on the exception thrown by the backend. And I'll write a patch to deprecate this stupid boundary thing.

Nathann

[SimonKing]

Shouldn't named graphs be immutable?

sage: G = graphs.PetersenGraph()
sage: G._backend
<class 'sage.graphs.base.sparse_graph.SparseGraphBackend'>
sage: G.delete_vertex(1)
sage: G
Petersen graph: Graph on 9 vertices
sage: G.delete_vertex(2)
sage: G
Petersen graph: Graph on 8 vertices

I would expect that in order to modify something "named", one should create a mutable copy first.

[ncohen]

Shouldn't named graphs be immutable?

Please no !

I would expect that in order to modify something "named", one should create a mutable copy first.

Yep. So when you add a vertex, the graph's name should change or be removed ? Or would you remove the name attribute itself for mutable graphs ? Or would you drop the name of a graph when it is converted to a mutable copy ?

If this is to be done someday (all named graphs made immutable), it will be after a very simple task : I want to be sure *first* that all current methods will work fine on immutable graphs. And I am 100% sure that it is *not* the case at the moment.

Because many graph methods can take a copy of self and modify it. But if self is immutable the copy will be immutable too, and no edge/vertices can be touched on the copy either. And these methods have not been written while taking this into account. And all these functions *will* break on immutable graphs.

We already had the experience of "bipartite graphs", a new class of graph that made sure all graphs stayed bipartite. Sometimes, adding an edge would raise an exception because such an edge couldn't be added while keeping the graph bipartite. This class was hell. Making it the default class of graphs.CompleteBipartiteGraph would have been hell too.

So please, the named graphs stay mutable for the moment, unless this job is done responsibly.

Nathann

[ncohen]

Honestly, I would prefer to drop graph names. I don't even see the point of that :-P

Nathann

[SimonKing]

Replying to ncohen:

Honestly, I would prefer to drop graph names. I don't even see the point of that :-P

Perhaps I was not clear enough. I have nothing against changing a graph that has a name. But I am against changing a graph that is part of a data base.

[SimonKing]

A different question: Shall we simply rely on the error that is raised by the static backend (which is an AttributeError when adding or deleting a vertex and a NotImplementedError when adding ), or should we catch the error and raise a TypeError instead, with an error message telling that this is an immutable graph and adding a vertex is a bad idea in the case of an immutable graph?

That's to say, would it be enough to have

sage: G_imm = Graph(graphs.PetersenGraph(), data_structure="static_sparse")
sage: G_imm.add_vertex(100)
Traceback (most recent call last):
...
AttributeError: 'StaticSparseBackend' object has no attribute 'vertex_ints'
sage: G_imm.delete_vertex(0)
Traceback (most recent call last):
...
AttributeError: 'StaticSparseBackend' object has no attribute 'vertex_ints'
sage: G_imm.add_edge(1,2)
Traceback (most recent call last):
...
NotImplementedError:

or would we like to have

sage: G_imm.add_edge(1,2)
Traceback (most recent call last):
...
TypeError: Can not add an edge to an immutable graph

[ncohen]

A different question: Shall we simply rely on the error that is raised by the static backend (which is an AttributeError when adding or deleting a vertex and a NotImplementedError when adding ), or should we catch the error and raise a TypeError instead, with an error message telling that this is an immutable graph and adding a vertex is a bad idea in the case of an immutable graph?

Hmmm.. Well, in the code of static_sparse_backend there is an add_vertex function which whose code is the following :

raise ValueError("Thou shalt not add a vertex to an immutable graph")

But somehow this is not the exception that appears first when you add a vertex from the Python object. Well, I agree with you that having an exception saying that "this graph is immutable, and that's probably the origin of your problem" would be cool. If would be prettier if those exceptions were in the backend, and if these exceptions did appear when calling the add_edge/vertex methods from the Python object though :-)

Nathann

[git]

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

​2fc8a77

Make digraphs using the static backend immutable and hashable

[SimonKing]

With the current commit, all tests should pass, changing (di)graphs using the static backend requires some criminal energy, they have a hash, and it is documented.

The ValueError you are mentioning is not part of the add_vertex method of the static backend, by the way:

sage: G = graphs.PetersenGraph()
sage: G_imm = DiGraph(G, data_structure="static_sparse")
sage: G_imm._backend.add_vertex.__module__
'sage.graphs.base.c_graph'
sage: G_imm._backend.__module__
'sage.graphs.base.static_sparse_backend'

EDIT: Here is the mro:

sage: G_imm._backend.__class__.mro()
[sage.graphs.base.static_sparse_backend.StaticSparseBackend,
 sage.graphs.base.c_graph.CGraphBackend,
 sage.graphs.base.graph_backends.GenericGraphBackend,
 sage.structure.sage_object.SageObject,
 object]

[SimonKing]

Since the topic of this ticket is "hash and equality for graphs" and since we now have a way (by saying data_structure="static_sparse" when creating the graph) to produce immutable hashable graphs that evaluate equal to the corresponding mutable graphs, I'd say we should postpone the improvement of error messages. Hence: Needs review.

[ncohen]

HMmmmmm okay. Though I really have no clue what the changes you made to cachefunc.pyx do O_o

Is this related to this patch, or is it independent of immutable graphs and thus could be made into another trac ticket, on on which this one would depend ?

Nathann

[SimonKing]

Replying to ncohen:

HMmmmmm okay. Though I really have no clue what the changes you made to cachefunc.pyx do O_o

Hein? My branch doesn't touch cachefunc.pyx at all! And why should it?

Is this related to this patch, or is it independent of immutable graphs and thus could be made into another trac ticket, on on which this one would depend ?

I don't even have a clue what you mean by "this". You have provided a "static" backend that is almost enough to produce immutable graphs. To really make them immutable (in the sense stated repeatedly), it was needed to allow G.weighted() but disallow G.weighted(new_value) on immutable graphs, since the latter would mutate the graph. And if something is immutable then it makes sense to provide it with a hash---which in the case of graphs means to provide the ._immutable attribute---and to make the hash faster (by using work on @cached_method that has already been done in #12601).

So, that's what this ticket is about. Or is there anything I forgot?

And my next aim is to continue work on #12630. There, it is useful to have hashable (immutable) (di)graphs that can be used as cache keys.

[SimonKing]

Replying to SimonKing:

Replying to ncohen:

HMmmmmm okay. Though I really have no clue what the changes you made to cachefunc.pyx do O_o

Hein? My branch doesn't touch cachefunc.pyx at all! And why should it?

Ahaha, now I understand. That's this dreaded feature of the new git workflow: The commits changing cachefunc.pyx belong to #12601, hence, to a dependency of this ticket. But Volker believes that it is a good thing that a reviewer also has a look at what happens in the dependencies.

Personally, I believe that #12601 has a positive review and provides a feature that does not rely on graphs, but it is handy to use here. Hence, I don't think your review of this ticket must comprise a second review of #12601. Of course, if you happen to spot something in #12601 that doesn't work then please speak up.

[ncohen]

Yooooooooooooo !!

Hein? My branch doesn't touch cachefunc.pyx at all! And why should it?

Arggggg.. Well, i see modifications to cachefunc.pyx when I click on the banch's name, in the description of this ticket, at the top of the page. But that's from the dependency on #12601 it seems.

Looks like reviewing git branches with dependencies is going to be painful. Especially since Volker didn't want to hear anything of what was said on ​https://groups.google.com/d/topic/sage-git/ZC5QB1o1JlE/discussion Sigh. Sorry for the misunderstanding :-/

I don't even have a clue what you mean by "this". You have provided a "static" backend that is almost enough to produce immutable graphs. To really make them immutable (in the sense stated repeatedly), it was needed to allow G.weighted() but disallow G.weighted(new_value) on immutable graphs, since the latter would mutate the graph. And if something is immutable then it makes sense to provide it with a hash---which in the case of graphs means to provide the ._immutable attribute---and to make the hash faster (by using work on @cached_method that has already been done in #12601).

So, that's what this ticket is about. Or is there anything I forgot?

Sorry sorry, it's just a misunderstanding about what this branch contains... T_T

And my next aim is to continue work on #12630. There, it is useful to have hashable (immutable) (di)graphs that can be used as cache keys.

Okayyyyyyyyyyyyyyyyyyyyyyyyyyyyyy ! I thought that it was the case as soon as these things were hashable, but if you say so O_o

Nathann

[ncohen]

HMmmmm... Don't you touch cachefunc.pyx in commit 126b03609e9bae78955ccbc97e36f1924a79603b ? That's when you merge #12601 in the present branch.

Gosh, I'm going to hate these git dependencies.

Some remarks, though :

• In .copy(), you add a line before everything else to handle your case. Couldn't you add a line after the second "if" block, the one after which we know for sure that data_structure has been defined, saying "if data_structure == "static_sparse" and hasattr(self,'_immutable')" then return self ? By the way, is an object considered mutable if it HAS a ._immutable variable equal to False ?

• Why wouldn't we add (later) a "immutable" flag to the constructor and to "copy" ? It would be nice to call Graph(graphs.PetersenGraph(),immutable=True) ? O_o

• What about an exception message for _hash_ that would give the hint that hashable graphs can be built ? Something like "This graph is mutable, and thus not hashable. To make it mutable, read the doc of Graph.copy." I personnally don't mind much, it's more for your crowd... They may think that it can't be done and leave.

Oh. And it's cool, the multiple edges problem and loops are handled by the backend too. Well, thus making graphs immutable looks rather shorter than I first thought :-)

Nathann

[ncohen]

(I just created #15507 to handle graphs on > 65536 vertices)

Nathann

[SimonKing]

Replying to ncohen:

(I just created #15507 to handle graphs on > 65536 vertices)

Nice! But I suppose the two tickets are independent (no dependency in either direction), right?

[ncohen]

Yes yes they should commute :-)

Nathann

[SimonKing]

Nathann, what info do you need? Is this because of your comment:39?

[ncohen]

Yepyep that's why ^^;

I look for things I could review among the patches in "needs_review" state from time to time, and some are just waiting for a reaction from the author. But we can deal with this one now if you want !

Nathann

[SimonKing]

Replying to ncohen:

HMmmmm... Don't you touch cachefunc.pyx in commit 126b03609e9bae78955ccbc97e36f1924a79603b ? That's when you merge #12601 in the present branch.

Splitting hair...

Gosh, I'm going to hate these git dependencies.

+1

• In .copy(), you add a line before everything else to handle your case. Couldn't you add a line after the second "if" block, the one after which we know for sure that data_structure has been defined, saying "if data_structure == "static_sparse" and hasattr(self,'_immutable')" then return self ?

I am working on it.

By the way, is an object considered mutable if it HAS a ._immutable variable equal to False ?

Hmm. Would this be possible? I think a graph should be considered immutable if and only if the static backend is used---or rather if and only if some static backend is used: Perhaps there will be more static backends in future.

So, instead of relying on an attribute ._immutable that the user could mess with, one could test for the type of the backend when we need to know whether a graph is immutable.

Problem: If I am not mistaken, people currently do mess with the attribute ._immutable, if I am not mistaken.

Would it be feasible to try to remove the ._immutable attribute (and testing the type of the backend instead), see how much fails, and fix the failing code by using "proper" immutable graphs?

• Why wouldn't we add (later) a "immutable" flag to the constructor and to "copy" ?

Would a flag in the "copy" function be supported by Python?

It would be nice to call Graph(graphs.PetersenGraph(),immutable=True) ? O_o

Yes. Only problem: We would then need to decide what to do if "immutable=False" and "backend="static_sparse" is simultaneously used.

• What about an exception message for _hash_ that would give the hint that hashable graphs can be built ? Something like "This graph is mutable, and thus not hashable. To make it mutable, read the doc of Graph.copy."

OK.

[ncohen]

Yoooooooooooo !!

HMmmmm... Don't you touch cachefunc.pyx in commit 126b03609e9bae78955ccbc97e36f1924a79603b ? That's when you merge #12601 in the present branch.

Splitting hair...

Ahahah. Well, not really.. In a merge commit you have sometimes to settle conflicts manually, adding any amount of code you like, and this code needs to be reviewed too. And I have absolutely no understanding of this part of the code :-P

And for some reason I thought when I made this comment that it was the case, though I can't find it back again O_o

Well, well...

I am working on it.

Cool !

Hmm. Would this be possible? I think a graph should be considered immutable if and only if the static backend is used---or rather if and only if some static backend is used: Perhaps there will be more static backends in future.

So, instead of relying on an attribute ._immutable that the user could mess with, one could test for the type of the backend when we need to know whether a graph is immutable.

Problem: If I am not mistaken, people currently do mess with the attribute ._immutable, if I am not mistaken.

Yes yes indeed, that's what Nicolas told me they did at the moment, and that's what Python uses too know whether it should consider the object as mutable or not. I just wondered if it checked whether the variable existed, or whether the variable was set to True too.

Would it be feasible to try to remove the ._immutable attribute (and testing the type of the backend instead), see how much fails, and fix the failing code by using "proper" immutable graphs?

Hmmmm, I thought that Python really needed this _immutable variable somewhere O_o

Would a flag in the "copy" function be supported by Python?

Well not in .__copy__ but in .copy() no problem I guess.

It would be nice to call Graph(graphs.PetersenGraph(),immutable=True) ? O_o

Yes. Only problem: We would then need to decide what to do if "immutable=False" and "backend="static_sparse" is simultaneously used.

I usually settle this by setting the keywords to "None" by default, instead of True/False?. Then if the user manually sets two keywords to contradicting values, either ignore one of the two or scream, as usual. I'll do that in another patch when this one will be reviewed, it will be an easier syntax.

Nathann

[SimonKing]

Could it be that I did a stupid mistake? In __copy__, I read

        if getattr(self, '_immutable', False):
            if implementation=='c_graph' and data_structure is None and sparse is not None:
                return self

Shouldn't it be "if getattr(self, '_immutable', True):`?

[SimonKing]

Oopy, sorry, for the noise, it is correct in this way :-/ (facepalm)

[SimonKing]

Replying to ncohen:

Problem: If I am not mistaken, people currently do mess with the attribute ._immutable, if I am not mistaken.

Yes yes indeed, that's what Nicolas told me they did at the moment, and that's what Python uses too know whether it should consider the object as mutable or not. I just wondered if it checked whether the variable existed, or whether the variable was set to True too.

The usage is if getattr(self,'_immutable',False/True): raise TypeError("...") (false or true depending on whether we want to allow something for all graphs except those that are known to be mutable, or allow something for all graphs except those that are known to be immutable).

Would it be feasible to try to remove the ._immutable attribute (and testing the type of the backend instead), see how much fails, and fix the failing code by using "proper" immutable graphs?

Hmmmm, I thought that Python really needed this _immutable variable somewhere O_o

I've never heard before that Python uses it.

Would a flag in the "copy" function be supported by Python?

Well not in .__copy__ but in .copy() no problem I guess.

Now we talk about three things. I was talking about Python's (or Sage's?) copy() function, which dispatches to __copy__ or to pickling, depending on what's available. You talk about the .__copy__() method, which exists for graphs, and the .copy() method, which is set to __copy__ for graphs.

The copy() function does not use any argument except the object that is being copied. For that reason, I think the __copy__ method should not accept any arguments except self. But currently, the .__copy__() method of graphs uses a plethora of optional arguments.

Instead, I suggest that one should introduce a separate .copy() method: Here, it is no problem to add arguments. In particular, you can use such method to create a mutable copy resp. an immutable copy of an immutable resp. a mutable (di)graph. And it would be available in the docs (unlike .__copy__()).

On the other hand (thinking after writing, as usual...): The optional arguments of __copy__ are not used, but when one defines copy=__copy__ then the method and its documentation do appear in the docs and can be used by people. Hm. In the end, it might be better to keep it.

But one question on copying needs to be addressed: I think in some places in Sage, copy(X) returns X if X is immutable, but in other places in Sage, copy(X) always returns a mutable copy of X, regardless whether X is mutable or not. What would you prefer for graphs?

In any case, I should add a test showing what happens with copies of immutable graphs.

I usually settle this by setting the keywords to "None" by default, instead of True/False?. Then if the user manually sets two keywords to contradicting values, either ignore one of the two or scream, as usual. I'll do that in another patch when this one will be reviewed, it will be an easier syntax.

Do I understand correctly: You say I shouldn't try to add the "nicer" syntax now, since you would take care of it in a review patch/other ticket?

[ncohen]

Hellooooooooo !!

The usage is if getattr(self,'_immutable',False/True): raise TypeError("...") (false or true depending on whether we want to allow something for all graphs except those that are known to be mutable, or allow something for all graphs except those that are known to be immutable).

I've never heard before that Python uses it.

Oh. Then I guess we are the only ones to use this ._immutable flag.

On the other hand (thinking after writing, as usual...): The optional arguments of __copy__ are not used, but when one defines copy=__copy__ then the method and its documentation do appear in the docs and can be used by people. Hm. In the end, it might be better to keep it.

But one question on copying needs to be addressed: I think in some places in Sage, copy(X) returns X if X is immutable, but in other places in Sage, copy(X) always returns a mutable copy of X, regardless whether X is mutable or not. What would you prefer for graphs?

In any case, I should add a test showing what happens with copies of immutable graphs.

Hmmm... Well, I guess it makes more sense to get with "copy" the same kind of object that was given as input. So copying an immutable graph would just return the same object. Unless copy is called with an argument specifying a different implementation of course O_o

Do I understand correctly: You say I shouldn't try to add the "nicer" syntax now, since you would take care of it in a review patch/other ticket?

Well, if you feel like doing in this ticket I will gladly review it here. Otherwise I feel that it would be better to let this ticket be set to positive review so that you can use it for whatever you have in mind, and I will write this kind of improvements that are useless to you but would make my life easier :-)

Nathann

[SimonKing]

Replying to ncohen:

I've never heard before that Python uses it.

Oh. Then I guess we are the only ones to use this ._immutable flag.

Ahem. Then I guess there are many things in Python that I've never heard of...

But one question on copying needs to be addressed: I think in some places in Sage, copy(X) returns X if X is immutable, but in other places in Sage, copy(X) always returns a mutable copy of X, regardless whether X is mutable or not. What would you prefer for graphs?

Hmmm... Well, I guess it makes more sense to get with "copy" the same kind of object that was given as input.

From my perspective, this behaviour would be fine. But I also see this:

sage: M = matrix([[1,2,3],[4,5,6]])
sage: M.set_immutable()
sage: M.is_immutable()
True
sage: m = copy(M)
sage: m.is_immutable()
False

There is one crucial difference, though: A mutable matrix can be made immutable, by M.set_immutable(). But a mutable graph can (currently?) not easily be made immutable, since mutability crucially relies on the backend, which is not the case for matrices.

Anyway, I don't think that there is a commonly accepted standard in Sage. Since we have no G.set_immutable() method for graphs, I guess it is better to have

• copy(G) has the same backend as G. In particular, mutability is copied. And if it is immutable, then we should have G is copy(G).
• If one wants an immutable/mutable copy of a mutable/immutable graph G, then it should be done either by Graph(G,backend='...') or G.copy(backend='...') respectively with a to-be-implemented mutable=True/False keyword.

[ncohen]

Helloooooooo !!

Ahem. Then I guess there are many things in Python that I've never heard of...

Ahahahah. That's how sure we both are of our Python knowledge :-PPP

From my perspective, this behaviour would be fine. But I also see this:

sage: M = matrix([[1,2,3],[4,5,6]])
sage: M.set_immutable()
sage: M.is_immutable()
True
sage: m = copy(M)
sage: m.is_immutable()
False

There is one crucial difference, though: A mutable matrix can be made immutable, by M.set_immutable(). But a mutable graph can (currently?) not easily be made immutable, since mutability crucially relies on the backend, which is not the case for matrices.

Yepyep. Making it mutable needs to copy it, so it has to go through .copy or through the constructor.

Anyway, I don't think that there is a commonly accepted standard in Sage. Since we have no G.set_immutable() method for graphs, I guess it is better to have

• copy(G) has the same backend as G. In particular, mutability is copied. And if it is immutable, then we should have G is copy(G).
• If one wants an immutable/mutable copy of a mutable/immutable graph G, then it should be done either by Graph(G,backend='...') or G.copy(backend='...') respectively with a to-be-implemented mutable=True/False keyword.

Yepyep, works for me :-)

Nathann

[git]

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

​51d6328

Trac 15278: Error messages explain how to create (im)mutable graph copy

[SimonKing]

Nathann, I think I have addressed your requests: The error messages explain how to create a mutable resp. an immutable copy, and I have moved the added lines a bit further down in __copy__.

[ncohen]

thaaaaaaaaaaaaaanks !!!

Nathann

[ncohen]

Helloooooo !!

I'm sorry but this ticket has to be rebased. I created #15603 which is based on this ticket and the patchbot reports a lot of broken doctests, which seems to happen as soon as one merges this ticket with 6.1.beta2. And I have no clue how this patch can have any effect on that code O_o

Here are the doctests that are reported to be broken on #15603

sage -t --long src/sage/combinat/posets/posets.py  # 37 doctests failed
sage -t --long src/sage/graphs/base/c_graph.pyx  # 3 doctests failed
sage -t --long src/sage/misc/c3_controlled.pyx  # 8 doctests failed
sage -t --long src/sage/combinat/posets/hasse_diagram.py  # 1 doctest failed
sage -t --long src/sage/combinat/posets/linear_extensions.py  # 78 doctests failed

The exceptions caused to c_graph.pyx seem to be my doing, though. Everything else looks related to linear extensions.

Nathann

[SimonKing]

I have just merged the branch from here (but not together with #15603!) with the latest develop branch, and will see what I can do.

[SimonKing]

I get

sage -t --long src/sage/graphs/base/c_graph.pyx
    [442 tests, 9.64 s]
----------------------------------------------------------------------
All tests passed!
----------------------------------------------------------------------
Total time for all tests: 10.0 seconds
    cpu time: 8.7 seconds
    cumulative wall time: 9.6 seconds

but I can confirm the errors in c3_controlled. Strange! Why did this not happen earlier? Can you identify a ticket that has been merged into Sage-6.1.beta2 and has to do with linear extensions?

[ncohen]

Yoooooooooo !

but I can confirm the errors in c3_controlled. Strange! Why did this not happen earlier? Can you identify a ticket that has been merged into Sage-6.1.beta2 and has to do with linear extensions?

Hmmmm... Well, I'd think that it is a Poset-related ticket, since all the linear_extension stuff seems to break. And well, it looks like I am responsible for the Poset stuff that got merged since 6.0:

~/sage/combinat$ git log --oneline --merges d --author Release ^6.0 .
5dc0fb6 Trac #15332: Poset.lt computes too much
4254523 Trac #15330: Poset.is_chain is wrong
576167b Trac #15055: minor cleanup in incidence structures
dadfe61 Trac #14770: Alternating sign matrix transformations
aaaf103 Trac #13872: Non-exceptional rigged configuration bijections
7066356 Trac #15065: clean up the doc of fast_callable
59f05bd Trac #15479: Finite Words should be proud of their finiteness
4859012 Trac #15405: Implement the six vertex model
c04a8de Trac #15185: Clean up interface to the PARI library
69b08fa Trac #15391: Implementing the Foata bijection on permutations
f570a54 Trac #15372: Alternating sign matrix lattice will not plot.
e603630 Trac #15503: DegreeSequences(n) returns false positive
85a23f3 Trac #15480: Words.__eq__ returns wrong answers
092c6f9 Trac #15313: is_linear_extension on posets is rather liberal
e201dcd Trac #15473: Minor fixes to symmetric functions
3125f9f Trac #15467: Partitions return wrong result for obvious reasons
ee684c1 Trac #15340: Bug in chord_and_tangent

~/sage/combinat$ git log --oneline --merges d --author Release ^6.0 posets/
5dc0fb6 Trac #15332: Poset.lt computes too much
4254523 Trac #15330: Poset.is_chain is wrong
092c6f9 Trac #15313: is_linear_extension on posets is rather liberal
ee684c1 Trac #15340: Bug in chord_and_tangent

(d is my develop branch).

But #15322 only simplifies code, and #15330 is a bugfix. Actually, I don't even understand how any of that could be related to the specific feature you implemented. Nobody should be calling that code. It may be related to #15313, who knows ? It is a bugfix too. Poset.is_linear_extension([1,2,3,4]) could return True even if 4 is not contained in the Poset, and the patch fixes it :-/ And #15340 looks totally unrelated.

Nathann

[SimonKing]

Oooooops:

sage: P = Poset(([1,2,3,4], [[1,3],[1,4],[2,3]]), linear_extension=True, facade = False)
sage: P
Finite poset containing 4 elements
sage: p = P.linear_extension([1,4,2,3])
<Booom>
sage: P
Finite poset containing 0 elements

So, somehow the linear extension steals the poset's elements

[ncohen]

Facades. What a wonder. I hate this thing. I hate parents, I hate elements, I hate categories, and I hate UniqueElement. #13747 was a long time ago though :-P

Nathann

[SimonKing]

... or rather

sage: P = Poset(([1,2,3,4], [[1,3],[1,4],[2,3]]), linear_extension=True, facade = False)
sage: P
Finite poset containing 4 elements
sage: P.linear_extensions()
The set of all linear extensions of Finite poset containing 0 elements
sage: P
Finite poset containing 0 elements
sage: P == Poset(([1,2,3,4], [[1,3],[1,4],[2,3]]), linear_extension=True, facade = False)
False

[ncohen]

I love the idea. Aren't Posets supposed to be immutable ? And aren't they modified when one calls "linear_extensions" ? Either way it has to be the graphs' fault somewhere. It only happens with this equality code.

Nathann

[SimonKing]

Ahaaa! By using trace(), I found that the above uses __copy__---and I did change it. More precisely: It copies the "Hasse diagram of a poset containing 4 elements", which has the ._immutable flag set to true, but the sage.graphs.base.sparse_graph.SparseGraphBackend.

So, the Hasse diagram is not truely immutable, but just pretends to be. Either we should use the static sparse backend for Hasse diagrams, or we should test the type of the backend, rather than only relying on the ._immutable flag (this is one of the things that I have suggested above, and perhaps we should implement it).

[SimonKing]

Or go the middle way: In __hash__ and in the self-mutating methods, we should rely on the flag, but in __copy__ we should be more careful, and should only return self if it is truely immutable.

Namely, it seems currently used to create the copy of a mock-immutable graph to mutate the copy, and thus we must return a proper copy rather than just self in this case.

[ncohen]

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

[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

[SimonKing]

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

[ncohen]

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

Nathann

[SimonKing]

Replying to ncohen:

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.

[SimonKing]

Replying to ncohen:

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.

[ncohen]

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

[ncohen]

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

[SimonKing]

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.

[ncohen]

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

[ncohen]

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

[git]

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

​2525d22

Trac 15278: Fix syntax error in doc test

[SimonKing]

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.

[ncohen]

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.

[SimonKing]

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?

[ncohen]

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

[SimonKing]

Replying to ncohen:

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?

[ncohen]

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