Minority Opinions

Not everyone can be mainstream, after all.

Yet Another Graph Class

leave a comment »

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.

Advertisements

Written by eswald

1 Jul 2010 at 10:15 am

Posted in Python

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s