Hi Nathan, Thanks for looking into this. I believe that I stayed within Sage's library when I wrote my test code. The general outline and some classes were originally written by a collaborator (I don't want to take credit, but I'll take responsibility where there are errors!) I couldn't find a way to attach files, so I've pasted the two classes below (plus a base class):
SAGE sage_cgraph_tester.py: import numpy as np from numpy import random as rnd from sage.all import DiGraph from tester import Tester class Tester_sage_cgraph( Tester ): def __init__(self): self.name = 'sage_cgraph' def set_graph(self,E,N): self.N = N self.M = DiGraph(N, implementation="networkx" ) #"c_graph", sparse=True) self.M.add_edges(E) def rand_row(self,R): i = self.rand_vert() self.M.add_edges([(i,self.rand_vert()) for j in range(R)]) def rand_col(self,R): i = self.rand_vert() self.M.add_edges([(self.rand_vert(),i) for j in range(R)]) def rand_entry(self): i = self.rand_vert() j = self.rand_vert() if not self.M.has_edge(i,j): self.M.add_edge(i,j) def subgraph(self,K): self.M.subgraph(self.rand_verts(K)) def scc(self): self.M.strongly_connected_components_digraph() NETWORKX networkx_tester.py (originally coded by my collaborator, but I'll take full responsibility for any errors :) ): import numpy as np from numpy import random as rnd import networkx from tester import Tester import rads_nx class Tester_networkx(Tester): def __init__(self): self.name = 'networkx' def set_graph(self,E,N): self.N = N self.M = networkx.DiGraph() self.M.add_nodes_from(range(N)) self.M.add_edges_from(E) def rand_row(self,R): i = self.rand_vert() self.M.add_edges_from([(i,self.rand_vert()) for j in range(R)]) def rand_col(self,R): i = self.rand_vert() self.M.add_edges_from([(self.rand_vert(),i) for j in range(R)]) def rand_entry(self): i = self.rand_vert() j = self.rand_vert() if not self.M.has_edge(i,j): self.M.add_edge(i,j) def subgraph(self,K): networkx.subgraph(self.M,self.rand_verts(K)) def scc(self): networkx.algorithms.components.strongly_connected_components(self.M) The base class Tester is in tester.py: import numpy as np from numpy import random as rnd class Tester: def rand_vert(self): return rnd.randint(0,self.N-1) def rand_verts(self,R): return rnd.randint(0,self.N-1,R) The NetworkX and Sage graph testers are initialize as follows: 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) print 'initializing testers... ', tester.set_graph(E,N) Operations are timed using the timeit module. Eg., test_str = 'testers[%i].%s(%s)' % ( tester, test['F'],test['args'] ) timer = timeit.Timer( test_str, import_str), where test['F'] is the method names and test['args'] contain any necessary args. Thanks again for your help. Happy holidays! Jesse On Dec 23, 6:43 pm, Nathann Cohen <nathann.co...@gmail.com> wrote: > Hello Jesse ! > > Well, for a start it wouldn't be very fair to compare graph libraries if > you do not use our graph methods and recode your own ! You seem to have > rewritten your version of "strongly connected components" to test the > libraries, and such low-level methods are in Sage written in Cython, so > this kind of running times are only those you would get if you use Sage > graphs but refuse to use any of the methods present in the library :-D > > This being said, I just did some tests and if they are far from being as > bad for Sage as yours are, I was quite disappointed myself. I was under the > impression we were leaving NetworkX far behind, and it looks like we > actually are behind in some cases, which will need to be fixed. Could I ask > you to provide examples of codes which have different running times for > NetworkX and Sage ? I guess you only use the add/remove edge/vertices > methods in your code, which may be the explanation. When you are doing that > you are actually calling Cython methods through Python functions, and > spending more time calling methods than actually getting the job done.... > Though to be honest I do not want to have to explain why Sage is slower, I > would like to show that it is faster :-) > > Hence, if you can provide the code, we could begin to talk about the > technical reasons. > > Good night ! > > Nathann -- To post to this group, send email to sage-support@googlegroups.com To unsubscribe from this group, send email to sage-support+unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/sage-support URL: http://www.sagemath.org