Immutable graph backend

[nathanncohen]

As the title says, this patch implements a data structure atop of the current "static sparse graphs" which can be used as a backend for a Sage Graph. Smaller in memory, and faster.

sage: g = graphs.CompleteGraph(400)                                 
sage: gi = Graph(g,data_structure="static_sparse")
sage: %timeit g.edges()                                             
1 loops, best of 3: 512 ms per loop
sage: %timeit gi.edges()
10 loops, best of 3: 30.3 ms per loop

The patch :

• Creates a new sage.graphs.base.static_sparse_backend modules containing two classes, StaticSparseCGraph and StaticSparseBackend, as it is done for the current sparse/dense backends.
• Updates the static_sparse_graph data structure to handle labels
• Updates the constructors of Graph and DiGraph by renaming the sparse keyword to data_structure which can now be set to sparse,dense or static_sparse (and others later)
• Deals with the consequences of renaming the keyword, i.e. changes doctests everywhere in the graph/ files, and into some other files of Sage too.

I tested this patch in many many ways, and in particular by adding at the end of graph/digraph __init__ method the following two lines:

• (if the backend is not static) build a copy of self using a static backend
• Check that both are equal, and otherwise scream in panic

This being said, many graph methods will break when the backend is static. The most obvious ones are add/remove vertex/edges, but other methods will break which supposed that any graph can be modified. For methods which do not modify the graph itself, this happens when it creates a temporary copy of it (which will use the same backend), and feel free to change that one.

I don't see an automatic way to spot them, I don't think it is very bad as this static backend is a new feature and hence will not break any existing code, and this patch is already very long (and hard to review) as it is ^^;

Nathann

Depends on #14805

CC: @dimpase @sagetrac-azi @sagetrac-Slani @simon-king-jena @vbraun @sagetrac-Stefan @nthiery @hivert

Component: graph theory

Author: Nathann Cohen

Reviewer: Jernej Azarija

Merged: sage-5.12.beta4

Issue created by migration from https://trac.sagemath.org/ticket/14806

[nathanncohen]

Dependencies: #14806

[nathanncohen]

Changed dependencies from #14806 to #14805

[vbraun]

comment:8

• Its either "Thou shalt not add a vertex to an immutable graph!"
  (Shakespeare) or "cannot add vertex to an immutable graph"
  (Python). In particular, lower case and no exclamation mark at the
  end ;)

• Methods that fail due to being immutable should raise ValueError,
  not NotImplementedError (are you going to implement it in the
  future?)

• It would be nice if INPUT/OUTPUT were consistent and would actually
  list all arguments, for example (though there are many more)
  StaticSparseBackend.degree does not document the "directed"
  argument.

• static_sparse_backend module docstring "Two classes" names the same
  class twice.

• StaticSparseCGraph docstring: ":mod:CGraph <sage.graphs.base.c_graph> class over :mod:static sparse graphs <sage.graphs.base.static_dense_graph>". I don't know what thats
  supposed to mean.

• The Python special __copy__() method does not allow any
  arguments. In particular, copy(graph) should return a mutable copy
  if the original graph is immutable.

• Having to write data_structure="sparse" is a lot less intuitive
  than the old sparse=True. It would be better to allow for both
  and raise a ValueError if both are changed from their default
  values.

[nathanncohen]

comment:9

Hello !

• Its either "Thou shalt not add a vertex to an immutable graph!"
  (Shakespeare) or "cannot add vertex to an immutable graph"
  (Python). In particular, lower case and no exclamation mark at the
  end ;)

I obviously chosed the "Thou shalt not add a vertex to an immutable graph".

• Methods that fail due to being immutable should raise ValueError,
  not NotImplementedError (are you going to implement it in the
  future?)

I change my mind so often that I wouldn't put it beyond reach. But just to please you I fixed it :-P

• It would be nice if INPUT/OUTPUT were consistent and would actually
  list all arguments, for example (though there are many more)
  StaticSparseBackend.degree does not document the "directed"
  argument.

Well, I defined the "INPUT" where it was not, but usually the outputs are pretty clear... Not to mention that those are rather meant to Sage developpers.

• static_sparse_backend module docstring "Two classes" names the same
  class twice.

It's a poetic license.

• StaticSparseCGraph docstring: ":mod:CGraph <sage.graphs.base.c_graph> class over :mod:static sparse graphs <sage.graphs.base.static_dense_graph>". I don't know what thats
  supposed to mean.

That it uses static sparse graphs as a data structure. By the way, the link and the name did not match. I rephrased it.

• The Python special __copy__() method does not allow any
  arguments. In particular, copy(graph) should return a mutable copy
  if the original graph is immutable.

There were arguments there before I learnt that Sage existed, and it is because this method can also be used through G.copy(whatever). This being said, I don't see why one should get a mutable graph as a copy of an immutable one. Copying a tuple certainly does not make it a list, and it would produce rather unexpected behaviour O_o

• Having to write data_structure="sparse" is a lot less intuitive
  than the old sparse=True. It would be better to allow for both
  and raise a ValueError if both are changed from their default
  values.

You have no idea how many hours I wasted on that. Unfortunately, you are right. I reversed those modifications and both keywords can now be used.

Patch updated !

Nathann

[sagetrac-azi]

comment:10

Hello!

As promised I peeked at the code!! In general the patch looks good to me with the exception of the above comments.

• Can we use xrange instead of range when we only iterate over something?

• Can we raise a ValeError in 'in_neighbors if u is not in the graph as to be consistent with how out_degree works?

• In the function iterator_in_edges why do we need the call to iter in the following line ?

            for x in iter(self.iterator_out_edges(vertices, labels)): 

[vbraun]

comment:11

Cython detects "for i in range(n)" loops and replaces them with a C loop. So there is no point in using xrange.

[nathanncohen]

comment:12

Hellooooooo !!

As promised I peeked at the code!!

Cooooooooooool ! :-P

• Can we use xrange instead of range when we only iterate over something?

Volker beat me to this one.

• Can we raise a ValeError in 'in_neighbors if u is not in the graph as to be consistent with how out_degree works?

T_T

You are right. Fixed.

• In the function iterator_in_edges why do we need the call to iter in the following line ?

Because I am an idiot. It actually explains a lot of things :-P

Fiiiiiiiiixed !

Nathann

[sagetrac-azi]

comment:13

Good!

As far as I am concerned the code is good to go! Do you want me to review it positively or wish for another less confused soul to review it as well?

...as for xrange/range... I can see the reason for using range to be compatible with Python 3.x but somehow I am afraid the transition will never happen :-)

[nathanncohen]

comment:14

Well... For me the code is good to go too, so if you agree with it I would be glad to see it in Sage ! Not to mention that I wrote this patch because of #14806, and that those guys will probably want to use it for their own dark ends once it will be merged :-)

As for Python 3, I don't know. It feels like it may take forever to move there, but then again things happened very efficiently to move to git, sooo... Well. Sage devs are surprising guys :-)

Nathann

[sagetrac-azi]

Reviewer: Jernej Azarija

[nathanncohen]

comment:16

Wow. THaaaaaaaaaaaaaaaaaanks ! :-)

Nathann

[jdemeyer]

comment:17

This needs to be rebased to sage-5.12.beta2.

[nathanncohen]

comment:18

Attachment: sparselabel.patch.gz

Done !

[jdemeyer]

Merged: sage-5.12.beta4

[nthiery]

comment:20

Merci Nathann!

[nathanncohen]

comment:21

Merci Nathann!

Maintenant pour me remercier faut l'utiliser, genre pour me convaincre que je ne l'ai pas codé pour rien :-P

Nathann