Graph Colouring, Part Five

Graph Colouring, Part Five

Rate This
  • Comments 14

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:

 

var offsets = new[,] {
/*rows*/    {new[] {0, 4, 8, 12}, new[] {0, 1, 2, 3 }},
/*columns*/ {new[] {0, 1, 2, 3},  new[] {0, 4, 8, 12}},
/*squares */{new[] {0, 2, 8, 10}, new[] {0, 1, 4, 5}}};
var cliques =
    from r in Enumerable.Range(0, 3)
    from i in offsets[r, 0]
    select (from j in offsets[r, 1] select i + j);
var edges = CliquesToEdges(cliques);
var graph = new Graph(16, edges);
var solver = new Solver(graph, 4);

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.

 

  • 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!

  • 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.

  • I await your next NP-Complete segue with interest :)

  • 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).

  • Exercise: Extend this program so it also reports whether the solution is unique, a detail often lost in Sudoku puzzle creation.

  • @oldnewthing: That's boring.  All it takes to do that is to mark the first solution found as invalid, thus forcing the backtracker to search for an alternative solution.

  • @Brian: Or change the line in Solve():

    from

       return solutions.FirstOrDefault();

    to

       return solutions.First();

    if you want an exception for non-unique solutions

  • rofl what a nice surprise. a sudoku solver is a nine-colorer of some specific graph.

  • @configurator: Toget an exception for a non-unique solution you would use:

      return solution.Single();

  • Now what;s the chances for a solver for next weeks lotto?

  • 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.

  • @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 :-)

  • @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.

  • 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.

Page 1 of 1 (14 items)