Project dream

[Andrew Dalke]

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.

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.)

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.)

                    Andrew
                    dalke at dalkescientific.com