Graph-tool interface

graph-tool
1

Hello,

I'm writing an application with heavy graph operations. It's written
in python, so i've tried networkx, igraph and lately i've tried to use
boost graph library bindings to python (BGL-PY).

Thanks god i ran into graph-tool which looks very complete and also is
doing a transition into something very handy for me (python accessible
boost-based library).

I'm having a look at the API i found here:
http://projects.forked.de/graph-tool/doc/quickstart.html#creating-and-manipulating-graphs

and i see i add vertices with g = Graph() g.add_vertices() and
calculate the betweeness centrality with
graph_tool.centrality.betweeness_centrality().

As i was looking for an implementation of a minimum spanning tree i
realized i couldn't find it in the reference i pointed a couple of
lines above.

So i had a look at the graph_tool.py that uses the library and
realized that the interface is different there.

Graph = GraphInterface()
Graph.GetBetweennessCentrality() or Graph.GetMinimumSpanningTree()
etc, and i cannot find any add_vertex() in this API.

I'm a bit confused, so i'm trying to understand what i should use to
have full power over the graph-tool API.

TIA

Claudio Martella

2

Hello Claudio,

Claudio Martella wrote:

Hello,

I'm writing an application with heavy graph operations. It's written
in python, so i've tried networkx, igraph and lately i've tried to use
boost graph library bindings to python (BGL-PY).

Thanks god i ran into graph-tool which looks very complete and also is
doing a transition into something very handy for me (python accessible
boost-based library).

Great. :wink:

I'm having a look at the API i found here:
forked.de steht zum Verkauf - Sedo GmbH

and i see i add vertices with g = Graph() g.add_vertices() and
calculate the betweeness centrality with
graph_tool.centrality.betweeness_centrality().

As i was looking for an implementation of a minimum spanning tree i
realized i couldn't find it in the reference i pointed a couple of
lines above.

So i had a look at the graph_tool.py that uses the library and
realized that the interface is different there.

Graph = GraphInterface()
Graph.GetBetweennessCentrality() or Graph.GetMinimumSpanningTree()
etc, and i cannot find any add_vertex() in this API.

I'm a bit confused, so i'm trying to understand what i should use to
have full power over the graph-tool API.

The minimum spanning tree code has not yet been ported to the new
scheme, so it does not work at the moment. If you dig in the source code
you will find the old code, but as you noticed it will not make much
sense. Right now, you cannot really use it, sorry. :frowning:

The interface from graph-tool with C++ (with the BGL) is also something
I plan to document, so that it will be easy for people to write
extensions. There is even a module called run_action which allows inline
embedding of C++ code, which is automatically compiled and run (via
scipy's weave).

I'm currently finishing the documentation of the features which are
implemented. I will then include more algorithms from BGL (such as
minimum spanning tree, which is a high priority), which are relatively
easy.

I cannot promise any time schedule, but hopefully all this will be done
soon, as I'm working at it regularly. I'll post something in this list
when it is done.

Cheers,
Tiago

3

Tiago de Paula Peixoto wrote:

Hello Claudio,

Claudio Martella wrote:

Hello,

I'm writing an application with heavy graph operations. It's written
in python, so i've tried networkx, igraph and lately i've tried to use
boost graph library bindings to python (BGL-PY).

Thanks god i ran into graph-tool which looks very complete and also is
doing a transition into something very handy for me (python accessible
boost-based library).

Great. :wink:

I'm having a look at the API i found here:
forked.de steht zum Verkauf - Sedo GmbH

and i see i add vertices with g = Graph() g.add_vertices() and
calculate the betweeness centrality with
graph_tool.centrality.betweeness_centrality().

As i was looking for an implementation of a minimum spanning tree i
realized i couldn't find it in the reference i pointed a couple of
lines above.

So i had a look at the graph_tool.py that uses the library and
realized that the interface is different there.

Graph = GraphInterface()
Graph.GetBetweennessCentrality() or Graph.GetMinimumSpanningTree()
etc, and i cannot find any add_vertex() in this API.

I'm a bit confused, so i'm trying to understand what i should use to
have full power over the graph-tool API.

The minimum spanning tree code has not yet been ported to the new
scheme, so it does not work at the moment. If you dig in the source code
you will find the old code, but as you noticed it will not make much
sense. Right now, you cannot really use it, sorry. :frowning:

The interface from graph-tool with C++ (with the BGL) is also something
I plan to document, so that it will be easy for people to write
extensions. There is even a module called run_action which allows inline
embedding of C++ code, which is automatically compiled and run (via
scipy's weave).

I'm currently finishing the documentation of the features which are
implemented. I will then include more algorithms from BGL (such as
minimum spanning tree, which is a high priority), which are relatively
easy.

I cannot promise any time schedule, but hopefully all this will be done
soon, as I'm working at it regularly. I'll post something in this list
when it is done.

Just to make some things more clear about your question: If you want to
calculate the betweenness centrality, for instance, you should do the
following:

    vbet, ebet = graph_tool.centrality.betweeness(g)

and then vbet and ebet are property maps with the vertex and edge
betweeness centrality. All documented functions have short examples, and
they show how you should use them. When minimum spanning tree is
implemented, it will also work in a similar fashion.

Best regards,
Tiago

4

Hello Tiago,

thanks for the answer. I'm really looking forward to contribute to
your project with some porting, as I need minimum spanning tree
capabilities and bellman-ford/dijkstra algorithms. I'll try to
understand a bit the architecture you've put in place in order to do
some implementations. In the meanwhile i wanted to run some
benchmarking scripts to see how quicker graph_tool with openmp is
compared to both networkx and and to igraph (ATM i can just compare
the betweenness centrality).

So i gitted the development code and tried to build it but i had some
compile time errors. I attach both the output of make and the
config.log. I added ubuntu's gcc-snapshot package (which provides gcc
4.4) and overrid the system compiler by using CC and CXX pointint to
the snapshot bins.

TIA

Claudio

config.log (86 KB)

output.log (7.45 KB)

5

Hi Claudio,

Claudio Martella wrote:

So i gitted the development code and tried to build it but i had some
compile time errors. I attach both the output of make and the
config.log. I added ubuntu's gcc-snapshot package (which provides gcc
4.4) and overrid the system compiler by using CC and CXX pointint to
the snapshot bins.

It seems to me the problem lies with boost, or with your boost + gcc
combination. You have boost 1.34 apparently. Can you install version
1.39?

Cheers,
Tiago

6

I installed 1.37 which is the latest boost on the latest ubuntu. the
compilation goes on further but it dies anyway. I wanted to keep the
system clean of scratch compilation but i'll work out a way to compile
the system on my MacOSX.

I'll let you know ASA I manage.

7

Claudio Martella wrote:

I installed 1.37 which is the latest boost on the latest ubuntu. the
compilation goes on further but it dies anyway. I wanted to keep the
system clean of scratch compilation but i'll work out a way to compile
the system on my MacOSX.

I'll let you know ASA I manage.

Please try the following if you have boost < 1.39:

    git checkout 9587bf8f5b7 src/graph/read_graphviz_spirit.cpp

This might help.

Cheers,
Taigo