#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 | Keywords:
Work issues: | Report Upstream: N/A
Reviewers: | Authors:
Merged in: | Dependencies:
Stopgaps: |
----------------------------+-----------------------------------------------
Several graph methods can be significantly speed up improving the data
structure, or at least the way some basic operations are performed.
For instance, many functions are faster using networkx graphs (conversion
time included) instead of sage graphs.
In fact, NetworkX uses dictionaries to store edges. If G is a networkx
graph, it is also a dictionary indexed by the vertices, and G[u] is a
dictionary indexed by neighbors and containing edge data. This way,
iterations are fast.
{{{
sage: G = graphs.RandomBarabasiAlbert(100,2)
sage: %timeit E = [(u,v) for u in G for v in G.neighbor_iterator(u)]
125 loops, best of 3: 1.63 ms per loop
sage: ggnx = G.networkx_graph()
sage: %timeit EE = [(u,v) for u in ggnx for v in ggnx.neighbors_iter(u)]
625 loops, best of 3: 141 µs per loop
sage: %timeit EE = [(u,v) for u in ggnx for v in ggnx[u]]
625 loops, best of 3: 127 µs per loop
}}}
We should at least improve iteration over the neighbors.
--
Ticket URL: <http://trac.sagemath.org/sage_trac/ticket/13730>
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.
