Graph Reduction in Linear Time

This is an implementation of an algorithm discovered by Arnborg, Courcelle, Proskurowski, and Seese. They discovered that, using rewrite rules, you can determine, in linear time, whether a particular graph of bounded treewidth has a property that is describable in monadic second order logic. (Whew. That's a mouthful.) Unfortunately, the proof was non-constructive, which means tht you are on your own if you want to automagically generate an algorithm that checks whether or not a set of graphs has a particular property or not.

This directory contains two implementations of the concept

n_to_the_k/: My first attempt, this code works, but it is not the super-cool linear time algorithm described in the paper. This particular algorithm is O(n^k) due to it being a naive implementation, although it does contain some pleasingly opaque generator-based code to generate all combinations of all permutations that was lifted from Knuth.
Note that this implementations is not quite correct - at the end it only checks whether or not your graph is equal to the null graph or the single point graph, rather than whether or not the reduced graph is isomorphic to any of the set of representatives. This is fine for the reduction sets I implemented, but not all sets have only those as their representatives - you have been warned.
linear/: This is the second attempt at the algorithm. As of 9/5/3 it works as well! It runs in O(n) (expected) time!