Opened 7 years ago
Closed 7 years ago
#15278 closed defect (fixed)
Hash and equality for graphs
Reported by:  SimonKing  Owned by:  

Priority:  major  Milestone:  sage6.1 
Component:  graph theory  Keywords:  
Cc:  ncohen  Merged in:  
Authors:  Simon King  Reviewers:  Nathann Cohen 
Report Upstream:  N/A  Work issues:  
Branch:  u/SimonKing/ticket/15278 (Commits)  Commit:  2525d22a6b3a687bf932c2afaa8297e40c7af3d8 
Dependencies:  #12601, #15491  Stopgaps: 
Description (last modified by )
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 nongraph (%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
 Is it really a good idea to raise an error when testing equality of a graph with a nongraph? Most likely not!
 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?
 Similarly for
.allows_loops()
.  Should
._weighted
be totally removed? Note the following comment in the documentation of the.weighted()
method: "edge weightings can still exist for (di)graphsG
whereG.weighted()
isFalse
". 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)
.
Change History (85)
comment:1 Changed 7 years ago by
comment:2 followup: ↓ 3 Changed 7 years ago by
 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)
ifG
is supposed to be immutable. Hence,G.weighted
should check for theG._immutable
flag. Similarly, we must proceed with all other nonunderscore methods that could potentially change the ==class ofG
.  In particular, we want that that
G._immutable
is set when the immutable backend is in use.
comment:3 in reply to: ↑ 2 Changed 7 years ago by
 Dependencies set to #12601
Replying to SimonKing:
 In order to fix the hash, it must take into account precisely the data that are used in
__eq__
.
Perhaps I am overeager 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 nonunderscore 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 recomputed, 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 7 years ago by
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 7 years ago by
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) <ipythoninput87ee33a4c939a> in <module>() > 1 copy(gi)._immutable AttributeError: 'Graph' object has no attribute '_immutable'
comment:6 Changed 7 years ago by
 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 7 years ago by
 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 7 years ago by
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 7 years ago by
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 7 years ago by
I have uploaded a preliminary "patch" (or branch, actually). The existing tests pass.
What it already does:
 If a graph is immutable then the
__copy__
method returns the graphunless 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 followup: ↓ 15 Changed 7 years ago by
 About not requiring
allows_multiple_edges
andallows_loops
to be equal : there is actually a technical problem there I just noticed : theget_edge_label
function behaves differently according to the value ofallow_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 inspanning_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, likeflow
oftraveling_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, returningself
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 tomemcpy
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
insage.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 7 years ago by
This has a branch, but its status is "new", not "needs review". Is it ready for review, Nathann?
comment:13 Changed 7 years ago by
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 followup: ↓ 16 Changed 7 years ago by
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 nonunderscore 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:
 `._backend.multiple_edges(None)
._backend.loops(None)
._backend.num_verts()
._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 nonunderscore 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 7 years ago by
Replying to ncohen:
 About not requiring
allows_multiple_edges
andallows_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 inspanning_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, likeflow
oftraveling_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 ; followup: ↓ 17 Changed 7 years ago by
Yooooooooo !!!
 The methods mentioned above call the backend, namely:
 `._backend.multiple_edges(None)
._backend.loops(None)
._backend.num_verts()
._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 nonunderscore 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 ; followups: ↓ 18 ↓ 19 Changed 7 years ago by
Replying to ncohen:
Nope.
multiple_edges
andloops
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 7 years ago by
comment:19 in reply to: ↑ 17 Changed 7 years ago by
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 followup: ↓ 21 Changed 7 years ago by
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 7 years ago by
comment:22 Changed 7 years ago by
 Dependencies changed from #12601 to #12601, #15491
comment:23 Changed 7 years ago by
 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 followup: ↓ 25 Changed 7 years ago by
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]
comment:25 in reply to: ↑ 24 Changed 7 years ago by
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 followup: ↓ 27 Changed 7 years ago by
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 7 years ago by
Shouldn't named graphs be immutable?
Please no !
I would expect that in order to modify something "named", one should create a mutable copy first.
Yep. So when you add a vertex, the graph's name should change or be removed ? Or would you remove the name attribute itself for mutable graphs ? Or would you drop the name of a graph when it is converted to a mutable copy ?
If this is to be done someday (all named graphs made immutable), it will be after a very simple task : I want to be sure *first* that all current methods will work fine on immutable graphs. And I am 100% sure that it is *not* the case at the moment.
Because many graph methods can take a copy of self and modify it. But if self is immutable the copy will be immutable too, and no edge/vertices can be touched on the copy either. And these methods have not been written while taking this into account. And all these functions *will* break on immutable graphs.
We already had the experience of "bipartite graphs", a new class of graph that made sure all graphs stayed bipartite. Sometimes, adding an edge would raise an exception because such an edge couldn't be added while keeping the graph bipartite. This class was hell. Making it the default class of graphs.CompleteBipartiteGraph
would have been hell too.
So please, the named graphs stay mutable for the moment, unless this job is done responsibly.
Nathann
comment:28 followup: ↓ 29 Changed 7 years ago by
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 7 years ago by
Replying to ncohen:
Honestly, I would prefer to drop graph names. I don't even see the point of that
:P
Perhaps I was not clear enough. I have nothing against changing a graph that has a name. But I am against changing a graph that is part of a data base.
comment:30 followup: ↓ 31 Changed 7 years ago by
A different question: Shall we simply rely on the error that is raised by the static backend (which is an AttributeError
when adding or deleting a vertex and a NotImplementedError
when adding ), or should we catch the error and raise a TypeError
instead, with an error message telling that this is an immutable graph and adding a vertex is a bad idea in the case of an immutable graph?
That's to say, would it be enough to have
sage: G_imm = Graph(graphs.PetersenGraph(), data_structure="static_sparse") sage: G_imm.add_vertex(100) Traceback (most recent call last): ... AttributeError: 'StaticSparseBackend' object has no attribute 'vertex_ints' sage: G_imm.delete_vertex(0) Traceback (most recent call last): ... AttributeError: 'StaticSparseBackend' object has no attribute 'vertex_ints' sage: G_imm.add_edge(1,2) Traceback (most recent call last): ... NotImplementedError:
or would we like to have
sage: G_imm.add_edge(1,2) Traceback (most recent call last): ... TypeError: Can not add an edge to an immutable graph
comment:31 in reply to: ↑ 30 Changed 7 years ago by
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 aNotImplementedError
when adding ), or should we catch the error and raise aTypeError
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 7 years ago by
 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 7 years ago by
With the current commit, all tests should pass, changing (di)graphs using the static backend requires some criminal energy, they have a hash, and it is documented.
The ValueError
you are mentioning is not part of the add_vertex
method of the static backend, by the way:
sage: G = graphs.PetersenGraph() sage: G_imm = DiGraph(G, data_structure="static_sparse") sage: G_imm._backend.add_vertex.__module__ 'sage.graphs.base.c_graph' sage: G_imm._backend.__module__ 'sage.graphs.base.static_sparse_backend'
EDIT: Here is the mro:
sage: G_imm._backend.__class__.mro() [sage.graphs.base.static_sparse_backend.StaticSparseBackend, sage.graphs.base.c_graph.CGraphBackend, sage.graphs.base.graph_backends.GenericGraphBackend, sage.structure.sage_object.SageObject, object]
comment:34 Changed 7 years ago by
 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 followup: ↓ 36 Changed 7 years ago by
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 ; followup: ↓ 37 Changed 7 years ago by
Replying to ncohen:
HMmmmmm okay. Though I really have no clue what the changes you made to cachefunc.pyx do
O_o
Hein? My branch doesn't touch cachefunc.pyx at all! And why should it?
Is this related to this patch, or is it independent of immutable graphs and thus could be made into another trac ticket, on on which this one would depend ?
I don't even have a clue what you mean by "this". You have provided a "static" backend that is almost enough to produce immutable graphs. To really make them immutable (in the sense stated repeatedly), it was needed to allow G.weighted()
but disallow G.weighted(new_value)
on immutable graphs, since the latter would mutate the graph. And if something is immutable then it makes sense to provide it with a hashwhich in the case of graphs means to provide the ._immutable
attributeand 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 7 years ago by
Replying to SimonKing:
Replying to ncohen:
HMmmmmm okay. Though I really have no clue what the changes you made to cachefunc.pyx do
O_o
Hein? My branch doesn't touch cachefunc.pyx at all! And why should it?
Ahaha, now I understand. That's this dreaded feature of the new git workflow: The commits changing cachefunc.pyx belong to #12601, hence, to a dependency of this ticket. But Volker believes that it is a good thing that a reviewer also has a look at what happens in the dependencies.
Personally, I believe that #12601 has a positive review and provides a feature that does not rely on graphs, but it is handy to use here. Hence, I don't think your review of this ticket must comprise a second review of #12601. Of course, if you happen to spot something in #12601 that doesn't work then please speak up.
comment:38 Changed 7 years ago by
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/sagegit/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 disallowG.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 hashwhich in the case of graphs means to provide the._immutable
attributeand 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 followup: ↓ 46 Changed 7 years ago by
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 thatdata_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 followup: ↓ 41 Changed 7 years ago by
(I just created #15507 to handle graphs on > 65536 vertices)
Nathann
comment:41 in reply to: ↑ 40 Changed 7 years ago by
comment:42 Changed 7 years ago by
Yes yes they should commute :)
Nathann
comment:43 Changed 7 years ago by
 Status changed from needs_review to needs_info
comment:44 Changed 7 years ago by
Nathann, what info do you need? Is this because of your comment:39?
comment:45 Changed 7 years ago by
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 ; followup: ↓ 47 Changed 7 years ago by
Replying to ncohen:
HMmmmm... Don't you touch cachefunc.pyx in commit 126b03609e9bae78955ccbc97e36f1924a79603b ? That's when you merge #12601 in the present branch.
Splitting hair...
Gosh, I'm going to hate these git dependencies.
+1
 In
.copy()
, you add a line before everything else to handle your case. Couldn't you add a line after the second "if" block, the one after which we know for sure thatdata_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 usedor 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 ; followup: ↓ 50 Changed 7 years ago by
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 usedor 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 7 years ago by
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 7 years ago by
Oopy, sorry, for the noise, it is correct in this way :/
(facepalm)
comment:50 in reply to: ↑ 47 ; followup: ↓ 51 Changed 7 years ago by
Replying to ncohen:
Problem: If I am not mistaken, people currently do mess with the attribute
._immutable
, if I am not mistaken.Yes yes indeed, that's what Nicolas told me they did at the moment, and that's what Python uses too know whether it should consider the object as mutable or not. I just wondered if it checked whether the variable existed, or whether the variable was set to True too.
The usage is if getattr(self,'_immutable',False/True): raise TypeError("...")
(false or true depending on whether we want to allow something for all graphs except those that are known to be mutable, or allow something for all graphs except those that are known to be immutable).
Would it be feasible to try to remove the
._immutable
attribute (and testing the type of the backend instead), see how much fails, and fix the failing code by using "proper" immutable graphs?Hmmmm, I thought that Python really needed this
_immutable
variable somewhereO_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 ; followup: ↓ 52 Changed 7 years ago by
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 definescopy=__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)
returnsX
ifX
is immutable, but in other places in Sage,copy(X)
always returns a mutable copy ofX
, regardless whetherX
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 ; followup: ↓ 53 Changed 7 years ago by
Replying to ncohen:
I've never heard before that Python uses it.
Oh. Then I guess we are the only ones to use this
._immutable
flag.
Ahem. Then I guess there are many things in Python that I've never heard of...
But one question on copying needs to be addressed: I think in some places in Sage,
copy(X)
returnsX
ifX
is immutable, but in other places in Sage,copy(X)
always returns a mutable copy ofX
, regardless whetherX
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 haveG 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='...')
orG.copy(backend='...')
respectively with a tobeimplementedmutable=True/False
keyword.
comment:53 in reply to: ↑ 52 Changed 7 years ago by
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() FalseThere 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 haveG 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='...')
orG.copy(backend='...')
respectively with a tobeimplementedmutable=True/False
keyword.
Yepyep, works for me :)
Nathann
comment:54 Changed 7 years ago by
 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 7 years ago by
 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 7 years ago by
 Reviewers set to Nathann Cohen
 Status changed from needs_review to positive_review
thaaaaaaaaaaaaaanks !!!
Nathann
comment:57 Changed 7 years ago by
 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 7 years ago by
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 followup: ↓ 60 Changed 7 years ago by
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 Sage6.1.beta2 and has to do with linear extensions?
comment:60 in reply to: ↑ 59 Changed 7 years ago by
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 Sage6.1.beta2 and has to do with linear extensions?
Hmmmm... Well, I'd think that it is a Posetrelated 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: Nonexceptional 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 7 years ago by
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 7 years ago by
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 7 years ago by
... 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 7 years ago by
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 7 years ago by
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 7 years ago by
Or go the middle way: In __hash__
and in the selfmutating 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 mockimmutable graph to mutate the copy, and thus we must return a proper copy rather than just self in this case.
comment:67 followup: ↓ 71 Changed 7 years ago by
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 7 years ago by
 Commit changed from 51d63284da70ffa4772a0d0fda6020750aef2e6d to fcf9e3018d5e87f49e1f3f3d68ad4cc49382c0b9
comment:69 Changed 7 years ago by
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 followup: ↓ 72 Changed 7 years ago by
Well the problem it solves is making this ticket compatible with beta2. So the hack stays ?
Nathann
comment:71 in reply to: ↑ 67 Changed 7 years ago by
Replying to ncohen:
This being said, checking the backend does not exactly mean that all other properties of graphs are "protected", like the embedding and everything.
That's why both the flag and the type of the backend are checked before returning "self" as a copy.
Okay, I just read your latest post : the point is that this ._immutable flag is a hack. Shouldn't we just make their code use the new backend, so that their code is not hacked anymore ? Right now they claim their graphs are immutable, though they aren't. Seems like the way to go, isn't it ?
In a way, yes. In a different way: Are we supposed to clean up their mess? If they use the static backend, as they should, then the should also let copy()
create a mutable copy; hence, each usage of copy()
should be decorated with an optional argument (such as: sparse=True
) which makes the copy be an actual mutable copy of the graph. So, it is more to do than just changing the backend, since in some places they pretend to have immutable graphs, but in others they want to mutate a copy of the graph.
comment:72 in reply to: ↑ 70 Changed 7 years ago by
Replying to ncohen:
Well the problem it solves is making this ticket compatible with beta2. So the hack stays ?
I only see one place where combinat
uses bla._immutable = True
:
src/sage/combinat/posets/posets.py: G._immutable = True
So, perhaps it would not be too much of a problem to change this to using the static sparse backend. But then, we also need to identify where stuff is copied.
comment:73 Changed 7 years ago by
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 7 years ago by
I get a doctest error in generic_graph.py :
+ sage: P = Poset(([1,2,3,4], [[1,3],[1,4],[2,3]]), + linear_extension=True, facade = False)
Nathann
comment:75 Changed 7 years ago by
Meanwhile I see at what point the copy is taken: It is
def transitive_reduction(self): r""" Returns a transitive reduction of a graph. The original graph is not modified. A transitive reduction H of G has a path from x to y if and only if there was a path from x to y in G. Deleting any edge of H destroys this property. A transitive reduction is not unique in general. A transitive reduction has the same transitive closure as the original graph. A transitive reduction of a complete graph is a tree. A transitive reduction of a tree is itself. EXAMPLES:: sage: g=graphs.PathGraph(4) sage: g.transitive_reduction()==g True sage: g=graphs.CompleteGraph(5) sage: edges = g.transitive_reduction().edges(); len(edges) 4 sage: g=DiGraph({0:[1,2], 1:[2,3,4,5], 2:[4,5]}) sage: g.transitive_reduction().size() 5 """ from copy import copy from sage.rings.infinity import Infinity G = copy(self) for e in self.edge_iterator(): # Try deleting the edge, see if we still have a path # between the vertices. G.delete_edge(e) if G.distance(e[0],e[1])==Infinity: # oops, we shouldn't have deleted it G.add_edge(e) return G
Hence, it seems that we indeed want a mutable copy here. And perhaps it isn't their mess after all, as this method is broken for all truely immutable graphs.
comment:76 Changed 7 years ago by
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 7 years ago by
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 7 years ago by
 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 followup: ↓ 80 Changed 7 years ago by
 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 counterhacked 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 counterhack too.
comment:80 in reply to: ↑ 79 Changed 7 years ago by
 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 counterhacked 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 counterhack 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 7 years ago by
Question, after some offticket 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 followup: ↓ 83 Changed 7 years ago by
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 7 years ago by
Replying to ncohen:
Well. What's the difference with implementing it in the ticket that will use it as the default backend for posets ? Nobody will use it in the meantime, and if you want to get technical it's not related to "hash and equality for graphs" either.
Good point. But I think it isn't in the "poset" ticket either". Would you mind if I created a new ticket "pickling of immutable graphs", that will end up to be a dependency for the poset ticket?
comment:84 Changed 7 years ago by
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 7 years ago by
 Resolution set to fixed
 Status changed from positive_review to closed
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.