#14806: Immutable graph backend
---------------------------------+------------------------------------------
Reporter: ncohen | Owner: jason, ncohen, rlm
Type: enhancement | Status: needs_review
Priority: major | Milestone: sage-5.12
Component: graph theory | Resolution:
Keywords: | Work issues:
Report Upstream: N/A | Reviewers:
Authors: Nathann Cohen | Merged in:
Dependencies: #14805 | Stopgaps:
---------------------------------+------------------------------------------
Changes (by ncohen):
* cc: dimpase, azi, Slani, SimonKing, vbraun, Stefan, nthiery, hivert
(added)
* status: new => needs_review
Old description:
> 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
>
> Apply:
> * [attachment:trac_14806.patch]
> * [attachment:trac_14806-update_keyword.patch]
New description:
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
--
--
Ticket URL: <http://trac.sagemath.org/sage_trac/ticket/14806#comment:7>
Sage <http://www.sagemath.org>
Sage: Creating a Viable Open Source Alternative to Magma, Maple, Mathematica,
and MATLAB
--
You received this message because you are subscribed to the Google Groups
"sage-trac" group.
To unsubscribe from this group and stop receiving emails from it, send an email
to [email protected].
To post to this group, send email to [email protected].
Visit this group at http://groups.google.com/group/sage-trac.
For more options, visit https://groups.google.com/groups/opt_out.
