[graph-tool] Building graph from adjacency matrix

Pietro Battiston ml at pietrobattiston.it
Thu Mar 20 11:30:26 CET 2014


Hello,

I tried graph-tool after some experience with networkx, in search for
better efficiency (attracted by [1]) ... but unfortunately, it seems
like it all depends on how data is stored!

The (several) networks I play with are dense weighted networks of 1435
nodes. They are defined in terms of their adjacency matrices, which are
pandas dataframes stored in a HDF5 store.

In order to get the relative network with networkx, I would do
dg = nx.from_numpy_matrix(hstore['my_df'].as_matrix(),
                          create_using=nx.DiGraph())

which took around 18 seconds. In graph-tool, the best alternative I
found, based on [2] and [3], is:


# Since the bottleneck is given by the calls to g.add_edge(),
# numba actually slows down things a bit.
#from numba import autojit
#
#@autojit
def graph_from_adj_matrix(m):
    g = Graph()
        
    n = m.shape[0]
    
    edges = list(g.add_vertex(n=n))
    
    c = Counter(every=10, until=n)
    for i in xrange(n):
        for j in xrange(n):
            if m[i,j]:
                g.add_edge(edges[i], edges[j])
        c.count()
    
    return g

g = graph_from_adj_matrix(hstore['my_df'].as_matrix())


... which takes around 200 seconds (and is still not even weighted!).

Is there anything trivial (or simply new) I'm missing (apart from the
possibility, mentioned in [3], of writing my code in C++)?

[1] : http://graph-tool.skewed.de/performance
[2] : 
 http://lists.skewed.de/pipermail/graph-tool/2011-September/000438.html
[3] : http://graph-tool.skewed.de/trac/ticket/106

Thanks,

Pietro




More information about the graph-tool mailing list