Thursday, July 29, 2010

I said last time that I was interested in finding colourings for graphs that have lots of fully connected subgraphs, aka "cliques". For instance, I'd like to find a four-colouring for this sixteen-node graph:

Yuck. What a mess.

What this graph is doing a bad job of conveying is that there are twelve fully connected subsets. {0, 1, 2, 3} forms a clique. So does {0, 1, 4, 5}. And so does {0, 4, 8, 12}.

It would be great if I had a better way to display full connectedness. How about this: I'll just draw a dotted ellipse around a fully connected subset, and you can then mentally fill in all the edges:

Hmm. That might not actually be better.

Anyway, you get the idea. What would be really nice is if I had a way to cleanly represent this in code. What I want to do is somehow take the concept of a sequence of fully connected subsets:

{0, 1, 2, 3}, {4, 5, 6, 7}, {8, 9, 10, 11}, {12, 13, 14, 15},
{0, 4, 8, 12}, {1, 5, 9, 13}, {2, 6, 10, 14}, {3, 7, 11, 15},
{0, 1, 4, 5}, {2, 3, 6, 7}, {8, 9, 12, 13}, {10, 11, 14, 15}

and turn that into a list of edges: {0, 1}, {0, 2}, {0, 3}, {1, 0}, {1, 2}, ...

If I end up with some of the edges on the list twice, who cares? I've implemented my graph as a Boolean array; no problem if I set one of the entries to true twice.

This is easily done with LINQ:

 Now, I suppose we could just make an array of arrays with all the numbers I listed above. But notice somthing about the pattern: 

 In that first line, we start with {0, 1, 2, 3}. Then we add four to each: {4, 5, 6, 7}. Then we add eight: {8, 9, 10, 11}. Then we add twelve: {12, 13, 14, 15}.

In the second line, we start with {0, 4, 8, 12}. Then we add one: {1, 5, 9, 13}. Then we add two. Then three.

In the third line, we start with  {0, 1, 4, 5}. Then we add two, eight and ten.

In short, we could write a generator for the subsets if we wanted to, by noting down the patterns:

And if we solve that  we get the colours 0, 1, 2, 3, 2, 3, 0, 1, 1, 0, 3, 2, 3, 2, 1, 0 for the 16 nodes:

And sure enough, every fully-connected subset with an ellipse around it has no two nodes of the same colour. Neat!

But let's not stop there! What if instead of sixteen nodes we had... eighty-one! And what if instead of twelve fully-connected subsets, we had... twenty-seven!

And what if we knew ahead of time what some, but not all of the colourings were?

First off, we can modify our subset generator easily enough:

The generation of the cliques and edges is the same. Let's make a solver for that graph and then restrict some of the colour choices ahead of time:

And we get the output 

358127469
279654831
461389752
847916325
135278694
692435187
784562913
516793248
923841576

Holy goodness! There I was, minding my own business, trying to solve problems in graph theory and I accidentally made a Sudoku puzzle solver! Isn't it funny how life turns out sometimes? But that's just how awesome LINQ is. 

And with that surprising result, I'm off to my ancestral homeland to spend a couple weeks visiting family and friends. We'll pick up with more Fabulous Adventures in September.