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 -- Claudio Martella claudio.martella@gmail.com
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.a... 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
On Thu, Nov 5, 2009 at 11:59 AM, Tiago de Paula Peixoto <tiago@forked.de> wrote:
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.a...
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?
Cheers, Tiago
_______________________________________________ graph-tool mailing list graph-tool@forked.de http://lists.forked.de/mailman/listinfo/graph-tool
-- Claudio Martella claudio.martella@gmail.com
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? On Fri, Nov 6, 2009 at 3:00 PM, Tiago de Paula Peixoto <tiago@forked.de> wrote:
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
_______________________________________________ graph-tool mailing list graph-tool@forked.de http://lists.forked.de/mailman/listinfo/graph-tool
-- Claudio Martella claudio.martella@gmail.com
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? On Fri, Nov 6, 2009 at 5:54 PM, Tiago de Paula Peixoto <tiago@forked.de> wrote:
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
_______________________________________________ graph-tool mailing list graph-tool@forked.de http://lists.forked.de/mailman/listinfo/graph-tool
-- Claudio Martella claudio.martella@gmail.com
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? On Fri, Nov 6, 2009 at 6:18 PM, Tiago de Paula Peixoto <tiago@forked.de> wrote:
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
_______________________________________________ graph-tool mailing list graph-tool@forked.de http://lists.forked.de/mailman/listinfo/graph-tool
-- Claudio Martella claudio.martella@gmail.com
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
participants (2)
-
Claudio Martella -
Tiago de Paula Peixoto