A Python Graph API?
This wiki page is a resource for some brainstorming around the possibility of a Python Graph API in the form of an informational PEP, similar to PEP 249, the Python DB API. The goal would be, in other words, to define how a graph (or various kinds of graphs) would be expected to behave (possibly from different perspectives) in order to increase interoperability among graph algorithms. The numeric array interface, recently developed by the Numeric Python community to increase interoperability between array-handling software, illustrates the general idea.
A comp.lang.python thread discussing this (with some useful ideas) may be found here.
This is not about plotting; for a definition of the kind of graph we're talking about, see here.
If you have interest in this, please feel free to add your ideas here. If you'd like to be named as a contributor in the case that some "standard" should emerge, please add your name to the list of contributors. (You might also want to create a user name and log in when doing changes, or possibly just state your name when you edit stuff, so one can see who did what.)
A simple use-case
Just to illustrate the point of this discussion, here is a simple example:
Let's say I have some special hardware that is able to search efficiently for complex patterns in byte sequences. I somehow use this to find various relationships between the genomes of different organisms, or between different genes in a given genome. This implicitly defines a graph, but I cannot put the graph explicitly in the form of a data structure that Python can manipulate, and, hence, I cannot use a ready-made graph library. So, I instead write an API to my system so that it can be probed and manipulated by other code as if it were a graph data structure.
Now, someone else might have written some nice graph code for, say, an approximated bipartite clique cover (or whatever) and I want to use that. In an ideal world, the clique partition code would be written using only an abstract notion of what a graph is (i.e. a protocol or interface/API) and I have implemented my hardware-based graph using the same graph notion/protocol. In this case I can simply write a small program that drops my hardware-based graph right into the clique partition code and it will work.
This ideal world scenario would only be possible, though, if some abstract graph notion or protocol is defined, so that both graph implementors and graph algorithm implementors can use it. The goal of this little project is, of course, to define such a protocol/API.
Note that the goal is not to implement a specific graph representation or a set of graph algorithms. The goal is only to mediate between developers of the two.
Preliminary ideas
General thoughts
Ideas so far include basing the API on the standard notion of using adjacency maps (such as dicts of neighbor lists), as described in Guido's well-known essay and used in these examples by David Eppstein, and using object adaptation (through the adapt() function, as described in PEP 246 and as used in PyProtocols) to allow access to graphs through various perspectives (such as adjacency maps, incidence maps, adjacency arrays, edge lists...). This would also allow graphs implementations with completely different interfaces to be adapted to a standard interface, and thus be used by generic graph algorithms.
An example of an existing graph library for Python, written by István Albert, may be found here. Note that this library is no longer maintained and its developers recommend using NetworkX instead (vide infra).
Bulbflow is an open-source Python persistence framework for graph databases. It uses Gremlin as the query language, and you can use it to connect to any Blueprints-enabled database, including TinkeGraph, Neo4j, OrientDB, Dex, InfiniteGraph, and OpenRDF.
NetworkX is another example of a graph library in Python.
python-graph a framework of generic graph classes and commonly used algorithms by Pedro Maitello. Under active development. The project aims to use pythonic conventions, and takes a modular approach to external dependancies.
graph-tool is an efficient python module for graph manipulation. It contains a comprehensive list of algorithms and network models, and integrates with GraphViz for visualization. It is implemented in C++ with the Boost Graph Library, which makes it orders of magnitude faster than implementations based purely on python.
py_graph is an example by Zach Frazier, partly inspired by Eppstein's example. No longer under development, the author recommends using NetworkX.
kjbuckets is a C extension and very fast, but imcomplete.
pypes appears never to have been released officially.
Bruno Preiss offers a very complete but somewhat unPythonic Graph type as part of an online book on data structures in Python. (Downloadable at the Opus7 package.)
Nathan Denny's graph library appears to be a fairly simplistic implementation.
Graphine is a Python 3 graph implementation with support for bridge, directed, and undirected multigraphs.
Pygr is billed as a "Python graph database framework for bioinformatics", and clearly aims to be more than just a graph library.
Gato, the Graph Animation Toolkit, is a visual tool intended to teach graph algorithms. It contains a fully functional graph library.
BOOST - how about BOOST? it seems to be well developed and has already Python bindings
pygraph, Beracah Yankama's pure python a/cyclic tk grapher for tk contains spring and hierarchical node placement algorithms, along with some basic classes for creating nodes & edges.
Graph::Easy for perl allows flowcharts to be defined in plain text and then outputted in multiple formats which is quite handy for web applications and creating diagrams via wiki-like mechanisms.
One possible underlying technology for graphs would be adjacency matrices using numarray. This approach would need to use sparse matrices to be practical for large graphs. The following library uses the numpy array and sparse scipy matrix for adjacency matrices: Another Python Graph Library.
Add your ideas here (Go wild, folks...)
- I think that the graph representation should be a redundant one, that allows the fast traversals, quick node, edge and neighbour lookups as well as fast iterations over all nodes or all edges. This will of course come at the expense of storage and/or graph initialization efficieny. For example in the python graph representation mentioned above (modeled after LEDA) the nodes and the edges are stored in a separate dictionaries. Each edge_id maps to a tuple of the head_id and the tail_id (the nodes) that form the edge. (Edge_ids are automatically created as they are added.) At the same time each node_id maps to a tuple of two lists corresponding to incoming and outgoing edges. (Istvan)
- IMO, one of the points of a standard interface is to let people choose their own representations. (Magnus).
- I believe that just as most people don't care how lists and dictionaries work behind the scenes they won't care (or want to have to deal with) picking a graph representation. The two representation that are listed in just about every computer science book, the adjacency matrix and the adjecency list representations are just about useless in the real world. These are what I would call a node centric view of the graph. It turns out in many probelms edges have far more utility.Graphs are a very rich methaphor and one rarely uses them in the stripped down version. What we need is a representation that is simple, fast and efficient enough in every case. (Istvan)
- This is not about giving people a graph library, but letting people who write graph representations and people who write graph algorithms interoperate more easily, by giving them a common interface. If people want to use a ready-made library, that's fine. The point is that people (like me) might want to represent graphs completely differently from the "textbook" version (in fact, compact graph representations is what my current research is about). It's the same with the DB API; by fixing a standard API, people can write programs that use databases without having to worry about which database or database library they use. I've added a use-case above to clear this up a bit. (Magnus)
- To write any graph algorithm, you need a set of standard methods. As far as I know, there are only two ways of getting this - either agree on a fixed interface which implementations