graph_tool
Ben Edwards
http://projects.skewed.de/graph-tool/
It actually is pretty fast, though the api is not totally clear and
it's not as complete as networkx. I do like the idea of using
underlying boost libraries to speed things up. Have rewriting some of
the basic classes in C or C++ been considered? Seems like we could get
some serious speed-up.
http://www.boost.org/doc/libs/1_45_0/libs/graph/doc/table_of_contents.html
Ben
Aric Hagberg
Boost is great. But one of the reasons we start NetworkX was to be
"Python-based" and not just a wrapper to another low-level library in
C or C++. Aren't there already Python bindings for boost?
Aric
Moritz Beber
http://www.boost.org/doc/libs/1_45_0/libs/python/doc/index.html
Ben Edwards
using them to great effect in the past year. Rather than using the
boost graph library, what about an alternative class say cGraph, which
copies exactly the functionality of Graph(or DiGraph or MultiGraph),
but is written from scratch in C++ and interfaces through boost? Sort
of like Pickle and cPickle.
I love networkx (and python), but even for the moderately sized graphs
I usually work on (tens of thousands of nodes), any algorithm too much
beyond n**2 tend to be just on the edge of frustratingly slow. Just a
thought, might be a useful branch...
On Dec 24, 6:35 pm, Moritz Beber <moritz.be...@googlemail.com> wrote:
> On 12/25/2010 01:42 AM, Aric Hagberg wrote:
>
>
>
>
>
>
>
> > On Sat, Dec 25, 2010 at 2:28 AM, Ben Edwards <bjedwa...@gmail.com> wrote:
> >> I came across this today...
>
> >>http://projects.skewed.de/graph-tool/
>
> >> It actually is pretty fast, though the api is not totally clear and
> >> it's not as complete as networkx. I do like the idea of using
> >> underlying boost libraries to speed things up. Have rewriting some of
> >> the basic classes in C or C++ been considered? Seems like we could get
> >> some serious speed-up.
>
Aric Hagberg
> The Python bindings for boost are quiet easy to use, and I've started
> using them to great effect in the past year. Rather than using the
> boost graph library, what about an alternative class say cGraph, which
> copies exactly the functionality of Graph(or DiGraph or MultiGraph),
> but is written from scratch in C++ and interfaces through boost? Sort
> of like Pickle and cPickle.
We have discussed this and there is an open ticket for creating a C
version of the classes (not using Boost though).
https://networkx.lanl.gov/trac/ticket/206
We did explore C language versions of the base classes, but with
dictionary-of-dictionary data structures you aren't going to do much
(any?) better than Python's implementation without a lot of work.
Certainly if you restrict the type of the nodes to integers and don't allow
extra data on nodes or edges, etc you can make much faster and more
memory efficient code for a graph data structure. But I think that
points to considering a Cython implementation.
> I usually work on (tens of thousands of nodes), any algorithm too much
> beyond n**2 tend to be just on the edge of frustratingly slow. Just a
> thought, might be a useful branch...
Writing algorithms in C or Cython (even using the existing NetworkX
Python classes) will definitely provide some speed-up. But of course
eventually nothing is going to solve your problem of running large
problems with algorithms that scale worse than n**2 in the number of
nodes.
Aric
Dan Schult
and it seems that having the data structure in C isn't enough.
Python's dict class is very fast and networkx uses it effectively.
The bottleneck seems to be in the algorithms and the interface
between C and Python (where translation takes time). If we write
some algorithms using C/Cython and restrict to integer nodes and
float edge weights, we should be able to speed things up. The
algorithms can access dicts directly so minimal translation between
Python and C is needed. In the comparison between C and Cython, I
think the performance is about the same, but Cython makes interfacing
with python and testing much easier and should be easier to maintain.
Dan
Tiago Peixoto
I'm the author of graph-tool, and I just found out about this
thread. :-)
Let me just give some quick clarifications:
* _All_ algorithms in graph-tool are written in C++, with the Boost
Graph Library (BGL). But it is not just a wrapper around it; the
graph
interface is specially designed to make it quite pythonic, and there
are additional algorithms.
* The main data structure is an adjacency list (the standard BGL
adjacency_list class), implemented with STL vectors. This means
vertices are simple integers. However, arbitrary properties
(scalars,
vectors, strings and arbitrary python objects) can be attached to
them
via property maps. These properties are recognizable as C++ native
types (when possible), so that the algorithms don't even know there
is
a python side of things, which make them very fast. The property
maps
are also reflected as numpy arrays, which make their manipulation
very
convenient from python.
* Graph filtering (of edges and/or vertices) is also implemented in C+
+,
with no performance penalty when it is not used.
* There is an official python binding for the BGL
(http://osl.iu.edu/~dgregor/bgl-python/), but it is no longer
maintained. It is very different design-wise from graph-tool, since
it
is not made with performance in mind (eg. the main adjacency list
uses
a linked-list representation).
Cheers,
Tiago
>
> Ben