Updaters

Depending on the questions you are investigating, there are many different values you might want to compute for each partition in your Markov chain. If you are interested in compactness, you might want to compute the area and perimeter of each part of the partition so that you can compute compactness scores. If you are interested in partisan lean, you might want to compute hypothetical election results using the districts defined by the partition.

The Partition class allows you to define custom properties for the partitions in your Markov chain. You can do this by providing a dictionary of updater functions when you first create a partition.

import networkx
from gerrychain import Partition, Graph

# Use NetworkX to create a graph
nx_graph = networkx.Graph()
nx_graph.add_edges_from([(0, 1), (1, 2), (2, 0)])

# Create a GerryChain Graph object from the NetworkX Graph object
graph = Graph.from_networkx(nx_graph)

assignment = {0: 1, 1: 1, 2: 2}


def my_updater(partition):
    return "Hello!"


partition = Partition(graph, assignment, {"my_custom_property": my_updater})

print(partition["my_custom_property"])

Hello!

This partition and all subsequent partitions in the chain will have this my_custom_property attribute. If we flip a node in partition to create a new partition, we can still access this property:

new_partition = partition.flip({1: 2})
print(f"Are the partitions different? {new_partition is not partition}")
print(new_partition["my_custom_property"])

Are the partitions different? True
Hello!

Useful Updater Functions in GerryChain

The gerrychain.updaters submodule provides some updaters for common tasks like aggregating data and computing the cut edges of a partition:

• Tally: Aggregates a node attribute (e.g. population) over each part of the partition.

• cut_edges: Returns the set of cut edges (edges whose nodes are in different parts of the partition) of the partition. This is required for most of the proposal functions in gerrychain.proposals.

Here is an example using both of these updaters:

from gerrychain.updaters import cut_edges, Tally

# Use NetworkX to create a 2x2 grid graph
nx_graph = networkx.Graph()
nx_graph.add_edges_from([(0, 1), (1, 2), (2, 3), (3, 0)])

# Create a GerryChain Graph object from the NetworkX Graph object
graph = Graph.from_networkx(nx_graph)

# Give each of the nodes population 100:
for node_id in graph.node_indices:
    graph.node_data(node_id)["population"] = 100

# Partition the grid into two halves:
assignment = {0: 0, 1: 0, 2: 1, 3: 1}
partition = Partition(
    graph, assignment, updaters={"cut_edges": cut_edges, "population": Tally("population")}
)
print(f"Population by district:\n\t{partition['population']}")
print(f"Cut edges in partition:\n\t{partition['cut_edges']}")

Population by district:
	{0: 200, 1: 200}
Cut edges in partition:
	{(1, 2), (0, 3)}

Our cut_edges updater returns a set of edges, each represented as a tuple of two nodes. Our population updater returns a dictionary mapping each part of the partition to the total population in that part. Since we divided our grid in half, we see parts 0 and 1 both have population 200.

Coding note

The node_ids printed for the cut edges are internal RustworkX node_ids, not the NetworkX node_ids we built the graph with. Here the two happen to be identical, which makes the distinction very easy to miss.

Creating a Partition converts the embedded graph to RustworkX, which always numbers nodes sequentially from 0 with no gaps. The node_ids in the assignment are translated to those new ids at the same time. Our grid’s original node_ids were already 0, 1, 2, 3, so the two numberings agree by coincidence. Had we used any other labels, they would not.

If your analysis does not depend on node_ids or edge_ids, you can safely ignore this. If it does, translate back with original_nx_node_id_for_internal_node_id.

To see the difference rather than take it on faith, here is the same square, with the same partition, built from nodes labelled "a" through "d" instead of 0 through 3:

lettered_nx_graph = networkx.Graph()
lettered_nx_graph.add_edges_from([("a", "b"), ("b", "c"), ("c", "d"), ("d", "a")])
lettered_graph = Graph.from_networkx(lettered_nx_graph)

lettered_partition = Partition(
    lettered_graph, {"a": 0, "b": 0, "c": 1, "d": 1}, updaters={"cut_edges": cut_edges}
)

# These are internal RustworkX node_ids, even though we built the graph from "a"-"d".
print(f"Cut edges as stored:\n\t{lettered_partition['cut_edges']}")

# Translate each endpoint back to the node_id we started with.
lettered_partition_graph = lettered_partition.graph
original_cut_edges = {
    (
        lettered_partition_graph.original_nx_node_id_for_internal_node_id(node1_id),
        lettered_partition_graph.original_nx_node_id_for_internal_node_id(node2_id),
    )
    for node1_id, node2_id in lettered_partition["cut_edges"]
}
print(f"The same cut edges, as original NetworkX node_ids:\n\t{original_cut_edges}")

Cut edges as stored:
	{(1, 2), (0, 3)}
The same cut edges, as original NetworkX node_ids:
	{('b', 'c'), ('a', 'd')}

The stored cut edges are pairs of integers even though no node in this graph is called 0 or 1. That is the point: those integers are positions in the RustworkX graph, and only the translated version refers to the nodes we actually named.

Now when we create a new partition by flipping a node of partition, we see the values of the updaters change:

new_partition = partition.flip({0: 1})
print(f"Population by district:\n\t{new_partition['population']}")
print(f"Cut edges in partition:\n\t{new_partition['cut_edges']}")

Population by district:
	{0: 100, 1: 300}
Cut edges in partition:
	{(0, 1), (1, 2)}

As we should expect, flipping node 0 into part 1 increases the population of part 1 to 300 and decreases the population of part 0 to 100. The cut edges of the new partition are both of the edges incident to node 1, since this is the last remaining node in part 0.

Writing Your Own Updater Function

When using GerryChain to experiment with new metrics, proposals, or acceptance rules, there usually comes a point when you need to implement a new updater. As we saw in the first example, an updater is a function that takes the partition as its argument and returns any type of value.

Let’s create an updater that returns the number of cut edges in the partition.

def number_of_cut_edges(partition):
    return len(partition["cut_edges"])

Important

Note that this updater uses the value of the cut_edges updater in its computation. This is completely allowed! All you need to do is make sure that any updater that your updater depends on is included in the updaters dictionary that we pass to Partition. We also need to make sure that we have no cyclic dependencies: if the cut_edges updater also depended on number_of_cut_edges, we would fall into an infinite loop when we called either of them, resulting in a RuntimeError: maximum recursion depth exceeded error.

To try out our updater, we’ll use NetworkX to create a complete graph on 4 nodes, which we’ll partition in halves like the 2x2 grid. A GerryChain Graph can be built from a NetworkX graph like this one, and wraps it until a Partition is created, at which point the graph is converted to RustworkX for speed.

import networkx

nx_graph = networkx.complete_graph(4)
graph = Graph.from_networkx(nx_graph)
assignment = {0: 0, 1: 0, 2: 1, 3: 1}
my_updaters = {"cut_edges": cut_edges, "number_of_cut_edges": number_of_cut_edges}
partition = Partition(graph, assignment, my_updaters)

Now we can try out our custom number_of_cut_edges updater, and verify that its value changes when the partition changes:

print(partition["number_of_cut_edges"])
new_partition = partition.flip({0: 1})
print(new_partition["number_of_cut_edges"])

4
3