Though not a federal standard, contiguity is the most common state-applied standard for district maps, and therefore is an important feature to be able to guarantee in any automated redistricting program. Put simply, one should be able to walk from any point in the district to any other point in the district without having to cross a district boundary.
Contiguity checks can be useful in other contexts, too. For example, when examining the changes made between a proposed district plan and its amended version in the redistricting process, it is relatively simple to generate statistics on, say, the people who were moved out of a particular district. But it’s possible that two different chunks of people were moved out, from opposite ends of the district and with different demographic profiles, or perhaps more than a dozen different chunks (see: changes to congressional district 5 in the Florida redistricting process). Sorting out the different groups can be done visually with a program like ArcGIS, but if you’re doing this process on a number of different districts in a number of different maps, it’d be nice to have an algorithm to separate out the pieces for you.
The process assumes a certain organization of your data. I use a large associative array, or dictionary object in Python, where each member represents a subunit of geography I want to build into districts – I’ll refer to these as blocks, although they can be whatever you’d like (Census tracts, voting precincts, etc.). The index for each member is a unique ID for the block, such as the Census GEOID, and the value is an array of information that will be used during the redistricting process. What is included depends on what factors you’re drawing on, but for this algorithm, you’ll need at least the district the block is currently assigned to, and a list of blocks that are adjacent to that block.
Two new lists drive the algorithm. The first is a list I’ll call the block list, with an index for each block in the district you’re checking contiguity for, and each value set to null to begin with. The second is the chunk list, which will ultimately tell you how many non-contiguous chunks the district is broken into (the hope is for just one, referring to a fully contiguous district), and it starts out empty. In the end, the value of each member of the block list will be an index for the chunk list.
Create a subset of your map-wide associative array that contains just the blocks that are in the district you’re interested in, and we’ll step through each member one by one (it doesn’t need to be sorted in any particular fashion).
The loop starts by taking the next block in the associative array subset. There are two possibilities: either its value in the block list will still be set to null, or it will have been given a value in a previous iteration. If it is null, add a new member to the end of the chunk list, with the value set equal to its index. Then, take that index number, and assign it as a value in the block list for the block you’re working with, and remember it as the working chunk number. If the block already has a value in the block list, your working chunk number is the value in the chunk list indexed by the value in the block list.
Next, pull the list of neighboring blocks for your current block, and step through each one. First, check if the neighbor is in the same district as your current block; if not, skip it. If it is, check to see if it has a value in the block list. If it doesn’t, set it to the working chunk number, and move on to the next neighbor. If it does have a value, check to see if the value in the chunk list indexed by the block list’s value is the same as the working chunk number; if so, move on. If not, note the neighbor’s chunk list value as the neighbor chunk number. Then, step through the chunk list, looking for any value that matches the neighbor chunk number, and reassign the value to the working chunk number.
That’s it. After going through every block in the district, count the number of unique values in the chunk list, and this will be the number of non-contiguous chunks you have – again, hopefully it’s just one. To know which chunk a particular block is in, use its value in the block list as an index in the chunk list.
Unfortunately, I don’t have the formal training in algorithms to tell you what sort of time this operates in, or how it compares to other potential approaches, but in practical testing, this was the quickest method I came up with. If you want to see a Python implementation of it, check out my automated redistricting script on my GitHub (the contiguity check starts at line 563).