# Building graph from adjacency matrix

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

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!

This is true. If your code essentially depends on python loops,
graph-tool will not provide any advantage.

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
g = Graph()

n = m.shape[0]

c = Counter(every=10, until=n)
for i in xrange(n):
for j in xrange(n):
if m[i,j]:
c.count()

return g

... 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++)?

The ability of inserting many edges without calling add_edge() several
times is indeed lacking...

Because of this, I have now just added a Graph.add_edge_list() to the
git version, which takes a list of edges to be added, which can be a
numpy array. If you have a full adjacency matrix instead of an edge
list, you can do simply:

This should be much faster than the Python loop above.

Best,
Tiago

This is really great, I will try the git version as soon as possible.

Thank you very much.

Pietro

Do you think it would make sense then to have something analogous for
PropertyMaps?

Like:

pm.set_from_list(a)

in place of:

for v in g.vertices():
pm[v] = a[i]

if pm is a property for vertices, and

for e in g.edges():
pm[e] = a[i]

if it is for edges?

Pietro

That's all ready simpler than that, as you can assign values of the
propertymap like that:

pm.a = a

Great! Thanks

Pietro

I think there is some problem with add_edge_list.

The following code:

I think there is some problem with add_edge_list.

The following code:

---------------------------------------------------------

from scipy import array
from graph_tool import Graph
from graph_tool.draw import graph_draw

def blocks_star(transpose=False):
g = Graph()
members = array([0,1,2])
edges_list = array([[0,1,2], [2,0,1]]).transpose()
edges_list_2 = array([[0,2],[1,0],[2,1]])
print edges_list
print edges_list_2
print all(edges_list == edges_list_2)
if transpose:
else:
graph_draw(g)

---------------------------------------------------------

gives me a different result if called with True or False as argument
(with True, the resulting graph is disconnected), while the edges lists
are clearly identical. I guess this has to do with the fact that
transposing, for numpy, is just a change of view, not a relocation of
elements... but I see your code is based on boost, which I have no
experience with. I am using package python-graph-tool 2.2.31-1 from your
Debian sid repositories.

This is a bug. The strides of the numpy array are not propagated
properly to the C++ side of things. I have fixed this now in the git
version.

Not really crucial issue, but... later it would be too late to raise it!

The only grammatically correct variations I see are "add edge list" or
"add list of edges". The phrase "add edges list" does not seem right.

Best,
Tiago

> I think there is some problem with add_edge_list.
>
> The following code:
>
> ---------------------------------------------------------
>
> from scipy import array
> from graph_tool import Graph
> from graph_tool.draw import graph_draw
>
> def blocks_star(transpose=False):
> g = Graph()
> members = array([0,1,2])
> edges_list = array([[0,1,2], [2,0,1]]).transpose()
> edges_list_2 = array([[0,2],[1,0],[2,1]])
> print edges_list
> print edges_list_2
> print all(edges_list == edges_list_2)
> if transpose:
> else:
> graph_draw(g)
>
> ---------------------------------------------------------
>
> gives me a different result if called with True or False as argument
> (with True, the resulting graph is disconnected), while the edges lists
> are clearly identical. I guess this has to do with the fact that
> transposing, for numpy, is just a change of view, not a relocation of
> elements... but I see your code is based on boost, which I have no
> experience with. I am using package python-graph-tool 2.2.31-1 from your
> Debian sid repositories.

This is a bug. The strides of the numpy array are not propagated
properly to the C++ side of things. I have fixed this now in the git
version.

Great!