bkelley at wi.mit.edu
Tue Jan 6 13:57:47 CET 2004
Andrew Dalke wrote:
> Lonnie Princehouse:
>>I keep thinking that a good graph module would be really handy (as in
>>nodes and edges, not plotting)
> I've wondered about Boost. There's Boost Python of course,
> and Boost includes a graph library with many of the features you've
> listed. But do the two work well together? I dunno.
>>with the ability to traverse and manipulate graphs in nice Pythonic ways,
> And I really don't know if the result will feel Pythonic. I barely
> understand how to make the examples work, much less what
> needs to be done to get a full melding.
>>basic graph theory (finding cycles, paths, cliques, etc). I've
>>started writing one, but it's nowhere near completion.
> I have two C extensions for Python which do max clique detection.
> See http://starship.python.net/crew/dalke/clique/ . But I haven't
> tested them in over 4 years.
I have and just last year. They work pretty well but I think that there
might be better algorithms. I had them working under python 2.2 but
they aren't useful out of the box since there is no driver. I can
package it with the one that I have (the graph is represented as a
numeric matrix) if anyone is really interested.
> BTW, I've done various bits of graph theory work for molecular
> structures. I've found that the nomenclature is different enough
> that it's hard for chemistry and graph theory to share each other's
> data structures directly. (Eg, we want "atoms", which are
> "colored nodes", and "bonds", which are "colored undirected
> edges" of low valence (usually 4 or less, rarely above 6, and
> never larger than about 13.)
This is a bit of a pain, algorithms might want to use node and edge or
vertex and edge while chemists want to use atom and bond.
> Still, I'll be interested in anything you have, especially
> subgraph isomorphism. (There is Brian Kelly's "Frowns"
> package which has a Python interface to the VF algorithm
> but it needs to convert to VF's data structures before doing
> the search, and that apparently takes most of the time.)
I have minimized this somewhat, but I expect that it still is going to
be slow to keep parallel graph structures (python->C++) (python->boost).
I have almost completed a pure-python version of vflib, mainly for the
purpose of doing recursive graph searching. It doesn't appear to be
much slower than the C++ counterpart and doesn't have the start up time
conversion. The vflib package is available seperately from frowns by
> dalke at dalkescientific.com
More information about the Python-list