id summary reporter owner description type status priority milestone component resolution keywords cc merged author reviewer upstream work_issues branch commit dependencies stopgaps
14806 Immutable graph backend ncohen jason ncohen rlm "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" enhancement closed major sage-5.12 graph theory fixed dimpase azi Slani SimonKing vbraun Stefan nthiery hivert sage-5.12.beta4 Nathann Cohen Jernej Azarija N/A #14805