Graph Colouring, Part Five

[アーティクル]
07/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:

public static IEnumerable<Tuple<int, int>> CliquesToEdges(IEnumerable<IEnumerable<int>> cliques)
{
return
    from clique in cliques
    from item1 in clique
    from item2 in clique
    where item1 != item2
    select Tuple.Create(item1, item2);
}

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:

var offsets = new[,] {
/*rows*/ {new[] {0, 9, 18, 27, 36, 45, 54, 63, 72}, new[] {0, 1, 2, 3, 4, 5, 6, 7, 8}},
/*columns*/{new[] {0, 1, 2, 3, 4, 5, 6, 7, 8}, new[] {0, 9, 18, 27, 36, 45, 54, 63, 72}},
/*boxes */ {new[] {0, 3, 6, 27, 30, 33, 54, 57, 60}, new[] {0, 1, 2, 9, 10, 11, 18, 19, 20}}};

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:

Graph graph = new Graph(81, edges);
var solver = new Solver(graph, 9);
string puzzle =
" 8 274 " +
" " +
" 6 38 52" +
" 32 " +
"1 7 4" +
" 92 " +
"78 62 1 " +
" " +
" 384 5 ";

int node = -1;
foreach (char c in puzzle)
{
    ++node;
    if (c == ' ') continue;
    solver = solver.SetColour(node, c - '1');
}
var result = solver.Solve();
int i = 0;
foreach (var r in result)
{
    Console.Write(r + 1);
if (i % 9 == 8)
        Console.WriteLine();
    ++i;
}

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.

Comments

Anonymous
July 28, 2010
Very sneaky, Eric. Honestly though, whenever you talk about the power of linq I remember a book from 1984 - Structure and Interpretation of Computer Programs. When it speaks of Streams, it's really talking about linq. If you want a couple of video lectures from '86 check out ocw.mit.edu/.../video-lectures - sessions 6a and 6b implement, use and discuss something very close to LINQ in Scheme. It makes me happy that these programming techniques I used when I was a kid are now available in a mainstream language... But it's sad that it took over 20 years. Have fun in your vacation!
Anonymous
July 28, 2010
Nice work Eric - though you pre-empted my idea for a blog post! I sensed this conclusion coming a couple of days ago when I was mulling over in my own mind how to write a Sudoku solver and realised there was a connection was colouring graphs.
Anonymous
July 29, 2010
I await your next NP-Complete segue with interest :)
Anonymous
July 29, 2010
Funny, I was thinking in the opposite direction of Samual Jack, and wondering if a Sudoku solver could be used to achieve graph coloring. More precisely, I was thinking about was Donald Knuth's "Dancing Links" (AKA DLX) algorithm, which is a recursive backtracking algorithm which can solve instances of the exact cover problem (e.g. Sudoku).
Anonymous
July 29, 2010
Exercise: Extend this program so it also reports whether the solution is unique, a detail often lost in Sudoku puzzle creation.
Anonymous
July 29, 2010
The comment has been removed
Anonymous
July 31, 2010
The comment has been removed
Anonymous
August 02, 2010
rofl what a nice surprise. a sudoku solver is a nine-colorer of some specific graph.
Anonymous
August 03, 2010
@configurator: Toget an exception for a non-unique solution you would use: return solution.Single();
Anonymous
August 05, 2010
Now what;s the chances for a solver for next weeks lotto?
Anonymous
August 17, 2010
There is an optimized way of doing this by using a square matrix to represent transitions between nodes and then using matrix multiplication to find the transitive closure of the matrix. The memory footprint, upper bound on the number of multiplications and performance information is known ahead of time for this implementation.
Anonymous
September 08, 2010
@Greg - if you claim that graph coloring is solvable by doing transitive closure with matrices please present the solution or leave a reference. Or even just for Sudoku. Not kidding - it's considered to be NP-complete and transitive closure is computable in N^3, so just in case that there might be a golden shortcut in some corner of the internet - one never knows :-)
Anonymous
October 04, 2010
@Eris - awesome post. @All - anybody knows other blogs where somebody would explain other algorithms from real world with a step by step implementation. I hate those blogs with theory only. :) Eric rules with his posts.
Anonymous
May 01, 2011
The Status property fails (returns Solved) in degenerate case when required number of colours = 1. Some check must be added. I think Eric would do it in the most elegant way. The whole job is just marvellous (breathtaking). Thank you very much, Eric.

次の方法で共有

Graph Colouring, Part Five

Comments

その他のリソース