Opened 9 years ago

Closed 9 years ago

# Hash and equality for graphs

Reported by: Owned by: SimonKing major sage-6.1 graph theory ncohen Simon King Nathann Cohen N/A u/SimonKing/ticket/15278 2525d22a6b3a687bf932c2afaa8297e40c7af3d8 #12601, #15491

At #14806, an immutable graph backend has been introduced. However, the resulting graphs are not known to be immutable.

```sage: g = graphs.CompleteGraph(400)
sage: gi = Graph(g,data_structure="static_sparse")
sage: hash(gi)
Traceback (most recent call last):
...
TypeError: graphs are mutable, and thus not hashable
```

So, when the immutable graph backend is used, then the `._immutable` attribute should be set to True.

But hang on: Does using the immutable graph backend really result in immutable graphs? I.e., would it really be impossible to change the `==`- and `cmp`-classes of a graph by "official" methods such as "`add_vertex()`"? And is the current equality testing really what we want to test?

Currently, `__eq__()` starts like this:

```        # inputs must be (di)graphs:
if not isinstance(other, GenericGraph):
raise TypeError("cannot compare graph to non-graph (%s)"%str(other))
from sage.graphs.all import Graph
g1_is_graph = isinstance(self, Graph) # otherwise, DiGraph
g2_is_graph = isinstance(other, Graph) # otherwise, DiGraph

if (g1_is_graph != g2_is_graph):
return False
if self.allows_multiple_edges() != other.allows_multiple_edges():
return False
if self.allows_loops() != other.allows_loops():
return False
if self.order() != other.order():
return False
if self.size() != other.size():
return False
if any(x not in other for x in self):
return False
if self._weighted != other._weighted:
return False
```
1. Is it really a good idea to raise an error when testing equality of a graph with a non-graph? Most likely not!
2. For sure, a graph that has multiple edges can not be equal to a graph that does not have multiple edges. But should it really matter whether a graph allows multiple edges when it actually doesn't have multiple edges?
3. Similarly for `.allows_loops()`.
4. Should `._weighted` be totally removed? Note the following comment in the documentation of the `.weighted()` method: "edge weightings can still exist for (di)graphs `G` where `G.weighted()` is `False`". Ouch.

Note the following annoying example from the docs of `.weighted()`:

```            sage: G = Graph({0:{1:'a'}}, sparse=True)
sage: H = Graph({0:{1:'b'}}, sparse=True)
sage: G == H
True

Now one is weighted and the other is not, and thus the graphs are
not equal::

sage: G.weighted(True)
sage: H.weighted()
False
sage: G == H
False
```

So, calling the method `weighted` with an argument changes the `==`-class, even though I guess most mathematicians would agree that `G` has not changed at all. And this would actually be the case even if `G` was using the immutable graph backend!!!

The aim of this ticket is to sort these things out. To the very least, graphs using the immutable graph backend should not be allowed to change their `==`-class by calling `G.weighted(True)`.

### comment:1 Changed 9 years ago by 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.

### comment:2 follow-up: ↓ 3 Changed 9 years ago by SimonKing

• Description modified (diff)

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.

### comment:3 in reply to: ↑ 2 Changed 9 years ago by SimonKing

• Dependencies set to #12601

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

### comment:4 Changed 9 years ago by 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.

### comment:5 Changed 9 years ago by 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'
```

### comment:6 Changed 9 years ago by SimonKing

• Branch set to u/SimonKing/ticket/15278
• Created changed from 10/14/13 14:22:48 to 10/14/13 14:22:48
• Modified changed from 10/15/13 10:51:43 to 10/15/13 10:51:43

### comment:7 Changed 9 years ago by anonymous

• Commit set to c774057bf07b2da8539f2395555b2062428874f4

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

### comment:8 Changed 9 years ago by 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

### comment:9 Changed 9 years ago by SimonKing

• Authors set to Simon King

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

### comment:10 Changed 9 years ago by SimonKing

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

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

### comment:11 follow-up: ↓ 15 Changed 9 years ago by 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

### comment:12 Changed 9 years ago by SimonKing

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

### comment:13 Changed 9 years ago by 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...

### comment:14 follow-up: ↓ 16 Changed 9 years ago by 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.

### comment:15 in reply to: ↑ 11 Changed 9 years ago by SimonKing

• 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

### comment:16 in reply to: ↑ 14 ; follow-up: ↓ 17 Changed 9 years ago by 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

### comment:17 in reply to: ↑ 16 ; follow-ups: ↓ 18 ↓ 19 Changed 9 years ago by SimonKing

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`

### comment:18 in reply to: ↑ 17 Changed 9 years ago by SimonKing

Honorary!

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

### comment:19 in reply to: ↑ 17 Changed 9 years ago by 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

### comment:20 follow-up: ↓ 21 Changed 9 years ago by 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
```

### comment:21 in reply to: ↑ 20 Changed 9 years ago by ncohen

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

### comment:22 Changed 9 years ago by ncohen

• Dependencies changed from #12601 to #12601, #15491

### comment:23 Changed 9 years ago by git

• Commit changed from c774057bf07b2da8539f2395555b2062428874f4 to 07bad466ab9a3e2ffe82c142cc6d0c515f1ae452

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

### comment:24 follow-up: ↓ 25 Changed 9 years ago by 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]
```
Last edited 9 years ago by SimonKing (previous) (diff)

### comment:25 in reply to: ↑ 24 Changed 9 years ago by 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

### comment:26 follow-up: ↓ 27 Changed 9 years ago by 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.

### comment:27 in reply to: ↑ 26 Changed 9 years ago by ncohen

Shouldn't named graphs be immutable?

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

### comment:28 follow-up: ↓ 29 Changed 9 years ago by ncohen

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

Nathann

### comment:29 in reply to: ↑ 28 Changed 9 years ago by SimonKing

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.

### comment:30 follow-up: ↓ 31 Changed 9 years ago by 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")
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'
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
```

### comment:31 in reply to: ↑ 30 Changed 9 years ago by 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

### comment:32 Changed 9 years ago by git

• Commit changed from 07bad466ab9a3e2ffe82c142cc6d0c515f1ae452 to 2fc8a772ee12fce7ac6abc4ecf9916f4746f5ee2

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

 ​2fc8a77 Make digraphs using the static backend immutable and hashable

### comment:33 Changed 9 years ago by 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.graphs.base.c_graph'
sage: G_imm._backend.__module__
'sage.graphs.base.static_sparse_backend'
```
Version 0, edited 9 years ago by SimonKing (next)

### comment:34 Changed 9 years ago by SimonKing

• Status changed from new to needs_review

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.

### comment:35 follow-up: ↓ 36 Changed 9 years ago by 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

### comment:36 in reply to: ↑ 35 ; follow-up: ↓ 37 Changed 9 years ago by SimonKing

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.

### comment:37 in reply to: ↑ 36 Changed 9 years ago by SimonKing

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.

### comment:38 Changed 9 years ago by 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

### comment:39 follow-up: ↓ 46 Changed 9 years ago by 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

### comment:40 follow-up: ↓ 41 Changed 9 years ago by ncohen

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

Nathann

### comment:41 in reply to: ↑ 40 Changed 9 years ago by SimonKing

(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?

### comment:42 Changed 9 years ago by ncohen

Yes yes they should commute `:-)`

Nathann

### comment:43 Changed 9 years ago by ncohen

• Status changed from needs_review to needs_info

### comment:44 Changed 9 years ago by SimonKing

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

### comment:45 Changed 9 years ago by 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

### comment:46 in reply to: ↑ 39 ; follow-up: ↓ 47 Changed 9 years ago by SimonKing

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.

### comment:47 in reply to: ↑ 46 ; follow-up: ↓ 50 Changed 9 years ago by 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

### comment:48 Changed 9 years ago by 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):`?

### comment:49 Changed 9 years ago by SimonKing

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

### comment:50 in reply to: ↑ 47 ; follow-up: ↓ 51 Changed 9 years ago by SimonKing

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?

### comment:51 in reply to: ↑ 50 ; follow-up: ↓ 52 Changed 9 years ago by 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

### comment:52 in reply to: ↑ 51 ; follow-up: ↓ 53 Changed 9 years ago by SimonKing

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.

### comment:53 in reply to: ↑ 52 Changed 9 years ago by 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

### comment:54 Changed 9 years ago by git

• Commit changed from 2fc8a772ee12fce7ac6abc4ecf9916f4746f5ee2 to 51d63284da70ffa4772a0d0fda6020750aef2e6d

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

 ​51d6328 `Trac 15278: Error messages explain how to create (im)mutable graph copy`

### comment:55 Changed 9 years ago by SimonKing

• Status changed from needs_info to needs_review

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

### comment:56 Changed 9 years ago by ncohen

• Reviewers set to Nathann Cohen
• Status changed from needs_review to positive_review

thaaaaaaaaaaaaaanks !!!

Nathann

### comment:57 Changed 9 years ago by ncohen

• Status changed from positive_review to needs_work

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

### comment:58 Changed 9 years ago by 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.

### comment:59 follow-up: ↓ 60 Changed 9 years ago by 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?

### comment:60 in reply to: ↑ 59 Changed 9 years ago by 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

### comment:61 Changed 9 years ago by 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

### comment:62 Changed 9 years ago by 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

### comment:63 Changed 9 years ago by 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
```

### comment:64 Changed 9 years ago by 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

### comment:65 Changed 9 years ago by 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).

### comment:66 Changed 9 years ago by 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.

### comment:67 follow-up: ↓ 71 Changed 9 years ago by 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

### comment:68 Changed 9 years ago by git

• Commit changed from 51d63284da70ffa4772a0d0fda6020750aef2e6d to fcf9e3018d5e87f49e1f3f3d68ad4cc49382c0b9

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`

### comment:69 Changed 9 years ago by 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`

### comment:70 follow-up: ↓ 72 Changed 9 years ago by ncohen

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

Nathann

### comment:71 in reply to: ↑ 67 Changed 9 years ago by SimonKing

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.

### comment:72 in reply to: ↑ 70 Changed 9 years ago by SimonKing

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.

### comment:73 Changed 9 years ago by 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

### comment:74 Changed 9 years ago by ncohen

I get a doctest error in generic_graph.py :

```+            sage: P = Poset(([1,2,3,4], [[1,3],[1,4],[2,3]]),
```

Nathann

### comment:75 Changed 9 years ago by 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
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.

### comment:76 Changed 9 years ago by 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

### comment:77 Changed 9 years ago by 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

### comment:78 Changed 9 years ago by git

• Commit changed from fcf9e3018d5e87f49e1f3f3d68ad4cc49382c0b9 to 2525d22a6b3a687bf932c2afaa8297e40c7af3d8

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

 ​2525d22 `Trac 15278: Fix syntax error in doc test`

### comment:79 follow-up: ↓ 80 Changed 9 years ago by SimonKing

• Status changed from needs_work to needs_review

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.

### comment:80 in reply to: ↑ 79 Changed 9 years ago by ncohen

• Status changed from needs_review to positive_review

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.

### comment:81 Changed 9 years ago by 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?

### comment:82 follow-up: ↓ 83 Changed 9 years ago by 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

### comment:83 in reply to: ↑ 82 Changed 9 years ago by SimonKing

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?

### comment:84 Changed 9 years ago by 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

### comment:85 Changed 9 years ago by vbraun

• Resolution set to fixed
• Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.