TORTOISE stands for To be Optimal Run Time O(N^M) Is Slow Eventually, HARE stands for Heuristically Agglomerates Rivals Efficiently.
How to run our gAIrrymander project:
- Clone the repository to your local machine.
Server.javain your IDE of choice, or open a terminal,
cdinto the folder that contains your cloned
gairrymanderfolder, and enter
javac gairrymander/*.java && java gairrymander.Server, and you should see the port (likely
8000) printed in the terminal, indicating the server is running.
- Open a web browser and navigate to
http://localhost:8000/, which should display a map of Oregon. Choose a party and algorithm and click the Submit button. A graph of counties should appear momentarily, as well as the election results of each district in the top right corner!
- If you encounter
FileNotFounderrors, try replacing the file paths in
Gerrymanderer.javaline 20 and
Server.javalines 38, 51 with the absolute paths to the files.
gAIrrymander is a web app that takes the user input of a political party and specified algorithm and then displays the optimal gerrymandering of the state so that the chosen political party has a majority in the most districts. Gerrymandering is the act of redistricting the congressional district boundaries to favor a certain party. This takes place every ten years after the census. Gerrymander appears in two main forms: cracking and packing. The first algorithm, TORTOISE, creates an optimal solution to gerrymander a state while the second algorithm, HARE, uses the packing strategy to gerrymander a state. Because it has to check all combinations, the TORTOISE algorithm runs slower than the HARE algorithm. At the moment, our program displays the districts in a rectangular grid to represent the graph inside the map of Oregon and a label describing the political party and which numbered district it is a part of. This project can be scaled up to work with other states given more state voting data. The graph can also be improved to show the geographical size of the gerrymandered states. The purpose of this is to give a fun way for students to learn about gerrymandering.
Our objective is to group counties/precincts/other subdivisions in a state into congressional districts to gerrymander in favor of a particular party. We assumed the following guidelines for a valid map: Districts are congruent; i.e. every precinct in a district is adjacent to another precinct in the district. Districts have roughly equal population, within 10% error of the average district population (total state population / number of districts). Disclaimer: Individual states may have different or additional redistricting guidelines, including preserving county boundaries, protecting special interest groups, and not disadvantaging minorities from electing their representatives of choice.
Why a graph? We chose to represent the map of precincts using a graph data structure because we needed to store the adjacent precincts of each precinct to ensure districts are contiguous, so a graph naturally lent itself to such a structure. We implemented a generic undirected graph with an underlying map of precincts to adjacency lists, which are LinkedLists of adjacent precincts. A graph with a generic type allows us the flexibility to change the node type if needed. The graph is undirected because precinct adjacency is bidirectional.
Precinct.java < District.java
The Precinct class represents any subdivision of a state. We originally planned to use precincts, hence the name, but our algorithm was too slow for thousands of nodes, so we used county data instead. A precinct contains relevant fields such as a unique precinct code used to assert equality between two precincts, population, percent Democratic voters, boolean for whether it is majority Democrat, district (initially unassigned), and x and y coordinates for drawing on the map. We only stored information about one party, assuming the two-party system meant the rest of the voters were of the opposing party. Precincts are comparable by their percent Democrat voters for our HARE packing algorithm, which requires sorting precincts by the highest percentage opposition.
The District class represents a congressional district, including population, Democrat population, and a set of precincts in the district. We kept the Democrat population instead of percentage because we needed to easily modify those values when adding and removing precincts.
The Gerrymanderer class is an AI that optimally groups precincts into districts so that a party has the highest majority in the most districts. It requires the state population, number of precincts, number of districts, and array of precincts, and declares an error margin (default 10%), empty graph to be populated by the user or automatically by the rect method into a rectangular graph.
TORTOISE (To be Optimal Run Time O(N^M) Is Slow Eventually) is a recursive optimization algorithm that uses choose-explore-unchoose to check all possible district combinations and output the most optimal solution. The method, called
gerrymander, takes an average precinct population and boolean for whether to gerrymander for Democrats, and passes those into a helper method along with an arbitrary root precinct, a set of unvisited precincts, and the current district. The method returns a set of districts, or null if there is no solution. At each precinct, the algorithm removes the precinct from the unvisited set, adds it to the current district, and recursively calls the algorithm to include each adjacent precinct to find the most optimal result. If a district is full within the error margin, a new district is created. If the district population exceeds the error margin, the algorithm returns null. An obvious issue with choose-explore-unchoose is the unconscionable runtime complexity beyond some tens of precincts (we chose Oregon’s 36 counties since it isn’t too terrible), so we attempted to memoize the algorithm, but due to the frequent copying of data structures to avoid object modification, it actually increased runtime.
HARE (Heuristically Agglomerates Rivals Efficiently) is a packing algorithm, called
pack, that takes in the same parameters as TORTOISE but first sorts the graph adjacency lists by opposition percentage from highest to lowest, then begins at the root precinct with the highest percent opposition. It has similar logic as TORTOISE, but does not “unchoose” and thus will run once-through in the best case, giving a complexity of O(N). It will only backtrack if the current district combination is invalid.
Server.java & Map.html
Our Java HTTPServer is hosted locally and serves the webpage Map.html and our backend code to the user. When the user sends a request with a party and choice of algorithm, the server responds with the gerrymandered graph in JSON form so the nodes and edges can be drawn on the map using Leaflet.js. Each precinct is a blue or red node for majority Democrat or Republican and is labeled with D or R and its assigned district number. The hypothetical election results for each district is displayed in the top right. Our demo is a graph of Oregon counties from 2020 election data, but we hope to include all the states in the future. We would also like to draw the actual district boundaries on the map instead of a graph representation in the future. We could not find data on the county adjacencies, so we initialized a rectangular graph.