Learning F# - Graph Coloring using Microsoft Solver Foundation

• Download project - 6.1 KB
• Download sample graph file - 132 B

Introduction

As many people know, programmers are typically lazy. I'm not an exception to that rule, so instead of implementing from scratch a solution for my problem (see the section "Background"), I searched for a library that could do this for me. It turned out that Microsoft Solver Foundation was the right choice. However, it didn't provide a clear, suitable for beginners example in F#. I found a nice C# one here and decided to translate it to F#. The main point of this tip is to let you know about some tricky points I found.

Background

The background for this project is a bit complicated and can be expressed as "a series of coincidences".

1. Not so long time ago, I started learning F#. After few first bad impressions ("My God - why is that so much immutable ??!"), I started getting on well with this language so that now I can't even imagine how could I live (i.e. "do programming" - in other languages like C++) without some features.
2. For some time, I've been playing with Project Euler - this thing can really blow somebody's mind up, can't it? One day, I got stuck solving a Sudoku problem. I knew there must a more elegant solution than brute force, but didn't know that at that moment.
3. You know coursera.org, don't you? There's a really cool course called Discrete Optimisation. I learnt a lot of great stuff there. Also - the professor mentioned some CSP (Constraint Programming) methods and the course resources contained a link to some useful libraries. "Cool" - I thought - "This will surely come in handy with my PE problem".
4. Searching for the most appropriate tool, I found MS Solver Foundation. As always, I wanted to kill two birds with a one stone and decided to give it a try using F#. The problem was I couldn't find an example in that language, so I had to translate one written in C#. However, there were some problems.

Using the Code

The project I attached to the tip was created using Visual Studio 2012. Moreover, you need to download Microsoft Solver Foundation (e.g. from here) and add a reference to your project (important: this requires your project to use .NET 4.0). Last but no least, I set a default cmd argument in project properties, so you can easily run the code from VS. You can also build it and run from command line, specifying your own file.

Part I: Translating

When I started translating, I thought "Naah, big deal - it's enough to replace definitions with let-bindings". As a result, when I saw a piece of code in C#:

Model model = context.CreateModel();

I replaced this with an F#-equivalent.

let model = context.CreateModel()

However - As you might expected, life was more brutal than it initially seemed to be. The first problem arose with the sequence:

Domain colors = Domain.Enum("red", "green", "blue", "yellow");
Decision be = new Decision(colors, "belgium");
Decision de = new Decision(colors, "germany");
Decision fr = new Decision(colors, "france");
Decision nl = new Decision(colors, "netherlands");
model.AddDecisions(be, de, fr, nl);

model.AddConstraints("borders", 
  be != de, be != fr, be != nl, de != fr, de != nl);

Literate translation caused the compilator to complain:

No good, but what could I do? I started searching on MSDN. The argument required by AddConstraints method should be of type Term. A quick look at the reference guide here and everything started to make sense. There is an implicit conversion from bool to Term...

... but F# DOESN'T support implicit conversions! So I had to make this "more explicit". There are several ways of doing so, but I think that defining an operator is the most convenient one.

let (!=) (d1 : Decision) (d2 : Decision) = Term.op_Inequality(d1, d2)

Part II: Extending the Code

That was enough to run the code. However, in the current version application was only able to tell you that it is possible to color the given map with 4 colors. That's far too little! I had my file with a graph and expected the application to read this and tell me if e.g. this can be colored with a given number of colors. The format of an external file was pretty straightforward:

N E
V1 U1
V2 U2
...
VE UE

where

• N - number of vertices
• E - number of edges
• Vi Ui - an edge from Vi^th to Ui^th vertex

An example of this would be:

4 3
0 1
1 2
1 3

I decided to pass the file's name as an application parameter instead of hardcoding it in the source. Also, I needed an additional data structure, but defining such in F# is ridiculously simple:

type Edge =
    {
        V1 : int
        V2 : int
    }

The code that parses data from a file is an example of what I love F# for:

let header, items = 
        File.ReadLines(argv.[0])
        |> Seq.map parseToTuple
        |> Seq.toList
        |> function
           | h::t -> h, t
           | _    -> failwith "Wrong data format"

    let N, E = header
    let Edges = List.map (fun (v1,v2) -> { V1 = v1 ; V2 = v2 } ) items |> Array.ofList

An equivalent code in C# would take at least twice as much space, wouldn't it?

Anyway - the next step was to do something about the Domain object. I'm a man, so I know only 8 colors. I believe there are graphs that require more of them, so I decided to change strings to ints in a Domain's definition. Luckily, it offers IntegerRange method. However, when I tried an obvious way of using it:

Deja vu ? Again - quick check on MSDN. Rational class supports implicit conversions from int. Fortunately, I know how to deal with the problem:

let rat (i : int) = Rational.op_Implicit i
let colors = Domain.IntegerRange(rat 1, rat maxNum)

Much better now. And the whole application is much more flexible now.

Part III - Going crazy!

After all of that, I decided to go crazy and extend the application even further. I wanted it to let me know the MINIMAL number of colors necessary for a given graph. However, with F#, this turned out to be trivial. I simply moved my whole solution to a function called solveUsingGivenSet which takes a number of colors available. Then I used F#-seq:

seq { 2 .. N } |> Seq.pick solveUsingGivenSet |> printfn "%s"

Seq.pick iterates through the elements of a given seq, applying a function to each of then. If the function returns "None", then the next item is evaluated. If the result of the evaluation is "Some x", then the iteration is stopped and "x" gets returned.

Pfeeew... that's it. "A little bit" of work ;).

Points of Interest

The most important thing I learnt is that F# doesn't support implicit conversions. I found one post on SO explaining this. Also, I found it nice to use Microsoft Solver. I've never seen such a library before and the opportunities it gives seem to be awesome!

Last thing - I believe there's a better way of using Microsoft SF in F# than a naive code translation, but couldn't find any example that would be simple enough to learn something without much pain. Moreover - the code itself isn't too efficient. Works fine for small problems, but not for larger ones. If you see any ways of improving it - feel free to shout! ...

... but - since I mentioned I'm lazy - this may take me a while to respond ;).