Planar graph layout, Pandemic

[diziet]

ceb gave me the board game Pandemic Rising Tide for Christmas. I like it a lot. However, the board layout, while very pretty and historically accurate, is awkward for play. I decided to produce a replacement board design, with a schematic layout.

I've done the data entry for the adjacencies etc. on the board. But I need to lay out the resulting planar graph. I could have laid it out by hand but because I'm a programmer and like doing things the hard way, I thought I would use a computer to lay out the graph.

This quite large yak has involved a number of smaller yaks.

Firstly, I discovered that there does not seem to be any good free software for layout of a planar graph given a planar embedding (eg, an ordered adjacency list for each vertex). There are a lot of complaints that graphviz doesn't work quite right: you give it a planar graph and it produces a non-planar drawing. And there is no way to specify the exact embedding anyway, so if it manages a planar drawing it might choose a different embedding (ie, a different layout) to the one you want.

So I thought I would tackle this problem. I was quite uncertain of success - this has been a research project for me. I've done a bit of reading of the academic literature and the problem has been studied but the actual production of a nice diagram for my problem seemed only to be tackled in a nonfree software package.

On Monday I succeeded at the hard part, well enough to be sure that project is actually going to bear fruit. What a relief. Here is the layout my program currently comes up with (This is a straight line drawing of the dual of the adjacency graph of the regions, roughly.)

To do this I have had to:

• Defeat cargo, the Rust curlbashware package manager, to let me have a local unpublished package ("crate" in Rust-speak) without committing to my own package source code the path on my laptop. This involved a horrendous wrapper script.
• Write a competent doubly-linked-list library for Rust.
• Write about a third of a planar graph handling library, including defining a file format, a minimal (and very poor) command line utility, an algorithm for computing duals, and so on.
• Write my own implementations of algorithms to make a planar graph biconnected, and to triangulate it, and to compute a planar canonical order. Boost has algorithms to do this but they do not let you specify the outer face. (Much research from Goossen Kant was very helpful, in particular[4].)
• Write and throw away a graph dual algorithm in Perl.
• Glue Rust to Boost's Chrobak-Payne planar straight line drawing algorithm.
• Glue Rust to GSL's simulated annealer (which I have used before) and hope for GSL siman to turn the very poor straight line drawing out of Chrobak-Payne into something pretty. Failure.
• Hunt for a better optimisation libraries and algorithms and come across NLopt[1]. Happily there was already a reasonable rust-nlopt glue library. Flail a bit glueing my existing cost function into NLopt's Sbplx[2] and Augmented Lagrangian algorithms[3]. Fix bugs in my code and one bug in rust-nlopt.
• Write a real-time graphical viewer for the graph layout optimiser's debugging output. I ended up using PyQt; this was a mistake. My natural inclination was to use Tcl/Tk, but I thought PyQt would do more of the job for me. I ended up redoing most of what I thought would be done for me, and I had to fight Qt on a number of points.
• Fix more bugs.

I will be writing more about this project, including publishing the relevant source code. But first I have some more tweaking etc. to do...

References:

[0]

M. Chrobak, T.H. Payne, A linear-time algorithm for drawing a planar graph on a grid, Information Processing Letters 54 (1995) 241-246.

[1]

Steven G. Johnson, The NLopt nonlinear-optimization package, http://ab-initio.mit.edu/nlopt

[2]

T. Rowan, "Functional Stability Analysis of Numerical Algorithms", Ph.D. thesis, Department of Computer Sciences, University of Texas at Austin, 1990.

[3]

Andrew R. Conn, Nicholas I. M. Gould, and Philippe L. Toint, "A globally convergent augmented Lagrangian algorithm for optimization with general constraints and simple bounds," SIAM J. Numer. Anal. vol. 28, no. 2, p. 545-572 (1991); G. Birgin and J. M. Martínez, "Improving ultimate convergence of an augmented Lagrangian method," Optimization Methods and Software vol. 23, no. 2, p. 177-195 (2008).

[4]

Goossen Kant, Algorithms for Drawing Planar Graphs (Algoritmen voor het Tekenen van Planaire Grafen), PhD thesis, Rijksuniversiteit te Utrecht, 14 June 1993.

(edit 2018-02-27 22:16 Z to fix formatting, add Subject, and tags; -28 00:23 Z fix formatting of xref to another DW)

Comments

[naath]

Peat Yak admires your dedication to shaving your yak pile. That is rather neat.