Hello list,

I'm going on with my algorithms and i'm stuck on a thing: I cannot

find the interface on graph_tool to access the adjacency matrix of the

graph.

The rationale behind my request is that i have a graph and i have a

matrix based algorithm to calculate new edges and new weights. So I'd

like to:

(1) create a graph through the usual API

(2) get its adjacency matrix

(3) modify it with my matrix operations based algorithm

(4) feed it back to the graph / create a new graph from the matrix

What is your suggestion to do this in graph_tool?

TIA,

Claudio

Hello Claudio,

Claudio Martella wrote:

Hello list,

I'm going on with my algorithms and i'm stuck on a thing: I cannot

find the interface on graph_tool to access the adjacency matrix of the

graph.

The rationale behind my request is that i have a graph and i have a

matrix based algorithm to calculate new edges and new weights. So I'd

like to:

(1) create a graph through the usual API

(2) get its adjacency matrix

(3) modify it with my matrix operations based algorithm

(4) feed it back to the graph / create a new graph from the matrix

What is your suggestion to do this in graph_tool?

Step 2 can be done with the adjacency() function of the spectral module:

http://projects.forked.de/graph-tool/doc/spectral.html#graph_tool.spectral.adjacency

Step 4 needs to be done by hand, but it should be something as simple as:

for i in xrange(N):

for j in xrange(N):

if a[i,j] != 0:

g.add_edge(g.vertex(i), g.vertex(j))

Cheers,

Tiago

Hello Claudio,

Claudio Martella wrote:

Hello list,

I'm going on with my algorithms and i'm stuck on a thing: I cannot

find the interface on graph_tool to access the adjacency matrix of the

graph.

The rationale behind my request is that i have a graph and i have a

matrix based algorithm to calculate new edges and new weights. So I'd

like to:

(1) create a graph through the usual API

(2) get its adjacency matrix

(3) modify it with my matrix operations based algorithm

(4) feed it back to the graph / create a new graph from the matrix

What is your suggestion to do this in graph_tool?

Step 2 can be done with the adjacency() function of the spectral module:

http://projects.forked.de/graph-tool/doc/spectral.html#graph_tool.spectral.adjacency

Step 4 needs to be done by hand, but it should be something as simple as:

for i in xrange(N):

for j in xrange(N):

if a[i,j] != 0:

g.add_edge(g.vertex(i), g.vertex(j))

Thanks, that is a solution i considered but it feels very expensive.

This means a continuous switch from python to C++, doesn't it?

Wouldn't it be way faster if i created such a function somewhere in

C++, passing the matrix?

Claudio Martella wrote:

Thanks, that is a solution i considered but it feels very expensive.

This means a continuous switch from python to C++, doesn't it?

Wouldn't it be way faster if i created such a function somewhere in

C++, passing the matrix?

That depends. You can improve that loop if your matrix is sparse (which

probably is), so that you build the graph in O(E) time. However, the

important question is what are you going to be doing with the matrix. If

you spend 90% of the time doing computations with it, it would not

matter much if the last step is carried out in python.

Cheers,

Tiago

yes, it's a small world of over 1.000.000 edges, at the moment, but

probably will be bigger in the future. I don't understand how i could

switch it to O(E) from the matrix. Can i get the non-zero elements of

the matrix?

Claudio Martella wrote:

yes, it's a small world of over 1.000.000 edges, at the moment, but

probably will be bigger in the future. I don't understand how i could

switch it to O(E) from the matrix. Can i get the non-zero elements of

the matrix?

The adjacency list returned is a sparse matrix object:

http://docs.scipy.org/doc/scipy/reference/sparse.html#module-scipy.sparse

You can get the non-zero elements with the nonzero() method of the matrix.

Cheers,

Tiago

Thank you very much Tiago.

I'm still having some troubles with the graphviz library in

graph-tool. I installed the packages (python-pygraphviz, libgv-py etc)

and made the link you suggested in some recent emails about this

troubles, but python is still complaining about gvg. Funny thing is

that networkx which also uses graphviz to draw graphs doesn't have the

same problem.

Any ideas?

Claudio Martella wrote:

I'm still having some troubles with the graphviz library in

graph-tool. I installed the packages (python-pygraphviz, libgv-py etc)

and made the link you suggested in some recent emails about this

troubles, but python is still complaining about gvg. Funny thing is

that networkx which also uses graphviz to draw graphs doesn't have the

same problem.

Networkx has its own interface to graphviz, and does not use libgv.

I'm assuming you are using ubuntu... There, the directories are slightly

different than Debian. You have to do the following:

ln -sf /usr/lib/pyshared/python2.6/libgv_python.so /usr/lib/pymodules/python2.6/_gv.so

And it should work. This is really a bug in Debian/Ubuntu...

Cheers,

Tiago

Thanks, that's exactly what I did yesterday night (there was no 2.5

file). Today i reinstalled my ubuntu workstation on parallels and this

time the workaround worked. So thanks.

I was trying to understand the API to the new function that calculates

distances but to me it looks like it just gives you the distances (in

terms of hops i guess) but not the actual paths that the distances

refer to. Is that correct?

Claudio Martella wrote:

Thanks, that's exactly what I did yesterday night (there was no 2.5

file). Today i reinstalled my ubuntu workstation on parallels and this

time the workaround worked. So thanks.

I was trying to understand the API to the new function that calculates

distances but to me it looks like it just gives you the distances (in

terms of hops i guess) but not the actual paths that the distances

refer to. Is that correct?

Yes. Obtaining all the paths would scale horribly, in the general case.

I plan to include general BFS/Dijkstra algorithms, at a later point,

from which those things could be obtained.

Cheers,

Tiago