Hi all,
I'm benchmarking some graph libraries. I was excited to see that
Sage's graph library has a backend implemented in Cython.
Unfortunately, it seems to be orders of magnitude slower than a pure
NetworkX implementation. Here a code summary:
import networkx
# read in test adjacency matrix using networkx
G = networkx.read_adjlist('testmat%i.adjlist' % (N))
N = len(G.nodes())
E = G.edges()
E = map(lambda x: (int(x[0]),int(x[1])), E)
# set up test object
tester.set_graph(E,N)
The tester object is either of two classes, Tester_networkx or
Tester_sage_cgraph, both of which set up the graph G in their
respective implementations. For instance, if N is the number of nodes,
tester is initialized as follows:
import networkx
...
self.M = networkx.DiGraph()
self.M.add_edges_from( range(N) )
self.M.add_edges(E)
or
from sage.all import DiGraph
…
self.M = DiGraph(N, implementation="c_graph") # tried sparse=True,
similar results
self.M.add_edges(E)
I am seeing the following timing results for the two different
implementations:
On a 1000 node graph, adding edges from node i to 100 randomly chosen
nodes (slowest of 100 trials):
networkx 298.02 usec
sage_cgraph 749.83 usec
Things get very bad when looking for strongly connected components
(slowest of 10 trials):
scc() -- 10 trials:
networkx 5846.98 usec
scc() -- 10 trials:
sage_cgraph 1363383.05 usec (231x networkx)
I tried changing the Sage Graph implementation to "networkx", hoping
to see identical behavior to the pure NetworkX version. Unfortunately,
it is somewhere in between:
scc() -- 10 trials:
sage_networkx 104291.92 usec (20x networkx)
I'm assuming I must be doing something wrong to see such large
differences. Any ideas??
Thanks for your help,
Jesse
--
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-support
URL: http://www.sagemath.org
