Sage: Ticket #15278: Hash and equality for graphs
https://trac.sagemath.org/ticket/15278
<p>
At <a class="closed ticket" href="https://trac.sagemath.org/ticket/14806" title="enhancement: Immutable graph backend (closed: fixed)">#14806</a>, an immutable graph backend has been introduced. However, the resulting graphs are not known to be immutable.
</p>
<pre class="wiki">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
</pre><p>
So, when the immutable graph backend is used, then the <code>._immutable</code> attribute should be set to True.
</p>
<p>
But hang on: Does using the immutable graph backend really result in immutable graphs? I.e., would it really be impossible to change the <code>==</code>- and <code>cmp</code>-classes of a graph by "official" methods such as "<code>add_vertex()</code>"? And is the current equality testing really what we want to test?
</p>
<p>
Currently, <code>__eq__()</code> starts like this:
</p>
<pre class="wiki"> # 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
</pre><ol><li>Is it really a good idea to raise an error when testing equality of a graph with a non-graph? Most likely not!
</li><li>For sure, a graph that <em>has</em> multiple edges can not be equal to a graph that does not have multiple edges. But should it really matter whether a graph <em>allows</em> multiple edges when it actually doesn't <em>have</em> multiple edges?
</li><li>Similarly for <code>.allows_loops()</code>.
</li><li>Should <code>._weighted</code> be totally removed? Note the following comment in the documentation of the <code>.weighted()</code> method: "edge weightings can still exist for (di)graphs <code>G</code> where <code>G.weighted()</code> is <code>False</code>". Ouch.
</li></ol><p>
Note the following annoying example from the docs of <code>.weighted()</code>:
</p>
<pre class="wiki"> 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
</pre><p>
So, calling the method <code>weighted</code> with an argument changes the <code>==</code>-class, even though I guess most mathematicians would agree that <code>G</code> has not changed at all. And this would actually be the case even if <code>G</code> was using the immutable graph backend!!!
</p>
<p>
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 <code>==</code>-class by calling <code>G.weighted(True)</code>.
</p>
en-usSagehttps://trac.sagemath.org/chrome/site/logo_sagemath_trac.png
https://trac.sagemath.org/ticket/15278
Trac 1.1.6SimonKingMon, 14 Oct 2013 14:34:54 GMT
https://trac.sagemath.org/ticket/15278#comment:1
https://trac.sagemath.org/ticket/15278#comment:1
<p>
Shouldn't the hash of graphs be cached, for efficiency? Currently it does <code>return hash((tuple(self.vertices()), tuple(self.edges())))</code>, which seems rather expensive.
</p>
<p>
Note that <a class="closed ticket" href="https://trac.sagemath.org/ticket/12601" title="enhancement: @cached_method does not work for special methods (closed: fixed)">#12601</a> makes it possible to comfortably turn the hash (and other special methods) into a cached method.
</p>
TicketSimonKingTue, 15 Oct 2013 10:28:54 GMTdescription changed
https://trac.sagemath.org/ticket/15278#comment:2
https://trac.sagemath.org/ticket/15278#comment:2
<ul>
<li><strong>description</strong>
modified (<a href="/ticket/15278?action=diff&version=2">diff</a>)
</li>
</ul>
<p>
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?
</p>
<p>
In any case, the hash is currently broken, since it does not take into account weightedness, but equality check does.
</p>
<p>
It seems to me that the following is the easiest way to go:
</p>
<ul><li>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.
</li><li>In order to fix the hash, it must take into account precisely the data that are used in <code>__eq__</code>.
</li><li>We want that graphs using the immutable graph backend are immutable in the sense stated above. Hence, we must disallow <code>G.weighted(True/False)</code> if <code>G</code> is supposed to be immutable. Hence, <code>G.weighted</code> should check for the <code>G._immutable</code> flag. Similarly, we must proceed with all other non-underscore methods that could potentially change the ==-class of <code>G</code>.
</li><li>In particular, we want that that <code>G._immutable</code> is set when the immutable backend is in use.
</li></ul>
TicketSimonKingTue, 15 Oct 2013 10:40:37 GMTdependencies set
https://trac.sagemath.org/ticket/15278#comment:3
https://trac.sagemath.org/ticket/15278#comment:3
<ul>
<li><strong>dependencies</strong>
set to <em>#12601</em>
</li>
</ul>
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/15278#comment:2" title="Comment 2">SimonKing</a>:
</p>
<blockquote class="citation">
<ul><li>In order to fix the hash, it must take into account precisely the data that are used in <code>__eq__</code>.
</li></ul></blockquote>
<p>
Perhaps I am over-eager at this point. The hash is <em>not</em> broken. Being broken means that two graphs that evaluate equal have distinct hash values. But this can currently not happen. So, it's fine.
</p>
<p>
Therefore I modify the "easiest way to go":
</p>
<ul><li>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 <em>with a fast hash</em>.
</li><li>We want that graphs using the immutable graph backend are immutable in the sense stated above. Hence, we must disallow G.weighted(<a class="missing wiki">True/False?</a>) 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.
</li><li>In particular, we want that that G._immutable is set when the immutable backend is in use.
</li><li>The hash will of course keep raising an error if <code>G._immutable</code> 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 <code>@cached_method</code> on the <code>__hash__</code>. We thus use <a class="closed ticket" href="https://trac.sagemath.org/ticket/12601" title="enhancement: @cached_method does not work for special methods (closed: fixed)">#12601</a>.
</li></ul><p>
Do you agree on using <a class="closed ticket" href="https://trac.sagemath.org/ticket/12601" title="enhancement: @cached_method does not work for special methods (closed: fixed)">#12601</a>?
</p>
TicketSimonKingTue, 15 Oct 2013 10:50:31 GMT
https://trac.sagemath.org/ticket/15278#comment:4
https://trac.sagemath.org/ticket/15278#comment:4
<p>
A related question: Shouldn't <code>copy(G)</code> return <code>G</code>, if <code>G</code> is immutable? Currently, we have
</p>
<pre class="wiki">sage: g = graphs.CompleteGraph(400)
sage: gi = Graph(g,data_structure="static_sparse")
sage: copy(gi) is gi
False
</pre><p>
Moreover, <code>copy(gi)</code> takes a lot of time.
</p>
TicketSimonKingTue, 15 Oct 2013 10:51:43 GMT
https://trac.sagemath.org/ticket/15278#comment:5
https://trac.sagemath.org/ticket/15278#comment:5
<p>
Moreover, copying a graph currently erases the <code>_immutable</code> flag:
</p>
<pre class="wiki">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'
</pre>
TicketSimonKingTue, 15 Oct 2013 14:18:12 GMTchangetime, time changed; branch set
https://trac.sagemath.org/ticket/15278#comment:6
https://trac.sagemath.org/ticket/15278#comment:6
<ul>
<li><strong>changetime</strong>
changed from <em>10/15/13 10:51:43</em> to <em>10/15/13 10:51:43</em>
</li>
<li><strong>branch</strong>
set to <em>u/SimonKing/ticket/15278</em>
</li>
<li><strong>time</strong>
changed from <em>10/14/13 14:22:48</em> to <em>10/14/13 14:22:48</em>
</li>
</ul>
TicketanonymousTue, 15 Oct 2013 14:19:11 GMTcommit set
https://trac.sagemath.org/ticket/15278#comment:7
https://trac.sagemath.org/ticket/15278#comment:7
<ul>
<li><strong>commit</strong>
set to <em>c774057bf07b2da8539f2395555b2062428874f4</em>
</li>
</ul>
<p>
New commits:
</p>
<table class="wiki">
<tr><td>[changeset:c774057]</td><td>Prepare hash and copy for immutable graphs. Let .weighted() respect mutability.
</td></tr><tr><td>[changeset:6cf1fad]</td><td>Faster and more thorough detection of special method names
</td></tr><tr><td>[changeset:fe1e739]</td><td>Remove trailing whitespace
</td></tr><tr><td>[changeset:13b500b]</td><td><a class="closed ticket" href="https://trac.sagemath.org/ticket/12601" title="enhancement: @cached_method does not work for special methods (closed: fixed)">#12601</a>: Cached special methods
</td></tr></table>
TicketncohenTue, 15 Oct 2013 14:20:12 GMT
https://trac.sagemath.org/ticket/15278#comment:8
https://trac.sagemath.org/ticket/15278#comment:8
<p>
New commits:
</p>
<table class="wiki">
<tr><td>[changeset:c774057]</td><td>Prepare hash and copy for immutable graphs. Let .weighted() respect mutability.
</td></tr><tr><td>[changeset:6cf1fad]</td><td>Faster and more thorough detection of special method names
</td></tr><tr><td>[changeset:fe1e739]</td><td>Remove trailing whitespace
</td></tr><tr><td>[changeset:13b500b]</td><td><a class="closed ticket" href="https://trac.sagemath.org/ticket/12601" title="enhancement: @cached_method does not work for special methods (closed: fixed)">#12601</a>: Cached special methods
</td></tr></table>
TicketSimonKingTue, 15 Oct 2013 14:24:57 GMTauthor set
https://trac.sagemath.org/ticket/15278#comment:9
https://trac.sagemath.org/ticket/15278#comment:9
<ul>
<li><strong>author</strong>
set to <em>Simon King</em>
</li>
</ul>
<p>
New commits:
</p>
<table class="wiki">
<tr><td>[changeset:c774057]</td><td>Prepare hash and copy for immutable graphs. Let .weighted() respect mutability.
</td></tr><tr><td>[changeset:6cf1fad]</td><td>Faster and more thorough detection of special method names
</td></tr><tr><td>[changeset:fe1e739]</td><td>Remove trailing whitespace
</td></tr><tr><td>[changeset:13b500b]</td><td><a class="closed ticket" href="https://trac.sagemath.org/ticket/12601" title="enhancement: @cached_method does not work for special methods (closed: fixed)">#12601</a>: Cached special methods
</td></tr></table>
TicketSimonKingTue, 15 Oct 2013 14:24:57 GMT
https://trac.sagemath.org/ticket/15278#comment:10
https://trac.sagemath.org/ticket/15278#comment:10
<p>
I have uploaded a preliminary "patch" (or branch, actually). The existing tests pass.
</p>
<p>
What it already does:
</p>
<ul><li>If a graph is immutable then the <code>__copy__</code> method returns the graph---unless of course optional arguments are passed to the <code>__copy__</code> method. This is standard behaviour for immutable things, IIRC.
</li><li>If <code>.weighted(...)</code> is used to modify an immutable graph, then an error is raised.
</li><li>The <code>__hash__</code> became a cached method
</li></ul><p>
So far, I am not setting the <code>._immutable</code> 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 <code>.weighted()</code>). This shall be done in the next commits.
</p>
TicketncohenWed, 16 Oct 2013 09:21:33 GMT
https://trac.sagemath.org/ticket/15278#comment:11
https://trac.sagemath.org/ticket/15278#comment:11
<ul><li>About not requiring <code>allows_multiple_edges</code> and <code>allows_loops</code> to be equal :
there is actually a technical problem there I just noticed : the
<code>get_edge_label</code> function behaves differently according to the value of
<code>allow_multiple_edges()</code>. It returns either a label, or a list of labels. And
that complicates things.
</li></ul><pre class="wiki">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]
</pre><blockquote>
<p>
(I hate labels and multiple edges)
</p>
</blockquote>
<blockquote>
<p>
Besides, testing whether the graph containts multiple edges is currently a bit
costly. I think we actually go over all edges, and test it.
</p>
</blockquote>
<ul><li>About <code>.weighted()</code> : looks like the meaning of "weighted" is only used in
<code>spanning_tree.pyx</code>. 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 <code>flow</code> of <code>traveling_salesman_problem</code>)
</li></ul><ul><li>I believe (note sure, never used it) that <code>.weighted()</code> 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.
</li></ul><ul><li>I don't see any problem with using <a class="closed ticket" href="https://trac.sagemath.org/ticket/12601" title="enhancement: @cached_method does not work for special methods (closed: fixed)">#12601</a>. Do you see one ?
</li></ul><ul><li><code>copy(gi)</code> takes a lot of time : indeed, returning <code>self</code> 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 <code>memcpy</code> and it's settled <code>:-P</code>
</li></ul><ul><li>Why didn't you use the decorators from your first immutable graph patch to
deal with immutability in <code>.weighted()</code> ?
</li></ul><ul><li>If you want to check that current functions act well on immutable graphs, you
may be interested by the decorator named <code>_run_it_on_static_instead</code> in
<code>sage.graphs.backends.static_sparse_backend</code>. 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 <code>;-)</code>
</li></ul><p>
Sorry for the delay. I moved a lot through Paris with my backpack during the
last days <code>:-P</code>
</p>
<p>
Nathann
</p>
TicketSimonKingThu, 05 Dec 2013 22:38:55 GMT
https://trac.sagemath.org/ticket/15278#comment:12
https://trac.sagemath.org/ticket/15278#comment:12
<p>
This has a branch, but its status is "new", not "needs review". Is it ready for review, Nathann?
</p>
TicketSimonKingThu, 05 Dec 2013 22:40:57 GMT
https://trac.sagemath.org/ticket/15278#comment:13
https://trac.sagemath.org/ticket/15278#comment:13
<p>
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...
</p>
TicketSimonKingFri, 06 Dec 2013 14:42:29 GMT
https://trac.sagemath.org/ticket/15278#comment:14
https://trac.sagemath.org/ticket/15278#comment:14
<p>
Back at questions on the static graph backend...
</p>
<p>
In <code>__eq__</code>, the following data play a role:
</p>
<ul><li><code>.allows_multiple_edges()</code>
</li><li><code>.allows_loops()</code>
</li><li><code>.order()</code>
</li><li><code>.size()</code>
</li><li><code>._weighted</code>
</li><li>vertex and edge labels, and of course start and endpoints of the edges.
</li></ul><p>
For immutability, it is thus essential that these methods do not change the answers after applying non-underscore methods.
</p>
<ul><li><code>._weighted</code> may be changed by the <code>.weighted(new)</code> method, which I thus made respectful against mutability. So, that is settled.
</li><li>The methods mentioned above call the backend, namely:
<ol><li>`._backend.multiple_edges(None)
</li><li><code>._backend.loops(None)</code>
</li><li><code>._backend.num_verts()</code>
</li><li><code>._backend.num_edges(self._directed)</code>
</li></ol></li></ul><p>
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 <code>__eq__</code> classes won't change when using the static graph backend, and I am happy.
</p>
<p>
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.
</p>
TicketSimonKingFri, 06 Dec 2013 14:51:10 GMT
https://trac.sagemath.org/ticket/15278#comment:15
https://trac.sagemath.org/ticket/15278#comment:15
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/15278#comment:11" title="Comment 11">ncohen</a>:
</p>
<blockquote class="citation">
<ul><li>About not requiring <code>allows_multiple_edges</code> and <code>allows_loops</code> to be equal :
</li></ul></blockquote>
<p>
It will probably be fine to keep them in <code>__eq__</code>, as they simply ask for the backend's opinion, and the static backend hopefully has no changeable mind.
</p>
<blockquote class="citation">
<ul><li>About <code>.weighted()</code> : looks like the meaning of "weighted" is only used in
<code>spanning_tree.pyx</code>. 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 <code>flow</code> of <code>traveling_salesman_problem</code>)
</li></ul></blockquote>
<p>
OK, but removing ".weighted()" from <code>__eq__</code> could be done later, I believe.
</p>
<blockquote class="citation">
<ul><li>I don't see any problem with using <a class="closed ticket" href="https://trac.sagemath.org/ticket/12601" title="enhancement: @cached_method does not work for special methods (closed: fixed)">#12601</a>. Do you see one ?
</li></ul></blockquote>
<p>
Nope.
</p>
<blockquote class="citation">
<ul><li>Why didn't you use the decorators from your first immutable graph patch to
deal with immutability in <code>.weighted()</code> ?
</li></ul></blockquote>
<p>
With the decorator, an error would be raised whenever <code>.weighted()</code> is called on a mutable graph. However, <code>.weighted</code> only mutates the graph if it has an argument. <code>G.weighted()</code> will not change <code>G</code>, but will only tell whether <code>G</code> is weighted or not. I am not using the decorator in order to preserve this behaviour.
Best regards,
</p>
<p>
Simon
</p>
TicketncohenFri, 06 Dec 2013 14:55:03 GMT
https://trac.sagemath.org/ticket/15278#comment:16
https://trac.sagemath.org/ticket/15278#comment:16
<p>
Yooooooooo !!!
</p>
<blockquote class="citation">
<ul><li>The methods mentioned above call the backend, namely:
<ol><li>`._backend.multiple_edges(None)
</li><li><code>._backend.loops(None)</code>
</li><li><code>._backend.num_verts()</code>
</li><li><code>._backend.num_edges(self._directed)</code>
</li></ol></li></ul><p>
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?
</p>
</blockquote>
<p>
Nope. <code>multiple_edges</code> and <code>loops</code> 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 !
</p>
<blockquote class="citation">
<p>
If it is not possible, then the <code>__eq__</code> classes won't change when using the static graph backend, and I am happy.
</p>
</blockquote>
<p>
You can't be Happy. This guy is already named Happy, and there can't be two.
<a class="ext-link" href="http://fairytail.wikia.com/wiki/Happy"><span class="icon"></span>http://fairytail.wikia.com/wiki/Happy</a>
</p>
<blockquote class="citation">
<p>
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.
</p>
</blockquote>
<p>
While saying each time that the labels *CAN* change if they are lists and that the users append/remove things from them. But indeed <code>:-P</code>
</p>
<p>
Nathann
</p>
TicketSimonKingFri, 06 Dec 2013 14:58:46 GMT
https://trac.sagemath.org/ticket/15278#comment:17
https://trac.sagemath.org/ticket/15278#comment:17
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/15278#comment:16" title="Comment 16">ncohen</a>:
</p>
<blockquote class="citation">
<p>
Nope. <code>multiple_edges</code> and <code>loops</code> 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 !
</p>
</blockquote>
<p>
Honorary!
</p>
<blockquote class="citation">
<p>
While saying each time that the labels *CAN* change if they are lists and that the users append/remove things from them. But indeed <code>:-P</code>
</p>
</blockquote>
<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 <code>:-P</code>
</p>
TicketSimonKingFri, 06 Dec 2013 15:00:36 GMT
https://trac.sagemath.org/ticket/15278#comment:18
https://trac.sagemath.org/ticket/15278#comment:18
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/15278#comment:17" title="Comment 17">SimonKing</a>:
</p>
<blockquote class="citation">
<p>
Honorary!
</p>
</blockquote>
<p>
To my automatic spell checker: "Hooray", not "honorary"...
</p>
TicketncohenFri, 06 Dec 2013 15:06:15 GMT
https://trac.sagemath.org/ticket/15278#comment:19
https://trac.sagemath.org/ticket/15278#comment:19
<blockquote class="citation">
<p>
Honorary!
</p>
</blockquote>
<p>
Indeed, indeed.
</p>
<blockquote class="citation">
<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 <code>:-P</code>
</p>
</blockquote>
<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 <code>:-P</code>
</p>
<p>
It should all work fine. I just looked at these <code>multiple_edges</code> and <code>loops</code> 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.
</p>
<p>
Have fuuuuuuuuuuuuuuuuuuuuun !
</p>
<p>
Nathann
</p>
TicketSimonKingSat, 07 Dec 2013 00:08:13 GMT
https://trac.sagemath.org/ticket/15278#comment:20
https://trac.sagemath.org/ticket/15278#comment:20
<p>
Is this a bug?
</p>
<pre class="wiki">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
</pre>
TicketncohenSat, 07 Dec 2013 08:37:25 GMT
https://trac.sagemath.org/ticket/15278#comment:21
https://trac.sagemath.org/ticket/15278#comment:21
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/15278#comment:20" title="Comment 20">SimonKing</a>:
</p>
<blockquote class="citation">
<p>
Is this a bug?
</p>
</blockquote>
<p>
It is ! My mistake ! And it is fixed by <a class="closed ticket" href="https://trac.sagemath.org/ticket/15491" title="defect: directed immutable graphs report twice too many edges (closed: fixed)">#15491</a>, which removes the ten characters that shouldn't have been there <code>^^;</code>
</p>
<p>
Nathann
</p>
TicketncohenSat, 07 Dec 2013 09:00:31 GMTdependencies changed
https://trac.sagemath.org/ticket/15278#comment:22
https://trac.sagemath.org/ticket/15278#comment:22
<ul>
<li><strong>dependencies</strong>
changed from <em>#12601</em> to <em>#12601, #15491</em>
</li>
</ul>
TicketgitSat, 07 Dec 2013 12:43:05 GMTcommit changed
https://trac.sagemath.org/ticket/15278#comment:23
https://trac.sagemath.org/ticket/15278#comment:23
<ul>
<li><strong>commit</strong>
changed from <em>c774057bf07b2da8539f2395555b2062428874f4</em> to <em>07bad466ab9a3e2ffe82c142cc6d0c515f1ae452</em>
</li>
</ul>
<p>
Branch pushed to git repo; I updated commit sha1. New commits:
</p>
<table class="wiki">
<tr><td><a class="ext-link" href="http://git.sagemath.org/sage.git/commit/?id=07bad46"><span class="icon"></span>07bad46</a></td><td>Merge branch 'u/ncohen/15491' of <a class="ext-link" href="git://trac.sagemath.org/sage"><span class="icon"></span>git://trac.sagemath.org/sage</a> into ticket/15278
</td></tr><tr><td><a class="ext-link" href="http://git.sagemath.org/sage.git/commit/?id=020cc82"><span class="icon"></span>020cc82</a></td><td>trac <a class="closed ticket" href="https://trac.sagemath.org/ticket/15491" title="defect: directed immutable graphs report twice too many edges (closed: fixed)">#15491</a>: addressing the reviewer's comments
</td></tr><tr><td><a class="ext-link" href="http://git.sagemath.org/sage.git/commit/?id=cd97926"><span class="icon"></span>cd97926</a></td><td>trac <a class="closed ticket" href="https://trac.sagemath.org/ticket/15491" title="defect: directed immutable graphs report twice too many edges (closed: fixed)">#15491</a>: directed immutable graphs report twice too many edges
</td></tr><tr><td><a class="ext-link" href="http://git.sagemath.org/sage.git/commit/?id=126b036"><span class="icon"></span>126b036</a></td><td>Merge branch 'master' into ticket/15278
</td></tr></table>
TicketSimonKingSat, 07 Dec 2013 21:11:05 GMT
https://trac.sagemath.org/ticket/15278#comment:24
https://trac.sagemath.org/ticket/15278#comment:24
<p>
I think we need to take care of another detail:
</p>
<p>
If the static graph backend is used, then <code>self.delete_vertex(vertex)</code> and similar mutating methods will result in an error raised by the backend.
</p>
<p>
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:
</p>
<div class="wiki-code"><div class="code"><pre> <span class="k">if</span> in_order<span class="p">:</span>
vertex <span class="o">=</span> <span class="bp">self</span><span class="o">.</span>vertices<span class="p">()[</span>vertex<span class="p">]</span>
<span class="k">if</span> vertex <span class="ow">not</span> <span class="ow">in</span> <span class="bp">self</span><span class="p">:</span>
<span class="k">raise</span> <span class="ne">RuntimeError</span><span class="p">(</span><span class="s">"Vertex (</span><span class="si">%s</span><span class="s">) not in the graph."</span><span class="o">%</span><span class="nb">str</span><span class="p">(</span>vertex<span class="p">))</span>
attributes_to_update <span class="o">=</span> <span class="p">(</span><span class="s">'_pos'</span><span class="p">,</span> <span class="s">'_assoc'</span><span class="p">,</span> <span class="s">'_embedding'</span><span class="p">)</span>
<span class="k">for</span> attr <span class="ow">in</span> attributes_to_update<span class="p">:</span>
<span class="k">if</span> <span class="nb">hasattr</span><span class="p">(</span><span class="bp">self</span><span class="p">,</span> attr<span class="p">)</span> <span class="ow">and</span> <span class="nb">getattr</span><span class="p">(</span><span class="bp">self</span><span class="p">,</span> attr<span class="p">)</span> <span class="ow">is</span> <span class="ow">not</span> <span class="bp">None</span><span class="p">:</span>
<span class="nb">getattr</span><span class="p">(</span><span class="bp">self</span><span class="p">,</span> attr<span class="p">)</span><span class="o">.</span>pop<span class="p">(</span>vertex<span class="p">,</span> <span class="bp">None</span><span class="p">)</span>
<span class="bp">self</span><span class="o">.</span>_boundary <span class="o">=</span> <span class="p">[</span>v <span class="k">for</span> v <span class="ow">in</span> <span class="bp">self</span><span class="o">.</span>_boundary <span class="k">if</span> v <span class="o">!=</span> vertex<span class="p">]</span>
<span class="bp">self</span><span class="o">.</span>_backend<span class="o">.</span>del_vertex<span class="p">(</span>vertex<span class="p">)</span>
</pre></div></div><p>
Shouldn't this better be
</p>
<div class="wiki-code"><div class="code"><pre> <span class="k">if</span> in_order<span class="p">:</span>
vertex <span class="o">=</span> <span class="bp">self</span><span class="o">.</span>vertices<span class="p">()[</span>vertex<span class="p">]</span>
<span class="k">if</span> vertex <span class="ow">not</span> <span class="ow">in</span> <span class="bp">self</span><span class="p">:</span>
<span class="k">raise</span> <span class="ne">RuntimeError</span><span class="p">(</span><span class="s">"Vertex (</span><span class="si">%s</span><span class="s">) not in the graph."</span><span class="o">%</span><span class="nb">str</span><span class="p">(</span>vertex<span class="p">))</span>
<span class="bp">self</span><span class="o">.</span>_backend<span class="o">.</span>del_vertex<span class="p">(</span>vertex<span class="p">)</span>
attributes_to_update <span class="o">=</span> <span class="p">(</span><span class="s">'_pos'</span><span class="p">,</span> <span class="s">'_assoc'</span><span class="p">,</span> <span class="s">'_embedding'</span><span class="p">)</span>
<span class="k">for</span> attr <span class="ow">in</span> attributes_to_update<span class="p">:</span>
<span class="k">if</span> <span class="nb">hasattr</span><span class="p">(</span><span class="bp">self</span><span class="p">,</span> attr<span class="p">)</span> <span class="ow">and</span> <span class="nb">getattr</span><span class="p">(</span><span class="bp">self</span><span class="p">,</span> attr<span class="p">)</span> <span class="ow">is</span> <span class="ow">not</span> <span class="bp">None</span><span class="p">:</span>
<span class="nb">getattr</span><span class="p">(</span><span class="bp">self</span><span class="p">,</span> attr<span class="p">)</span><span class="o">.</span>pop<span class="p">(</span>vertex<span class="p">,</span> <span class="bp">None</span><span class="p">)</span>
<span class="bp">self</span><span class="o">.</span>_boundary <span class="o">=</span> <span class="p">[</span>v <span class="k">for</span> v <span class="ow">in</span> <span class="bp">self</span><span class="o">.</span>_boundary <span class="k">if</span> v <span class="o">!=</span> vertex<span class="p">]</span>
</pre></div></div>
TicketncohenSat, 07 Dec 2013 21:39:21 GMT
https://trac.sagemath.org/ticket/15278#comment:25
https://trac.sagemath.org/ticket/15278#comment:25
<blockquote class="citation">
<p>
If the static graph backend is used, then <code>self.delete_vertex(vertex)</code> and similar mutating methods will result in an error raised by the backend.
</p>
</blockquote>
<p>
If this thing is the code of <code>.delete_vertex</code> then we have a lot of things to worry about. WHY THE HELL is this thing building a list of size <code>number_of_vertices</code> for the <code>_boundary</code> operation EACH TIME A VERTEX IS REMOVED ? <code>O_O</code>
</p>
<p>
Anyway. What you want to do is a good way out. Adding a decorator to <code>set_boundary</code> 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 <code>list.remove</code> or something, in order to NOT create a list each time a vertex is deleted.
</p>
<p>
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 <code>>_<</code>
</p>
<p>
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.
</p>
<p>
Nathann
</p>
TicketSimonKingSun, 08 Dec 2013 20:13:40 GMT
https://trac.sagemath.org/ticket/15278#comment:26
https://trac.sagemath.org/ticket/15278#comment:26
<p>
Shouldn't named graphs be immutable?
</p>
<pre class="wiki">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
</pre><p>
I would expect that in order to modify something "named", one should create a mutable copy first.
</p>
TicketncohenSun, 08 Dec 2013 20:25:07 GMT
https://trac.sagemath.org/ticket/15278#comment:27
https://trac.sagemath.org/ticket/15278#comment:27
<blockquote class="citation">
<p>
Shouldn't named graphs be immutable?
</p>
</blockquote>
<p>
Please no !
</p>
<blockquote class="citation">
<p>
I would expect that in order to modify something "named", one should create a mutable copy first.
</p>
</blockquote>
<p>
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 ?
</p>
<p>
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.
</p>
<p>
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.
</p>
<p>
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 <code>graphs.CompleteBipartiteGraph</code> would have been hell too.
</p>
<p>
So please, the named graphs stay mutable for the moment, unless this job is done responsibly.
</p>
<p>
Nathann
</p>
TicketncohenSun, 08 Dec 2013 20:49:53 GMT
https://trac.sagemath.org/ticket/15278#comment:28
https://trac.sagemath.org/ticket/15278#comment:28
<p>
Honestly, I would prefer to drop graph names. I don't even see the point of that <code>:-P</code>
</p>
<p>
Nathann
</p>
TicketSimonKingSun, 08 Dec 2013 21:39:36 GMT
https://trac.sagemath.org/ticket/15278#comment:29
https://trac.sagemath.org/ticket/15278#comment:29
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/15278#comment:28" title="Comment 28">ncohen</a>:
</p>
<blockquote class="citation">
<p>
Honestly, I would prefer to drop graph names. I don't even see the point of that <code>:-P</code>
</p>
</blockquote>
<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.
</p>
TicketSimonKingSun, 08 Dec 2013 21:48:49 GMT
https://trac.sagemath.org/ticket/15278#comment:30
https://trac.sagemath.org/ticket/15278#comment:30
<p>
A different question: Shall we simply rely on the error that is raised by the static backend (which is an <code>AttributeError</code> when adding or deleting a vertex and a <code>NotImplementedError</code> when adding ), or should we catch the error and raise a <code>TypeError</code> 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?
</p>
<p>
That's to say, would it be enough to have
</p>
<pre class="wiki">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:
</pre><p>
or would we like to have
</p>
<pre class="wiki">sage: G_imm.add_edge(1,2)
Traceback (most recent call last):
...
TypeError: Can not add an edge to an immutable graph
</pre>
TicketncohenSun, 08 Dec 2013 21:56:28 GMT
https://trac.sagemath.org/ticket/15278#comment:31
https://trac.sagemath.org/ticket/15278#comment:31
<blockquote class="citation">
<p>
A different question: Shall we simply rely on the error that is raised by the static backend (which is an <code>AttributeError</code> when adding or deleting a vertex and a <code>NotImplementedError</code> when adding ), or should we catch the error and raise a <code>TypeError</code> 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?
</p>
</blockquote>
<p>
Hmmm.. Well, in the code of <code>static_sparse_backend</code> there is an add_vertex function which whose code is the following :
</p>
<pre class="wiki">raise ValueError("Thou shalt not add a vertex to an immutable graph")
</pre><p>
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 <code>:-)</code>
</p>
<p>
Nathann
</p>
TicketgitSun, 08 Dec 2013 22:34:29 GMTcommit changed
https://trac.sagemath.org/ticket/15278#comment:32
https://trac.sagemath.org/ticket/15278#comment:32
<ul>
<li><strong>commit</strong>
changed from <em>07bad466ab9a3e2ffe82c142cc6d0c515f1ae452</em> to <em>2fc8a772ee12fce7ac6abc4ecf9916f4746f5ee2</em>
</li>
</ul>
<p>
Branch pushed to git repo; I updated commit sha1. New commits:
</p>
<table class="wiki">
<tr><td><a class="ext-link" href="http://git.sagemath.org/sage.git/commit/?id=2fc8a77"><span class="icon"></span>2fc8a77</a></td><td>Make digraphs using the static backend immutable and hashable
</td></tr></table>
TicketSimonKingSun, 08 Dec 2013 22:42:18 GMT
https://trac.sagemath.org/ticket/15278#comment:33
https://trac.sagemath.org/ticket/15278#comment:33
<p>
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.
</p>
<p>
The <code>ValueError</code> you are mentioning is not part of the <code>add_vertex</code> method of the static backend, by the way:
</p>
<pre class="wiki">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'
</pre><p>
EDIT: Here is the mro:
</p>
<pre class="wiki">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]
</pre>
TicketSimonKingMon, 09 Dec 2013 11:01:42 GMTstatus changed
https://trac.sagemath.org/ticket/15278#comment:34
https://trac.sagemath.org/ticket/15278#comment:34
<ul>
<li><strong>status</strong>
changed from <em>new</em> to <em>needs_review</em>
</li>
</ul>
<p>
Since the topic of this ticket is "hash and equality for graphs" and since we now have a way (by saying <code>data_structure="static_sparse"</code> 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.
</p>
TicketncohenMon, 09 Dec 2013 11:06:15 GMT
https://trac.sagemath.org/ticket/15278#comment:35
https://trac.sagemath.org/ticket/15278#comment:35
<p>
HMmmmmm okay. Though I really have no clue what the changes you made to cachefunc.pyx do <code>O_o</code>
</p>
<p>
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 ?
</p>
<p>
Nathann
</p>
TicketSimonKingMon, 09 Dec 2013 11:21:34 GMT
https://trac.sagemath.org/ticket/15278#comment:36
https://trac.sagemath.org/ticket/15278#comment:36
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/15278#comment:35" title="Comment 35">ncohen</a>:
</p>
<blockquote class="citation">
<p>
HMmmmmm okay. Though I really have no clue what the changes you made to cachefunc.pyx do <code>O_o</code>
</p>
</blockquote>
<p>
Hein? My branch doesn't touch cachefunc.pyx at all! And why should it?
</p>
<blockquote class="citation">
<p>
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 ?
</p>
</blockquote>
<p>
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 <code>G.weighted()</code> but disallow <code>G.weighted(new_value)</code> 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 <code>._immutable</code> attribute---and to make the hash faster (by using work on @cached_method that has already been done in <a class="closed ticket" href="https://trac.sagemath.org/ticket/12601" title="enhancement: @cached_method does not work for special methods (closed: fixed)">#12601</a>).
</p>
<p>
So, that's what this ticket is about. Or is there anything I forgot?
</p>
<p>
And my next aim is to continue work on <a class="closed ticket" href="https://trac.sagemath.org/ticket/12630" title="enhancement: Add representations of quivers and quiver algebras to sage (closed: fixed)">#12630</a>. There, it is useful to have hashable (immutable) (di)graphs that can be used as cache keys.
</p>
TicketSimonKingMon, 09 Dec 2013 11:30:00 GMT
https://trac.sagemath.org/ticket/15278#comment:37
https://trac.sagemath.org/ticket/15278#comment:37
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/15278#comment:36" title="Comment 36">SimonKing</a>:
</p>
<blockquote class="citation">
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/15278#comment:35" title="Comment 35">ncohen</a>:
</p>
<blockquote class="citation">
<p>
HMmmmmm okay. Though I really have no clue what the changes you made to cachefunc.pyx do <code>O_o</code>
</p>
</blockquote>
<p>
Hein? My branch doesn't touch cachefunc.pyx at all! And why should it?
</p>
</blockquote>
<p>
Ahaha, now I understand. That's this dreaded feature of the new git workflow: The commits changing cachefunc.pyx belong to <a class="closed ticket" href="https://trac.sagemath.org/ticket/12601" title="enhancement: @cached_method does not work for special methods (closed: fixed)">#12601</a>, 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.
</p>
<p>
Personally, I believe that <a class="closed ticket" href="https://trac.sagemath.org/ticket/12601" title="enhancement: @cached_method does not work for special methods (closed: fixed)">#12601</a> 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 <a class="closed ticket" href="https://trac.sagemath.org/ticket/12601" title="enhancement: @cached_method does not work for special methods (closed: fixed)">#12601</a>. Of course, if you happen to spot something in <a class="closed ticket" href="https://trac.sagemath.org/ticket/12601" title="enhancement: @cached_method does not work for special methods (closed: fixed)">#12601</a> that doesn't work then please speak up.
</p>
TicketncohenMon, 09 Dec 2013 11:30:57 GMT
https://trac.sagemath.org/ticket/15278#comment:38
https://trac.sagemath.org/ticket/15278#comment:38
<p>
Yooooooooooooo !!
</p>
<blockquote class="citation">
<blockquote>
<p>
Hein? My branch doesn't touch cachefunc.pyx at all! And why should it?
</p>
</blockquote>
</blockquote>
<p>
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 <a class="closed ticket" href="https://trac.sagemath.org/ticket/12601" title="enhancement: @cached_method does not work for special methods (closed: fixed)">#12601</a> it seems.
</p>
<p>
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 <a class="ext-link" href="https://groups.google.com/d/topic/sage-git/ZC5QB1o1JlE/discussion"><span class="icon"></span>https://groups.google.com/d/topic/sage-git/ZC5QB1o1JlE/discussion</a>
Sigh. Sorry for the misunderstanding :-/
</p>
<blockquote class="citation">
<blockquote>
<p>
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 <code>G.weighted()</code> but disallow <code>G.weighted(new_value)</code> 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 <code>._immutable</code> attribute---and to make
the hash faster (by using work on @cached_method that has already been
done in <a class="closed ticket" href="https://trac.sagemath.org/ticket/12601" title="enhancement: @cached_method does not work for special methods (closed: fixed)">#12601</a>).
</p>
</blockquote>
<blockquote>
<p>
So, that's what this ticket is about. Or is there anything I forgot?
</p>
</blockquote>
</blockquote>
<p>
Sorry sorry, it's just a misunderstanding about what this branch contains... T_T
</p>
<blockquote class="citation">
<blockquote>
<p>
And my next aim is to continue work on <a class="closed ticket" href="https://trac.sagemath.org/ticket/12630" title="enhancement: Add representations of quivers and quiver algebras to sage (closed: fixed)">#12630</a>. There, it is useful to have
hashable (immutable) (di)graphs that can be used as cache keys.
</p>
</blockquote>
</blockquote>
<p>
Okayyyyyyyyyyyyyyyyyyyyyyyyyyyyyy ! I thought that it was the case as soon as these things were hashable, but if you say so O_o
</p>
<p>
Nathann
</p>
TicketncohenMon, 09 Dec 2013 16:04:52 GMT
https://trac.sagemath.org/ticket/15278#comment:39
https://trac.sagemath.org/ticket/15278#comment:39
<p>
HMmmmm... Don't you touch cachefunc.pyx in commit 126b03609e9bae78955ccbc97e36f1924a79603b ? That's when you merge <a class="closed ticket" href="https://trac.sagemath.org/ticket/12601" title="enhancement: @cached_method does not work for special methods (closed: fixed)">#12601</a> in the present branch.
</p>
<p>
Gosh, I'm going to hate these git dependencies.
</p>
<p>
Some remarks, though :
</p>
<ul><li>In <code>.copy()</code>, 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 <code>data_structure</code> 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 ?
</li></ul><ul><li>Why wouldn't we add (later) a "immutable" flag to the constructor and to "copy" ? It would be nice to call <code>Graph(graphs.PetersenGraph(),immutable=True)</code> ? <code>O_o</code>
</li></ul><ul><li>What about an exception message for <code>_hash_</code> 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.
</li></ul><p>
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 <code>:-)</code>
</p>
<p>
Nathann
</p>
TicketncohenTue, 10 Dec 2013 14:10:23 GMT
https://trac.sagemath.org/ticket/15278#comment:40
https://trac.sagemath.org/ticket/15278#comment:40
<p>
(I just created <a class="closed ticket" href="https://trac.sagemath.org/ticket/15507" title="enhancement: Static sparse graphs on > 65536 vertices (closed: fixed)">#15507</a> to handle graphs on > 65536 vertices)
</p>
<p>
Nathann
</p>
TicketSimonKingTue, 10 Dec 2013 14:33:42 GMT
https://trac.sagemath.org/ticket/15278#comment:41
https://trac.sagemath.org/ticket/15278#comment:41
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/15278#comment:40" title="Comment 40">ncohen</a>:
</p>
<blockquote class="citation">
<p>
(I just created <a class="closed ticket" href="https://trac.sagemath.org/ticket/15507" title="enhancement: Static sparse graphs on > 65536 vertices (closed: fixed)">#15507</a> to handle graphs on > 65536 vertices)
</p>
</blockquote>
<p>
Nice! But I suppose the two tickets are independent (no dependency in either direction), right?
</p>
TicketncohenTue, 10 Dec 2013 19:09:18 GMT
https://trac.sagemath.org/ticket/15278#comment:42
https://trac.sagemath.org/ticket/15278#comment:42
<p>
Yes yes they should commute <code>:-)</code>
</p>
<p>
Nathann
</p>
TicketncohenTue, 24 Dec 2013 16:31:50 GMTstatus changed
https://trac.sagemath.org/ticket/15278#comment:43
https://trac.sagemath.org/ticket/15278#comment:43
<ul>
<li><strong>status</strong>
changed from <em>needs_review</em> to <em>needs_info</em>
</li>
</ul>
TicketSimonKingWed, 25 Dec 2013 13:50:14 GMT
https://trac.sagemath.org/ticket/15278#comment:44
https://trac.sagemath.org/ticket/15278#comment:44
<p>
Nathann, what info do you need? Is this because of your <a class="ticket" href="https://trac.sagemath.org/ticket/15278#comment:39" title="Comment 39">comment:39</a>?
</p>
TicketncohenWed, 25 Dec 2013 13:52:57 GMT
https://trac.sagemath.org/ticket/15278#comment:45
https://trac.sagemath.org/ticket/15278#comment:45
<p>
Yepyep that's why <code>^^;</code>
</p>
<p>
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 !
</p>
<p>
Nathann
</p>
TicketSimonKingWed, 25 Dec 2013 14:07:49 GMT
https://trac.sagemath.org/ticket/15278#comment:46
https://trac.sagemath.org/ticket/15278#comment:46
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/15278#comment:39" title="Comment 39">ncohen</a>:
</p>
<blockquote class="citation">
<p>
HMmmmm... Don't you touch cachefunc.pyx in commit 126b03609e9bae78955ccbc97e36f1924a79603b ? That's when you merge <a class="closed ticket" href="https://trac.sagemath.org/ticket/12601" title="enhancement: @cached_method does not work for special methods (closed: fixed)">#12601</a> in the present branch.
</p>
</blockquote>
<p>
Splitting hair...
</p>
<blockquote class="citation">
<p>
Gosh, I'm going to hate these git dependencies.
</p>
</blockquote>
<p>
+1
</p>
<blockquote class="citation">
<ul><li>In <code>.copy()</code>, 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 <code>data_structure</code> has been defined, saying "if data_structure == "static_sparse" and hasattr(self,'_immutable')" then return self ?
</li></ul></blockquote>
<p>
I am working on it.
</p>
<blockquote class="citation">
<p>
By the way, is an object considered mutable if it HAS a ._immutable variable equal to False ?
</p>
</blockquote>
<p>
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 <em>some</em> static backend is used: Perhaps there will be more static backends in future.
</p>
<p>
So, instead of relying on an attribute <code>._immutable</code> 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.
</p>
<p>
Problem: If I am not mistaken, people currently <em>do</em> mess with the attribute <code>._immutable</code>, if I am not mistaken.
</p>
<p>
Would it be feasible to try to remove the <code>._immutable</code> attribute (and testing the type of the backend instead), see how much fails, and fix the failing code by using "proper" immutable graphs?
</p>
<blockquote class="citation">
<ul><li>Why wouldn't we add (later) a "immutable" flag to the constructor and to "copy" ?
</li></ul></blockquote>
<p>
Would a flag in the "copy" function be supported by Python?
</p>
<blockquote class="citation">
<p>
It would be nice to call <code>Graph(graphs.PetersenGraph(),immutable=True)</code> ? <code>O_o</code>
</p>
</blockquote>
<p>
Yes. Only problem: We would then need to decide what to do if "immutable=False" and "backend="static_sparse" is simultaneously used.
</p>
<blockquote class="citation">
<ul><li>What about an exception message for <code>_hash_</code> 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."
</li></ul></blockquote>
<p>
OK.
</p>
TicketncohenWed, 25 Dec 2013 14:21:42 GMT
https://trac.sagemath.org/ticket/15278#comment:47
https://trac.sagemath.org/ticket/15278#comment:47
<p>
Yoooooooooooo !!
</p>
<blockquote class="citation">
<blockquote class="citation">
<p>
HMmmmm... Don't you touch cachefunc.pyx in commit 126b03609e9bae78955ccbc97e36f1924a79603b ? That's when you merge <a class="closed ticket" href="https://trac.sagemath.org/ticket/12601" title="enhancement: @cached_method does not work for special methods (closed: fixed)">#12601</a> in the present branch.
</p>
</blockquote>
<p>
Splitting hair...
</p>
</blockquote>
<p>
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 <code>:-P</code>
</p>
<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 <code>O_o</code>
</p>
<p>
Well, well...
</p>
<blockquote class="citation">
<p>
I am working on it.
</p>
</blockquote>
<p>
Cool !
</p>
<blockquote class="citation">
<p>
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 <em>some</em> static backend is used: Perhaps there will be more static backends in future.
</p>
<p>
So, instead of relying on an attribute <code>._immutable</code> 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.
</p>
<p>
Problem: If I am not mistaken, people currently <em>do</em> mess with the attribute <code>._immutable</code>, if I am not mistaken.
</p>
</blockquote>
<p>
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.
</p>
<blockquote class="citation">
<p>
Would it be feasible to try to remove the <code>._immutable</code> attribute (and testing the type of the backend instead), see how much fails, and fix the failing code by using "proper" immutable graphs?
</p>
</blockquote>
<p>
Hmmmm, I thought that Python really needed this <code>_immutable</code> variable somewhere <code>O_o</code>
</p>
<blockquote class="citation">
<p>
Would a flag in the "copy" function be supported by Python?
</p>
</blockquote>
<p>
Well not in <code>.__copy__</code> but in <code>.copy()</code> no problem I guess.
</p>
<blockquote class="citation">
<blockquote class="citation">
<p>
It would be nice to call <code>Graph(graphs.PetersenGraph(),immutable=True)</code> ? <code>O_o</code>
</p>
</blockquote>
</blockquote>
<blockquote class="citation">
<p>
Yes. Only problem: We would then need to decide what to do if "immutable=False" and "backend="static_sparse" is simultaneously used.
</p>
</blockquote>
<p>
I usually settle this by setting the keywords to "None" by default, instead of <a class="missing wiki">True/False?</a>. 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.
</p>
<p>
Nathann
</p>
TicketSimonKingFri, 27 Dec 2013 11:06:05 GMT
https://trac.sagemath.org/ticket/15278#comment:48
https://trac.sagemath.org/ticket/15278#comment:48
<p>
Could it be that I did a stupid mistake? In <code>__copy__</code>, I read
</p>
<pre class="wiki"> if getattr(self, '_immutable', False):
if implementation=='c_graph' and data_structure is None and sparse is not None:
return self
</pre><p>
Shouldn't it be "if getattr(self, '_immutable', True):`?
</p>
TicketSimonKingFri, 27 Dec 2013 11:09:36 GMT
https://trac.sagemath.org/ticket/15278#comment:49
https://trac.sagemath.org/ticket/15278#comment:49
<p>
Oopy, sorry, for the noise, it is correct in this way <code>:-/</code> (facepalm)
</p>
TicketSimonKingFri, 27 Dec 2013 17:25:15 GMT
https://trac.sagemath.org/ticket/15278#comment:50
https://trac.sagemath.org/ticket/15278#comment:50
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/15278#comment:47" title="Comment 47">ncohen</a>:
</p>
<blockquote class="citation">
<blockquote class="citation">
<p>
Problem: If I am not mistaken, people currently <em>do</em> mess with the attribute <code>._immutable</code>, if I am not mistaken.
</p>
</blockquote>
<p>
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.
</p>
</blockquote>
<p>
The usage is <code>if getattr(self,'_immutable',False/True): raise TypeError("...")</code> (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).
</p>
<blockquote class="citation">
<blockquote class="citation">
<p>
Would it be feasible to try to remove the <code>._immutable</code> attribute (and testing the type of the backend instead), see how much fails, and fix the failing code by using "proper" immutable graphs?
</p>
</blockquote>
<p>
Hmmmm, I thought that Python really needed this <code>_immutable</code> variable somewhere <code>O_o</code>
</p>
</blockquote>
<p>
I've never heard before that Python uses it.
</p>
<blockquote class="citation">
<blockquote class="citation">
<p>
Would a flag in the "copy" function be supported by Python?
</p>
</blockquote>
<p>
Well not in <code>.__copy__</code> but in <code>.copy()</code> no problem I guess.
</p>
</blockquote>
<p>
Now we talk about three things. I was talking about Python's (or Sage's?) <code>copy()</code> function, which dispatches to <code>__copy__</code> or to pickling, depending on what's available. You talk about the <code>.__copy__()</code> method, which exists for graphs, and the <code>.copy()</code> method, which is set to <code>__copy__</code> for graphs.
</p>
<p>
The <code>copy()</code> <em>function</em> does not use any argument except the object that is being copied. For that reason, I think the <code>__copy__</code> method <em>should</em> not accept any arguments except <code>self</code>. But currently, the <code>.__copy__()</code> method of graphs uses a plethora of optional arguments.
</p>
<p>
Instead, I suggest that one should introduce a separate <code>.copy()</code> 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 <code>.__copy__()</code>).
</p>
<p>
On the other hand (thinking after writing, as usual...): The optional arguments of <code>__copy__</code> are not used, but when one defines <code>copy=__copy__</code> 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.
</p>
<p>
But one question on copying needs to be addressed: I think in some places in Sage, <code>copy(X)</code> returns <code>X</code> if <code>X</code> is immutable, but in other places in Sage, <code>copy(X)</code> always returns a <em>mutable</em> copy of <code>X</code>, regardless whether <code>X</code> is mutable or not. What would you prefer for graphs?
</p>
<p>
In any case, I should add a test showing what happens with copies of immutable graphs.
</p>
<blockquote class="citation">
<p>
I usually settle this by setting the keywords to "None" by default, instead of <a class="missing wiki">True/False?</a>. 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.
</p>
</blockquote>
<p>
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?
</p>
TicketncohenFri, 27 Dec 2013 17:42:31 GMT
https://trac.sagemath.org/ticket/15278#comment:51
https://trac.sagemath.org/ticket/15278#comment:51
<p>
Hellooooooooo !!
</p>
<blockquote class="citation">
<p>
The usage is <code>if getattr(self,'_immutable',False/True): raise TypeError("...")</code> (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).
</p>
<p>
I've never heard before that Python uses it.
</p>
</blockquote>
<p>
Oh. Then I guess we are the only ones to use this <code>._immutable</code> flag.
</p>
<blockquote class="citation">
<p>
On the other hand (thinking after writing, as usual...): The optional arguments of <code>__copy__</code> are not used, but when one defines <code>copy=__copy__</code> 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.
</p>
<p>
But one question on copying needs to be addressed: I think in some places in Sage, <code>copy(X)</code> returns <code>X</code> if <code>X</code> is immutable, but in other places in Sage, <code>copy(X)</code> always returns a <em>mutable</em> copy of <code>X</code>, regardless whether <code>X</code> is mutable or not. What would you prefer for graphs?
</p>
<p>
In any case, I should add a test showing what happens with copies of immutable graphs.
</p>
</blockquote>
<p>
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 <code>O_o</code>
</p>
<blockquote class="citation">
<p>
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?
</p>
</blockquote>
<p>
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 <code>:-)</code>
</p>
<p>
Nathann
</p>
TicketSimonKingFri, 27 Dec 2013 19:24:40 GMT
https://trac.sagemath.org/ticket/15278#comment:52
https://trac.sagemath.org/ticket/15278#comment:52
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/15278#comment:51" title="Comment 51">ncohen</a>:
</p>
<blockquote class="citation">
<blockquote class="citation">
<p>
I've never heard before that Python uses it.
</p>
</blockquote>
<p>
Oh. Then I guess we are the only ones to use this <code>._immutable</code> flag.
</p>
</blockquote>
<p>
Ahem. Then I guess there are many things in Python that I've never heard of...
</p>
<blockquote class="citation">
<blockquote class="citation">
<p>
But one question on copying needs to be addressed: I think in some places in Sage, <code>copy(X)</code> returns <code>X</code> if <code>X</code> is immutable, but in other places in Sage, <code>copy(X)</code> always returns a <em>mutable</em> copy of <code>X</code>, regardless whether <code>X</code> is mutable or not. What would you prefer for graphs?
</p>
</blockquote>
<p>
Hmmm... Well, I guess it makes more sense to get with "copy" the same kind of object that was given as input.
</p>
</blockquote>
<p>
From my perspective, this behaviour would be fine. But I also see this:
</p>
<pre class="wiki">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
</pre><p>
There is one crucial difference, though: A mutable matrix can be made immutable, by <code>M.set_immutable()</code>. 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.
</p>
<p>
Anyway, I don't think that there is a commonly accepted standard in Sage. Since we have no <code>G.set_immutable()</code> method for graphs, I guess it is better to have
</p>
<ul><li><code>copy(G)</code> has the same backend as G. In particular, mutability is copied. And if it is immutable, then we should have <code>G is copy(G)</code>.
</li><li>If one wants an immutable/mutable copy of a mutable/immutable graph G, then it should be done either by <code>Graph(G,backend='...')</code> or <code>G.copy(backend='...')</code> respectively with a to-be-implemented <code>mutable=True/False</code> keyword.
</li></ul>
TicketncohenFri, 27 Dec 2013 19:32:26 GMT
https://trac.sagemath.org/ticket/15278#comment:53
https://trac.sagemath.org/ticket/15278#comment:53
<p>
Helloooooooo !!
</p>
<blockquote class="citation">
<p>
Ahem. Then I guess there are many things in Python that I've never heard of...
</p>
</blockquote>
<p>
Ahahahah. That's how sure we both are of our Python knowledge <code>:-PPP</code>
</p>
<blockquote class="citation">
<p>
From my perspective, this behaviour would be fine. But I also see this:
</p>
<pre class="wiki">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
</pre><p>
There is one crucial difference, though: A mutable matrix can be made immutable, by <code>M.set_immutable()</code>. 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.
</p>
</blockquote>
<p>
Yepyep. Making it mutable needs to copy it, so it has to go through .copy or through the constructor.
</p>
<blockquote class="citation">
<p>
Anyway, I don't think that there is a commonly accepted standard in Sage. Since we have no <code>G.set_immutable()</code> method for graphs, I guess it is better to have
</p>
<ul><li><code>copy(G)</code> has the same backend as G. In particular, mutability is copied. And if it is immutable, then we should have <code>G is copy(G)</code>.
</li><li>If one wants an immutable/mutable copy of a mutable/immutable graph G, then it should be done either by <code>Graph(G,backend='...')</code> or <code>G.copy(backend='...')</code> respectively with a to-be-implemented <code>mutable=True/False</code> keyword.
</li></ul></blockquote>
<p>
Yepyep, works for me <code>:-)</code>
</p>
<p>
Nathann
</p>
TicketgitFri, 27 Dec 2013 21:13:35 GMTcommit changed
https://trac.sagemath.org/ticket/15278#comment:54
https://trac.sagemath.org/ticket/15278#comment:54
<ul>
<li><strong>commit</strong>
changed from <em>2fc8a772ee12fce7ac6abc4ecf9916f4746f5ee2</em> to <em>51d63284da70ffa4772a0d0fda6020750aef2e6d</em>
</li>
</ul>
<p>
Branch pushed to git repo; I updated commit sha1. New commits:
</p>
<table class="wiki">
<tr><td><a class="ext-link" href="http://git.sagemath.org/sage.git/commit/?id=51d6328"><span class="icon"></span>51d6328</a></td><td><code>Trac 15278: Error messages explain how to create (im)mutable graph copy</code>
</td></tr></table>
TicketSimonKingFri, 27 Dec 2013 21:20:45 GMTstatus changed
https://trac.sagemath.org/ticket/15278#comment:55
https://trac.sagemath.org/ticket/15278#comment:55
<ul>
<li><strong>status</strong>
changed from <em>needs_info</em> to <em>needs_review</em>
</li>
</ul>
<p>
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 <code>__copy__</code>.
</p>
TicketncohenSat, 28 Dec 2013 06:35:35 GMTstatus changed; reviewer set
https://trac.sagemath.org/ticket/15278#comment:56
https://trac.sagemath.org/ticket/15278#comment:56
<ul>
<li><strong>status</strong>
changed from <em>needs_review</em> to <em>positive_review</em>
</li>
<li><strong>reviewer</strong>
set to <em>Nathann Cohen</em>
</li>
</ul>
<p>
thaaaaaaaaaaaaaanks !!!
</p>
<p>
Nathann
</p>
TicketncohenSun, 29 Dec 2013 11:03:51 GMTstatus changed
https://trac.sagemath.org/ticket/15278#comment:57
https://trac.sagemath.org/ticket/15278#comment:57
<ul>
<li><strong>status</strong>
changed from <em>positive_review</em> to <em>needs_work</em>
</li>
</ul>
<p>
Helloooooo !!
</p>
<p>
I'm sorry but this ticket has to be rebased. I created <a class="closed ticket" href="https://trac.sagemath.org/ticket/15603" title="enhancement: "immutable=True" for Graph/Digraph __init__ and copy() (closed: fixed)">#15603</a> 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 <code>6.1.beta2</code>. And I have no clue how this patch can have any effect on that code <code>O_o</code>
</p>
<p>
Here are the doctests that are reported to be broken on <a class="closed ticket" href="https://trac.sagemath.org/ticket/15603" title="enhancement: "immutable=True" for Graph/Digraph __init__ and copy() (closed: fixed)">#15603</a>
</p>
<pre class="wiki">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
</pre><p>
The exceptions caused to <code>c_graph.pyx</code> seem to be my doing, though. Everything else looks related to linear extensions.
</p>
<p>
Nathann
</p>
TicketSimonKingSun, 29 Dec 2013 11:47:58 GMT
https://trac.sagemath.org/ticket/15278#comment:58
https://trac.sagemath.org/ticket/15278#comment:58
<p>
I have just merged the branch from here (but not together with <a class="closed ticket" href="https://trac.sagemath.org/ticket/15603" title="enhancement: "immutable=True" for Graph/Digraph __init__ and copy() (closed: fixed)">#15603</a>!) with the latest develop branch, and will see what I can do.
</p>
TicketSimonKingSun, 29 Dec 2013 12:10:00 GMT
https://trac.sagemath.org/ticket/15278#comment:59
https://trac.sagemath.org/ticket/15278#comment:59
<p>
I get
</p>
<pre class="wiki">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
</pre><p>
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?
</p>
TicketncohenSun, 29 Dec 2013 12:20:41 GMT
https://trac.sagemath.org/ticket/15278#comment:60
https://trac.sagemath.org/ticket/15278#comment:60
<p>
Yoooooooooo !
</p>
<blockquote class="citation">
<p>
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?
</p>
</blockquote>
<p>
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:
</p>
<pre class="wiki">~/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
</pre><pre class="wiki">~/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
</pre><p>
(<code>d</code> is my <code>develop</code> branch).
</p>
<p>
But <a class="closed ticket" href="https://trac.sagemath.org/ticket/15322" title="enhancement: Testing for antichains and chains in arbitrary posets (closed: fixed)">#15322</a> only simplifies code, and <a class="closed ticket" href="https://trac.sagemath.org/ticket/15330" title="defect: Poset.is_chain is wrong (closed: fixed)">#15330</a> 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 <a class="closed ticket" href="https://trac.sagemath.org/ticket/15313" title="defect: is_linear_extension on posets is rather liberal (closed: fixed)">#15313</a>, who knows ? It is a bugfix too. <code>Poset.is_linear_extension([1,2,3,4])</code> could return True even if 4 is not contained in the Poset, and the patch fixes it <code>:-/</code>
And <a class="closed ticket" href="https://trac.sagemath.org/ticket/15340" title="defect: Bug in chord_and_tangent (closed: fixed)">#15340</a> looks totally unrelated.
</p>
<p>
Nathann
</p>
TicketSimonKingSun, 29 Dec 2013 12:22:50 GMT
https://trac.sagemath.org/ticket/15278#comment:61
https://trac.sagemath.org/ticket/15278#comment:61
<p>
Oooooops:
</p>
<pre class="wiki">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
</pre><p>
So, somehow the linear extension steals the poset's elements
</p>
TicketncohenSun, 29 Dec 2013 12:30:09 GMT
https://trac.sagemath.org/ticket/15278#comment:62
https://trac.sagemath.org/ticket/15278#comment:62
<p>
Facades. What a wonder. I hate this thing. I hate parents, I hate elements, I hate categories, and I hate <code>UniqueElement</code>. <a class="closed ticket" href="https://trac.sagemath.org/ticket/13747" title="defect: Change default behaviour of Poset to facade = True (closed: fixed)">#13747</a> was a long time ago though <code>:-P</code>
</p>
<p>
Nathann
</p>
TicketSimonKingSun, 29 Dec 2013 12:35:33 GMT
https://trac.sagemath.org/ticket/15278#comment:63
https://trac.sagemath.org/ticket/15278#comment:63
<p>
... or rather
</p>
<pre class="wiki">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
</pre>
TicketncohenSun, 29 Dec 2013 12:37:59 GMT
https://trac.sagemath.org/ticket/15278#comment:64
https://trac.sagemath.org/ticket/15278#comment:64
<p>
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.
</p>
<p>
Nathann
</p>
TicketSimonKingSun, 29 Dec 2013 12:42:23 GMT
https://trac.sagemath.org/ticket/15278#comment:65
https://trac.sagemath.org/ticket/15278#comment:65
<p>
Ahaaa! By using <code>trace()</code>, I found that the above uses <code>__copy__</code>---and I did change it. More precisely: It copies the "Hasse diagram of a poset containing 4 elements", which has the <code>._immutable</code> flag set to true, but the <code>sage.graphs.base.sparse_graph.SparseGraphBackend</code>.
</p>
<p>
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 <code>._immutable</code> flag (this is one of the things that I have suggested above, and perhaps we should implement it).
</p>
TicketSimonKingSun, 29 Dec 2013 12:46:15 GMT
https://trac.sagemath.org/ticket/15278#comment:66
https://trac.sagemath.org/ticket/15278#comment:66
<p>
Or go the middle way: In <code>__hash__</code> and in the self-mutating methods, we should rely on the flag, but in <code>__copy__</code> we should be more careful, and should only return <code>self</code> if it is truely immutable.
</p>
<p>
Namely, it seems currently used to create the copy of a mock-immutable graph to mutate the copy, and thus we must return a <em>proper</em> copy rather than just self in this case.
</p>
TicketncohenSun, 29 Dec 2013 12:50:51 GMT
https://trac.sagemath.org/ticket/15278#comment:67
https://trac.sagemath.org/ticket/15278#comment:67
<p>
Oh. I see. Hacks.
</p>
<p>
Well, that makes sense indeed. Looks like a proof that we shouldn't rely on this <code>_immutable</code> flag. Especially when none of us knows who exactly uses it <code>:-P</code>
</p>
<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.
</p>
<p>
This being said, checking the backend does not exactly mean that all other properties of graphs are "protected", like the embedding and everything.
</p>
<p>
Hmmm...
</p>
<p>
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 ?
</p>
<p>
Nathann
</p>
TicketgitSun, 29 Dec 2013 12:58:55 GMTcommit changed
https://trac.sagemath.org/ticket/15278#comment:68
https://trac.sagemath.org/ticket/15278#comment:68
<ul>
<li><strong>commit</strong>
changed from <em>51d63284da70ffa4772a0d0fda6020750aef2e6d</em> to <em>fcf9e3018d5e87f49e1f3f3d68ad4cc49382c0b9</em>
</li>
</ul>
<p>
Branch pushed to git repo; I updated commit sha1. New commits:
</p>
<table class="wiki">
<tr><td><a class="ext-link" href="http://git.sagemath.org/sage.git/commit/?id=fcf9e30"><span class="icon"></span>fcf9e30</a></td><td><code>Trac 15278: Only graphs that use the static backend are identical with their copy</code>
</td></tr><tr><td><a class="ext-link" href="http://git.sagemath.org/sage.git/commit/?id=8fc9c94"><span class="icon"></span>8fc9c94</a></td><td><code>Merge branch 'develop' into ticket/15278</code>
</td></tr></table>
TicketSimonKingSun, 29 Dec 2013 13:00:48 GMT
https://trac.sagemath.org/ticket/15278#comment:69
https://trac.sagemath.org/ticket/15278#comment:69
<p>
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?
</p>
<p>
Anyway, the commit that is now being pushed should solve the problem.
</p>
<hr />
<p>
New commits:
</p>
<table class="wiki">
<tr><td><a class="ext-link" href="http://git.sagemath.org/sage.git/commit/?id=fcf9e30"><span class="icon"></span>fcf9e30</a></td><td><code>Trac 15278: Only graphs that use the static backend are identical with their copy</code>
</td></tr><tr><td><a class="ext-link" href="http://git.sagemath.org/sage.git/commit/?id=8fc9c94"><span class="icon"></span>8fc9c94</a></td><td><code>Merge branch 'develop' into ticket/15278</code>
</td></tr></table>
TicketncohenSun, 29 Dec 2013 13:04:37 GMT
https://trac.sagemath.org/ticket/15278#comment:70
https://trac.sagemath.org/ticket/15278#comment:70
<p>
Well the problem it solves is making this ticket compatible with beta2. So the hack stays ?
</p>
<p>
Nathann
</p>
TicketSimonKingSun, 29 Dec 2013 13:06:56 GMT
https://trac.sagemath.org/ticket/15278#comment:71
https://trac.sagemath.org/ticket/15278#comment:71
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/15278#comment:67" title="Comment 67">ncohen</a>:
</p>
<blockquote class="citation">
<p>
This being said, checking the backend does not exactly mean that all other properties of graphs are "protected", like the embedding and everything.
</p>
</blockquote>
<p>
That's why <em>both</em> the flag and the type of the backend are checked before returning "self" as a copy.
</p>
<blockquote class="citation">
<p>
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 ?
</p>
</blockquote>
<p>
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 <code>copy()</code> create a <em>mutable</em> copy; hence, each usage of <code>copy()</code> should be decorated with an optional argument (such as: <code>sparse=True</code>) 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.
</p>
TicketSimonKingSun, 29 Dec 2013 13:10:50 GMT
https://trac.sagemath.org/ticket/15278#comment:72
https://trac.sagemath.org/ticket/15278#comment:72
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/15278#comment:70" title="Comment 70">ncohen</a>:
</p>
<blockquote class="citation">
<p>
Well the problem it solves is making this ticket compatible with beta2. So the hack stays ?
</p>
</blockquote>
<p>
I only see one place where <code>combinat</code> uses <code>bla._immutable = True</code>:
</p>
<pre class="wiki">src/sage/combinat/posets/posets.py: G._immutable = True
</pre><p>
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.
</p>
TicketncohenSun, 29 Dec 2013 13:15:02 GMT
https://trac.sagemath.org/ticket/15278#comment:73
https://trac.sagemath.org/ticket/15278#comment:73
<blockquote class="citation">
<p>
That's why both the flag and the type of the backend are checked before returning "self" as a copy.
</p>
</blockquote>
<p>
Okay.
</p>
<blockquote class="citation">
<p>
In a way, yes. In a different way: Are we supposed to clean up their mess?
</p>
</blockquote>
<p>
...
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.
</p>
<p>
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.
</p>
<p>
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 <code>O_O</code>
</p>
<p>
Nathann
</p>
TicketncohenSun, 29 Dec 2013 13:25:01 GMT
https://trac.sagemath.org/ticket/15278#comment:74
https://trac.sagemath.org/ticket/15278#comment:74
<p>
I get a doctest error in generic_graph.py :
</p>
<pre class="wiki">+ sage: P = Poset(([1,2,3,4], [[1,3],[1,4],[2,3]]),
+ linear_extension=True, facade = False)
</pre><p>
Nathann
</p>
TicketSimonKingSun, 29 Dec 2013 13:27:00 GMT
https://trac.sagemath.org/ticket/15278#comment:75
https://trac.sagemath.org/ticket/15278#comment:75
<p>
Meanwhile I see at what point the copy is taken: It is
</p>
<div class="wiki-code"><div class="code"><pre> <span class="k">def</span> <span class="nf">transitive_reduction</span><span class="p">(</span><span class="bp">self</span><span class="p">):</span>
<span class="sd">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
"""</span>
<span class="kn">from</span> <span class="nn">copy</span> <span class="kn">import</span> copy
<span class="kn">from</span> <span class="nn">sage.rings.infinity</span> <span class="kn">import</span> Infinity
G <span class="o">=</span> copy<span class="p">(</span><span class="bp">self</span><span class="p">)</span>
<span class="k">for</span> e <span class="ow">in</span> <span class="bp">self</span><span class="o">.</span>edge_iterator<span class="p">():</span>
<span class="c"># Try deleting the edge, see if we still have a path</span>
<span class="c"># between the vertices.</span>
G<span class="o">.</span>delete_edge<span class="p">(</span>e<span class="p">)</span>
<span class="k">if</span> G<span class="o">.</span>distance<span class="p">(</span>e<span class="p">[</span><span class="mi">0</span><span class="p">],</span>e<span class="p">[</span><span class="mi">1</span><span class="p">])</span><span class="o">==</span>Infinity<span class="p">:</span>
<span class="c"># oops, we shouldn't have deleted it</span>
G<span class="o">.</span>add_edge<span class="p">(</span>e<span class="p">)</span>
<span class="k">return</span> G
</pre></div></div><p>
Hence, it seems that we indeed want a mutable copy here. And perhaps it isn't <em>their</em> mess after all, as this method is broken for all truely immutable graphs.
</p>
TicketncohenSun, 29 Dec 2013 13:31:50 GMT
https://trac.sagemath.org/ticket/15278#comment:76
https://trac.sagemath.org/ticket/15278#comment:76
<p>
Ahahaha. Well, given that there are no immutable graphs in Sage at the moment, this function can't really be said to be broken <code>:-D</code>
</p>
<p>
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 <code>:-P</code>
</p>
<p>
This copy has to be flagged with "immutable=False" (but that's only available in my patch) or with a specific data structure.
</p>
<p>
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.
</p>
<p>
Aaaaaaaand now I have to go eat <code>T_T</code>
</p>
<p>
Nathann
</p>
TicketncohenSun, 29 Dec 2013 13:59:49 GMT
https://trac.sagemath.org/ticket/15278#comment:77
https://trac.sagemath.org/ticket/15278#comment:77
<p>
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 <code>;-)</code>
</p>
<p>
Nathann
</p>
TicketgitSun, 29 Dec 2013 15:03:42 GMTcommit changed
https://trac.sagemath.org/ticket/15278#comment:78
https://trac.sagemath.org/ticket/15278#comment:78
<ul>
<li><strong>commit</strong>
changed from <em>fcf9e3018d5e87f49e1f3f3d68ad4cc49382c0b9</em> to <em>2525d22a6b3a687bf932c2afaa8297e40c7af3d8</em>
</li>
</ul>
<p>
Branch pushed to git repo; I updated commit sha1. New commits:
</p>
<table class="wiki">
<tr><td><a class="ext-link" href="http://git.sagemath.org/sage.git/commit/?id=2525d22"><span class="icon"></span>2525d22</a></td><td><code>Trac 15278: Fix syntax error in doc test</code>
</td></tr></table>
TicketSimonKingSun, 29 Dec 2013 15:12:24 GMTstatus changed
https://trac.sagemath.org/ticket/15278#comment:79
https://trac.sagemath.org/ticket/15278#comment:79
<ul>
<li><strong>status</strong>
changed from <em>needs_work</em> to <em>needs_review</em>
</li>
</ul>
<p>
Fixed the syntax error, and checked that the failing test passes.
</p>
<p>
So, with the last two commits, we counter-hacked the hack with the <code>._immutable</code> attribute. Next step will be to make <a class="closed ticket" href="https://trac.sagemath.org/ticket/15603" title="enhancement: "immutable=True" for Graph/Digraph __init__ and copy() (closed: fixed)">#15603</a> ready (can you merge the missing commits from here into <a class="closed ticket" href="https://trac.sagemath.org/ticket/15603" title="enhancement: "immutable=True" for Graph/Digraph __init__ and copy() (closed: fixed)">#15603</a>, please?), and in a third step, we will properly remove the hack and perhaps the counter-hack too.
</p>
TicketncohenSun, 29 Dec 2013 15:21:28 GMTstatus changed
https://trac.sagemath.org/ticket/15278#comment:80
https://trac.sagemath.org/ticket/15278#comment:80
<ul>
<li><strong>status</strong>
changed from <em>needs_review</em> to <em>positive_review</em>
</li>
</ul>
<blockquote class="citation">
<p>
Fixed the syntax error, and checked that the failing test passes.
</p>
</blockquote>
<p>
Yep. And they just passed on my computer too in graph/ combinat/ and misc/. Soooo <code>positive_review</code> again !
</p>
<blockquote class="citation">
<p>
So, with the last two commits, we counter-hacked the hack with the <code>._immutable</code> attribute.
</p>
</blockquote>
<p>
Nod.
</p>
<blockquote class="citation">
<p>
Next step will be to make <a class="closed ticket" href="https://trac.sagemath.org/ticket/15603" title="enhancement: "immutable=True" for Graph/Digraph __init__ and copy() (closed: fixed)">#15603</a> ready (can you merge the missing commits from here into <a class="closed ticket" href="https://trac.sagemath.org/ticket/15603" title="enhancement: "immutable=True" for Graph/Digraph __init__ and copy() (closed: fixed)">#15603</a>, please?)
</p>
</blockquote>
<p>
Nod. Plus I will probably have some conflicts because of what I do in <code>.__copy__</code>. Shouldn't be very long.
</p>
<blockquote class="citation">
<p>
and in a third step, we will properly remove the hack and perhaps the counter-hack too.
</p>
</blockquote>
<p>
Nod.
</p>
<p>
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 <code>;-)</code>
</p>
<p>
Nathann
</p>
<p>
P.S. : it takes a lifetime to add a comment on a ticket.
</p>
TicketSimonKingWed, 01 Jan 2014 18:43:49 GMT
https://trac.sagemath.org/ticket/15278#comment:81
https://trac.sagemath.org/ticket/15278#comment:81
<p>
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?
</p>
TicketncohenWed, 01 Jan 2014 18:51:24 GMT
https://trac.sagemath.org/ticket/15278#comment:82
https://trac.sagemath.org/ticket/15278#comment:82
<p>
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.
</p>
<p>
And this patch will be in <code>needs_review</code> 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 <code>:-P</code>
</p>
<p>
Nathann
</p>
TicketSimonKingWed, 01 Jan 2014 20:00:56 GMT
https://trac.sagemath.org/ticket/15278#comment:83
https://trac.sagemath.org/ticket/15278#comment:83
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/15278#comment:82" title="Comment 82">ncohen</a>:
</p>
<blockquote class="citation">
<p>
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.
</p>
</blockquote>
<p>
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?
</p>
TicketncohenThu, 02 Jan 2014 10:31:32 GMT
https://trac.sagemath.org/ticket/15278#comment:84
https://trac.sagemath.org/ticket/15278#comment:84
<p>
Ahahahah... Okay, if you think you would sleep better this way, no problem. I just created ticket <a class="closed ticket" href="https://trac.sagemath.org/ticket/15619" title="enhancement: Pickling of immutable graphs (closed: fixed)">#15619</a> for that, with part of the patch I was writing for the immutable backend of posets.
</p>
<p>
Nathann
</p>
TicketvbraunSun, 05 Jan 2014 02:56:56 GMTstatus changed; resolution set
https://trac.sagemath.org/ticket/15278#comment:85
https://trac.sagemath.org/ticket/15278#comment:85
<ul>
<li><strong>status</strong>
changed from <em>positive_review</em> to <em>closed</em>
</li>
<li><strong>resolution</strong>
set to <em>fixed</em>
</li>
</ul>
Ticket