## Yet Another Graph Class

I found myself wanting a class for a couple of operations on a directed acyclic graph. In particular, I needed to add vertices, add edges if and only if they wouldn’t create a cycle, collect all of the root vertices, remove those roots with any respective edges, and check whether any vertices were left. In Python, with a license that I wouldn’t feel bad about uploading to Google Apps.

It turns out that there are are quite a few packages already available for working with graphs. The first one I found, after a very simple PyPI search, was graph. It’s a fairly simple package; two python modules, a few test cases, and something resembling documentation. The test cases showed me how to create a graph and add edges and vertices to it, and I even figured out a way to check whether a new edge would create a cycle. I was a bit surprised that a new edge got added to the graph before I had explicitly added it, but even that wouldn’t be a problem for my use case.

However, everything pointed to a license file that didn’t exist. The setup.py file mentioned something about a “modified” PSF license, so it’s probably open source, but I wasn’t entirely sure. On top of that, it simply felt like I was making the program do more work than it really needed to.

After that, I took a look around a few other places. The python-graph module showed up in my next search, but seemed like it had quite a bit of functionality that I really didn’t need, without any obvious way to do what I did need. There are several wrappers for C-based libraries, but I need pure Python for this app. There are abstract base classes attempting to help them all work together, but I don’t really care about the ability to switch my underlying tech. Then there’s Guido’s essay on using dictionaries as graphs, which probably influenced my final design.

In the end, everything I really needed fit into a single class, mostly a wrapper around a single dictionary. This implementation could be considered backwards, but that makes the most complicated method simple. It is by no means complete, but it fits my needs perfectly.

class Graph(object): r'''Directed acyclic graph structure. Reconnecting branches are allowed, but cycles are prevented on edge creation. '''#"""#''' def __init__(self, vertices): r'''Create a new Graph. `vertices` is a sequence of distinct hashable objects. '''#"""#''' # Store the inbound connections in a dictionary. # Outbound would make remove() easier, but roots() harder. self.vertices = dict((v, set()) for v in vertices) def edge(self, source, sink): r'''Create an edge from the source to the sink, as long as the graph remains acyclic. `source` and `sink` must be vertices. Returns whether the edge was created. '''#"""#''' connected = set() while connected: inbound = self.vertices[connected.pop()] if sink in inbound: return False connected.update(inbound) self.vertices[sink].add(source) return True def roots(self): r'''Collect the vertices with no inbound edges. These are the roots of the tree. '''#"""#''' return [key for key in self.vertices if not self.vertices[key]] def remove(self, vertex): r'''Remove a vertex from the graph. '''#"""#''' del self.vertices[vertex] for inbound in self.vertices.values(): inbound.discard(vertex) def __nonzero__(self): r'''Truth value for the graph. A Graph is true if it contains any vertices. '''#"""#''' return bool(self.vertices)

I don’t expect anyone else to find it particularly helpful, but if you do, feel free to use it.

## Leave a Reply