Project dream

[Brian Kelley]

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 
the way.

> 
>                     Andrew
>                     dalke at dalkescientific.com
> 
> 

Brian.