Opened 6 years ago

Closed 6 years ago

Last modified 6 years ago

#14806 closed enhancement (fixed)

Immutable graph backend

Reported by: ncohen Owned by: jason, ncohen, rlm
Priority: major Milestone: sage-5.12
Component: graph theory Keywords:
Cc: dimpase, azi, Slani, SimonKing, vbraun, Stefan, nthiery, hivert Merged in: sage-5.12.beta4
Authors: Nathann Cohen Reviewers: Jernej Azarija
Report Upstream: N/A Work issues:
Branch: Commit:
Dependencies: #14805 Stopgaps:

Description (last modified by ncohen)

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

Attachments (1)

sparselabel.patch (77.9 KB) - added by ncohen 6 years ago.

Download all attachments as: .zip

Change History (22)

comment:1 Changed 6 years ago by ncohen

  • Description modified (diff)

comment:2 Changed 6 years ago by ncohen

  • Description modified (diff)

comment:3 Changed 6 years ago by ncohen

  • Dependencies set to #14806

comment:4 Changed 6 years ago by ncohen

  • Dependencies changed from #14806 to #14805
  • Description modified (diff)

comment:5 Changed 6 years ago by ncohen

  • Description modified (diff)

comment:6 Changed 6 years ago by ncohen

  • Component changed from PLEASE CHANGE to graph theory
  • Description modified (diff)
  • Owner changed from tbd to jason, ncohen, rlm

comment:7 Changed 6 years ago by ncohen

  • Cc dimpase azi Slani SimonKing vbraun Stefan nthiery hivert added
  • Description modified (diff)
  • Status changed from new to needs_review

comment:8 follow-up: Changed 6 years ago by vbraun

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

comment:9 in reply to: ↑ 8 Changed 6 years ago by ncohen

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

comment:10 follow-up: Changed 6 years ago by azi

Hello!

As promised I peaked 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)): 

Version 0, edited 6 years ago by azi (next)

comment:11 Changed 6 years ago by vbraun

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

comment:12 in reply to: ↑ 10 Changed 6 years ago by ncohen

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

comment:13 Changed 6 years ago by azi

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

comment:14 Changed 6 years ago by ncohen

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

comment:15 Changed 6 years ago by azi

  • Reviewers set to Jernej Azarija
  • Status changed from needs_review to positive_review

comment:16 Changed 6 years ago by ncohen

Wow. THaaaaaaaaaaaaaaaaaanks ! :-)

Nathann

comment:17 Changed 6 years ago by jdemeyer

  • Status changed from positive_review to needs_work

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

Changed 6 years ago by ncohen

comment:18 Changed 6 years ago by ncohen

  • Status changed from needs_work to positive_review

Done !

comment:19 Changed 6 years ago by jdemeyer

  • Merged in set to sage-5.12.beta4
  • Resolution set to fixed
  • Status changed from positive_review to closed

comment:20 follow-up: Changed 6 years ago by nthiery

Merci Nathann!

comment:21 in reply to: ↑ 20 Changed 6 years ago by ncohen

Merci Nathann!

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

Nathann

Note: See TracTickets for help on using tickets.