Mutability of Graphs

[simon-king-jena]

This patch allows to create immutable graphs, so that they can be used as keys in dictionaries.

Previously, calling hash on a graph did work after assigning the attribute _immutable to the graph. That's a hack, and it would in fact not prevent the graph from being mutated.

With this patch, the attempt to change an immutable graph be means of methods such as add_vertex or add_edge or delete_vertex, will result in an error. If one really wants to play nasty, one could make an immutable graph mutable and change it, or use the backend of the graph for changing the underlying data.

Apply attachment: trac14535-immutable_graphs_vb.patch

Depends on #14524 Depends on #14732

CC: @sagetrac-jernej

Component: graph theory

Keywords: mutability graph

Author: Simon King, Volker Braun

Reviewer: Simon King, Nathann Cohen

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

[simon-king-jena]

comment:1

Attachment: trac14535-immutable_graphs.patch.gz

[6bdad4c1-1e26-4f2f-a442-a01a2292c181]

comment:2

Hello !

• Could you show that there is no slowdown in the graph functions because of that please ?

• Besides, why do you need decorators in the Python classes if you forbid modifications directly in the backend ?

• You create 4 functions in a class that already has a LOT of them. We have several functions that work like that already :

sage: g.mutable()
Tells you if it is mutable
sage: g.mutable(True)
Sets it to be mutable

• There is a lot of things that graphs store and which are not vertices, nor edges. For example the vertices' layout, or its name... You can see the list of these awful things in GenericGraph.__eq__. If you just want to take edges and vertices in consideration could you say it explicitely in the documentation of the *_mutable methods ?

And.. Well.. Could you add me in Cc when you write things like that ?

Nathann

[simon-king-jena]

comment:4

Hi!

Replying to @nathanncohen:

Hello !

• Could you show that there is no slowdown in the graph functions because of that please ?

There certainly is a slowdown in all methods that are protected in this way. And I do not use the decorator in cdef classes, in an attempt to prevent a regression.

Does it make sense to time methods like add_vertex separately? In my applications, one would build a graph, and then it will never again be changed. But I am sure you have better use cases than I. Do you have examples in which add/delete_vertex/edge will typically be called zillions of times?

• Besides, why do you need decorators in the Python classes if you forbid modifications directly in the backend ?

I do not forbid to change the graphs in the backend. Or at least, I did not intend to modify the backends. If I did, then it was by mistake. If G is an immutable graph, then G._backend.add_vertex(...) should not complain.

The reason is, again, that I don't want a slow-down in the "private" methods. If one has an immutable graph used as key in a dictionary, and then decides to work around the "protected" methods add_vertex, add_edge etc by changing the graph G via G._backend, then this is a conscious decision for which the user takes full responsibility.

So, protection of the user will be restricted to the "official" methods G.add_vertex etc.

• You create 4 functions in a class that already has a LOT of them. We have several functions that work like that already :

sage: g.mutable()
Tells you if it is mutable
sage: g.mutable(True)
Sets it to be mutable

I did not find any support for mutability in graphs, except for the hack that makes hash work.

• There is a lot of things that graphs store and which are not vertices, nor edges. For example the vertices' layout, or its name... You can see the list of these awful things in GenericGraph.__eq__. If you just want to take edges and vertices in consideration could you say it explicitely in the documentation of the *_mutable methods ?

Not good. Yes, I should have looked up GenericGraph.__eq__ and take into account all data used there.

And.. Well.. Could you add me in Cc when you write things like that ?

Actually, when I created the ticket, I first looked at a preview, and saw that you are among the (default) owners of this ticket. Hence, I concluded that there is no need in adding you in Cc, because you already were on the list of recipients. Sorry if I misinterpreted the meaning of the list of "owners".

[simon-king-jena]

comment:5

Here is a little timing.

Without patch:

sage: K12 = graphs.CompleteGraph(12)
sage: K4 = graphs.CompleteGraph(4)
sage: def test(g,h):              
....:     g.delete_edges(h.edge_iterator())
....:     g.add_edges(h.edge_iterator())
....:     
sage: %timeit test(K12,K4)
10000 loops, best of 3: 118 us per loop

With patch:

sage: K12 = graphs.CompleteGraph(12)
sage: K4 = graphs.CompleteGraph(4)
sage: def test(g,h):
....:     g.delete_edges(h.edge_iterator())
....:     g.add_edges(h.edge_iterator())
....:     
sage: %timeit test(K12,K4)
10000 loops, best of 3: 131 us per loop
sage: (131-118)/118.*100
11.0169491525424

So, there is a slow-down of 11% in this example. I don't know if in "real" examples, the backend would be used (without slow-down) internally.

[simon-king-jena]

comment:6

Here are two more timings, this time using DenseGraph (hence, not using the decorator) and hash:

Without patch:

sage: from sage.graphs.base.dense_graph import DenseGraph
sage: D = DenseGraph(nverts=10, extra_vertices=10)
sage: def test(g):
....:     for i in xrange(100):
....:         g.add_vertex(i)
....:     for i in xrange(100):
....:         for j in xrange(100):
....:             g.add_arc(i,j)
....:     for i in xrange(100):
....:         g.del_vertex(i)
....:         
sage: %timeit test(D)
100 loops, best of 3: 2.59 ms per loop
sage: K12 = graphs.CompleteGraph(12)
sage: K12._immutable = True
sage: hash(K12)
-1604610596753853799
sage: %timeit hash(K12)
1000 loops, best of 3: 212 us per loop

With the patch:

...
sage: %timeit test(D)
100 loops, best of 3: 2.72 ms per loop
sage: (2.72-2.59)/2.59*100  # 5% slowdown
5.01930501930503
sage: K12 = graphs.CompleteGraph(12)
sage: K12.set_immutable()
sage: %timeit hash(K12)
1000 loops, best of 3: 216 us per loop

Anyway, I presume that in real use cases, faster unsafe methods would/could/should be used internally.

[simon-king-jena]

comment:7

I think I gave the info, so, back to "needs review"...

[6bdad4c1-1e26-4f2f-a442-a01a2292c181]

comment:8

Hellooooooooooooooo !!!

There certainly is a slowdown in all methods that are protected in this way. And I do not use the decorator in cdef classes, in an attempt to prevent a regression.

Hmmmm. And why should we accept a 10% slowdown in order to have immutable graphs ? :-P

Does it make sense to time methods like add_vertex separately? In my applications, one would build a graph, and then it will never again be changed. But I am sure you have better use cases than I. Do you have examples in which add/delete_vertex/edge will typically be called zillions of times?

Not really. Like you, in my examples I spend most of my time reading graphs. And wasting my time translating labels into integers :-P

• Besides, why do you need decorators in the Python classes if you forbid modifications directly in the backend ?

I do not forbid to change the graphs in the backend. Or at least, I did not intend to modify the backends. If I did, then it was by mistake. If G is an immutable graph, then G._backend.add_vertex(...) should not complain.

? But you make changes to CGraph, SparseGraph and DenseGraph, don't you ? O_o And why wouldn't it be better to only deal with immutability directly in the backends ? No need for decorators if it is done there, and if it is only a "if" with a niiice C variable which never changes. Would reduce the slowdown, wouldn't it ?

The reason is, again, that I don't want a slow-down in the "private" methods. If one has an immutable graph used as key in a dictionary, and then decides to work around the "protected" methods add_vertex, add_edge etc by changing the graph G via G._backend, then this is a conscious decision for which the user takes full responsibility.

Hmmmm... But the developpers could have to do that to make some methods more efficient, and then we would have to deal with immutability by hand. But really I am interested in your answer : why don't you prefer to deal with immutability in the backends directly ? In the graphs/base/ files ?

• You create 4 functions in a class that already has a LOT of them. We have several functions that work like that already :

sage: g.mutable()
Tells you if it is mutable
sage: g.mutable(True)
Sets it to be mutable

I did not find any support for mutability in graphs, except for the hack that makes hash work.

Nonono, we don't have such a method at all ! But we have two methods to allow loops and test if they are allowed :

sage: g = graphs.PetersenGraph()
sage: g.allows_loops()
False
sage: g.allow_loops(True)
sage: g.allows_multiple_edges()
False
sage: g.allow_multiple_edges(True)

So it's already half of what you take, and we could even merge two functions like allows_loops and allow_loops into one, as in my previous example. That's one of the joys of coding in Python.

Actually, when I created the ticket, I first looked at a preview, and saw that you are among the (default) owners of this ticket. Hence, I concluded that there is no need in adding you in Cc, because you already were on the list of recipients. Sorry if I misinterpreted the meaning of the list of "owners".

Oh. I see. Then it's the Trac developper's fault. The owners of a section are expected to receive an email indeed, except when there are ... several owners. In that case, no mails are sent :-P

http://trac.edgewall.org/ticket/7793

Nathann

[simon-king-jena]

comment:9

Replying to @nathanncohen:

There certainly is a slowdown in all methods that are protected in this way. And I do not use the decorator in cdef classes, in an attempt to prevent a regression.

Hmmmm. And why should we accept a 10% slowdown in order to have immutable graphs ? :-P

It would be nice to have a better solution, but, as for matrices, I do think it would be good to be able to use graphs as keys in dictionaries without a hack.

I do not forbid to change the graphs in the backend. Or at least, I did not intend to modify the backends. If I did, then it was by mistake. If G is an immutable graph, then G._backend.add_vertex(...) should not complain.

? But you make changes to CGraph, SparseGraph and DenseGraph, don't you ? O_o

Then we may have different notions of "backend". By "backend", I understood the stuff that is assigned to G._backend and is defined in sage.graphs.base.graph_backends`.

You think it might be better to move all mutability checks into the backend? I thought so as well, initially. But then I found that a couple of add_ methods first change some data outside* of the backend, and call the backend method only later. So, I thought it is safer to check mutability not in the backend, but in the graph.

Hmmmm... But the developpers could have to do that to make some methods more efficient, and then we would have to deal with immutability by hand. But really I am interested in your answer : why don't you prefer to deal with immutability in the backends directly ? In the graphs/base/ files ?

I would prefer to deal with it in the backends.

[6bdad4c1-1e26-4f2f-a442-a01a2292c181]

comment:10

It would be nice to have a better solution, but, as for matrices, I do think it would be good to be able to use graphs as keys in dictionaries without a hack.

And you would trade 10% of speed for that ? O_o

Really, the only way I see to do this properly is to write an immutable backend...

Then we may have different notions of "backend". By "backend", I understood the stuff that is assigned to G._backend and is defined in sage.graphs.base.graph_backends`.

Oh. Sorry, then. I call backend whatever is in the base/ folder, but perhaps that isn't right. In any case :

sage: type(Graph()._backend)
<class 'sage.graphs.base.sparse_graph.SparseGraphBackend'>

You think it might be better to move all mutability checks into the backend? I thought so as well, initially.

Yep. Looks much cleaner !

But then I found that a couple of add_ methods first change some data outside* of the backend, and call the backend method only later.

Oh ? Like which ones ? O_o

So, I thought it is safer to check mutability not in the backend, but in the graph.

I would prefer to deal with it in the backends.

+1.

Nathann

[simon-king-jena]

comment:11

Replying to @nathanncohen:

Oh. Sorry, then. I call backend whatever is in the base/ folder, but perhaps that isn't right. In any case :

sage: type(Graph()._backend)
<class 'sage.graphs.base.sparse_graph.SparseGraphBackend'>

OK, then we have the same notions...

But then I found that a couple of add_ methods first change some data outside* of the backend, and call the backend method only later.

Oh ? Like which ones ? O_o

sage.graphs.generic_graph.GenericGraph.delete_vertex, which is

        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]

and only afterwards calls the backend. If the order of dealing with attributes and dealing with the backend could be reversed, then making the backend immutable would be enough. But in this order, calling the method on an immutable graph backend would destroy some data before raising the error.

Perhaps I should have tried first whether it can be reversed...

Cheers,

Simon

[6bdad4c1-1e26-4f2f-a442-a01a2292c181]

comment:12

sage.graphs.generic_graph.GenericGraph.delete_vertex, which is

        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]

and only afterwards calls the backend.

Oh, yeah.. The boundary is stored by graphs, too >_<

If the order of dealing with attributes and dealing with the backend could be reversed, then making the backend immutable would be enough. But in this order, calling the method on an immutable graph backend would destroy some data before raising the error.

Perhaps I should have tried first whether it can be reversed...

Hmmmmmm. First I would like to know something : do you really want everything in the graph to be immutable ? Or only edges and vertices ?

Nathann

[simon-king-jena]

comment:13

Replying to @nathanncohen:

Oh, yeah.. The boundary is stored by graphs, too >_<

Right. Actually I can't recall if my patch protects changing the boundary.

Hmmmmmm. First I would like to know something : do you really want everything in the graph to be immutable ? Or only edges and vertices ?

I want that they are immutable in this sense: "It is impossible to change the hash or to change the ==-equivalence class of an immutable object by calling methods that do not start with an underscore.

[6bdad4c1-1e26-4f2f-a442-a01a2292c181]

comment:14

I want that they are immutable in this sense: "It is impossible to change the hash or to change the ==-equivalence class of an immutable object by calling methods that do not start with an underscore.

Then there's a nightmare ahead of you :-P

Nathann

[90e8124e-743e-4424-88b0-22f5ae41372b]

comment:15

I haven't looked at the patch yet, but I want to keep an eye on it, and I want to advocate uniformity: try to make the mutability behavior and interface the same as that of Sage's matrices.

I'd be happy if we got immutable graphs. I'd be very happy if we could add/delete/contract and get a copy of the graph without explicitly saying "inplace=False" all the time, but one can dream...

And what about the following?

sage: G = graphs.PetersenGraph()
sage: G
Petersen graph: Graph on 10 vertices
sage: G.add_vertex(11)
sage: G
Petersen graph: Graph on 11 vertices

Should named graphs be immutable?

[nbruin]

comment:16

sage: g.mutable()
Tells you if it is mutable
sage: g.mutable(True)
Sets it to be mutable

I hope that last line remains fantasy: Changing the mutability of an object is a mutation, so should be forbidden on an immutable object (the only case where g.mutable(True) should succeed is when g is already mutable).

[simon-king-jena]

comment:17

Replying to @nbruin:

I hope that last line remains fantasy: Changing the mutability of an object is a mutation, so should be forbidden on an immutable object (the only case where g.mutable(True) should succeed is when g is already mutable).

Sure it is a mutation. However, I was told a couple of times that the "pythonic way" is to pretend that programmers are adult people who know what they do and who are prepared to take responsibility for their actions. Hence, while there should be some protection against accidental changes to an immutable object, it should still be possible to work around the protection.

I conclude that it would be the anti-pythonic way to

• allow to make a mutable object immutable, but not the other way (this is by making _is_immutable a cdef attribute, and restrict the interface to three methods is_immutable, is_mutable and set_immutable)
• make it virtually impossible that a sub-class overrides a mutation-protected method by a method that does not check for mutation (this is possible with metaclasses)
• turn an object into an immutable object as soon as its hash is computed, so that its hash bucket will henceforth never change.

We need to find a reasonable middle way between the overly permissive approach ("all graphs are mutable and hashable, the programmer really has to be careful") and the overly protective approach (as described in the bulleted list).

[90e8124e-743e-4424-88b0-22f5ae41372b]

comment:18

Again, Matrices have (in my opinion) a decent balance:

sage: A = matrix([[1,2],[3,4]])
sage: A.set_immutable()
sage: A[1,1] = 4
Traceback (most recent call last):
...
ValueError: matrix is immutable; please change a copy instead (i.e., use copy(M) to change a copy of M).
sage: B = copy(A)
sage: B[1,1] = 1

Follow that lead, and be consistent with other parts of Sage.

[simon-king-jena]

comment:19

Replying to @sagetrac-Stefan:

Again, Matrices have (in my opinion) a decent balance:

sage: A = matrix([[1,2],[3,4]])
sage: A.set_immutable()
sage: A[1,1] = 4
Traceback (most recent call last):
...
ValueError: matrix is immutable; please change a copy instead (i.e., use copy(M) to change a copy of M).
sage: B = copy(A)
sage: B[1,1] = 1

Actually I have not been aware that there is no A.set_mutable. So, thank you for the pointer!

[nbruin]

comment:20

Replying to @simon-king-jena:

Sure it is a mutation. However, I was told a couple of times that the "pythonic way" is to pretend that programmers are adult people who know what they do and who are prepared to take responsibility for their actions. Hence, while there should be some protection against accidental changes to an immutable object, it should still be possible to work around the protection.

This goes a step further, though: Once an object is immutable, people can use it as a key in a dictionary (and as you know, caching methods such as UniqueRepresentation constructors) can do so in quite unobvious ways.

If you then later allow the object to become mutable again, you have now made the graph illegal as dictionary key again! (in fact, if you now mutate it and set it back to mutable, you've made your key unfindable in the dictionaries. That would create VERY hard to debug bugs (as we've recently seen on an object that was just inadvertently changing its hash).

There's already precedent: marking a matrix immutable is a one-way street. Of course, if you really try (and reach in) you can still mutate the matrix. That's where the "consenting adults" comes in. But changing an object from immutable to mutable should never be "official" API.

I don't think you'll lose anything. Making an immutable structure mutable is always a bug. Changing an immutable structure in a way that doesn't "essentially" change it might not be, but in that case it's reasonable to expect you can make that change even without the structure being mutable (e.g., by reaching into the backend to make the change)

[6bdad4c1-1e26-4f2f-a442-a01a2292c181]

comment:21

Should named graphs be immutable?

Hmmmmmm :-/ I see the points (we could cache nice information inside of them which is hard to compute), but I don't like it much :-/ We already had some problems with the class BipartiteGraph which constrained some operations (you were not able to add an edge between two vertices of the same class, for instance). The CompleteBipartiteGraph and RandomBipartiteGraph were automatically BipartiteGraph instances, and it really was a mess. Because you could not expect a function thought for regular graphs to work well on such instances, and the only way out was to make copies of these input again and again into normal graphs, then work on them... :-/

Then again, perhaps you are right and I just complain because I am used to the old way... :-/

Nathann

[vbraun]

comment:22

Patch needs to be rebased. Also:

• set_mutable should be removed. If you know what you are doing, you can change the _is_immutable attribute. But we shouldn't write and document a method where you are likely to shoot yourself in the foot.
• Override __copy__ and make the copy an immutable object mutable. Its a common pattern to copy(const_obj) to get a mutable copy.
• Please no g.mutable(x=None). Method names should be crystal-clear about whether they mutate or not. But this is intentionally straddling the boundary between const and mutable, making code intentional hard to read. And there are lots of fun things that can go wrong now, for starters x=None will make it look like you are changing it while actually getting the value.

This is also in accord with what matrices are doing.

[6bdad4c1-1e26-4f2f-a442-a01a2292c181]

comment:23

I'm still totally against a performance loss in exchange for a feature.

To me the only way out is an immutable backend.

Nathann

[vbraun]

comment:24

You mean performance loss because we are checking one cdef boolean? This is not really a measurable amount of time, I think. It might even be free if the compiler correctly identifies the unlikely branch and speculative execution works its way. On the plus side, you can then use graphs as hash keys which allows you to implement more efficient algorithms. From that point of view, we are talking about a net performance gain.

[vbraun]

Attachment: trac14535-immutable_graphs_vb.patch.gz

Updated patch

[simon-king-jena]

comment:25

Replying to @vbraun:

You mean performance loss because we are checking one cdef boolean?

If I recall correctly, the current decorator is indeed not very quick.

By the way, what changes did you do?

[vbraun]

Description changed:

--- 
+++ 
@@ -4,3 +4,4 @@

 With this patch, the attempt to change an immutable graph be means of methods such as add_vertex or add_edge or delete_vertex, will result in an error. If one really wants to play nasty, one could make an immutable graph mutable and change it, or use the backend of the graph for changing the underlying data.

+Apply [attachment: trac14535-immutable_graphs_vb.patch](https://github.com/sagemath/sage-prod/files/10657735/trac14535-immutable_graphs_vb.patch.gz)

[vbraun]

comment:26

I've updated the patch.

I also removed the mutability checks from some of the backends. The central user-facing point to implement them is in GenericGraph / GenericGraph_pyx. This is similar to the matrix code where we, for example, don't patch linbox to support (im)mutability.

It seems there is quite a bit of overhead in graph construction since the GenericGraph._backend is a Python class. This means various dictionary lookups to locate add_vertex and friends. You could shave off a lot of overhead by

1. Move the construction methods (add_vertex etc) from GenericGraph to GenericGraph_pyx
2. Switch GenericGraphBackend and its subclasses to Cython and make its methods cdef
3. Equip GenericGraph_pyx with a Cython attribute cdef GenericGraphBackend _backend See also http://docs.cython.org/src/userguide/early_binding_for_speed.html But thats material for another ticket.

Once all the constructions methods are in GenericGraph_pyx it'll also be easy to switch the mutability check to a very fast inline function.

[vbraun]

Changed author from Simon King to Simon King, Volker Braun

[6bdad4c1-1e26-4f2f-a442-a01a2292c181]

comment:27

Why don't you implement these immutable graph with a boolean value in the sage/graphs/base/ files ? I have nothing against a cdef boolean value that would be checked when add_edge/vertex methods are called (even though I think that the only good way to implement this is to write another backend for immutable graphs. But I can do that later, I don't mind), but I do have something against any unnecessary loss of performances in these classes, and especially in these functions.

I exchange many emails these days about how these base classes should be reimplemented efficiently, and if on the other hand you just come and add 10% there or there, we're just wasting our time.

Nathann

[vbraun]

comment:28

Another backend for immutable NetworkX graphs, another backend for immutable dense graphs, another backend for immutable sparse graphs? Thats crazy.

We could move the mutability stuff to the base GenericGraphBackend but then we still have to push the actual check into each backend. Its a possibility, but it does include quite a bit of copy&pasting. And you then can't use the backend in some other code without the mutability check. I think it would be cleaner to just encapsulate the backend (whatever it may be), and push our implementation of mutability into GenericGraph_pyx.

I can produce a patch that switches the backends to Cython but we should first be onboard that this is the way to go.

[6bdad4c1-1e26-4f2f-a442-a01a2292c181]

comment:29

Another backend for immutable NetworkX graphs, another backend for immutable dense graphs, another backend for immutable sparse graphs? Thats crazy.

? Welll..... That makes one backend per data structure. How crazy is that ? O_o

We could move the mutability stuff to the base GenericGraphBackend but then we still have to push the actual check into each backend. Its a possibility, but it does include quite a bit of copy&pasting.

Yep. That's precisely why I don't like it. To me the only way to implement this cleanly and efficiently is to write a backend for that.

Because you can store data much better, and write much more efficient methods for edge queries and neighbor listings when you know that your data will never change. Just write all of it in a big sorted C array.

This way you have no need to copy/paste anything, you surely don't slow anything down, and and you actually gain performance on immutable graphs by using the fact that your data will never change.

Nathann

[vbraun]

comment:30

If you think you can implement a better immutable-only backend then thats great. But chances are it won't be the best implementation in all cases (e.g. dense vs. sparse). If the user-facing part of the immutability is in GenericGraph_pyx then its easy to add an imutable backend next to mutable ones, the only difference is that the constructor will already set the immutability flag for the immutable backend(s). Whereas duplicating the backends means twice as many bugs and nothing to base Quivers on until you get around to implementing all of them...

[6bdad4c1-1e26-4f2f-a442-a01a2292c181]

comment:31

If you think you can implement a better immutable-only backend then thats great.

Well, it's on the way : #14589 for dense graphs or for sparse graphes http://www.sagemath.org/doc/reference/graphs/sage/graphs/base/static_sparse_graph.html

But these have been written for C implementations of time-consuming algorithms. And thus they do not support labels at all (I personally hate labels more than anything). But I intend to write general-purpose immutable backends for these kinds of graphs in not so long, sooo...

But chances are it won't be the best implementation in all cases (e.g. dense vs. sparse).

Of course not. That's precisely why we have several backends.

If the user-facing part of the immutability is in GenericGraph_pyx then its easy to add an imutable backend next to mutable ones, the only difference is that the constructor will already set the immutability flag for the immutable backend(s).

Well, what I had in mind was something like that

immutable_g = Graph(g, immutable = True)

Rather simple.

Whereas duplicating the backends means twice as many bugs

Come on Volker. A backend has very few and very short functions. And immutable data structure are the simplest of all. Are you scared of bugs ? :-P

and nothing to base Quivers on until you get around to implementing all of them...

O_o

Having nothing to base Quivers on is probably the last of my worries. Besides, it does not make much sense to have an immutable dense backend that supports multiple edges and edge labels (they just contradict what 'dense' means), so only a sparse one will exist. No choice, no worry :-P

Nathann

[vbraun]

comment:32

So your proposal is to copy&paste the (im)mutability check from GenericGraph_pyx into each mutable backend, and then write immutable backends that eventually will reach feature parity with the mutable backends. And all that so that you don't have to check the mutability flag for the backends that are already immutable? Which is one clock cycle, and possibly for free?

[6bdad4c1-1e26-4f2f-a442-a01a2292c181]

comment:33

I don't get what you say. The system of decorators that this patch uses seems to induce a 10% slowdown in a couple of fundamental functions, doesn't it ? If you want to implement immutable graphs with just an additional test of a cdef boolean variable in the necessary functions I don't have anything against it a priori, as the slowdown would be much smaller O_o

And I don't like copied/pasted code. But if you end up writing a patch that does that, I cannot really complain about anything as there are no immutable backends available to replace it. I can't set such a patch to "needs work" saying that you have to implement a real backend, can I ? :-P So if you end up writing a patch with a lot of copy and paste, and because I will not like it at all, I will later write another patch with a real immutable backend and remove all those copied/pasted code.

And the world will be at peace.

Nathann

[vbraun]

comment:34

whether or not there is an immutable backend doesn't change the fact that we want to mark mutable graphs as immutable. Unless you always want to copy the graph data in that step, it will always require you to check a mutability flag.

[6bdad4c1-1e26-4f2f-a442-a01a2292c181]

comment:35

whether or not there is an immutable backend doesn't change the fact that we want to mark mutable graphs as immutable.

If you just want to mark the Graph object as immutable, then that does not prevent you from changing the backend while you are at it. Doing so may mean that you get better performances for the adjacency tests later on if a real immutable backend is implemented somewhere.

Unless you always want to copy the graph data in that step, it will always require you to check a mutability flag.

Once more : checking that the graph is immutable is fine with me if you must do it this way, and I will try to save this by writing an immutable graph backend later on. What I want to avoid is a slowdown in current graphs methods.

I expect that, as you say, check a cdef boolean value would not produce a significant slowdown, while the current patch based on decorators does produce a slowdown.

Nathann

[tscrim]

comment:36

Could we also get this so that we can construct immutable graphs using something like Graph(4, immutable=True)?

[tscrim]

Changed dependencies from #14524 to #14524 #14732

[tscrim]

comment:37

We (FindStat) need the output of a @combinatorial_map to be hashable, so this will need to convert the result of #14732 into the proper framework once this ticket is completed.

[6bdad4c1-1e26-4f2f-a442-a01a2292c181]

comment:38

Hello guys !

I just updated #14806, which now contains a (rather large, sorry :-/) patch which implements a static graph backend. The graphs themselves are not immutable, for they contain many mutable stuff that isn't located in the backends (positions, boundary, fancy other stuff), but at least with this patch you will not have to add decorators to the basic graph methods. And as a result, you will even get better performances with these graphs. It may even improve your own computation if you switch to those backends, as I am told that you do not modify your graphs often. Well, now this information is put to good use :-)

I tried to add documentation/comments to the code, but this patch is so long that there will obviously be things that need fixing. Now I need the "second pair of eyes" which our review process says to be the key to perfection :-P

Nathann

[6bdad4c1-1e26-4f2f-a442-a01a2292c181]

comment:39

Would you have anything against my setting this ticket to needs_work, as there is now an immutable backend on which this feature could definitely use ?

Nathann

[vbraun]

comment:40

So whats the roadmap? add set_immutable as a flag or force the user to make an immutable copy if he wants to hash a graph?

[simon-king-jena]

comment:43

I notice that this is still "needs work". Is it not the case that we meanwhile have fully-fledged immutable graphs? So, is it a duplicate?

[6bdad4c1-1e26-4f2f-a442-a01a2292c181]

comment:44

O_o

Well yes, I guess we have immutable graphs right now. I mean, I fixed many many many bugs because of them, and I would hate to think I fixed all these bugs even though we have no immutable graphs.

I wouldn't stand it.

Nathann

[simon-king-jena]

Reviewer: Simon King, Nathann Cohen

[simon-king-jena]

comment:45

Great! So, it is "positive review" with the suggested resolution "duplicate".