{ "cells": [ { "cell_type": "markdown", "id": "a12bcef2", "metadata": {}, "source": [ "# Updaters\n", "\n", "\n", "\n", "Depending on the questions you are investigating, there are many different\n", "values you might want to compute for each partition in your Markov chain. If you\n", "are interested in compactness, you might want to compute the area and perimeter\n", "of each part of the partition so that you can compute compactness scores. If you\n", "are interested in partisan lean, you might want to compute hypothetical election\n", "results using the districts defined by the partition.\n", "\n", "The `Partition` class allows you to define custom properties for the partitions\n", "in your Markov chain. You can do this by providing a dictionary of updater\n", "functions when you first create a partition." ] }, { "cell_type": "code", "execution_count": null, "id": "3f9cafbe", "metadata": {}, "outputs": [], "source": [ "import networkx\n", "from gerrychain import Partition, Graph\n", "\n", "# Use NetworkX to create a graph\n", "nx_graph = networkx.Graph()\n", "nx_graph.add_edges_from([(0, 1), (1, 2), (2, 0)])\n", "\n", "# Create a GerryChain Graph object from the NetworkX Graph object\n", "graph = Graph.from_networkx(nx_graph)\n", "\n", "assignment = {0: 1, 1: 1, 2: 2}\n", "\n", "\n", "def my_updater(partition):\n", " return \"Hello!\"\n", "\n", "\n", "partition = Partition(graph, assignment, {\"my_custom_property\": my_updater})\n", "\n", "print(partition[\"my_custom_property\"])" ] }, { "cell_type": "markdown", "id": "70853a2d", "metadata": {}, "source": [ "This partition and all subsequent partitions in the chain will have this\n", "`my_custom_property` attribute. If we flip a node in `partition` to create a new\n", "partition, we can still access this property:" ] }, { "cell_type": "code", "execution_count": null, "id": "7bca01a8", "metadata": {}, "outputs": [], "source": [ "new_partition = partition.flip({1: 2})\n", "print(f\"Are the partitions different? {new_partition is not partition}\")\n", "print(new_partition[\"my_custom_property\"])" ] }, { "cell_type": "markdown", "id": "4964e194", "metadata": {}, "source": [ "## Useful Updater Functions in GerryChain\n", "\n", "The `gerrychain.updaters` submodule provides some updaters for common tasks like\n", "aggregating data and computing the cut edges of a partition:\n", "\n", "- `Tally`: Aggregates a node attribute (e.g. population) over each part of the\n", " partition.\n", "- `cut_edges`: Returns the set of cut edges (edges whose nodes are in\n", " different parts of the partition) of the partition. This is required for\n", " most of the proposal functions in `gerrychain.proposals`.\n", "\n", "Here is an example using both of these updaters:" ] }, { "cell_type": "code", "execution_count": null, "id": "28fa7fc5", "metadata": {}, "outputs": [], "source": [ "from gerrychain.updaters import cut_edges, Tally\n", "\n", "# Use NetworkX to create a 2x2 grid graph\n", "nx_graph = networkx.Graph()\n", "nx_graph.add_edges_from([(0, 1), (1, 2), (2, 3), (3, 0)])\n", "\n", "# Create a GerryChain Graph object from the NetworkX Graph object\n", "graph = Graph.from_networkx(nx_graph)\n", "\n", "# Give each of the nodes population 100:\n", "for node_id in graph.node_indices:\n", " graph.node_data(node_id)[\"population\"] = 100\n", "\n", "# Partition the grid into two halves:\n", "assignment = {0: 0, 1: 0, 2: 1, 3: 1}\n", "partition = Partition(\n", " graph, assignment, updaters={\"cut_edges\": cut_edges, \"population\": Tally(\"population\")}\n", ")\n", "print(f\"Population by district:\\n\\t{partition['population']}\")\n", "print(f\"Cut edges in partition:\\n\\t{partition['cut_edges']}\")" ] }, { "cell_type": "markdown", "id": "3aa47376", "metadata": {}, "source": [ "Our `cut_edges` updater returns a set of edges, each represented as a tuple of\n", "two nodes. Our `population` updater returns a dictionary mapping each part of\n", "the partition to the total population in that part. Since we divided our grid in\n", "half, we see parts `0` and `1` both have population 200.\n", "\n", "> Coding note\n", ">\n", "> The node_ids printed for the cut edges are *internal* RustworkX node_ids, not the NetworkX\n", "> node_ids we built the graph with. Here the two happen to be identical, which makes the\n", "> distinction very easy to miss.\n", ">\n", "> Creating a `Partition` converts the embedded graph to RustworkX, which always numbers nodes\n", "> sequentially from 0 with no gaps. The node_ids in the assignment are translated to those new\n", "> ids at the same time. Our grid's original node_ids were already `0, 1, 2, 3`, so the two\n", "> numberings agree by coincidence. Had we used any other labels, they would not.\n", ">\n", "> If your analysis does not depend on node_ids or edge_ids, you can safely ignore this. If it\n", "> does, translate back with `original_nx_node_id_for_internal_node_id`.\n", "\n", "To see the difference rather than take it on faith, here is the same square, with the\n", "same partition, built from nodes labelled `\"a\"` through `\"d\"` instead of `0` through `3`:" ] }, { "cell_type": "code", "id": "5f339599", "source": [ "lettered_nx_graph = networkx.Graph()\n", "lettered_nx_graph.add_edges_from([(\"a\", \"b\"), (\"b\", \"c\"), (\"c\", \"d\"), (\"d\", \"a\")])\n", "lettered_graph = Graph.from_networkx(lettered_nx_graph)\n", "\n", "lettered_partition = Partition(\n", " lettered_graph, {\"a\": 0, \"b\": 0, \"c\": 1, \"d\": 1}, updaters={\"cut_edges\": cut_edges}\n", ")\n", "\n", "# These are internal RustworkX node_ids, even though we built the graph from \"a\"-\"d\".\n", "print(f\"Cut edges as stored:\\n\\t{lettered_partition['cut_edges']}\")\n", "\n", "# Translate each endpoint back to the node_id we started with.\n", "lettered_partition_graph = lettered_partition.graph\n", "original_cut_edges = {\n", " (\n", " lettered_partition_graph.original_nx_node_id_for_internal_node_id(node1_id),\n", " lettered_partition_graph.original_nx_node_id_for_internal_node_id(node2_id),\n", " )\n", " for node1_id, node2_id in lettered_partition[\"cut_edges\"]\n", "}\n", "print(f\"The same cut edges, as original NetworkX node_ids:\\n\\t{original_cut_edges}\")" ], "metadata": {}, "execution_count": null, "outputs": [] }, { "cell_type": "markdown", "id": "061912bf", "source": [ "The stored cut edges are pairs of integers even though no node in this graph is called `0` or\n", "`1`. That is the point: those integers are positions in the RustworkX graph, and only the\n", "translated version refers to the nodes we actually named.\n", "\n", "Now when we create a new partition by flipping a node of `partition`, we see the\n", "values of the updaters change:" ], "metadata": {} }, { "cell_type": "code", "execution_count": null, "id": "ef32e311", "metadata": {}, "outputs": [], "source": [ "new_partition = partition.flip({0: 1})\n", "print(f\"Population by district:\\n\\t{new_partition['population']}\")\n", "print(f\"Cut edges in partition:\\n\\t{new_partition['cut_edges']}\")" ] }, { "cell_type": "markdown", "id": "44e27dc7", "metadata": {}, "source": [ "As we should expect, flipping node `0` into part `1` increases the population of\n", "part `1` to 300 and decreases the population of part `0` to 100. The cut edges\n", "of the new partition are both of the edges incident to node `1`, since this is\n", "the last remaining node in part `0`.\n", "\n", "## Writing Your Own Updater Function\n", "\n", "When using GerryChain to experiment with new metrics, proposals, or acceptance\n", "rules, there usually comes a point when you need to implement a new updater. As\n", "we saw in the first example, an updater is a function that takes the partition\n", "as its argument and returns any type of value.\n", "\n", "Let's create an updater that returns the number of cut edges in the partition." ] }, { "cell_type": "code", "execution_count": null, "id": "f9b970f2", "metadata": {}, "outputs": [], "source": [ "def number_of_cut_edges(partition):\n", " return len(partition[\"cut_edges\"])" ] }, { "cell_type": "markdown", "id": "3b66d5eb", "metadata": {}, "source": [ "> Important\n", ">\n", "> Note that this updater uses the value of the `cut_edges` updater in its\n", "> computation. This is completely allowed! All you need to do is make sure that\n", "> any updater that your updater depends on is included in the `updaters`\n", "> dictionary that we pass to `Partition`. We also need to make sure that we have\n", "> no cyclic dependencies: if the `cut_edges` updater also depended on\n", "> `number_of_cut_edges`, we would fall into an infinite loop when we called either\n", "> of them, resulting in a `RuntimeError: maximum recursion depth exceeded` error.\n", "\n", "To try out our updater, we'll use [NetworkX](https://networkx.github.io) to\n", "create a complete graph on 4 nodes, which we'll partition in halves like the 2x2\n", "grid. A GerryChain `Graph` can be built from a NetworkX graph like this one, and\n", "wraps it until a `Partition` is created, at which point the graph is converted to\n", "RustworkX for speed." ] }, { "cell_type": "code", "execution_count": null, "id": "43212d64", "metadata": {}, "outputs": [], "source": [ "import networkx\n", "\n", "nx_graph = networkx.complete_graph(4)\n", "graph = Graph.from_networkx(nx_graph)\n", "assignment = {0: 0, 1: 0, 2: 1, 3: 1}\n", "my_updaters = {\"cut_edges\": cut_edges, \"number_of_cut_edges\": number_of_cut_edges}\n", "partition = Partition(graph, assignment, my_updaters)" ] }, { "cell_type": "markdown", "id": "1ccfaae0", "metadata": {}, "source": [ "Now we can try out our custom `number_of_cut_edges` updater, and verify that its\n", "value changes when the partition changes:" ] }, { "cell_type": "code", "execution_count": null, "id": "00b5a422", "metadata": {}, "outputs": [], "source": [ "print(partition[\"number_of_cut_edges\"])\n", "new_partition = partition.flip({0: 1})\n", "print(new_partition[\"number_of_cut_edges\"])" ] } ], "metadata": { "kernelspec": { "display_name": "Python 3", "language": "python", "name": "python3" } }, "nbformat": 4, "nbformat_minor": 5 }