Sage: Ticket #15619: Pickling of immutable graphs
https://trac.sagemath.org/ticket/15619
<p>
Before
</p>
<pre class="wiki">sage: g=Graph(graphs.PetersenGraph(),immutable=True)
sage: g == loads(dumps(g))
...
TypeError: __cinit__() takes exactly 1 positional argument (0 given)
</pre><p>
After
</p>
<pre class="wiki">sage: g=Graph(graphs.PetersenGraph(),immutable=True)
sage: g == loads(dumps(g))
True
</pre>en-usSagehttps://trac.sagemath.org/chrome/site/logo_sagemath_trac.png
https://trac.sagemath.org/ticket/15619
Trac 1.1.6ncohenThu, 02 Jan 2014 10:34:21 GMTstatus changed; branch set
https://trac.sagemath.org/ticket/15619#comment:1
https://trac.sagemath.org/ticket/15619#comment:1
<ul>
<li><strong>status</strong>
changed from <em>new</em> to <em>needs_review</em>
</li>
<li><strong>branch</strong>
set to <em>u/ncohen/15619</em>
</li>
</ul>
TicketgitThu, 02 Jan 2014 10:36:56 GMTcommit set
https://trac.sagemath.org/ticket/15619#comment:2
https://trac.sagemath.org/ticket/15619#comment:2
<ul>
<li><strong>commit</strong>
set to <em>02293487b6268d373896d4c18b0a41a54ef36acd</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=0229348"><span class="icon"></span>0229348</a></td><td><code>trac #15619: Pickling of immutable graphs</code>
</td></tr><tr><td><a class="ext-link" href="http://git.sagemath.org/sage.git/commit/?id=7860f39"><span class="icon"></span>7860f39</a></td><td><code>trac #15603: "immutable=True" for Graph/Digraph __init__ and copy()</code>
</td></tr><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><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><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><tr><td><a class="ext-link" href="http://git.sagemath.org/sage.git/commit/?id=2fc8a77"><span class="icon"></span>2fc8a77</a></td><td><code>Make digraphs using the static backend immutable and hashable</code>
</td></tr><tr><td><a class="ext-link" href="http://git.sagemath.org/sage.git/commit/?id=07bad46"><span class="icon"></span>07bad46</a></td><td><code>Merge branch 'u/ncohen/15491' of git://trac.sagemath.org/sage into ticket/15278</code>
</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><code>Merge branch 'master' into ticket/15278</code>
</td></tr><tr><td><a class="ext-link" href="http://git.sagemath.org/sage.git/commit/?id=c774057"><span class="icon"></span>c774057</a></td><td><code>Prepare hash and copy for immutable graphs. Let .weighted() respect mutability.</code>
</td></tr></table>
TicketSimonKingThu, 02 Jan 2014 10:56:12 GMT
https://trac.sagemath.org/ticket/15619#comment:3
https://trac.sagemath.org/ticket/15619#comment:3
<p>
I am not convinced that creating a graph in order to pickle a backend is the best possible solution. So, I'll do some further experiments with a reduce method for graphs---no need for you to worry about it at this point...
</p>
TicketncohenThu, 02 Jan 2014 10:59:03 GMT
https://trac.sagemath.org/ticket/15619#comment:4
https://trac.sagemath.org/ticket/15619#comment:4
<p>
Of course not, it is indeed ugly code, and my point is that I write ugly code because I am forced by a machine to write code for which I have no personal use <code>:-P</code>
</p>
<p>
Yet it passes those stupid tests, and for this I am grateful. Right now I am fighting with "Poset.promotion", and I have noooooooo idea on earth of where the broken doctests are coming from <code>O_o</code>
</p>
<p>
Nathann
</p>
TicketncohenThu, 02 Jan 2014 11:01:53 GMT
https://trac.sagemath.org/ticket/15619#comment:5
https://trac.sagemath.org/ticket/15619#comment:5
<p>
It does minimize the amount of code necessary for such a function, though. And clear code is good by itself <code>:-P</code>
</p>
<p>
Nathann
</p>
TicketSimonKingThu, 02 Jan 2014 11:25:02 GMT
https://trac.sagemath.org/ticket/15619#comment:6
https://trac.sagemath.org/ticket/15619#comment:6
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/15619#comment:4" title="Comment 4">ncohen</a>:
</p>
<blockquote class="citation">
<p>
Of course not, it is indeed ugly code, and my point is that I write ugly code because I am forced by a machine to write code for which I have no personal use <code>:-P</code>
</p>
</blockquote>
<p>
Sage is a community project after all.
</p>
TicketncohenThu, 02 Jan 2014 11:33:10 GMT
https://trac.sagemath.org/ticket/15619#comment:7
https://trac.sagemath.org/ticket/15619#comment:7
<p>
I don't see the relationship <code>O_o</code>
</p>
TicketSimonKingThu, 02 Jan 2014 11:33:50 GMT
https://trac.sagemath.org/ticket/15619#comment:8
https://trac.sagemath.org/ticket/15619#comment:8
<p>
What do you think about the following way to pickle generic graphs?
</p>
<pre class="wiki"> def __reduce__(self):
# copy the dict
D = dict(self.__dict__.iteritems())
# remove something that may not be picklable
try:
del D['_backend']
except KeyError:
pass
return type(self), (self.edges(),), D
</pre><p>
Is this elegant enough for you? Additional bait: We may even remove the existing <code>__reduce__</code> methods of the other backends <code>;-)</code>
</p>
TicketSimonKingThu, 02 Jan 2014 11:35:10 GMT
https://trac.sagemath.org/ticket/15619#comment:9
https://trac.sagemath.org/ticket/15619#comment:9
<p>
PS: With the above <code>__reduce__</code> method put into sage.graphs.generic_graph.py, one has
</p>
<pre class="wiki">sage: G = graphs.PetersenGraph()
sage: g = G.copy(data_structure='static_sparse')
sage: loads(dumps(g))
Graph on 10 vertices
sage: g == _
True
</pre>
TicketSimonKingThu, 02 Jan 2014 11:42:31 GMT
https://trac.sagemath.org/ticket/15619#comment:10
https://trac.sagemath.org/ticket/15619#comment:10
<p>
Some little timing:
</p>
<p>
Your way of pickling:
</p>
<pre class="wiki">sage: G = graphs.PetersenGraph()
sage: g = G.copy(data_structure='static_sparse')
sage: %timeit h = loads(dumps(g))
1000 loops, best of 3: 1.11 ms per loop
</pre><p>
My way of pickling:
</p>
<pre class="wiki">sage: G = graphs.PetersenGraph()
sage: g = G.copy(data_structure='static_sparse')
sage: %timeit h = loads(dumps(g))
1000 loops, best of 3: 493 us per loop
</pre><p>
<code>:-P</code>
</p>
TicketSimonKingThu, 02 Jan 2014 11:47:31 GMT
https://trac.sagemath.org/ticket/15619#comment:11
https://trac.sagemath.org/ticket/15619#comment:11
<p>
On the other hand, I think I did something severely wrong:
</p>
<pre class="wiki">sage: h = loads(dumps(g))
sage: type(h._backend)
<class 'sage.graphs.base.sparse_graph.SparseGraphBackend'>
</pre><p>
Bad. So, it doesn't work in the way I thought...
</p>
TicketSimonKingThu, 02 Jan 2014 12:22:16 GMT
https://trac.sagemath.org/ticket/15619#comment:12
https://trac.sagemath.org/ticket/15619#comment:12
<p>
Would it be possible to let the static graph backend <code>__init__</code> accept a list of edges rather than a graph? Then, your <code>__reduce__</code> method could be simplified (and actually it seems odd that the creation of a graph *backend* needs a graph!).
</p>
TicketSimonKingThu, 02 Jan 2014 12:36:59 GMT
https://trac.sagemath.org/ticket/15619#comment:13
https://trac.sagemath.org/ticket/15619#comment:13
<p>
Hm. I tried to understand what happens when one creates a static sparse backend.
</p>
<p>
I always thought that one needs a backend to implement a graph. But in fact <code>__init__</code> and <code>__cinit__</code> and <code>init_short_digraph</code> (which are all involved in the creation of a static sparse backend) rely on the input being a graph. <code>:-/</code>
</p>
TicketncohenThu, 02 Jan 2014 12:57:53 GMT
https://trac.sagemath.org/ticket/15619#comment:14
https://trac.sagemath.org/ticket/15619#comment:14
<p>
Well, that can be changed too at some point if it is really needed (I would personally hate to change all this code just because the guy who implemented <a class="missing wiki">TestSuite?</a> decide for everybody that all the graphs classes HE tested should be picklable), but building a graph is not such a trivial matter. Because you have labels of not, because you have multiple edges or not, because the labels can be integers, have labels, because you can have loops, because they can be oriented or not.
</p>
<p>
I mean, that's actually a lot of stuff, and it's not funny to implement it so many times in the code. It's already *VERY* messy in the <code>Graph</code>/<code>DiGraph</code> constructors.
</p>
<p>
Honestly, I don't think pickling really needs any amount of efficient code. So as we are just implementing it to make the testsuite happy, and unless you want to mess with all this code just because of that, let's use it. It's short and it works. It's bad code of course, because pickling is bad work. It's a generic way to store data, that should work regardless of what the data is. It's like XML. Saving data is not something that should be done without *knowing* what the data is. If you want to write generic code for this, it will end up being bad code.
</p>
<p>
Anyway. The only problem I would like to see solved is to have Posets use a static data structure. That would make them both faster and lighter. And I think something should be done about the time complexity of the <code>Graph</code>/<code>DiGraph</code> constructor too.
</p>
<p>
Let's move on. Can you help me with this promotion bug ? I have no idea of how it should be solved, and it seems to be the last step before having the Posets use a static backend.
</p>
<p>
Nathann
</p>
TicketSimonKingThu, 02 Jan 2014 13:15:27 GMT
https://trac.sagemath.org/ticket/15619#comment:15
https://trac.sagemath.org/ticket/15619#comment:15
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/15619#comment:14" title="Comment 14">ncohen</a>:
</p>
<blockquote class="citation">
<p>
but building a graph is not such a trivial matter. Because you have labels of not, because you have multiple edges or not, because the labels can be integers, have labels, because you can have loops, because they can be oriented or not.
</p>
</blockquote>
<p>
Right. This is in fact a strong argument for implementing the pickling in the way you did. All these optional arguments of <code>(Di)Graph.__init__</code> are a mess.
</p>
<blockquote class="citation">
<p>
Honestly, I don't think pickling really needs any amount of efficient code.
</p>
</blockquote>
<p>
That's a valid point, too. Efficient pickling mainly plays a role if *copying* is implemented by pickling, since this may happen interactively and frequently. But we have a separate and hopefully efficient implementation of <code>__copy__</code>, and thus <code>__reduce__</code> is really only involved when people want to store a poset (and hence, an immutable graph, and thus, a static sparse backend) into a file. So, spending some milli seconds seems acceptable.
</p>
<blockquote class="citation">
<p>
So as we are just implementing it to make the testsuite happy, and unless you want to mess with all this code just because of that, let's use it. It's short and it works. It's bad code of course, because pickling is bad work. It's a generic way to store data, that should work regardless of what the data is. It's like XML. Saving data is not something that should be done without *knowing* what the data is.
</p>
</blockquote>
<p>
Careful! You are just arguing that the person who knows the data structure best (i.e., you) is responsible for making pickling work <code>:-)</code>
</p>
<blockquote class="citation">
<p>
If you want to write generic code for this, it will end up being bad code.
</p>
</blockquote>
<p>
Correct. Sometimes generic code just works, but in some cases <code>__reduce__</code> needs to be provided. Wonderful that Python is object oriented and lets us do such things...
</p>
<blockquote class="citation">
<p>
Anyway. The only problem I would like to see solved is to have Posets use a static data structure. That would make them both faster and lighter. And I think something should be done about the time complexity of the <code>Graph</code>/<code>DiGraph</code> constructor too.
</p>
</blockquote>
<p>
Here or on a different ticket?
</p>
<blockquote class="citation">
<p>
Let's move on. Can you help me with this promotion bug ?
</p>
</blockquote>
<p>
OK. So, I'll review your pickling approach, and in the meantime you point me to your branch for "making posets use immutable graphs", so that I can test the promotion bug.
</p>
TicketSimonKingThu, 02 Jan 2014 13:46:24 GMT
https://trac.sagemath.org/ticket/15619#comment:16
https://trac.sagemath.org/ticket/15619#comment:16
<p>
Just for completeness: It would also be possible to say "graphs do not want being pickled", which would force all structures that use graphs to implement their own pickling by storing the defining data of the graphs they use, rather than storing these graphs directly.
</p>
<p>
Hence, one could provide Poset with a custom <code>__reduce__</code> method that just stores the list of edges of the graph, rather than the graph itself. However, I think in the long run it would be better if graphs knew how to save themselves.
</p>
TicketncohenThu, 02 Jan 2014 13:54:06 GMT
https://trac.sagemath.org/ticket/15619#comment:17
https://trac.sagemath.org/ticket/15619#comment:17
<p>
Well. So what do we do with this commit ? Is it good for you ? And more importantly, what do we do with this bug in <code>linear_extensions.py</code> in the u/ncohen/tmp branch ? <code>:-/</code>
</p>
<p>
Nathann
</p>
TicketSimonKingThu, 02 Jan 2014 19:17:00 GMT
https://trac.sagemath.org/ticket/15619#comment:18
https://trac.sagemath.org/ticket/15619#comment:18
<p>
This one seems to be the underlying reason for the problems with posets:
</p>
<pre class="wiki">sage: uc = [[2,3], [], [1], [1], [1], [3,4]]
sage: D = DiGraph(dict([[i,uc[i]] for i in range(len(uc))]), data_structure="static_sparse")
sage: loads(dumps(D)) == D
False
</pre>
TicketSimonKingThu, 02 Jan 2014 19:18:14 GMT
https://trac.sagemath.org/ticket/15619#comment:19
https://trac.sagemath.org/ticket/15619#comment:19
<p>
The pickling result is in fact seriously wrong:
</p>
<pre class="wiki">sage: d = loads(dumps(D))
sage: d.edges()
[(0, 2, None), (0, 3, None)]
sage: D.edges()
[(0, 2, None),
(0, 3, None),
(2, 1, None),
(3, 1, None),
(4, 1, None),
(5, 3, None),
(5, 4, None)]
</pre>
TicketSimonKingThu, 02 Jan 2014 19:35:51 GMT
https://trac.sagemath.org/ticket/15619#comment:20
https://trac.sagemath.org/ticket/15619#comment:20
<p>
Indeed the error occurs when constructing the graph used to pickle the graph backend:
</p>
<pre class="wiki">sage: constructor = DiGraph
sage: self = D._backend
sage: G.add_vertices(self.iterator_verts(None))
sage: G
Digraph on 6 vertices
sage: G.vertices()
[0, 1, 2, 3, 4, 5]
sage: D.vertices()
[0, 1, 2, 3, 4, 5]
sage: G.add_edges(list(self.iterator_edges(self.iterator_verts(None),1)))
sage: G.edges()
[(0, 2, None), (0, 3, None)]
</pre><p>
Bug in <code>iterator_edges</code>? Then you should thank the guy who invented the <code>TestSuite</code>, since it helped you uncover a bug in a method you probably care about (namely iteration over edges).
</p>
TicketSimonKingThu, 02 Jan 2014 19:40:03 GMT
https://trac.sagemath.org/ticket/15619#comment:21
https://trac.sagemath.org/ticket/15619#comment:21
<p>
In pure form, the failing example is
</p>
<pre class="wiki">sage: uc = [[2,3], [], [1], [1], [1], [3,4]]
sage: D = DiGraph(dict([[i,uc[i]] for i in range(len(uc))]), data_structure="static_sparse")
sage: list(D._backend.iterator_edges(D.vertices(), True))
[(0, 2, None), (0, 3, None)]
</pre>
TicketncohenThu, 02 Jan 2014 19:49:16 GMT
https://trac.sagemath.org/ticket/15619#comment:22
https://trac.sagemath.org/ticket/15619#comment:22
<p>
Ahahah. You are oversimplying things. It's good that we found a bug. But that does not justify all at once the principle of testsuites and its use.
</p>
<p>
I'm trying to fix that. It's weird, if you use <code>iterator_out_edges</code> instead there is no problem anymore <code>O_o</code>
</p>
<p>
Nathann
</p>
TicketncohenThu, 02 Jan 2014 19:51:42 GMT
https://trac.sagemath.org/ticket/15619#comment:23
https://trac.sagemath.org/ticket/15619#comment:23
<p>
(by the way, <code>D.show</code> fails <code>:-P</code>)
</p>
TicketncohenThu, 02 Jan 2014 19:53:30 GMT
https://trac.sagemath.org/ticket/15619#comment:24
https://trac.sagemath.org/ticket/15619#comment:24
<p>
Oh. Well, it is not really a bug. It's just that <code>iterator_edges</code> is not meant for digraphs <code>O_o</code>
</p>
<p>
Nathann
</p>
TicketncohenThu, 02 Jan 2014 19:54:33 GMT
https://trac.sagemath.org/ticket/15619#comment:25
https://trac.sagemath.org/ticket/15619#comment:25
<p>
Did you find a place in the code that call the backend's <code>iterator_edges</code> functions ?
</p>
<p>
Nathann
</p>
TicketncohenThu, 02 Jan 2014 19:56:30 GMT
https://trac.sagemath.org/ticket/15619#comment:26
https://trac.sagemath.org/ticket/15619#comment:26
<p>
I mean... For a <a class="missing wiki">DiGraph?</a>. I should probably add an exception there when this function is used with a digraph, but it is clearly meant for undirected graphs only.
</p>
<pre class="wiki"> if j < i and j in vertices:
continue
</pre><p>
It only outputs an edge once <code>:-P</code>
</p>
<p>
Nathann
</p>
TicketncohenThu, 02 Jan 2014 20:05:01 GMT
https://trac.sagemath.org/ticket/15619#comment:27
https://trac.sagemath.org/ticket/15619#comment:27
<p>
I just added an exception to this method when it is used on undirected graphs, and it looks like the only code that calls this method on undirected graphs is .... the hash function <code>:-PPPPPPPPP</code>
</p>
<p>
Nathann
</p>
TicketSimonKingThu, 02 Jan 2014 20:05:48 GMT
https://trac.sagemath.org/ticket/15619#comment:28
https://trac.sagemath.org/ticket/15619#comment:28
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/15619#comment:24" title="Comment 24">ncohen</a>:
</p>
<blockquote class="citation">
<p>
Oh. Well, it is not really a bug. It's just that <code>iterator_edges</code> is not meant for digraphs <code>O_o</code>
</p>
</blockquote>
<p>
Is this documented? If it *is* documented, then it is not a bug. But then, its use in <code>__reduce__</code> should be replaced by something that works.
</p>
TicketncohenThu, 02 Jan 2014 20:06:14 GMT
https://trac.sagemath.org/ticket/15619#comment:29
https://trac.sagemath.org/ticket/15619#comment:29
<p>
What I just said doesn't make sense... <code>T_T</code>
</p>
<p>
Still, the only exceptions I see happen with hashs...
</p>
<p>
Nathann
</p>
TicketSimonKingThu, 02 Jan 2014 20:07:10 GMT
https://trac.sagemath.org/ticket/15619#comment:30
https://trac.sagemath.org/ticket/15619#comment:30
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/15619#comment:27" title="Comment 27">ncohen</a>:
</p>
<blockquote class="citation">
<p>
I just added an exception to this method when it is used on undirected graphs, and it looks like the only code that calls this method on undirected graphs is .... the hash function <code>:-PPPPPPPPP</code>
</p>
</blockquote>
<p>
Ahm... Does it *work* for undirected graphs or does it *not* work for undirected graphs? In your previous post, I understood that it is wrong to have it on a digraph.
</p>
TicketncohenThu, 02 Jan 2014 20:08:34 GMT
https://trac.sagemath.org/ticket/15619#comment:31
https://trac.sagemath.org/ticket/15619#comment:31
<p>
It is not meant to be used on digraphs. It works on graphs : it just returns an edge i,j if i<j. Otherwise it is skipped. If we don't do that every undirected edge is returned twice. It's clearly meant for undirected graphs <code>O_o</code>
</p>
<p>
Nathann
</p>
TicketSimonKingThu, 02 Jan 2014 20:11:30 GMT
https://trac.sagemath.org/ticket/15619#comment:32
https://trac.sagemath.org/ticket/15619#comment:32
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/15619#comment:31" title="Comment 31">ncohen</a>:
</p>
<blockquote class="citation">
<p>
It is not meant to be used on digraphs. It works on graphs : it just returns an edge i,j if i<j. Otherwise it is skipped. If we don't do that every undirected edge is returned twice. It's clearly meant for undirected graphs <code>O_o</code>
</p>
</blockquote>
<p>
Would it be difficult to make it work on digraphs? After all, the backend knows whether it is directed, and thus one could make it so that the "i<j" test is only applied in the undirected case.
</p>
TicketncohenThu, 02 Jan 2014 20:12:27 GMT
https://trac.sagemath.org/ticket/15619#comment:33
https://trac.sagemath.org/ticket/15619#comment:33
<p>
Okay I'm stupid. I hadn't noticed I used this in <code>__reduce__</code>. Totally my mystake. I'm going to fix this and see how it works out. Should make a hell of a difference.
</p>
<p>
Nathann
</p>
TicketSimonKingThu, 02 Jan 2014 20:15:58 GMT
https://trac.sagemath.org/ticket/15619#comment:34
https://trac.sagemath.org/ticket/15619#comment:34
<p>
Wait a minute. I am about to push a fix to iterator_edges, that makes it work on digraphs and would thus also fix the pickling problem.
</p>
TicketncohenThu, 02 Jan 2014 20:16:57 GMT
https://trac.sagemath.org/ticket/15619#comment:35
https://trac.sagemath.org/ticket/15619#comment:35
<p>
No, please. We need to discuss what the function should return before anything. I don't find any good answer for that. Short of a thing so ugly it should not be implemented <code>:-P</code>
</p>
<p>
Nathann
</p>
TicketncohenThu, 02 Jan 2014 20:21:01 GMT
https://trac.sagemath.org/ticket/15619#comment:36
https://trac.sagemath.org/ticket/15619#comment:36
<p>
Okay, replacing <code>iterator_edges</code> by <code>iterator_out_edges</code> in the <code>__reduce__</code> function of the static sparse backend fixes the pickling-related problems. Some other weird bugs remain in the poset/ folder though <code>T_T</code>
</p>
<p>
Nathann
</p>
TicketSimonKingThu, 02 Jan 2014 20:24:04 GMT
https://trac.sagemath.org/ticket/15619#comment:37
https://trac.sagemath.org/ticket/15619#comment:37
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/15619#comment:35" title="Comment 35">ncohen</a>:
</p>
<blockquote class="citation">
<p>
No, please. We need to discuss what the function should return before anything. I don't find any good answer for that. Short of a thing so ugly it should not be implemented <code>:-P</code>
</p>
</blockquote>
<p>
I was in the process of pushing, now I have interrupted it. I don't know if this has worked or if my commit has already been posted.
</p>
<p>
But why would you hesitate to make <code>iterator_edges</code> work on digraphs?
</p>
TicketncohenThu, 02 Jan 2014 20:25:11 GMT
https://trac.sagemath.org/ticket/15619#comment:38
https://trac.sagemath.org/ticket/15619#comment:38
<p>
It looks like it hasn't been posted.
</p>
<p>
I hesitate because I don't think there is a good definition of what it should output. Let's try it this way : tell me what you wanted it to output and I will give you the graph which I think make it a bad definition. If I find no graph then we will implement it <code>:-P</code>
</p>
<p>
Nathann
</p>
TicketSimonKingThu, 02 Jan 2014 20:25:45 GMT
https://trac.sagemath.org/ticket/15619#comment:39
https://trac.sagemath.org/ticket/15619#comment:39
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/15619#comment:35" title="Comment 35">ncohen</a>:
</p>
<blockquote class="citation">
<p>
No, please. We need to discuss what the function should return before anything. I don't find any good answer for that.
</p>
</blockquote>
<p>
Well, of course it should return an iterator over the edges of the digraph. What else should it do?
</p>
TicketgitThu, 02 Jan 2014 20:26:15 GMTcommit changed
https://trac.sagemath.org/ticket/15619#comment:40
https://trac.sagemath.org/ticket/15619#comment:40
<ul>
<li><strong>commit</strong>
changed from <em>02293487b6268d373896d4c18b0a41a54ef36acd</em> to <em>2eb2c95a4512592f452a2046d98a22c9ec171e8d</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=2eb2c95"><span class="icon"></span>2eb2c95</a></td><td><code>trac #15619: bug in the former definition; exception to avoid it in the future</code>
</td></tr></table>
TicketncohenThu, 02 Jan 2014 20:26:40 GMT
https://trac.sagemath.org/ticket/15619#comment:41
https://trac.sagemath.org/ticket/15619#comment:41
<blockquote class="citation">
<p>
Well, of course it should return an iterator over the edges of the digraph. What else should it do?
</p>
</blockquote>
<p>
<code>O_o</code>
</p>
<p>
What about the <code>vertices</code> argument ?
</p>
<p>
Nathann
</p>
<hr />
<p>
New commits:
</p>
<table class="wiki">
<tr><td><a class="ext-link" href="http://git.sagemath.org/sage.git/commit/?id=2eb2c95"><span class="icon"></span>2eb2c95</a></td><td><code>trac #15619: bug in the former definition; exception to avoid it in the future</code>
</td></tr></table>
TicketSimonKingThu, 02 Jan 2014 20:27:21 GMT
https://trac.sagemath.org/ticket/15619#comment:42
https://trac.sagemath.org/ticket/15619#comment:42
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/15619#comment:38" title="Comment 38">ncohen</a>:
</p>
<blockquote class="citation">
<p>
It looks like it hasn't been posted.
</p>
<p>
I hesitate because I don't think there is a good definition of what it should output. Let's try it this way : tell me what you wanted it to output
</p>
</blockquote>
<p>
For example (this is the doctest of my not-posted commit):
</p>
<pre class="wiki">sage: uc = [[2,3], [], [1], [1], [1], [3,4]]
sage: D = DiGraph(dict([[i,uc[i]] for i in range(len(uc))]))
sage: G = Graph(dict([[i,uc[i]] for i in range(len(uc))]))
sage: from sage.graphs.base.static_sparse_backend import StaticSparseBackend
sage: d = StaticSparseBackend(D)
sage: g = StaticSparseBackend(G)
sage: list(d.iterator_edges(d.iterator_verts(None), False))
[(0, 2), (0, 3), (2, 1), (3, 1), (4, 1), (5, 3), (5, 4)]
sage: list(g.iterator_edges(g.iterator_verts(None), False))
[(0, 2), (0, 3), (1, 2), (1, 3), (1, 4), (3, 5), (4, 5)]
</pre>
TicketSimonKingThu, 02 Jan 2014 20:28:07 GMT
https://trac.sagemath.org/ticket/15619#comment:43
https://trac.sagemath.org/ticket/15619#comment:43
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/15619#comment:41" title="Comment 41">ncohen</a>:
</p>
<blockquote class="citation">
<p>
What about the <code>vertices</code> argument ?
</p>
</blockquote>
<p>
Ahaha, you mean whether it is supposed to be the in or out vertices of the edges being returned?
</p>
TicketncohenThu, 02 Jan 2014 20:30:23 GMT
https://trac.sagemath.org/ticket/15619#comment:44
https://trac.sagemath.org/ticket/15619#comment:44
<p>
Yep. You can make it the in-edges, or the out-edges. And both definitions are bad. Or you can make it the sum of both. But then you would return twice the edges that links two vertices of your set <code>vertices</code>. Unless you look for them and remove them before returning them. And this I think is ugly. What do you think ? <code>:-P</code>
</p>
<p>
By the way the commit I just uploaded does not work. Sorry for that. I'll fix it in a second.
</p>
<p>
Nathann
</p>
TicketSimonKingThu, 02 Jan 2014 20:33:29 GMT
https://trac.sagemath.org/ticket/15619#comment:45
https://trac.sagemath.org/ticket/15619#comment:45
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/15619#comment:44" title="Comment 44">ncohen</a>:
</p>
<blockquote class="citation">
<p>
Yep. You can make it the in-edges, or the out-edges. And both definitions are bad. Or you can
make it the sum of both. But then you would return twice the edges that links two vertices of
your set <code>vertices</code>. Unless you look for them and remove them before returning them. And this I
think is ugly. What do you think ?
</p>
</blockquote>
<p>
Agreed.
</p>
<blockquote class="citation">
<p>
By the way the commit I just uploaded does not work. Sorry for that. I'll fix it in a second.
</p>
</blockquote>
<p>
Agreed (it is self._directed, not self.directed).
</p>
TicketncohenThu, 02 Jan 2014 20:35:43 GMT
https://trac.sagemath.org/ticket/15619#comment:46
https://trac.sagemath.org/ticket/15619#comment:46
<p>
Okayokay, I just fixed this <code>_directed</code>, what's left seems to work.
</p>
<p>
The funny thing is that the only code that actually tests this pickling stuff is the poset code... So this can only be tested seriously with static graph backends for posets <code>^^;</code>
</p>
<p>
Nathann
</p>
TicketncohenThu, 02 Jan 2014 20:40:05 GMTcommit deleted
https://trac.sagemath.org/ticket/15619#comment:47
https://trac.sagemath.org/ticket/15619#comment:47
<ul>
<li><strong>commit</strong>
<em>2eb2c95a4512592f452a2046d98a22c9ec171e8d</em> deleted
</li>
</ul>
<p>
Okay, I just updated it. It worked with the other flag because I added this variable while working on the poset stuff. That's part of what I will have to clean before sending this other patch <code>^^;</code>
</p>
<p>
Anyway, this one looks good.
</p>
<p>
Nathann
</p>
TicketgitThu, 02 Jan 2014 20:40:28 GMTcommit set
https://trac.sagemath.org/ticket/15619#comment:48
https://trac.sagemath.org/ticket/15619#comment:48
<ul>
<li><strong>commit</strong>
set to <em>c4411781fa8a64d3e89568069ad85caab47b81d2</em>
</li>
</ul>
<p>
Branch pushed to git repo; I updated commit sha1. Last 10 new commits:
</p>
<table class="wiki">
<tr><td><a class="ext-link" href="http://git.sagemath.org/sage.git/commit/?id=c441178"><span class="icon"></span>c441178</a></td><td><code>trac #15619: bug in the former definition; exception to avoid it in the future</code>
</td></tr><tr><td><a class="ext-link" href="http://git.sagemath.org/sage.git/commit/?id=0229348"><span class="icon"></span>0229348</a></td><td><code>trac #15619: Pickling of immutable graphs</code>
</td></tr><tr><td><a class="ext-link" href="http://git.sagemath.org/sage.git/commit/?id=7860f39"><span class="icon"></span>7860f39</a></td><td><code>trac #15603: "immutable=True" for Graph/Digraph __init__ and copy()</code>
</td></tr><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><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><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><tr><td><a class="ext-link" href="http://git.sagemath.org/sage.git/commit/?id=2fc8a77"><span class="icon"></span>2fc8a77</a></td><td><code>Make digraphs using the static backend immutable and hashable</code>
</td></tr><tr><td><a class="ext-link" href="http://git.sagemath.org/sage.git/commit/?id=07bad46"><span class="icon"></span>07bad46</a></td><td><code>Merge branch 'u/ncohen/15491' of git://trac.sagemath.org/sage into ticket/15278</code>
</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><code>Merge branch 'master' into ticket/15278</code>
</td></tr></table>
TicketSimonKingThu, 02 Jan 2014 20:41:25 GMT
https://trac.sagemath.org/ticket/15619#comment:49
https://trac.sagemath.org/ticket/15619#comment:49
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/15619#comment:46" title="Comment 46">ncohen</a>:
</p>
<blockquote class="citation">
<p>
The funny thing is that the only code that actually tests this pickling stuff is the poset code... So this can only be tested seriously with static graph backends for posets <code>^^;</code>
</p>
</blockquote>
<p>
If I recall correctly, in the "good old days" (before we had posets), the doctest coverage script was checking in each file whether it contains a "loads(dumps(bla)) == bla" test. So, people did want to pickle stuff even before some guy came up with category testsuites.
</p>
<p>
By the way, if you want that static graphs aren't just tested via posets, then you should provide a category of graphs! Its testsuite would automatically test whether pickling works <code>:-p</code>.
</p>
<hr />
<p>
New commits:
</p>
<table class="wiki">
<tr><td><a class="ext-link" href="http://git.sagemath.org/sage.git/commit/?id=c441178"><span class="icon"></span>c441178</a></td><td><code>trac #15619: bug in the former definition; exception to avoid it in the future</code>
</td></tr></table>
TicketSimonKingThu, 02 Jan 2014 20:43:40 GMT
https://trac.sagemath.org/ticket/15619#comment:50
https://trac.sagemath.org/ticket/15619#comment:50
<p>
Thank you for the fix! I'll review it then and add a few tests.
</p>
TicketncohenThu, 02 Jan 2014 20:46:30 GMT
https://trac.sagemath.org/ticket/15619#comment:51
https://trac.sagemath.org/ticket/15619#comment:51
<blockquote class="citation">
<p>
If I recall correctly, in the "good old days" (before we had posets), the doctest coverage script was checking in each file whether it contains a "loads(dumps(bla)) == bla" test. So, people did want to pickle stuff even before some guy came up with category testsuites.
</p>
</blockquote>
<p>
I blame those who carry on as much as those who initiate it <code>:-P</code>
</p>
<blockquote class="citation">
<p>
By the way, if you want that static graphs aren't just tested via posets, then you should provide a category of graphs! Its testsuite would automatically test whether pickling works <code>:-p</code>.
</p>
</blockquote>
<p>
Ahahahah. Over my dead body. I have been debugging code for two full evenings because people decided I should only implement picklable graphs, and this is because I try to fix combinat's hack of immutable posets. And that's not even the end of it. So let's make that clear : over my dead body <code>:-P</code>
</p>
<p>
And there are still broken doctests in the combinat/poset/ folder now. I just updated the u/ncohen/tmp branch with this commit.
</p>
<p>
Nathann
</p>
TicketncohenThu, 02 Jan 2014 20:48:21 GMT
https://trac.sagemath.org/ticket/15619#comment:52
https://trac.sagemath.org/ticket/15619#comment:52TicketncohenThu, 02 Jan 2014 20:50:06 GMT
https://trac.sagemath.org/ticket/15619#comment:53
https://trac.sagemath.org/ticket/15619#comment:53
<p>
This being said, thank you for your help with this. It was driving me crazy. Actually the other bugs from combinat/poset in the u/ncohen/tmp branch are still driving me crazy <code>T_T</code>
</p>
TicketncohenThu, 02 Jan 2014 21:04:27 GMT
https://trac.sagemath.org/ticket/15619#comment:54
https://trac.sagemath.org/ticket/15619#comment:54
<p>
Hmmmm... Looks like the <code>StaticSparseBackend</code> has a working <code>relabel</code> function <code>:-PPPPPPPP</code>
</p>
<p>
Nathann
</p>
TicketncohenThu, 02 Jan 2014 21:12:10 GMT
https://trac.sagemath.org/ticket/15619#comment:55
https://trac.sagemath.org/ticket/15619#comment:55
<p>
Annnnnnnnnd with this all tests pass.. WUUUUUHUUUUUUUUUUUUUUUUUUUUUUUU !! <code>O_O_O</code>
</p>
<p>
Nathann
</p>
TicketncohenThu, 02 Jan 2014 21:39:23 GMT
https://trac.sagemath.org/ticket/15619#comment:56
https://trac.sagemath.org/ticket/15619#comment:56
<p>
<a class="closed ticket" href="https://trac.sagemath.org/ticket/15623" title="enhancement: Immutable graph backend for Posets (closed: fixed)">#15623</a> makes Posets use immutable graphs. Cool, isn't it ? <code>:-PPP</code>
</p>
<p>
Nathann
</p>
TicketSimonKingThu, 02 Jan 2014 22:52:56 GMT
https://trac.sagemath.org/ticket/15619#comment:57
https://trac.sagemath.org/ticket/15619#comment:57
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/15619#comment:54" title="Comment 54">ncohen</a>:
</p>
<blockquote class="citation">
<p>
Hmmmm... Looks like the <code>StaticSparseBackend</code> has a working <code>relabel</code> function <code>:-PPPPPPPP</code>
</p>
</blockquote>
<p>
Ouch. But you take care of this in <a class="closed ticket" href="https://trac.sagemath.org/ticket/15622" title="defect: Immutable graphs must not be relabeled (closed: fixed)">#15622</a>, right?
</p>
<p>
Apart from this: All doctests pass, and the code looks fine to me. In a review commit, I'll add some tests for issues we discussed here.
</p>
TicketncohenFri, 03 Jan 2014 08:15:08 GMT
https://trac.sagemath.org/ticket/15619#comment:58
https://trac.sagemath.org/ticket/15619#comment:58
<p>
Indeed, indeed !
</p>
<p>
Nathann
</p>
TicketSimonKingFri, 03 Jan 2014 11:29:50 GMT
https://trac.sagemath.org/ticket/15619#comment:59
https://trac.sagemath.org/ticket/15619#comment:59
<p>
Right now I am testing whether everything keeps working after merging my review patch from <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>
TicketSimonKingFri, 03 Jan 2014 12:49:01 GMTchangetime, branch, time changed
https://trac.sagemath.org/ticket/15619#comment:60
https://trac.sagemath.org/ticket/15619#comment:60
<ul>
<li><strong>changetime</strong>
changed from <em>01/03/14 11:29:50</em> to <em>01/03/14 11:29:50</em>
</li>
<li><strong>branch</strong>
changed from <em>u/ncohen/15619</em> to <em>u/SimonKing/ticket/15619</em>
</li>
<li><strong>time</strong>
changed from <em>01/02/14 10:31:12</em> to <em>01/02/14 10:31:12</em>
</li>
</ul>
TicketSimonKingFri, 03 Jan 2014 12:51:48 GMTstatus, commit changed; reviewer set
https://trac.sagemath.org/ticket/15619#comment:61
https://trac.sagemath.org/ticket/15619#comment:61
<ul>
<li><strong>status</strong>
changed from <em>needs_review</em> to <em>positive_review</em>
</li>
<li><strong>reviewer</strong>
set to <em>Simon King</em>
</li>
<li><strong>commit</strong>
changed from <em>c4411781fa8a64d3e89568069ad85caab47b81d2</em> to <em>cabc96968cab75cbca1e85f1e8efc7b3c50f85e7</em>
</li>
</ul>
<p>
I am not sure if pushing my changes properly worked (apparently I needed to manually set the commit I added). Anyway, if you like my review commit, then it is a positive review.
</p>
TicketncohenFri, 03 Jan 2014 12:58:14 GMT
https://trac.sagemath.org/ticket/15619#comment:62
https://trac.sagemath.org/ticket/15619#comment:62
<p>
Argggggggg sorry. I just noticed that there is a problem with this code. It does not handle multiple edges and loops correctly.
</p>
<p>
I HAAAAAAAAAAAAAAAAAAAAATE THESE THINGS.
</p>
<pre class="wiki">sage: g = Graph(multiedges = True)
sage: g.add_edges(graphs.PetersenGraph().edges())
sage: g.add_edges(graphs.PetersenGraph().edges())
sage: gi = g.copy(immutable=True)
sage: loads(dumps(gi))
Multi-graph on 10 vertices
sage: loads(dumps(gi)) == gi
False
sage: gi.size()
30
sage: loads(dumps(gi)).size()
15
</pre><p>
I will add a commit to this one within 10 minutes. Need to write it first <code>>_<</code>
</p>
<p>
Nathann
</p>
TicketncohenFri, 03 Jan 2014 13:07:21 GMTstatus, branch changed; commit deleted
https://trac.sagemath.org/ticket/15619#comment:63
https://trac.sagemath.org/ticket/15619#comment:63
<ul>
<li><strong>status</strong>
changed from <em>positive_review</em> to <em>needs_work</em>
</li>
<li><strong>commit</strong>
<em>cabc96968cab75cbca1e85f1e8efc7b3c50f85e7</em> deleted
</li>
<li><strong>branch</strong>
changed from <em>u/SimonKing/ticket/15619</em> to <em>public/15619</em>
</li>
</ul>
TicketncohenFri, 03 Jan 2014 13:07:30 GMTstatus changed
https://trac.sagemath.org/ticket/15619#comment:64
https://trac.sagemath.org/ticket/15619#comment:64
<ul>
<li><strong>status</strong>
changed from <em>needs_work</em> to <em>needs_review</em>
</li>
</ul>
TicketgitFri, 03 Jan 2014 13:11:34 GMTcommit set
https://trac.sagemath.org/ticket/15619#comment:65
https://trac.sagemath.org/ticket/15619#comment:65
<ul>
<li><strong>commit</strong>
set to <em>e761346c888f8ef6f5dd5b43f52b20d23fef500c</em>
</li>
</ul>
<p>
Branch pushed to git repo; I updated commit sha1. Last 10 new commits:
</p>
<table class="wiki">
<tr><td><a class="ext-link" href="http://git.sagemath.org/sage.git/commit/?id=e761346"><span class="icon"></span>e761346</a></td><td><code>trac #15619: Pickling multigraphs with loops and labels</code>
</td></tr><tr><td><a class="ext-link" href="http://git.sagemath.org/sage.git/commit/?id=cabc969"><span class="icon"></span>cabc969</a></td><td><code>Trac 15619: Review commit</code>
</td></tr><tr><td><a class="ext-link" href="http://git.sagemath.org/sage.git/commit/?id=c441178"><span class="icon"></span>c441178</a></td><td><code>trac #15619: bug in the former definition; exception to avoid it in the future</code>
</td></tr><tr><td><a class="ext-link" href="http://git.sagemath.org/sage.git/commit/?id=0229348"><span class="icon"></span>0229348</a></td><td><code>trac #15619: Pickling of immutable graphs</code>
</td></tr><tr><td><a class="ext-link" href="http://git.sagemath.org/sage.git/commit/?id=7860f39"><span class="icon"></span>7860f39</a></td><td><code>trac #15603: "immutable=True" for Graph/Digraph __init__ and copy()</code>
</td></tr><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><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><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><tr><td><a class="ext-link" href="http://git.sagemath.org/sage.git/commit/?id=2fc8a77"><span class="icon"></span>2fc8a77</a></td><td><code>Make digraphs using the static backend immutable and hashable</code>
</td></tr></table>
TicketncohenFri, 03 Jan 2014 13:12:30 GMT
https://trac.sagemath.org/ticket/15619#comment:66
https://trac.sagemath.org/ticket/15619#comment:66
<p>
Done. tested on the most ugly graphs I could build.
</p>
<p>
I hate multigraphs. I hate loops. I hate labels.
</p>
<p>
Nathann
</p>
TicketncohenSat, 04 Jan 2014 09:49:44 GMT
https://trac.sagemath.org/ticket/15619#comment:67
https://trac.sagemath.org/ticket/15619#comment:67
<p>
Helloooo Simon ! Is this one good for you ? It depends on a patch with <code>positive_review</code>, and a patch with <code>positive_review</code> depends on it, but it still unchecked <code>:-P</code>
</p>
<p>
Nathann
</p>
TicketSimonKingSat, 04 Jan 2014 19:22:31 GMT
https://trac.sagemath.org/ticket/15619#comment:68
https://trac.sagemath.org/ticket/15619#comment:68
<p>
The solution seems logical to me (to the extent that multigraphs with labels and loops can be "logical"...), and the example is carefully chosen to cover all cases (including isolated vertices). Hence, if the doctests pass (I'll know in about one hour) then I'll give it a positive review.
</p>
TicketSimonKingSat, 04 Jan 2014 20:32:22 GMTstatus changed
https://trac.sagemath.org/ticket/15619#comment:69
https://trac.sagemath.org/ticket/15619#comment:69
<ul>
<li><strong>status</strong>
changed from <em>needs_review</em> to <em>positive_review</em>
</li>
</ul>
<pre class="wiki">----------------------------------------------------------------------
All tests passed!
----------------------------------------------------------------------
Total time for all tests: 3981.0 seconds
cpu time: 6195.0 seconds
cumulative wall time: 7673.1 seconds
</pre><p>
OK, a bit more than an hour.
</p>
<p>
According to the previous comment, this is a positive review.
</p>
TicketvbraunSun, 05 Jan 2014 02:56:50 GMTstatus changed; resolution set
https://trac.sagemath.org/ticket/15619#comment:70
https://trac.sagemath.org/ticket/15619#comment:70
<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