id,summary,reporter,owner,description,type,status,priority,milestone,component,resolution,keywords,cc,merged,author,reviewer,upstream,work_issues,branch,commit,dependencies,stopgaps
13730,Speed up some graph iterations,dcoudert,jason ncohen rlm,"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.",enhancement,needs_work,major,sage-6.4,graph theory,,,azi ncohen slani brunellus vdelecroix,,,,N/A,,,,,