TopoColour

TopoColour uses graph theory to colour polygon layers. Furthermore it can save the adjacency as a DOT format file and create a layer showing the adjacencies.

Instructions

Start

QGis plugins must be installed and then activated from the plugin menu. TopoColour adds one option to an entry in the Plugins menu. Start by running it from there.

You'll need a polygon layer to work on. Here I'll show you how to colour the countries of Africa so that no two adjacent polygons are in the same colour. I load my Africa shapefile and it looks like this:

Choose Layer

When I start the plugin it asks me for a layer and attribute. I use the CNTRY_NAME attribute which is unique for countries.

Choose Colouring

Once I've selected the attribute the plugin computes the adjacency between polygons in the layer. This may take some time, so a progress dialog allows you to cancel it. Beware that large layers may be very slow at this point, or even crash QGis if memory becomes a problem.

When the adjacency is computed, the main tabbed dialog appears. The first tab is the Graph Colouring tab.

Graph colouring, or vertex colouring, is an operation in graph theory. In our case the graph nodes are countries and the graph edges represent adjacencies between countries. Our colouring algorithm assigns numbers to the nodes so that no two directly connected nodes have the same number.

The plugin may eventually have a selection of colouring algorithms. Choose one from the dropdown box and click 'Compute Colouring'. This will then work out how many colours are needed for the graph and display this on the dialog. If the algorithm has randomness in it, you could try computing it again to get a different number of colours. For example, the current Greedy algorithm chooses which node to work on randomly. In the text below the algorithm buttons you'll see a list of the adjacencies in the map.

When you are happy with the graph colouring you can move on to the Layer Style tab

Layer Styling

This dialog lets you choose a colour scheme and style for the layer. The colour palettes are derived from Color Brewer qualitative palettes. You can also choose the line width, style, and colour. When happy with your choice, hit 'Apply'.

Finished Product

Now you can see the result - a map of Africa with no adjacent countries the same colour.

Other Features and Notes

Adjacency Layer

If you click the "Add Adjacency Layer" button then a new layer will appear on your map. This shows which features are adjacent to which other features. Note that the point used for a feature is the centre of the bounding box, so there's no guarantee that it will lie within the feature's polygons. Each line has an attribute giving the attribute values of the nodes it connects. Here's what the African adjacency layer looks like: The layer is kept in memory, so save it as a shapefile to preserve it.

Save DOT file

This button lets you save the adjacency as a DOT format file. This is not a map or GIS format, and only stores the connections between polygons. DOT files can be visualised and mapped in various ways. Check out GraphView for more information.

Algorithm Details

Greedy

This operates as follows:

start with all nodes uncoloured
repeat:
  pick an uncoloured node at random
  colour this node with the smallest integer
       not contained in the set of adjacent node colours
  for all nodes
This algorithm has randomness, so repeated application may result in different numbers of colours needed.

Planar Graphs and The Four-Colour Theorem

In theory, all polygon maps without overlaps or exclaves should be colourable with 4 colours or fewer. This is the famous (infamous?) Four-Colour Theorem. In practice GIS data sets will probably need more, and anyway an algorithm to find a four-colouring could be complex. Given that a GIS data set might not even be planar because of features being non-contiguous (e.g. having islands).

Credits

Written by Barry Rowlingson <b.rowlingson@lancaster.ac.uk>