Generating random planar graphs

I am a great fan of the QuickCheck testing library for Haskell and have been using it for some time now. If you don't know about it stop reading this immediately and go read the original ICFP paper. Alternatively (for the impatient) browse the article on Wikipedia which also refers to some re-implementations in other languages.

QuickCheck can be seen as two domain-specific languages embedded in Haskell: one for generating test data and another writing properties of Haskell programs (and also collecting coverage statistics). But you can also use QuickCheck to generate complex input data for programs in any language.

The example I am reporting came up when setting up a problem for TIUP, a locally organized ACM-style programming contest for undergraduate students. The competitors must solve a number of coding problems in C/C++, Java or PASCAL. The solutions are tested automatically by running the programs against a number of hidden test inputs to assess output correctness (and perhaps efficiency by imposing time and space limits).

For my particular problem, the inputs are planar graphs representing a city road map. I used Haskell and QuickCheck to generate random planar graphs of increasing size. The idea is simple (and probably not original): start with a regular mesh and randomly delete some edges; some care is needed to avoid disconnecting the graph and avoid leaving nodes with a single outward edge (for esthetical reasons).

Here are some examples of generated graphs with 25 nodes and an increasing number of edges removed.

Full mesh

20% random edges removed

50% edges removed

You can download the source file here: Graph.hs. This Haskell script generates some random graphs and invokes graphviz to render them. It is very short (around 120 lines) and, I my opinion, quite readable; it should also be easy to modify. The functional programming "idioms" like parametric polymorphism, higher-order functions, list comprehensions and point-free style really shine on this kind of problem.