Pickling of immutable graphs

[ncohen]

Before

sage: g=Graph(graphs.PetersenGraph(),immutable=True)
sage: g == loads(dumps(g))
...
TypeError: __cinit__() takes exactly 1 positional argument (0 given)

After

sage: g=Graph(graphs.PetersenGraph(),immutable=True)
sage: g == loads(dumps(g))
True

[git]

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

​0229348	trac #15619: Pickling of immutable graphs
​7860f39	trac #15603: "immutable=True" for Graph/Digraph __init__ and copy()
​2525d22	Trac 15278: Fix syntax error in doc test
​fcf9e30	Trac 15278: Only graphs that use the static backend are identical with their copy
​8fc9c94	Merge branch 'develop' into ticket/15278
​51d6328	Trac 15278: Error messages explain how to create (im)mutable graph copy
​2fc8a77	Make digraphs using the static backend immutable and hashable
​07bad46	Merge branch 'u/ncohen/15491' of git://trac.sagemath.org/sage into ticket/15278
​126b036	Merge branch 'master' into ticket/15278
​c774057	Prepare hash and copy for immutable graphs. Let .weighted() respect mutability.

[SimonKing]

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

[ncohen]

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 :-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 O_o

Nathann

[ncohen]

It does minimize the amount of code necessary for such a function, though. And clear code is good by itself :-P

Nathann

[SimonKing]

Replying to ncohen:

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 :-P

Sage is a community project after all.

[ncohen]

I don't see the relationship O_o

[SimonKing]

What do you think about the following way to pickle generic graphs?

    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

Is this elegant enough for you? Additional bait: We may even remove the existing __reduce__ methods of the other backends ;-)

[SimonKing]

PS: With the above __reduce__ method put into sage.graphs.generic_graph.py, one has

sage: G = graphs.PetersenGraph()
sage: g = G.copy(data_structure='static_sparse')
sage: loads(dumps(g))
Graph on 10 vertices
sage: g == _
True

[SimonKing]

Some little timing:

Your way of pickling:

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

My way of pickling:

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

:-P

[SimonKing]

On the other hand, I think I did something severely wrong:

sage:  h = loads(dumps(g))
sage: type(h._backend)
<class 'sage.graphs.base.sparse_graph.SparseGraphBackend'>

Bad. So, it doesn't work in the way I thought...

[SimonKing]

Would it be possible to let the static graph backend __init__ accept a list of edges rather than a graph? Then, your __reduce__ method could be simplified (and actually it seems odd that the creation of a graph *backend* needs a graph!).

[SimonKing]

Hm. I tried to understand what happens when one creates a static sparse backend.

I always thought that one needs a backend to implement a graph. But in fact __init__ and __cinit__ and init_short_digraph (which are all involved in the creation of a static sparse backend) rely on the input being a graph. :-/

[ncohen]

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 TestSuite? 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.

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 Graph/DiGraph constructors.

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.

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 Graph/DiGraph constructor too.

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.

Nathann

[SimonKing]

Replying to ncohen:

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.

Right. This is in fact a strong argument for implementing the pickling in the way you did. All these optional arguments of (Di)Graph.__init__ are a mess.

Honestly, I don't think pickling really needs any amount of efficient code.

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 __copy__, and thus __reduce__ 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.

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.

Careful! You are just arguing that the person who knows the data structure best (i.e., you) is responsible for making pickling work :-)

If you want to write generic code for this, it will end up being bad code.

Correct. Sometimes generic code just works, but in some cases __reduce__ needs to be provided. Wonderful that Python is object oriented and lets us do such things...

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 Graph/DiGraph constructor too.

Here or on a different ticket?

Let's move on. Can you help me with this promotion bug ?

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.

[SimonKing]

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.

Hence, one could provide Poset with a custom __reduce__ 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.

[ncohen]

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 linear_extensions.py in the u/ncohen/tmp branch ? :-/

Nathann

[SimonKing]

This one seems to be the underlying reason for the problems with posets:

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

[SimonKing]

The pickling result is in fact seriously wrong:

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)]

[SimonKing]

Indeed the error occurs when constructing the graph used to pickle the graph backend:

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)]

Bug in iterator_edges? Then you should thank the guy who invented the TestSuite, since it helped you uncover a bug in a method you probably care about (namely iteration over edges).

[SimonKing]

In pure form, the failing example is

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)]

[ncohen]

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.

I'm trying to fix that. It's weird, if you use iterator_out_edges instead there is no problem anymore O_o

Nathann

[ncohen]

(by the way, D.show fails :-P)

[ncohen]

Oh. Well, it is not really a bug. It's just that iterator_edges is not meant for digraphs O_o

Nathann

[ncohen]

Did you find a place in the code that call the backend's iterator_edges functions ?

Nathann

[ncohen]

I mean... For a DiGraph?. I should probably add an exception there when this function is used with a digraph, but it is clearly meant for undirected graphs only.

		if j < i and j in vertices:
                    continue

It only outputs an edge once :-P

Nathann

[ncohen]

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 :-PPPPPPPPP

Nathann

[SimonKing]

Replying to ncohen:

Oh. Well, it is not really a bug. It's just that iterator_edges is not meant for digraphs O_o

Is this documented? If it *is* documented, then it is not a bug. But then, its use in __reduce__ should be replaced by something that works.

[ncohen]

What I just said doesn't make sense... T_T

Still, the only exceptions I see happen with hashs...

Nathann

[SimonKing]

Replying to ncohen:

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 :-PPPPPPPPP

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.

[ncohen]

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 O_o

Nathann

[SimonKing]

Replying to ncohen:

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 O_o

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.

[ncohen]

Okay I'm stupid. I hadn't noticed I used this in __reduce__. Totally my mystake. I'm going to fix this and see how it works out. Should make a hell of a difference.

Nathann

[SimonKing]

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.

[ncohen]

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 :-P

Nathann

[ncohen]

Okay, replacing iterator_edges by iterator_out_edges in the __reduce__ function of the static sparse backend fixes the pickling-related problems. Some other weird bugs remain in the poset/ folder though T_T

Nathann

[SimonKing]

Replying to ncohen:

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

But why would you hesitate to make iterator_edges work on digraphs?

[ncohen]

It looks like it hasn't been posted.

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 :-P

Nathann

[SimonKing]

Replying to ncohen:

No, please. We need to discuss what the function should return before anything. I don't find any good answer for that.

Well, of course it should return an iterator over the edges of the digraph. What else should it do?

[git]

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

​2eb2c95

trac #15619: bug in the former definition; exception to avoid it in the future

[ncohen]

Well, of course it should return an iterator over the edges of the digraph. What else should it do?

O_o

What about the vertices argument ?

Nathann

---

New commits:

​2eb2c95

trac #15619: bug in the former definition; exception to avoid it in the future

[SimonKing]

Replying to ncohen:

It looks like it hasn't been posted.

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

For example (this is the doctest of my not-posted commit):

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)]

[SimonKing]

Replying to ncohen:

What about the vertices argument ?

Ahaha, you mean whether it is supposed to be the in or out vertices of the edges being returned?

[ncohen]

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 vertices. Unless you look for them and remove them before returning them. And this I think is ugly. What do you think ? :-P

By the way the commit I just uploaded does not work. Sorry for that. I'll fix it in a second.

Nathann

[SimonKing]

Replying to ncohen:

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 vertices. Unless you look for them and remove them before returning them. And this I think is ugly. What do you think ?

Agreed.

By the way the commit I just uploaded does not work. Sorry for that. I'll fix it in a second.

Agreed (it is self._directed, not self.directed).

[ncohen]

Okayokay, I just fixed this _directed, what's left seems to work.

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 ^^;

Nathann

[ncohen]

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 ^^;

Anyway, this one looks good.

Nathann

[git]

Branch pushed to git repo; I updated commit sha1. Last 10 new commits:

​c441178	trac #15619: bug in the former definition; exception to avoid it in the future
​0229348	trac #15619: Pickling of immutable graphs
​7860f39	trac #15603: "immutable=True" for Graph/Digraph __init__ and copy()
​2525d22	Trac 15278: Fix syntax error in doc test
​fcf9e30	Trac 15278: Only graphs that use the static backend are identical with their copy
​8fc9c94	Merge branch 'develop' into ticket/15278
​51d6328	Trac 15278: Error messages explain how to create (im)mutable graph copy
​2fc8a77	Make digraphs using the static backend immutable and hashable
​07bad46	Merge branch 'u/ncohen/15491' of git://trac.sagemath.org/sage into ticket/15278
​126b036	Merge branch 'master' into ticket/15278

[SimonKing]

Replying to ncohen:

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 ^^;

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.

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 :-p.

---

New commits:

​c441178

trac #15619: bug in the former definition; exception to avoid it in the future

[SimonKing]

Thank you for the fix! I'll review it then and add a few tests.

[ncohen]

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.

I blame those who carry on as much as those who initiate it :-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 :-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 :-P

And there are still broken doctests in the combinat/poset/ folder now. I just updated the u/ncohen/tmp branch with this commit.

Nathann

[ncohen]

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 T_T

[ncohen]

Hmmmm... Looks like the StaticSparseBackend has a working relabel function :-PPPPPPPP

Nathann

[ncohen]

Annnnnnnnnd with this all tests pass.. WUUUUUHUUUUUUUUUUUUUUUUUUUUUUUU !! O_O_O

Nathann

[ncohen]

#15623 makes Posets use immutable graphs. Cool, isn't it ? :-PPP

Nathann

[SimonKing]

Replying to ncohen:

Hmmmm... Looks like the StaticSparseBackend has a working relabel function :-PPPPPPPP

Ouch. But you take care of this in #15622, right?

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.

[ncohen]

Indeed, indeed !

Nathann

[SimonKing]

Right now I am testing whether everything keeps working after merging my review patch from #15603.

[SimonKing]

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.

[ncohen]

Argggggggg sorry. I just noticed that there is a problem with this code. It does not handle multiple edges and loops correctly.

I HAAAAAAAAAAAAAAAAAAAAATE THESE THINGS.

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

I will add a commit to this one within 10 minutes. Need to write it first >_<

Nathann

[git]

Branch pushed to git repo; I updated commit sha1. Last 10 new commits:

​e761346	trac #15619: Pickling multigraphs with loops and labels
​cabc969	Trac 15619: Review commit
​c441178	trac #15619: bug in the former definition; exception to avoid it in the future
​0229348	trac #15619: Pickling of immutable graphs
​7860f39	trac #15603: "immutable=True" for Graph/Digraph __init__ and copy()
​2525d22	Trac 15278: Fix syntax error in doc test
​fcf9e30	Trac 15278: Only graphs that use the static backend are identical with their copy
​8fc9c94	Merge branch 'develop' into ticket/15278
​51d6328	Trac 15278: Error messages explain how to create (im)mutable graph copy
​2fc8a77	Make digraphs using the static backend immutable and hashable

[ncohen]

Done. tested on the most ugly graphs I could build.

I hate multigraphs. I hate loops. I hate labels.

Nathann

[ncohen]

Helloooo Simon ! Is this one good for you ? It depends on a patch with positive_review, and a patch with positive_review depends on it, but it still unchecked :-P

Nathann

[SimonKing]

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.

[SimonKing]

----------------------------------------------------------------------
All tests passed!
----------------------------------------------------------------------
Total time for all tests: 3981.0 seconds
    cpu time: 6195.0 seconds
    cumulative wall time: 7673.1 seconds

OK, a bit more than an hour.

According to the previous comment, this is a positive review.