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
