Friday, 25 May 2012

Graph coloring in F#

Eric Lippert of the Visual C# compiler team at Microsoft wrote a fascinating series of five blog posts about graph coloring. The articles develop a C# program with 20 lines of code devoted to defining the problem (coloring the planar graph of borders between 13 South American countries) followed by another 200 lines of C# code to solve the graph coloring problem. In the fourth article, this culminates in the solution 0, 1, 2, 1, 2, 1, 0, 2, 0, 1, 2, 1, 3 that uses just three colors to solve the problem.
Let's solve the same problem using the F# programming language instead. We begin by defining the problem using a union type to represent the countries and nested lists to represent the adjacencies:
type Country =
  | Brazil | FrenchGuiana | Suriname | Guyana | Venezuala | Colombia
  | Ecuador | Peru | Chile | Bolivia | Paraguay | Uruguay | Argentina
let countries =
  [|Brazil; FrenchGuiana; Suriname; Guyana; Venezuala; Colombia;
    Ecuador; Peru; Chile; Bolivia; Paraguay; Uruguay; Argentina|]
let edges =
    Brazil, [ FrenchGuiana; Suriname; Guyana; Venezuala; Colombia;
              Peru; Bolivia; Paraguay; Uruguay; Argentina ]
    FrenchGuiana, [ Brazil; Suriname ]
    Suriname, [ Brazil; FrenchGuiana; Guyana ]
    Guyana, [ Brazil; Suriname; Venezuala ]
    Venezuala, [ Brazil; Guyana; Colombia ]
    Colombia, [ Brazil; Venezuala; Peru; Ecuador ]
    Ecuador, [ Colombia; Peru ]
    Peru, [ Brazil; Colombia; Ecuador; Bolivia; Chile ]
    Chile, [ Peru; Bolivia; Argentina ]
    Bolivia, [ Chile; Peru; Brazil; Paraguay; Argentina ]
    Paraguay, [ Bolivia; Brazil; Argentina ]
    Argentina, [ Chile; Bolivia; Paraguay; Brazil; Uruguay ]
    Uruguay, [ Brazil; Argentina ] 
These are the vertices and edges of our graph.
The countries of South America are, of course, a planar graph so we know they can be assigned colors with no two adjacent countries having the same color using a total of no more than four different colors. Let us define the set of all four possible colors as follows:

let allColors = set[0..3]

The graph coloring problem may then be solved by adding our vertices and edges to an empty graph, generating a sequence of possible colorings at each step:

let solve (V, E)  =
  ((Set.empty, seq[Map.empty]), V)
  ||> Seq.fold (fun (vertices, solutions) vertex ->
    let neighbors =
      [|for src, dsts in E do
          if src = vertex then yield! Set.intersect vertices (set dsts) else
            for dst in dsts do
              if dst = vertex && Set.contains src vertices then
               yield src|]
    Set.add vertex vertices,
    seq { for color in solutions do
            for newColor in allColors do
              if Seq.forall (fun u -> color.[u] <> newColor) neighbors then
                yield Map.add vertex newColor color })

Eric's result may then be obtained by taking the first of the valid colorings and using it to enumerate the colors of each country in turn:

let answer =
  let _, colors = solve (countries, edges)
  let color = Seq.head colors
  [ for country in countries -> color.[country] ]

Remarkably, we have solved the same problem in just 19 lines of F# code! One can only imagine how much simpler Microsoft's Roslyn compiler could have been had it been written in F#...

No comments: