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:
forked.de steht zum Verkauf - Sedo GmbH
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