Project dream

[Lonnie Princehouse]

I keep thinking that a good graph module would be really handy (as in
nodes and edges, not plotting), with the ability to traverse and
manipulate graphs in nice Pythonic ways, as well as implement some
basic graph theory (finding cycles, paths, cliques, etc). I've
started writing one, but it's nowhere near completion.

 

[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
(e-mail address removed)

 

[Brian Kelley]

Lonnie Princehouse:



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.




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.




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
(e-mail address removed)

Brian.

 

[Lonnie Princehouse]

I can't find any reference to the Boost Graph library being used with
Boost Python, but that doesn't mean it can't be done =)

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.

What I mean by Pythonic is mostly an ability to subclass Graphs and
Nodes and perhaps even Edges. This would help the nomenclature
disparity, but probably comes with a considerable performance hit:

class Molecule(Graph):
...

class Atom(Node):
...

class Bond(Edge):
...

My motivation is to tinker around with control flow in abstract syntax
trees, so I'm using directed acyclic graphs. It will certainly
involve lots of searching for subgraph isomorphism, though.

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.

I wasn't aware of vflib, but it looks very nice. Perhaps I'll stop
working on my own internal graph representation and start working on a
way to make all of the various graph libraries play nicely together in
Python (I'm thinking Boost Graphs + vflib + graphviz).. and also to
improve the graphviz/Python bindings a little bit (apparently it still
requires writing/reading files in graphviz's language)

 

[Ionutz Borcoman]

Suppose you have the time and the money to start a new project in
Python. What would you like to do?

I want to do a 'Where Is It?' clone in Python. Probably use Metakit
and e4graph as the database. PyGTK or WxPython for the GUI (most
probably PyGTK).

I'll probably do it anyway, but money would help a lot

ionutz