#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 )
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)
Change History (22)
comment:1 Changed 8 years ago by
- Description modified (diff)
comment:2 Changed 8 years ago by
- Description modified (diff)
comment:3 Changed 8 years ago by
- Dependencies set to #14806
comment:4 Changed 8 years ago by
- Dependencies changed from #14806 to #14805
- Description modified (diff)
comment:5 Changed 8 years ago by
- Description modified (diff)
comment:6 Changed 8 years ago by
- Component changed from PLEASE CHANGE to graph theory
- Description modified (diff)
- Owner changed from tbd to jason, ncohen, rlm
comment:7 Changed 8 years ago by
- Cc dimpase azi Slani SimonKing vbraun Stefan nthiery hivert added
- Description modified (diff)
- Status changed from new to needs_review
comment:8 follow-up: ↓ 9 Changed 8 years ago by
comment:9 in reply to: ↑ 8 Changed 8 years ago by
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
, notNotImplementedError
(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 originalgraph
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 oldsparse=True
. It would be better to allow for both and raise aValueError
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: ↓ 12 Changed 8 years ago by
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)):
comment:11 Changed 8 years ago by
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 8 years ago by
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 8 years ago by
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 8 years ago by
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 8 years ago by
- Reviewers set to Jernej Azarija
- Status changed from needs_review to positive_review
comment:16 Changed 8 years ago by
Wow. THaaaaaaaaaaaaaaaaaanks ! :-)
Nathann
comment:17 Changed 8 years ago by
- Status changed from positive_review to needs_work
This needs to be rebased to sage-5.12.beta2.
Changed 8 years ago by
comment:19 Changed 8 years ago by
- Merged in set to sage-5.12.beta4
- Resolution set to fixed
- Status changed from positive_review to closed
comment:20 follow-up: ↓ 21 Changed 8 years ago by
Merci Nathann!
comment:21 in reply to: ↑ 20 Changed 8 years ago by
Merci Nathann!
Maintenant pour me remercier faut l'utiliser, genre pour me convaincre que je ne l'ai pas codé pour rien :-P
Nathann
ValueError
, notNotImplementedError
(are you going to implement it in the future?)StaticSparseBackend.degree
does not document the "directed" argument.class over :mod:
static sparse graphs <sage.graphs.base.static_dense_graph>`". I don't know what thats supposed to mean.__copy__()
method does not allow any arguments. In particular,copy(graph)
should return a mutable copy if the originalgraph
is immutable.data_structure="sparse"
is a lot less intuitive than the oldsparse=True
. It would be better to allow for both and raise aValueError
if both are changed from their default values.