#14535: Mutability of Graphs
--------------------------------------------+-------------------------------
Reporter: SimonKing | Owner: jason, ncohen, rlm
Type: enhancement | Status: needs_review
Priority: major | Milestone: sage-5.10
Component: graph theory | Resolution:
Keywords: mutability graph | Work issues:
Report Upstream: N/A | Reviewers:
Authors: Simon King, Volker Braun | Merged in:
Dependencies: #14524 | Stopgaps:
--------------------------------------------+-------------------------------
Changes (by {'newvalue': u'Simon King, Volker Braun', 'oldvalue': u'Simon
King'}):
* author: Simon King => Simon King, Volker Braun
Old description:
> This patch allows to create immutable graphs, so that they can be used as
> keys in dictionaries.
>
> Previously, calling hash on a graph did work after assigning the
> attribute `_immutable` to the graph. That's a hack, and it would in fact
> ''not'' prevent the graph from being mutated.
>
> With this patch, the attempt to change an immutable graph be means of
> methods such as add_vertex or add_edge or delete_vertex, will result in
> an error. If one really wants to play nasty, one could make an immutable
> graph mutable and change it, or use the backend of the graph for changing
> the underlying data.
New description:
This patch allows to create immutable graphs, so that they can be used as
keys in dictionaries.
Previously, calling hash on a graph did work after assigning the attribute
`_immutable` to the graph. That's a hack, and it would in fact ''not''
prevent the graph from being mutated.
With this patch, the attempt to change an immutable graph be means of
methods such as add_vertex or add_edge or delete_vertex, will result in an
error. If one really wants to play nasty, one could make an immutable
graph mutable and change it, or use the backend of the graph for changing
the underlying data.
Apply [attachment:trac14535-immutable_graphs_vb.patch]
--
Comment:
I've updated the patch.
I also removed the mutability checks from some of the backends. The
central user-facing point to implement them is in `GenericGraph` /
`GenericGraph_pyx`. This is similar to the matrix code where we, for
example, don't patch linbox to support (im)mutability.
It seems there is quite a bit of overhead in graph construction since the
`GenericGraph._backend` is a Python class. This means various dictionary
lookups to locate `add_vertex` and friends. You could shave off a lot of
overhead by
1. Move the construction methods (`add_vertex` etc) from `GenericGraph`
to `GenericGraph_pyx`
1. Switch `GenericGraphBackend` and its subclasses to Cython and make
its methods cdef
1. Equip `GenericGraph_pyx` with a Cython attribute `cdef
GenericGraphBackend _backend`
See also http://docs.cython.org/src/userguide/early_binding_for_speed.html
But thats material for another ticket.
Once all the constructions methods are in `GenericGraph_pyx` it'll also be
easy to switch the mutability check to a very fast inline function.
--
Ticket URL: <http://trac.sagemath.org/sage_trac/ticket/14535#comment:26>
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?hl=en.
For more options, visit https://groups.google.com/groups/opt_out.
