#13730: Speed up some graph iterations
--------------------------------+-------------------------------------------
Reporter: dcoudert | Owner: jason, ncohen, rlm
Type: enhancement | Status: new
Priority: major | Milestone: sage-5.6
Component: graph theory | Resolution:
Keywords: | Work issues:
Report Upstream: N/A | Reviewers:
Authors: | Merged in:
Dependencies: | Stopgaps:
--------------------------------+-------------------------------------------
Comment (by azi):
Hello guys!
I have implemented a stupid "fix" by adding a hash table to the graph
object storing neighbours for every vertex of the graph. I then modified
the add_edge/delete_edge methods to update the hash table accordingly.
The speedup was drastic (as with networkX graphs) and it also speed up
other graph theory functions (since many things rely on obtaining the
neighbours of some vertices)
HOWEVER. Many of the graph theory tests made sage crash which makes
uncomfortable in posting the patch here. I am not aware enough of the
graph internals to be able to write a sane patch that is not just some
naive fix.
Hence I call someone that is more experienced with the c_graph
implementation to add this feature. It is really really worth doing it!
--
Ticket URL: <http://trac.sagemath.org/sage_trac/ticket/13730#comment:5>
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 post to this group, send email to [email protected].
To unsubscribe from this group, send email to
[email protected].
For more options, visit this group at
http://groups.google.com/group/sage-trac?hl=en.
