API Reference

Adjacency graphs 

class gerrychain.graph.graph.Graph[source]

frm TODO: Documentation: Clean up this documentation

frm: this class encapsulates / hides the underlying graph which can either be a NetworkX graph or a RustworkX graph. The intent is that it provides the same external interface as a NetworkX graph (for all of the uses that GerryChain cares about, at least) so that legacy code that operated on NetworkX based Graph objects can continue to work unchanged.

When a graph is added to a partition, however, the NX graph will be converted into an RX graph and the NX graph will become unaccessible to the user. The RX graph may also be “frozen” the way the NX graph was “frozen” in the legacy code, but we have not yet gotten that far in the implementation.

It is not clear whether the code that does the heavy lifting on partitions will need to use the old NX syntax or whether it will be useful to allow unfettered access to the RX graph so that RX code can be used in these modules. TBD…

add_data(df: DataFrame, columns: Iterable[str] | None = None) → None[source]

Add columns of a DataFrame to a graph as node attributes by matching the DataFrame’s index to node ids.

Parameters:

df (pandas.DataFrame) – Dataframe containing given columns.
columns (Optional[Iterable[str]], optional) – list of dataframe column names to add. Default is None.

Returns:

None

add_edge(node_id1: Any, node_id2: Any) → None[source]

Add an edge to the graph from node_id1 to node_id2

Parameters:

node_id1 (Any) – The node_id for one of the nodes in the edge
node_id2 (Any) – The node_id for one of the nodes in the edge

Return type:

None

convert_from_nx_to_rx() → Graph[source]

Convert an NX-based graph object to be an RX-based graph object.

The primary use case for this routine is support for users constructing a graph using NetworkX functionality and then converting that NetworkX graph to RustworkX when creating a Partition object.

Returns:: An RX-based graph that is “the same” as the given NX-based graph
Return type:: “Graph”

degree(node_id: Any) → int[source]

Return the degree of the given node, that is, the number of other nodes directly connected to the given node.

Parameters:: node_id (Any) – The ID of a node
Returns:: Number of nodes directly connected to the given node
Return type:: int

edge_data(edge_id: Any) → dict[Any, Any][source]

Return the data dictionary that contains the data for the given edge.

Note that in NetworkX an edge_id can be almost anything, for instance, a string or even a tuple. However, in RustworkX, an edge_id is an integer. This code handles both kinds of edge_ids - hence the type, Any.

Parameters:: edge_id (Any) – The ID of the edge
Returns:: The data dictionary for the given edge’s data
Return type:: dict[Any, Any]

property edge_indices: set[Any]

Return a set of the edge_ids in the graph

Return type:: set[Any]

property edges: set[tuple[Any, Any]]

Return a set of all of the edges in the graph, where each edge is a tuple of node_ids

Return type:: set[tuple[Any, Any]]:

classmethod from_file(filename: str, adjacency: str = 'rook', cols_to_add: list[str] | None = None, reproject: bool = False, ignore_errors: bool = False) → Graph[source]

Create a Graph from a shapefile (or GeoPackage, or GeoJSON, or any other library that geopandas can read. See from_geodataframe() for more details.

Parameters:

filename (str) – Path to the shapefile / GeoPackage / GeoJSON / etc.
adjacency (str, optional) – The adjacency type to use (“rook” or “queen”). Default is “rook”
cols_to_add (Optional[list[str]], optional) – The names of the columns that you want to add to the graph as node attributes. Default is None.
reproject (bool, optional) – Whether to reproject to a UTM projection before creating the graph. Default is False.
ignore_errors (bool, optional) – Whether to ignore all invalid geometries and try to continue creating the graph. Default is False.

Returns:

The Graph object of the geometries from filename.

Return type:

Graph

Warning

This method requires the optional geopandas dependency. So please install gerrychain with the geo extra via the command:

pip install gerrychain[geo]

or install geopandas separately.

classmethod from_geodataframe(dataframe: DataFrame, adjacency: str = 'rook', cols_to_add: list[str] | None = None, reproject: bool = False, ignore_errors: bool = False, crs_override: str | int | None = None) → Graph[source]

Create the adjacency Graph of geometries described by dataframe. The areas of the polygons are included as node attributes (with key area). The shared perimeter of neighboring polygons are included as edge attributes (with key shared_perim). Nodes corresponding to polygons on the boundary of the union of all the geometries (e.g., the state, if your dataframe describes VTDs) have a boundary_node attribute (set to True) and a boundary_perim attribute with the length of this “exterior” boundary.

By default, areas and lengths are computed in a UTM projection suitable for the geometries. This prevents the bizarro area and perimeter values that show up when you accidentally do computations in Longitude-Latitude coordinates. If the user specifies reproject=False, then the areas and lengths will be computed in the GeoDataFrame’s current coordinate reference system. This option is for users who have a preferred CRS they would like to use.

Parameters:

dataframe (geopandas.GeoDataFrame) – The GeoDateFrame to convert
adjacency (str, optional) – The adjacency type to use (“rook” or “queen”). Default is “rook”.
cols_to_add (Optional[list[str]], optional) – The names of the columns that you want to add to the graph as node attributes. Default is None.
reproject (bool, optional) – Whether to reproject to a UTM projection before creating the graph. Default is False.
ignore_errors (bool, optional) – Whether to ignore all invalid geometries and attept to create the graph anyway. Default is False.
crs_override (Optional[Union[str,int]], optional) – Value to override the CRS of the GeoDataFrame. Default is None.

Returns:

The adjacency graph of the geometries from dataframe.

Return type:

Graph

classmethod from_json(json_file_name: str) → Graph[source]

Create a Graph from a JSON file

Parameters:: json_file_name (str) – JSON file # frm: TODO: Documentation: more detail on contents of JSON file needed here
Returns:: A GerryChain Graph object with data from JSON file
Return type:: “Graph”

classmethod from_networkx(nx_graph: Graph) → Graph[source]

Create a Graph from a NetworkX.Graph object

This supports the use case of users creating a graph using NetworkX which is convenient - both for users of the previous implementation of a GerryChain object which was a subclass of NetworkX.Graph and for users more generally who are familiar with NetworkX.

Note that most users will not ever call this function directly, because they can create a GerryChain Partition object directly from a NetworkX graph, and the Partition initialization code will use this function to convert the NetworkX graph to a GerryChain Graph object.

Parameters:: nx_graph (networkx.Graph) – A NetworkX.Graph object with node and edge data to be converted into a GerryChain Graph object.
Returns:: …text…
Return type:: <type>

classmethod from_rustworkx(rx_graph: PyGraph) → Graph[source]

Create a Graph from a RustworkX.PyGraph object

There are three primary use cases for this routine: 1) converting an NX-based Graph to be an RX-based Graph, 2) creating a subgraph of an RX-based Graph, and 3) creating a Graph whose node_ids do not need to be mapped to some previous graph’s node_ids.

In a little more detail:

1) A typical way to use GerryChain is to create a graph using NetworkX functionality and to then rely on the initialization code in the Partition class to create an RX-based Graph object. That initialization code constructs a RustworkX PyGraph and then uses this routine to create an RX-based Graph object, and it then creates maps from the node_ids of the resulting RX-based Graph back to the original NetworkX.Graph’s node_ids.

2) When creating a subgraph of a RustworkX PyGraph object, the node_ids of the subgraph are (in general) different from those of the parent graph. So we create a mapping from the subgraph’s node_ids to the node_ids of the parent. The subgraph() routine creates a RustworkX PyGraph subgraph, then uses this routine to create an RX-based Graph using that subgraph, and it then creates the mapping of subgraph node_ids to the parent (RX) graph’s node_ids.

3) In those cases where no node_id mapping is needed this routine provides a simple way to create an RX-based GerryChain graph object.

Parameters:: rx_graph (rustworkx.PyGraph) – a RustworkX PyGraph object
Returns:: a GerryChain Graph object with an embedded RustworkX.PyGraph object
Return type:: “Graph”

generic_bfs_edges(source, neighbors=None, depth_limit=None) → Generator[tuple[Any, Any], None, None][source]

Parameters:: <param_name> (<type>) – …text… …more text…
Returns:: …text…
Return type:: <type>

generic_bfs_predecessors(root_node_id: Any) → dict[Any, Any][source]

Parameters:: <param_name> (<type>) – …text… …more text…
Returns:: …text…
Return type:: <type>

generic_bfs_successors(root_node_id: Any) → dict[slice(Any, Any, None)][source]

Parameters:: <param_name> (<type>) – …text… …more text…
Returns:: …text…
Return type:: <type>

generic_bfs_successors_generator(root_node_id: Any) → Generator[tuple[Any, Any], None, None][source]

Parameters:: <param_name> (<type>) – …text… …more text…
Returns:: …text…
Return type:: <type>

get_edge_from_edge_id(edge_id: Any) → tuple[Any, Any][source]

Return the edge (tuple of node_ids) corresponding to the given edge_id

Note that in NX, an edge_id is the same as an edge - it is just a tuple of node_ids. However, in RX, an edge_id is an integer, so if you want to get the tuple of node_ids you need to use the edge_id to get that tuple…

Parameters:: edge_id (Any) – The ID of the desired edge
Returns:: An edge, namely a tuple of node_ids
Return type:: tuple[Any, Any]

get_edge_id_from_edge(edge: tuple[Any, Any]) → Any[source]

Get the edge_id that corresponds to the given edge.

In RX an edge_id is an integer that designates an edge (an edge is a tuple of node_ids). In NX, an edge_id IS the tuple of node_ids. So, in general, to support both NX and RX, if you want to get access to the edge data for an edge (tuple of node_ids), you need to ask for the edge_id.

This functionality is needed, for instance, when

Parameters:: edge (tuple[Any, Any]) – A tuple of node_ids.
Returns:: The ID associated with the given edge
Return type:: Any

get_nx_graph() → Graph[source]

Return the embedded NX graph object

Return type:: networkx.Graph

get_nx_to_rx_node_id_map() → dict[Any, Any][source]

Return the dict that maps NX node_ids to RX node_ids

The primary use case for this routine is to support automatically converting NX-based graph objects to be RX-based when creating a Partition object. The issue is that when you convert from NX to RX the node_ids change and so you need to update the Partition object’s Assignment to use the new RX node_ids. This routine is used to translate those NX node_ids to the new RX node_ids when initializing a Partition object.

Return type:: dict[Any, Any]

get_rx_graph() → PyGraph[source]

Return the embedded RX graph object

Return type:: rustworkx.PyGraph

internal_node_id_for_original_nx_node_id(original_nx_node_id: Any) → Any[source]

Discover the “internal” node_id in the current GerryChain graph that corresponds to the “original” node_id in the top-level graph (presumably an NX-based graph object).

This was originally created to facilitate testing where it was convenient to express the test success criteria in terms of “original” node_ids, but the actual test needed to be made using the “internal” (RX) node_ids.

Parameters:: original_nx_node_id (Any) – The “original” node_id
Returns:: The corresponding “internal” node_id
Return type:: Any

is_a_tree() → bool[source]

Return whether the current graph is a tree - meaning that it is connected and that it has no cycles.

Returns:: Whether the current graph is a tree
Return type:: bool

is_nx_graph() → bool[source]

Determine if the graph is NX-based

Return type:: bool

is_rx_graph() → bool[source]

Determine if the graph is RX-based

Return type:: bool

property islands: set[Any]

Return a set of all node_ids that are not connected via an edge to any other node in the graph - that is, nodes with degree = 0

Returns:: A set of all node_ids for nodes of degree 0
Return type:: set[Any]

issue_warnings() → None[source]

Issue any warnings concerning the content or structure of the graph.

Return type:: None

join(dataframe: DataFrame, columns: list[str] | None = None, left_index: str | None = None, right_index: str | None = None) → None[source]

Add data from a dataframe to the graph, matching nodes to rows when the node’s left_index attribute equals the row’s right_index value.

Parameters:: dataframe (pandas.DataFrame) – DataFrame.
Columns:: The columns whose data you wish to add to the graph. If not provided, all columns are added. Default is None.
Left_index:: The node attribute used to match nodes to rows. If not provided, node IDs are used. Default is None.
Right_index:: The DataFrame column name to use to match rows to nodes. If not provided, the DataFrame’s index is used. Default is None.
Returns:: None

laplacian_matrix() → csr_array[source]

Parameters:: <param_name> (<type>) – …text… …more text…
Returns:: …text…
Return type:: <type>

neighbors(node_id: Any) → list[Any][source]

Return a list of the node_ids of the nodes that are neighbors of the given node - that is, all of the nodes that are directly connected to the given node by an edge.

Parameters:: node_id (Any) – The ID of a node
Returns:: A list of neighbor node_ids
Return type:: list[Any]

node_data(node_id: Any) → dict[Any, Any][source]

Return the data dictionary that contains the given node’s data.

As docmented elsewhere, in GerryChain code before the conversion to RustworkX, users could access node data using the syntax:

graph.nodes[node_id][attribute_name]

This was because a GerryChain Graph object in that codebase was a subclass of NetworkX.Graph, and NetworkX was clever and implemented dict-like behavior for the syntax graph.nodes[]…

This Python cleverness was not carried over to the RustworkX implementation, so in the current GerryChain Graph implementation users need to access node data using the syntax:

graph.node_data(node_id)[attribute_name]

Parameters:: node_id (Any) – The ID of a node
Returns:: Data dictionary containing the given node’s data.
Return type:: dict[Any, Any]

property node_indices: set[Any]

Return a set of the node_ids in the graph

Return type:: set[Any]

property nodes: list[Any]

Return a list of all of the node_ids in the graph.

This routine still exists because there is a lot of legacy code that uses this syntax to iterate through all of the nodes in a graph.

There is another routine, node_indices(), which does essentially the same thing (it returns a set of node_ids, however, rather than a list).

Why have two routines that do the same thing? The answer is that with move to RX, it seemed appropriate to emphasize the distinction between objects and the IDs for objects, hence the introduction of node_indices() and edge_indices() routines. This distinction is critical for edges, but mostly not important for nodes. In fact this routine is implemented by just converting node_indices to a list. So, it is essentially a style issue - when referring to nodes, we are almost always really referring to node_ids, so why not use a routine called node_indices()?

Note that there is a subtle point to be made about node names vs. node_ids. It was common before the transition to RX to create nodes with IDs that were essentially names. That is, the ID had semantic weight. This is not true with RX node_ids. So, any code that relies on the semantics of a node’s ID (treating it like a name) is suspect in the new RX world.

Returns:: A list of all of the node_ids in the graph
Return type:: list[Any]

normalized_laplacian_matrix() → dia_array[source]

Parameters:: <param_name> (<type>) – …text… …more text…
Returns:: …text…
Return type:: <type>

num_connected_components() → int[source]

Return the number of connected components.

Note: A connected component is a maximal subgraph where every vertex is reachable from every other vertex in that same subgraph. In a graph that is not fully connected, connected components are the separate, distinct “islands” of connected nodes. Every node in a graph belongs to exactly one connected component.

Returns:: The number of connected components
Return type:: int

original_nx_node_id_for_internal_node_id(internal_node_id: Any) → Any[source]

Translate a node_id to its “original” node_id.

Parameters:: internal_node_id (Any) – A node_id to be translated
Returns:: A translated node_id
Return type:: Any

original_nx_node_ids_for_list(list_of_node_ids: list[Any]) → list[Any][source]

Translate a list of node_ids to their “original” node_ids.

Parameters:: list_of_node_ids (list[Any]) – A list of node_ids to be translated
Returns:: A list of translated node_ids
Return type:: list[Any]

original_nx_node_ids_for_set(set_of_node_ids: set[Any]) → Any[source]

Translate a set of node_ids to their “original” node_ids.

Parameters:: set_of_node_ids (set[Any]) – A set of node_ids to be translated
Returns:: A set of translated node_ids
Return type:: set[Any]

predecessors(root_node_id: Any) → dict[slice(Any, Any, None)][source]

Parameters:: <param_name> (<type>) – …text… …more text…
Returns:: …text…
Return type:: <type>

subgraph(nodes: Iterable[Any]) → Graph[source]

Create a subgraph that contains the given nodes.

Note that creating a subgraph of an RustworkX (RX) graph renumbers the nodes, so that a node that had node_id: 4 in the parent graph might have node_id: 2 in the subgraph. This is a HUGE difference from the NX world where the node_ids in a subgraph do not change from those in the parent graph.

In order to make sense of the nodes in a subgraph in the RX world, we need to maintain mappings from the node_ids in the subgraph to the node_ids of the immediate parent graph and to the “original” top-level graph that contains all of the nodes. You will notice the creation of those maps in the code below.

Parameters:: nodes (Iterable[Any]) – The nodes to be included in the subgraph
Returns:: A subgraph containing the given nodes.
Return type:: “Graph”

subgraphs_for_connected_components() → list[Graph][source]

Create and return a list of subgraphs for each set of nodes in the given graph that are connected.

Note that a connected graph is one in which there is a path from every node in the graph to every other node in the graph.

Note also that each of the subgraphs returned is a maximal subgraph of connected components, meaning that there is no other larger subgraph of connected components that includes it as a subset.

Returns:: A list of “maximal” subgraphs each of which contains nodes that are connected.
Return type:: list[“Graph”]

successors(root_node_id: Any) → dict[slice(Any, Any, None)][source]

Parameters:: <param_name> (<type>) – …text… …more text…
Returns:: …text…
Return type:: <type>

to_json(json_file_name: str, include_geometries_as_geojson: bool = False) → None[source]

Dump a GerryChain Graph object to disk as a JSON file

Parameters:: json_file_name (str) – name of JSON file to be created
Return type:: None

to_networkx_graph() → Graph[source]

Create a NetworkX.Graph object that has the same nodes, edges, node_data, and edge_data as the GerryChain Graph object.

The intended purpose of this routine is to allow a user to run a MarkovChain - which uses an embedded RustworkX graph and then extract an equivalent version of that graph with all of its data as a NetworkX.Graph object - in order to use NetworkX routines to access and manipulate the graph.

In short, this routine allows users to use NetworkX functionality on a graph after running a MarkovChain.

If the GerryChain graph object is NX-based, then this routine merely returns the embedded NetworkX.Graph object.

Returns:: A NetworkX.Graph object that is equivalent to the GerryChain Graph object (nodes, edges, node_data, edge_data)
Return type:: networkx.Graph

translate_subgraph_node_ids_for_flips(flips: dict[Any, int]) → dict[Any, int][source]

Translate the given flips so that the subgraph node_ids in the flips have been translated to the appropriate node_ids in the parent graph.

The flips parameter is a dict mapping node_ids to parts (districts).

This routine is used when a computation that creates flips is made on a subgraph, but those flips want to be translated into the context of the parent graph at the end of the computation.

For more details, refer to the larger comment on subgraphs…

Parameters:: flips (dict[Any, int]) – A dict containing “flips” which associate a node with a new part in a partition (a “part” is the same as a district in common parlance).
Returns:: A dict containing “flips” that have been translated to have node_ids appropriate for the parent graph
Return type:: dict[Any, int]

translate_subgraph_node_ids_for_set_of_nodes(set_of_nodes: set[Any]) → set[Any][source]

Translate the given set_of_nodes to have the appropriate node_ids for the parent graph.

This routine is used when a computation that creates a set of nodes is made on a subgraph, but those nodes want to be translated into the context of the parent graph at the end of the computation.

For more details, refer to the larger comment on subgraphs…

Parameters:: set_of_nodes (set[Any]) – A set of node_ids in a subgraph
Returns:: A set of node_ids that have been translated to have the node_ids appropriate for the parent graph
Return type:: set[Any]

verify_graph_is_valid() → bool[source]

Verify that the graph is valid.

This may be overkill, but the idea is that at least in development mode, it would be prudent to check periodically to see that the graph data structure has not been corrupted.

Returns:: True if the graph is deemed valid
Return type:: bool

warn_for_islands() → None[source]

Issue a warning if there are any islands in the graph - that is, if there are any nodes in the graph that are not connected to any other node (degree = 0)

Return type:: None

Partitions 

class gerrychain.partition.GeographicPartition(graph=None, assignment=None, updaters=None, parent=None, flips=None, use_default_updaters=True)[source]

Bases: Partition

A Partition with areas, perimeters, and boundary information included. These additional data allow you to compute compactness scores like Polsby-Popper.

Parameters:

graph – Underlying graph.
assignment – Dictionary assigning nodes to districts.
updaters – Dictionary of functions to track data about the partition. The keys are stored as attributes on the partition class, which the functions compute.
use_default_updaters – If False, do not include default updaters.

class gerrychain.partition.Partition(graph=None, assignment=None, updaters=None, parent=None, flips=None, use_default_updaters=True)[source]

Bases: object

Partition represents a partition of the nodes of the graph. It will perform the first layer of computations at each step in the Markov chain - basic aggregations and calculations that we want to optimize.

Variables:

graph – The underlying graph.
assignment – Maps node IDs to district IDs.
parts – Maps district IDs to the set of nodes in that district.
subgraphs – Maps district IDs to the induced subgraph of that district.

Parameters:

graph (Graph) – Underlying graph.
assignment (Assignment) – Dictionary assigning nodes to districts.
updaters – Dictionary of functions to track data about the partition. The keys are stored as attributes on the partition class, which the functions compute.
use_default_updaters – If False, do not include default updaters.

crosses_parts(edge: Tuple) → bool[source]

Parameters:: edge (Tuple) – tuple of node IDs
Returns:: True if the edge crosses from one part of the partition to another
Return type:: bool

flip(flips: Dict, use_original_nx_node_ids=False) → Partition[source]

Returns the new partition obtained by performing the given flips on this partition.

Parameters:: flips – dictionary assigning nodes of the graph to their new districts
Returns:: the new Partition
Return type:: Partition

classmethod from_districtr_file(graph: Graph, districtr_file: str, updaters: Dict[str, Callable] | None = None) → Partition[source]

Create a Partition from a districting plan created with Districtr, a free and open-source web app created by MGGG for drawing districts.

The provided graph should be created from the same shapefile as the Districtr module used to draw the districting plan. These shapefiles may be found in a repository in the mggg-states GitHub organization, or by request from MGGG.

Parameters:

graph (Graph) – The graph to create the Partition from
districtr_file (str) – the path to the .json file exported from Districtr
updaters (Optional[Dict[str, Callable]], optional) – dictionary of updaters

Returns:

The partition created from the Districtr file

Return type:

Partition

classmethod from_random_assignment(graph: ~gerrychain.graph.graph.Graph, n_parts: int, epsilon: float, pop_col: str, updaters: ~typing.Dict[str, ~typing.Callable] | None = None, use_default_updaters: bool = True, method: ~typing.Callable = <function recursive_tree_part>) → Partition[source]

Create a Partition with a random assignment of nodes to districts.

Parameters:

graph (Graph) – The graph to create the Partition from.
n_parts (int) – The number of districts to divide the nodes into.
epsilon (float population. Should be in [0,1].) – The maximum relative population deviation from the ideal
pop_col (str) – The column of the graph’s node data that holds the population data.
updaters (Optional[Dict[str, Callable]], optional) – Dictionary of updaters
use_default_updaters (bool, optional) – If False, do not include default updaters.
method (Callable, optional) – The function to use to partition the graph into n_parts. Defaults to recursive_tree_part().

Returns:

The partition created with a random assignment

Return type:

Partition

plot(geometries=None, **kwargs)[source]

Plot the partition, using the provided geometries.

Parameters:

geometries (geopandas.GeoDataFrame or geopandas.GeoSeries) – A geopandas.GeoDataFrame or geopandas.GeoSeries holding the geometries to use for plotting. Its Index should match the node labels of the partition’s underlying Graph.
**kwargs – Additional arguments to pass to geopandas.GeoDataFrame.plot() to adjust the plot.

Returns:

The matplotlib axes object. Which plots the Partition.

Return type:

matplotlib.axes.Axes

Markov chains 

class gerrychain.MarkovChain(proposal: Callable, constraints: Iterable[Callable] | Validator | Iterable[Bounds] | Callable, accept: Callable, initial_state: Partition, total_steps: int)[source]

MarkovChain is a class that creates an iterator for iterating over the states of a Markov chain run in a gerrymandering analysis context.

It allows for the generation of a sequence of partitions (states) of a political districting plan, where each partition represents a possible state in the Markov chain.

Example usage:

chain = MarkovChain(proposal, constraints, accept, initial_state, total_steps)
for state in chain:
    # Do whatever you want - print output, compute scores, ...

Parameters:

proposal (Callable) – Function proposing the next state from the current state.
constraints (Union[Iterable[Callable], Validator, Iterable[Bounds], Callable]) – A function with signature Partition -> bool determining whether the proposed next state is valid (passes all binary constraints). Usually this is a Validator class instance.
accept (Callable) – Function accepting or rejecting the proposed state. In the most basic use case, this always returns True. But if the user wanted to use a Metropolis-Hastings acceptance rule, this is where you would implement it.
initial_state (Partition) – Initial gerrychain.partition.Partition class.
total_steps (int) – Number of steps to run.

Returns:

None

Raises:

ValueError – If the initial_state is not valid according to the constraints.

property constraints: Validator

Read_only alias for the is_valid property. Returns the constraints of the Markov chain.

Returns:: The constraints of the Markov chain.
Return type:: String

with_progress_bar()[source]

Wraps the Markov chain in a tqdm progress bar.

Useful for long-running Markov chains where you want to keep track of the progress. Requires the tqdm package to be installed.

Returns:: A tqdm-wrapped Markov chain.

Proposals 

gerrychain.proposals.propose_chunk_flip(partition: Partition) → Partition[source]

Chooses a random boundary node and proposes to flip it and all of its neighbors

Parameters:: partition (Partition) – The current partition to propose a flip from.
Returns:: A possible next ~gerrychain.Partition
Return type:: Partition

gerrychain.proposals.propose_random_flip(partition: Partition) → Partition[source]

Proposes a random boundary flip from the partition.

Parameters:: partition (Partition) – The current partition to propose a flip from.
Returns:: A possible next ~gerrychain.Partition
Return type:: Partition

gerrychain.proposals.recom(partition: ~gerrychain.partition.partition.Partition, pop_col: str, pop_target: int | float, epsilon: float, node_repeats: int = 1, region_surcharge: ~typing.Dict | None = None, method: ~typing.Callable = <function bipartition_tree>) → Partition[source]

ReCom (short for ReCombination) is a Markov Chain Monte Carlo (MCMC) algorithm used for redistricting. At each step of the algorithm, a pair of adjacent districts is selected at random and merged into a single district. The region is then split into two new districts by generating a spanning tree using the Kruskal/Karger algorithm and cutting an edge at random. The edge is checked to ensure that it separates the region into two new districts that are population balanced, and, if not, a new edge is selected at random and the process is repeated.

Example usage:

from functools import partial
from gerrychain import MarkovChain
from gerrychain.proposals import recom

# ...define constraints, accept, partition, total_steps here...

# Ideal population:
pop_target = sum(partition["population"].values()) / len(partition)

proposal = partial(
    recom, pop_col="POP10", pop_target=pop_target, epsilon=.05, node_repeats=10
)

chain = MarkovChain(proposal, constraints, accept, partition, total_steps)

Parameters:

partition (Partition) – The initial partition.
pop_col (str) – The name of the population column.
pop_target (Union[int,float]) – The target population for each district.
epsilon (float) – The epsilon value for population deviation as a percentage of the target population.
node_repeats (int, optional) – The number of times to repeat the bipartitioning step. Default is 1.
region_surcharge (Optional[Dict], optional) – The surcharge dictionary for the graph used for region-aware partitioning of the grid. Default is None.
method (Callable, optional) – The method used for bipartitioning the tree. Default is bipartition_tree().

Returns:

The new partition resulting from the ReCom algorithm. print(“bipartition_tree: updating restarts and attempts”)

Return type:

Partition

gerrychain.proposals.reversible_recom(partition: ~gerrychain.partition.partition.Partition, pop_col: str, pop_target: int | float, epsilon: float, balance_edge_fn: ~typing.Callable = <function find_balanced_edge_cuts_memoization>, M: int = 1, repeat_until_valid: bool = False, choice: ~typing.Callable = <bound method Random.choice of <random.Random object>>) → Partition[source]

Reversible ReCom algorithm for redistricting.

This function performs the reversible ReCom algorithm, which is a Markov Chain Monte Carlo (MCMC) algorithm used for redistricting. For more information, see the paper “Spanning Tree Methods for Sampling Graph Partitions” by Cannon, et al. (2022) at https://arxiv.org/abs/2210.01401

Parameters:

partition (Partition) – The initial partition.
pop_col (str) – The name of the population column.
pop_target (Union[int,float]) – The target population for each district.
epsilon (float) – The epsilon value for population deviation as a percentage of the target population.
balance_edge_fn (Callable, optional frm: it returns a list of Cuts - a named tuple defined in tree.py) – The balance edge function. Default is find_balanced_edge_cuts_memoization.
M (int, optional) – The maximum number of balance edges. Default is 1.
repeat_until_valid (bool, optional) – Flag indicating whether to repeat until a valid partition is found. Default is False.
choice (Callable, optional) – The choice function for selecting a random element. Default is random.choice.

Returns:

The new partition resulting from the reversible ReCom algorithm.

Return type:

Partition

gerrychain.proposals.spectral_recom(partition: Partition, weight_type: str | None = None, lap_type: str = 'normalized') → Partition[source]

Spectral ReCom proposal.

Uses spectral clustering to bipartition a subgraph of the original graph formed by merging the nodes corresponding to two adjacent districts.

Example usage:

from functools import partial
from gerrychain import MarkovChain
from gerrychain.proposals import recom

# ...define constraints, accept, partition, total_steps here...


proposal = partial(
    spectral_recom, weight_type=None, lap_type="normalized"
)

chain = MarkovChain(proposal, constraints, accept, partition, total_steps)

Parameters:

partition (Partition) – The initial partition.
weight_type (Optional[str], optional) – The type of weight to be used in the Laplacian. Default is None.
lap_type (str, optional) – The type of Laplacian to be used. Default is “normalized”.

Returns:

The new partition resulting from the spectral ReCom algorithm.

Return type:

Partition

Binary constraints 

The gerrychain.constraints module provides a collection of constraint functions and helper classes for the validation step in GerryChain.

Helper classes
`Validator`	Collection of constraints
`Bounds`	Bounds on numeric constraints
`UpperBound`	Upper bounds on numeric constraints
`LowerBound`	Lower bounds on numeric constraints
`SelfConfiguringUpperBound`	Automatic upper bounds on numeric constraints
`SelfConfiguringLowerBound`	Automatic lower bounds on numeric constraints
`WithinPercentRangeOfBounds`	Percentage bounds for numeric constraints

Binary constraint functions
`no_worse_L1_reciprocal_polsby_popper()`	Lower bounded L1-reciprocal Polsby-Popper
`no_worse_L_minus_1_reciprocal_polsby_popper()`	Lower bounded L(-1)-reciprocal Polsby-Popper
`contiguous()`	Districts are contiguous (with NetworkX methods)
`single_flip_contiguous()`	Districts are contiguous (optimized for `propose_random_flip` proposal)
`no_vanishing_districts()`	No districts may be completely consumed

Each new step proposed to the chain is passed off to the “validator” functions here to determine whether or not the step is valid. If it is invalid (breaks contiguity, for instance), then the step is immediately rejected.

A validator should take in a Partition instance, and should return whether or not the instance is valid according to their rules. Many top-level functions following this signature in this module are examples of this.

class gerrychain.constraints.Bounds(func: Callable, bounds: Tuple[float, float])[source]

Wrapper for numeric-validators to enforce upper and lower limits.

This class is meant to be called as a function after instantiation; its return is True if the numeric validator is within set limits, and False otherwise.

Parameters:

func (Callable) – Numeric validator function. Should return an iterable of values.
bounds (Tuple[float, float]) – Tuple of (lower, upper) numeric bounds.

gerrychain.constraints.L1_polsby_popper(partition: Partition) → float[source]

Returns the \(L^1\) norm of the Polsby-Popper scores for the given partition

Parameters:: partition (Partition) – Partition representing a districting plan
Returns:: \(L^1\) norm of the reciprocal Polsby-Popper scores
Return type:: float

gerrychain.constraints.L1_reciprocal_polsby_popper(partition: Partition) → float[source]

Returns the \(L^1\) norm of the reciprocal Polsby-Popper scores for the given partition

Parameters:: partition (Partition) – Partition representing a districting plan
Returns:: \(L^1\) norm of the reciprocal Polsby-Popper scores
Return type:: float

gerrychain.constraints.L2_polsby_popper(partition: Partition) → float[source]

Returns the \(L^2\) norm of the Polsby-Popper scores for the given partition.

Parameters:: partition (Partition) – Partition representing a districting plan
Returns:: \(L^2\) norm of the Polsby-Popper scores
Return type:: float

gerrychain.constraints.L_minus_1_polsby_popper(partition)[source]

Returns the \(L^{-1}\) norm of the Polsby-Popper scores for the given partition.

Parameters:: partition (Partition) – Partition representing a districting plan
Returns:: \(L^{-1}\) norm of the Polsby-Popper scores
Return type:: float

class gerrychain.constraints.LowerBound(func: Callable, bound: float)[source]

Wrapper for numeric-validators to enforce lower limits.

This class is meant to be called as a function after instantiation; its return is True if the numeric validator is within a set lower limit, and False otherwise.

Parameters:

func (Callable) – Numeric validator function. Should return a comparable value.
bounds (float) – Comparable lower bound.

class gerrychain.constraints.SelfConfiguringLowerBound(func: Callable, epsilon: float = 0.05)[source]

Wrapper for numeric-validators to enforce automatic lower limits.

When instantiated, the initial lower bound is set as the initial value of the numeric-validator minus some configurable ε.

This class is meant to be called as a function after instantiation; its return is True if the numeric validator is within a set lower limit, and False otherwise.

Parameters:

func (Callable) – Numeric validator function.
epsilon (float, optional) – Initial population deviation allowable by the validator as a percentage of the ideal population. Defaults to 0.05.

class gerrychain.constraints.SelfConfiguringUpperBound(func: Callable)[source]

Wrapper for numeric-validators to enforce automatic upper limits.

When instantiated, the initial upper bound is set as the initial value of the numeric-validator.

This class is meant to be called as a function after instantiation; its return is True if the numeric validator is within a set upper limit, and False otherwise.

Parameters:: func (Callable) – Numeric validator function.

class gerrychain.constraints.UpperBound(func: Callable, bound: float)[source]

Wrapper for numeric-validators to enforce upper limits.

This class is meant to be called as a function after instantiation; its return is True if the numeric validator is within a set upper limit, and False otherwise.

Parameters:

func (Callable) – Numeric validator function. Should return a comparable value.
bounds (float) – Comparable upper bound.

class gerrychain.constraints.Validator(constraints: List[Callable])[source]

A single callable for checking that a partition passes a collection of constraints. Intended to be passed as the is_valid parameter when instantiating MarkovChain.

This class is meant to be called as a function after instantiation; its return is True if all validators pass, and False if any one fails.

Example usage:

is_valid = Validator([constraint1, constraint2, constraint3])
chain = MarkovChain(proposal, is_valid, accept, initial_state, total_steps)

Variables:: constraints – List of validator functions that will check partitions.
Parameters:: constraints (List[Callable]) – List of validator functions that will check partitions.

class gerrychain.constraints.WithinPercentRangeOfBounds(func: Callable, percent: float)[source]

Wrapper for numeric-validators to enforce upper and lower limits determined by a percentage of the initial value.

When instantiated, the initial upper and lower bounds are set as the initial value of the numeric-validator times (1 ± percent).

This class is meant to be called as a function after instantiation; its return is True if the numeric validator is within the desired percentage range of the initial value, and False otherwise.

Parameters:

func (Callable) – Numeric validator function.
percent (float) – Percentage of the initial value to use as the bounds.

Returns:

None

Warning

The percentage is assumed to be in the range [0.0, 100.0].

gerrychain.constraints.contiguous(partition: Partition) → bool[source]

Check if the parts of a partition are connected

Parameters:: partition (Partition) – The proposed next Partition
Returns:: Whether the partition is contiguous
Return type:: bool

gerrychain.constraints.contiguous_bfs(partition: Partition) → bool[source]

Checks that a given partition’s parts are connected as graphs using a simple breadth-first search.

Parameters:: partition (Partition) – Instance of Partition
Returns:: Whether the parts of this partition are connected
Return type:: bool

gerrychain.constraints.deviation_from_ideal(partition: Partition, attribute: str = 'population') → Dict[int, float][source]

Computes the deviation of the given attribute from exact equality among parts of the partition. Usually attribute is the population, and this function is used to compute how far a districting plan is from exact population equality.

By “deviation” we mean (actual_value - ideal)/ideal (not the absolute value).

Parameters:

partition (Partition) – A partition.
attribute (str, optional) – The Tally to compute deviation for. Default is "population".

Returns:

dictionary from parts to their deviation

Return type:

Dict[int, float]

gerrychain.constraints.districts_within_tolerance(partition: Partition, attribute_name: str = 'population', percentage: float = 0.1) → bool[source]

Check if all districts are within a certain percentage of the “smallest” district, as defined by the given attribute.

Parameters:

partition (Partition) – Partition class instance
attrName (str, optional) – String that is the name of an updater in partition. Default is "population".
percentage (float, optional) – What percent (as a number between 0 and 1) difference is allowed. Default is 0.1.

Returns:

Whether the districts are within specified tolerance

Return type:

bool

gerrychain.constraints.no_vanishing_districts(partition: Partition) → bool[source]

Require that no districts be completely consumed.

Parameters:: partition (Partition) – Partition to check.
Returns:: Whether no districts are completely consumed.
Return type:: bool

gerrychain.constraints.refuse_new_splits(partition_county_field: str) → Callable[[Partition], bool][source]

Refuse all proposals that split a county that was previous unsplit.

Parameters:: partition_county_field (str) – Name of field for county information generated by county_splits().
Returns:: Function that returns True if the proposal does not split any new counties.
Return type:: Callable[[Partition], bool]

gerrychain.constraints.single_flip_contiguous(partition: Partition) → bool[source]

Check if swapping the given node from its old assignment disconnects the old assignment class.

Parameters:: partition (Partition) – The proposed next Partition
Returns:: whether the partition is contiguous
Return type:: bool

We assume that removed_node belonged to an assignment class that formed a connected subgraph. To see if its removal left the subgraph connected, we check that the neighbors of the removed node are still connected through the changed graph.

gerrychain.constraints.within_percent_of_ideal_population(initial_partition: Partition, percent: float = 0.01, pop_key: str = 'population') → Bounds[source]

Require that all districts are within a certain percent of “ideal” (i.e., uniform) population.

Ideal population is defined as “total population / number of districts.”

Parameters:

initial_partition (Partition) – Starting partition from which to compute district information.
percent (float, optional) – Allowed percentage deviation. Default is 1%.
pop_key (str, optional) – The name of the population Tally. Default is "population".

Returns:

A Bounds constraint on the population attribute identified by pop_key.

Return type:

Bounds

Updaters 

class gerrychain.updaters.CountySplit(value)[source]

Enum to track county splits in a partition.

Variables:

NOT_SPLIT – The county is not split.
NEW_SPLIT – The county is split in the current partition.
OLD_SPLIT – The county is split in the parent partition.

class gerrychain.updaters.DataTally(data: Dict | Series | str, alias: str)[source]

An updater for tallying numerical data that is not necessarily stored as node attributes

Variables:

data – A Dict or Series indexed by the graph’s nodes, or the string key for a node attribute containing the Tally’s data.
alias – The name of the tally in the Partition’s updaters dictionary

Parameters:

data (Union[Dict, pandas.Series, str]) – A Dict or Series indexed by the graph’s nodes, or the string key for a node attribute containing the Tally’s data.
alias (str) – The name of the tally in the Partition’s updaters dictionary

Returns:

None

class gerrychain.updaters.Election(name: str, party_names_to_node_attribute_names: Dict | List, alias: str | None = None)[source]

Represents the data of one election, with races conducted in each part of the partition.

As we vary the districting plan, we can use the same node-level vote totals to tabulate hypothetical elections. To do this manually with tallies, we would have to maintain tallies for each party, as well as the total number of votes, and then compute the electoral results and percentages from scratch every time. To make this simpler, this class provides an ElectionUpdater to manage these tallies. The updater returns an ElectionResults class giving a convenient view of the election results, with methods like wins() or percent() for common queries the user might make on election results.

Example usage:

# Assuming your nodes have attributes "2008_D", "2008_R"
# with (for example) 2008 senate election vote totals
election = Election(
    "2008 Senate",
    {"Democratic": "2008_D", "Republican": "2008_R"},
    alias="2008_Sen"
)

# Assuming you already have a graph and assignment:
partition = Partition(
    graph,
    assignment,
    updaters={"2008_Sen": election}
)

# The updater returns an ElectionResults instance, which
# we can use (for example) to see how many seats a given
# party would win in this partition using this election's
# vote distribution:
partition["2008_Sen"].wins("Republican")

Variables:

name – The name of the election. (e.g. “2008 Presidential”)
parties – A list of the names of the parties in the election.
node_attribute_names – A list of the node_attribute_names in the graph’s node data that hold the vote totals for each party.
party_names_to_node_attribute_names – A dictionary mapping party names to the node_attribute_names in the graph’s node data that hold the vote totals for that party.
tallies – A dictionary mapping party names to DataTally objects that manage the vote totals for that party.
updater – An ElectionUpdater object that manages the tallies and returns an ElectionResults object.
alias – The name that the election is registered under in the partition’s dictionary of updaters.

Parameters:

name (str) – The name of the election. (e.g. “2008 Presidential”)
party_names_to_node_attribute_names (Dict[str, str]) – A mapping from the name of a party to the name of an attribute of a node that contains the vote totals for that party. This parameter can be either a list or a dict. If a list, then the name of the party and the name of the node attribute are the same, for instance: [“Dem”, “Rep”] would indicate that the “Dem” party vote totals are stored in the “Dem” node attribute. If a list, then there are two possibilities.

A dictionary matching party names to their: data node_attribute_names, either as actual node_attribute_names (list-like, indexed by nodes) or as string keys for the node attributes that hold the party’s vote totals. Or, a list of strings which will serve as both the party names and the node attribute keys.

Parameters:: alias (Optional[str], optional) – Alias that the election is registered under in the Partition’s dictionary of updaters.

class gerrychain.updaters.Tally(fields: str | ~typing.List[str], alias: str | None = None, dtype: ~typing.Type = <class 'int'>)[source]

An updater for keeping a tally of one or more node attributes.

Variables:

fields – The list of node attributes that you want to tally. Or just a single attribute name as a string.
alias – The aliased name of this Tally (meaning, the key corresponding to this Tally in the Partition’s updaters dictionary)
dtype – The type (int, float, etc.) that you want the tally to have

Parameters:

fields (Union[str, List[str]]) – The list of node attributes that you want to tally. Or a just a single attribute name as a string.
alias (Optional[str], optional) – The aliased name of this Tally (meaning, the key corresponding to this Tally in the Partition’s updaters dictionary). Default is None.
dtype (Any, optional) – The type (int, float, etc.) that you want the tally to have. Default is int.

Returns:

None

gerrychain.updaters.boundary_nodes(partition, alias: str = 'boundary_nodes') → Set[source]

Parameters:

partition (Partition) – A partition of a Graph
alias (str, optional) – The name of the attribute that the boundary nodes are stored under. Default is ‘boundary_nodes’.

Returns:

The set of nodes in the partition that are on the boundary.

Return type:

Set

gerrychain.updaters.compute_edge_flows(partition) → Dict[source]

Parameters:: partition (Partition) – A partition of a Graph
Returns:: A flow dictionary containing the flow from the parent of this partition to this partition. This dictionary is of the form {part: {‘in’: <set of edges that flowed in>, ‘out’: <set of edges that flowed out>}}.
Return type:: Dict

gerrychain.updaters.county_splits(partition_name: str, county_field_name: str) → Callable[source]

Update that allows for the tracking of county splits.

Parameters:

partition_name (str) – Name that the Partition instance will store.
county_field_name (str) – Name of county ID field on the graph.

Returns:

The tracked data is a dictionary keyed on the county ID. The stored values are tuples of the form (split, nodes, seen). split is a CountySplit enum, nodes is a list of node IDs, and seen is a list of assignment IDs that are contained in the county.

Return type:

Callable

gerrychain.updaters.cut_edges(partition)[source]

Parameters:: partition (Partition) – A partition of a Graph
Returns:: The set of edges that are cut by the given partition.
Return type:: Set[Tuple]

gerrychain.updaters.cut_edges_by_part(partition, previous: Set[Tuple], new_edges: Set[Tuple], old_edges: Set[Tuple]) → Set[Tuple][source]

Updater function that responds to the flow of edges between different partitions.

Parameters:

partition (Partition) – A partition of a Graph
previous (Set[Tuple]) – The previous set of edges for a fixed part of the given partition.
new_edges (Set[Tuple]) – The set of edges that have flowed into the given part of the partition.
old_edges (Set[Tuple]) – The set of cut edges in the previous partition.

Returns:

The new set of cut edges for the newly generated partition.

Return type:

Set

gerrychain.updaters.exterior_boundaries(partition, previous: Set, inflow: Set, outflow: Set) → Dict[source]

Updater function that responds to the flow of nodes between different partitions.

Parameters:

partition (Partition) – A partition of a Graph
previous (Set) – The previous set of exterior boundary nodes for a fixed part of the given partition.
inflow (Set) – The set of nodes that have flowed into the given part of the partition.
outflow (Set) – The set of nodes that have flowed out of the given part of the partition.

Returns:

A dict mapping each part of the partition to the new exterior boundary of that part.

Return type:

Dict

gerrychain.updaters.exterior_boundaries_as_a_set(partition, previous: Set, inflow: Set, outflow: Set) → Set[source]

Updater function that responds to the flow of nodes between different partitions.

Parameters:

partition (Partition) – A partition of a Graph
previous (Set) – The previous set of exterior boundary nodes for a fixed part of the given partition.
inflow (Set) – The set of nodes that have flowed into the given part of the partition.
outflow (Set) – The set of nodes that have flowed out of the given part of the partition.

Returns:

The new set of exterior boundary nodes for the given part of the partition.

Return type:

Set

gerrychain.updaters.flips(partition) → Dict[source]

Parameters:: partition (Partition) – A partition of a Graph
Returns:: The flips that were made to get from the parent partition to the given partition.
Return type:: Dict

gerrychain.updaters.flows_from_changes(old_partition, new_partition) → Dict[source]

Parameters:

old_partition (Partition) – A partition of a Graph representing the previous step.
new_partition (Partition) – A partition of a Graph representing the current step.

Returns:

A dictionary mapping each node that changed assignment between the previous and current partitions to a dictionary of the form {‘in’: <set of nodes that flowed in>, ‘out’: <set of nodes that flowed out>}.

Return type:

Dict

gerrychain.updaters.interior_boundaries(partition, previous: Set, new_edges: Set, old_edges: Set) → Dict[source]

Updater function that responds to the flow of nodes between different partitions.

Parameters:

partition (Partition) – A partition of a Graph
previous (Set) – The previous set of exterior boundary nodes for a fixed part of the given partition.
new_edges (Set) – The set of edges that have flowed into the given part of the partition.
old_edges (Set) – The set of edges that have flowed out of the given part of the partition.

Returns:

A dict mapping each part of the partition to the new interior boundary of that part.

Return type:

Dict

gerrychain.updaters.num_spanning_trees(partition) → Dict[int, int][source]

Returns:: The number of spanning trees in each part (district) of a partition.
Return type:: Dict[int, int]

gerrychain.updaters.perimeter(partition) → Dict[int, float][source]

Parameters:: partition (Partition) – A partition of a Graph
Returns:: A dictionary mapping each part of a partition to its perimeter.
Return type:: Dict[int, float]

gerrychain.updaters.tally_region_splits(reg_attr_lst)[source]

A naive updater for tallying the number of times a region attribute is split. for each region attribute in reg_attr_lst.

Parameters:: reg_attr_lst (List[str]) – A list of region names to tally splits for.
Returns:: A function that takes a partition and returns a dictionary which maps the region name to the number of times that it is split in a a particular partition.
Return type:: Callable

Elections 

class gerrychain.updaters.election.Election(name: str, party_names_to_node_attribute_names: Dict | List, alias: str | None = None)[source]

Represents the data of one election, with races conducted in each part of the partition.

As we vary the districting plan, we can use the same node-level vote totals to tabulate hypothetical elections. To do this manually with tallies, we would have to maintain tallies for each party, as well as the total number of votes, and then compute the electoral results and percentages from scratch every time. To make this simpler, this class provides an ElectionUpdater to manage these tallies. The updater returns an ElectionResults class giving a convenient view of the election results, with methods like wins() or percent() for common queries the user might make on election results.

Example usage:

# Assuming your nodes have attributes "2008_D", "2008_R"
# with (for example) 2008 senate election vote totals
election = Election(
    "2008 Senate",
    {"Democratic": "2008_D", "Republican": "2008_R"},
    alias="2008_Sen"
)

# Assuming you already have a graph and assignment:
partition = Partition(
    graph,
    assignment,
    updaters={"2008_Sen": election}
)

# The updater returns an ElectionResults instance, which
# we can use (for example) to see how many seats a given
# party would win in this partition using this election's
# vote distribution:
partition["2008_Sen"].wins("Republican")

Variables:

name – The name of the election. (e.g. “2008 Presidential”)
parties – A list of the names of the parties in the election.
node_attribute_names – A list of the node_attribute_names in the graph’s node data that hold the vote totals for each party.
party_names_to_node_attribute_names – A dictionary mapping party names to the node_attribute_names in the graph’s node data that hold the vote totals for that party.
tallies – A dictionary mapping party names to DataTally objects that manage the vote totals for that party.
updater – An ElectionUpdater object that manages the tallies and returns an ElectionResults object.
alias – The name that the election is registered under in the partition’s dictionary of updaters.

Parameters:

name (str) – The name of the election. (e.g. “2008 Presidential”)
party_names_to_node_attribute_names (Dict[str, str]) – A mapping from the name of a party to the name of an attribute of a node that contains the vote totals for that party. This parameter can be either a list or a dict. If a list, then the name of the party and the name of the node attribute are the same, for instance: [“Dem”, “Rep”] would indicate that the “Dem” party vote totals are stored in the “Dem” node attribute. If a list, then there are two possibilities.

A dictionary matching party names to their: data node_attribute_names, either as actual node_attribute_names (list-like, indexed by nodes) or as string keys for the node attributes that hold the party’s vote totals. Or, a list of strings which will serve as both the party names and the node attribute keys.

Parameters:: alias (Optional[str], optional) – Alias that the election is registered under in the Partition’s dictionary of updaters.

class gerrychain.updaters.election.ElectionResults(election: Election, counts: Dict[str, Dict[int, float]], regions: List[int])[source]

Represents the results of an election. Provides helpful methods to answer common questions you might have about an election (Who won? How many seats?, etc.).

Variables:

election – The Election object that these results are associated with.
totals_for_party – A dictionary mapping party names to the total number of votes that party received in each part of the partition.
regions – A list of regions that we would like the results for.
totals – A dictionary mapping each part of the partition to the total number of votes cast in that part.
percents_for_party – A dictionary mapping party names to the percentage of votes that party received in each part of the partition.

Note

The variable “regions” is generally called “parts” in other sections of the codebase, but we have changed it here to avoid confusion with the parameter “party” that often appears within the class.

Parameters:

election (Election) – The Election object that these results are associated with.
regions (List[int]) – A list of regions that we would like to consider (e.g. congressional districts).

Counts:

A dictionary mapping party names to the total number of votes that party received in each part of the partition.

Returns:

None

count(party: str, region: str | None = None) → int[source]

Parameters:

party (str) – Party ID.
region (Optional[int], optional) – ID of the part of the partition whose votes we want to tally.

Returns:

The total number of votes that party received in a given region (part of the partition). If region is omitted, returns the overall vote total of party.

Return type:

int

counts(party: str) → Tuple[source]

Parameters:: party (str) – Party ID
Returns:: tuple of the total votes cast for party in each part of the partition
Return type:: Tuple

efficiency_gap() → float[source]

Computes the efficiency gap for this ElectionResults object.

See: efficiency_gap()

Returns:: The efficiency gap for this election.
Return type:: float

mean_median() → float[source]

Computes the mean-median score for this ElectionResults object.

See: mean_median()

Returns:: The mean-median score for this election.
Return type:: float

mean_thirdian() → float[source]

Computes the mean-thirdian score for this ElectionResults object.

See: mean_thirdian()

Returns:: The mean-thirdian score for this election.
Return type:: float

partisan_bias() → float[source]

Computes the partisan bias for this ElectionResults object.

See: partisan_bias()

Returns:: The partisan bias for this election.
Return type:: float

partisan_gini() → float[source]

Computes the Gini score for this ElectionResults object.

See: partisan_gini()

Returns:: The partisan Gini score for this election.
Return type:: float

percent(party: str, region: int | None = None) → float[source]

Parameters:

party (str) – Party ID.
region (Optional[int], optional) – ID of the part of the partition whose votes we want to tally.

Returns:

The percentage of the vote that party received in a given region (part of the partition). If region is omitted, returns the overall vote share of party.

Return type:

float

percents(party: str) → Tuple[source]

Parameters:: party (str) – Party ID
Returns:: The tuple of the percentage of votes that party received in each part of the partition
Return type:: Tuple

seats(party: str) → int[source]

Parameters:: party (str) – Party name
Returns:: The number of seats that party won.
Return type:: int

total_votes() → int[source]

Returns:: The total number of votes cast in the election.
Return type:: int

votes(party: str) → Tuple[source]

An alias for counts().

Parameters:: party (str) – Party ID
Returns:: tuple of the total votes cast for party in each part of the partition
Return type:: Tuple

wins(party: str) → int[source]

An alias for seats().

Parameters:: party (str) – Party name
Returns:: The number of seats that party won.
Return type:: int

won(party: str, region: str) → bool[source]

Parameters:

party (str) – Party ID
region (str) – ID of the part of the partition whose votes we want to tally.

Returns:

Answer to “Did party win the region in part region?”

Return type:

bool

class gerrychain.updaters.election.ElectionUpdater(election: Election)[source]

The updater for computing the election results in each part of the partition after each step in the Markov chain. The actual results are returned to the user as an ElectionResults instance.

Variables:: election – The Election object that this updater is associated with.

get_previous_values(partition) → Dict[str, Dict[int, float]][source]

Parameters:: partition (Partition) – The partition whose parent we want to obtain the previous vote totals from.
Returns:: A dictionary mapping party names to the vote totals that party received in each part of the parent of the current partition.
Return type:: Dict[str, Dict[int, float]]

gerrychain.updaters.election.format_part_results(percents_for_party: Dict[str, Dict[int, float]], part: int) → str[source]

Parameters:

percents_for_party (Dict[str, Dict[int, float]]) – A dictionary mapping party names to a dict containing the percentage of votes that party received in each part of the partition.
part (int) – The part of the partition whose results we want to format.

Returns:

A formatted string containing the results for the given part of the partition.

Return type:

str

gerrychain.updaters.election.get_percents(counts: Dict, totals: Dict) → Dict[source]

Parameters:

counts (Dict) – A dictionary mapping each part in a partition to the count of the number of votes that a party received in that part.
totals (Dict) – A dictionary mapping each part in a partition to the total number of votes cast in that part.

Returns:

A dictionary mapping each part in a partition to the percentage

Return type:

Dict

Grids 

To make it easier to play around with GerryChain, we have provided a Grid class representing a partition of a grid graph. This is especially useful if you want to start experimenting but do not yet have a clean set of data and geometries to build your graph from.

class gerrychain.grid.Grid(dimensions: Tuple[int, int] | None = None, with_diagonals: bool = False, assignment: Dict | None = None, updaters: Dict[str, Callable] | None = None, parent: Grid | None = None, flips: Dict[Tuple[int, int], int] | None = None)[source]

The Grid class represents a grid partitioned into districts. It is useful for running little experiments with GerryChain without needing to do any data processing or cleaning to get started.

Example usage:

grid = Grid((10,10))

The nodes of grid.graph are labelled by tuples (i,j), for 0 <= i <= 10 and 0 <= j <= 10. Each node has an area of 1 and each edge has shared_perim 1.

If the updaters are not specified, the default updaters are used, which are as follows:

default_updaters = {
    "cut_edges": cut_edges,
    "population": Tally("population"),
    "perimeter": perimeter,
    "exterior_boundaries": exterior_boundaries,
    "interior_boundaries": interior_boundaries,
    "boundary_nodes": boundary_nodes,
    "area": Tally("area", alias="area"),
    "polsby_popper": polsby_popper,
    "cut_edges_by_part": cut_edges_by_part,
}

Parameters:

dimensions (Tuple[int, int], optional) – The grid dimensions (rows, columns), defaults to None.
with_diagonals (bool, optional) – If True, includes diagonal connections, defaults to False.
assignment (Dict, optional) – Node-to-district assignments, defaults to None.
updaters (Dict[str, Callable], optional) – Custom updater functions, defaults to None.
parent (Grid, optional) – Parent Grid object for inheritance, defaults to None.
flips (Dict[Tuple[int, int], int], optional) – Node flips for partition changes, defaults to None.

Raises:

Exception – If neither dimensions nor parent is provided.

Spanning tree methods 

The recom() proposal function operates on spanning trees of the adjacency graph in order to generate new contiguous districting plans with balanced population.

The gerrychain.tree submodule exposes some helpful functions for partitioning graphs using spanning trees methods. These may be used to implement proposal functions or to generate initial plans for running Markov chains, as described in MGGG’s 2018 Virginia House of Delegates report.

This module provides tools and algorithms for manipulating and analyzing graphs, particularly focused on partitioning graphs based on population data. It leverages the NetworkX library to handle graph structures and implements various algorithms for graph partitioning and tree traversal.

Key functionalities include:

Predecessor and successor functions for graph traversal using breadth-first search.
Implementation of random and uniform spanning trees for graph partitioning.
The PopulatedGraph class, which represents a graph with additional population data, and methods for assessing and modifying this data.
Functions for finding balanced edge cuts in a populated graph, either through contraction or memoization techniques.
A suite of functions (bipartition_tree, recursive_tree_part, _get_seed_chunks, etc.) for partitioning graphs into balanced subsets based on population targets and tolerances.
Utility functions like get_max_prime_factor_less_than and _recursive_seed_part_inner to assist in complex partitioning tasks.

Dependencies:

networkx: Used for graph data structure and algorithms.
random: Provides random number generation for probabilistic approaches.
typing: Used for type hints.

Last Updated: 25 April 2024

frm: This file, tree.py, needed to be modified to operate on new Graph

objects instead of NetworkX Graph objects because the routines are used by the Graph objects inside a Partion, which will soon be based on RustworkX. More specifically, these routines are used by Proposals, and we will soon switch to having the underlying Graph object used in Partitions and Proposals be based on RustworkX.

It may be the case that they are ONLY ever used by Proposals and hence could just have been rewritten to operate on RustworkX Graph objects, but there seemed to be no harm in having them work either way. It was also a good proving ground for testing whether the new Graph object could behave like a NetworkX Graph object (in terms of attribute access and syntax).

frm: RX Documentation

Many of the functions in this file operate on subgraphs which are different from NX subgraphs because the node_ids change in the subgraph. To deal with this, in graph.py we have a _node_id_to_parent_node_id_map data member for Graph objects which maps the node_ids in a subgraph to the corresponding node_id in its parent graph. This will allow routines operating on subgraphs to return results using the node_ids of the parent graph.

Note that for top-level graphs, we still define this _node_id_to_parent_node_id_map, but in this case it is an identity map that just maps each node_id to itself. This allows code to always translate correctly, even if operating on a top-level graph.

As a matter of coding convention, all calls to graph.subgraph() have been placed in the actual parameter list of function calls. This limits the scope of the subgraph node_ids to the called function - eliminating the risk of those node_ids leaking into surrounding code. Stated differently, this eliminates the cognitive load of trying to remember whether a node_id is a parent or a subgraph node_id.

exception gerrychain.tree.BalanceError[source]: Raised when a balanced cut cannot be found.

exception gerrychain.tree.BipartitionWarning[source]: Generally raised when it is proving difficult to find a balanced cut.

class gerrychain.tree.Cut(edge=None, weight=None, subset=None)

Represents a cut in a graph.

Create new instance of Cut(edge, weight, subset)

edge: The edge where the cut is made. Defaults to None.

subset: The (frozen) subset of nodes on one side of the cut. Defaults to None.

weight: The weight assigned to the edge (if any). Defaults to None.

class gerrychain.tree.PopulatedGraph(graph: Graph, populations: Dict, ideal_pop: float | int, epsilon: float)[source]

A class representing a graph with population information.

Variables:

graph – The underlying graph structure.
subsets – A dictionary mapping nodes to their subsets.
population – A dictionary mapping nodes to their populations.
tot_pop – The total population of the graph.
ideal_pop – The ideal population for each district.
epsilon – The tolerance for population deviation from the ideal population within each district.

Parameters:

graph (Graph) – The underlying graph structure.
populations (Dict) – A dictionary mapping nodes to their populations.
ideal_pop (Union[float, int]) – The ideal population for each district.
epsilon (float) – The tolerance for population deviation as a percentage of the ideal population within each district.

has_ideal_population(node, one_sided_cut: bool = False) → bool[source]

Checks if a node has an ideal population within the graph up to epsilon.

Parameters:

node (Any) – The node to check.
one_sided_cut (bool, optional) – Whether or not we are cutting off a single district. When set to False, we check if the node we are cutting and the remaining graph are both within epsilon of the ideal population. When set to True, we only check if the node we are cutting is within epsilon of the ideal population. Defaults to False.

Returns:

True if the node has an ideal population within the graph up to epsilon.

Return type:

bool

exception gerrychain.tree.PopulationBalanceError[source]: Raised when the population of a district is outside the acceptable epsilon range.

exception gerrychain.tree.ReselectException[source]: Raised when the tree-splitting algorithm is unable to find a balanced cut after some maximum number of attempts, but the user has allowed the algorithm to reselect the pair of districts from parent graph to try and recombine.

gerrychain.tree.bipartition_tree(subgraph_to_split: ~gerrychain.graph.graph.Graph, pop_col: str, pop_target: int | float, epsilon: float, node_repeats: int = 1, spanning_tree: ~gerrychain.graph.graph.Graph | None = None, spanning_tree_fn: ~typing.Callable = <function random_spanning_tree>, region_surcharge: ~typing.Dict | None = None, balance_edge_fn: ~typing.Callable = <function find_balanced_edge_cuts_memoization>, one_sided_cut: bool = False, choice: ~typing.Callable = <bound method Random.choice of <random.Random object>>, max_attempts: int | None = 100000, warn_attempts: int = 1000, allow_pair_reselection: bool = False, cut_choice: ~typing.Callable = <function _region_preferred_max_weight_choice>) → Set[source]

This function finds a balanced 2 partition of a graph by drawing a spanning tree and finding an edge to cut that leaves at most an epsilon imbalance between the populations of the parts. If a root fails, new roots are tried until node_repeats in which case a new tree is drawn.

Builds up a connected subgraph with a connected complement whose population is epsilon * pop_target away from pop_target.

Parameters:

graph (Graph) – The graph to partition.
pop_col (str) – The node attribute holding the population of each node.
pop_target (Union[int, float]) – The target population for the returned subset of nodes.
epsilon (float) – The allowable deviation from pop_target (as a percentage of pop_target) for the subgraph’s population.
node_repeats (int, optional) – A parameter for the algorithm: how many different choices of root to use before drawing a new spanning tree. Defaults to 1.
spanning_tree (Optional[Graph], optional) – The spanning tree for the algorithm to use (used when the algorithm chooses a new root and for testing).
spanning_tree_fn (Callable, optional) – The random spanning tree algorithm to use if a spanning tree is not provided. Defaults to random_spanning_tree().
region_surcharge (Optional[Dict], optional) – A dictionary of surcharges for the spanning tree algorithm. Defaults to None.
balance_edge_fn (Callable, optional) – The function to find balanced edge cuts. Defaults to find_balanced_edge_cuts_memoization().
one_sided_cut (bool, optional) – Passed to the balance_edge_fn. Determines whether or not we are cutting off a single district when partitioning the tree. When set to False, we check if the node we are cutting and the remaining graph are both within epsilon of the ideal population. When set to True, we only check if the node we are cutting is within epsilon of the ideal population. Defaults to False.
choice (Callable, optional) – The function to make a random choice of root node for the population tree. Passed to balance_edge_fn. Can be substituted for testing. Defaults to random.random().
max_attempts (Optional[int], optional) – The maximum number of attempts that should be made to bipartition. Defaults to 10000.
warn_attempts (int, optional) – The number of attempts after which a warning is issued if a balanced cut cannot be found. Defaults to 1000.
allow_pair_reselection (bool, optional) – Whether we would like to return an error to the calling function to ask it to reselect the pair of nodes to try and recombine. Defaults to False.
cut_choice (Callable, optional) – The function used to select the cut edge from the list of possible balanced cuts. Defaults to _region_preferred_max_weight_choice() .

Returns:

A subset of nodes of graph (whose induced subgraph is connected). The other part of the partition is the complement of this subset.

Return type:

Set

Raises:

BipartitionWarning – If a possible cut cannot be found after 1000 attempts.
RuntimeError – If a possible cut cannot be found after the maximum number of attempts given by max_attempts.

gerrychain.tree.bipartition_tree_random(subgraph_to_split: ~gerrychain.graph.graph.Graph, pop_col: str, pop_target: int | float, epsilon: float, node_repeats: int = 1, repeat_until_valid: bool = True, spanning_tree: ~gerrychain.graph.graph.Graph | None = None, spanning_tree_fn: ~typing.Callable = <function random_spanning_tree>, balance_edge_fn: ~typing.Callable = <function find_balanced_edge_cuts_memoization>, one_sided_cut: bool = False, choice: ~typing.Callable = <bound method Random.choice of <random.Random object>>, max_attempts: int | None = 100000) → Set[Any] | None[source]

This is like bipartition_tree() except it chooses a random balanced cut, rather than the first cut it finds.

This function finds a balanced 2 partition of a graph by drawing a spanning tree and finding an edge to cut that leaves at most an epsilon imbalance between the populations of the parts. If a root fails, new roots are tried until node_repeats in which case a new tree is drawn.

Builds up a connected subgraph with a connected complement whose population is epsilon * pop_target away from pop_target.

Parameters:

graph (Graph) – The graph to partition.
pop_col (str) – The node attribute holding the population of each node.
pop_target (Union[int, float]) – The target population for the returned subset of nodes.
epsilon (float) – The allowable deviation from pop_target (as a percentage of pop_target) for the subgraph’s population.
node_repeats (int) – A parameter for the algorithm: how many different choices of root to use before drawing a new spanning tree. Defaults to 1.
repeat_until_valid (bool, optional) – Determines whether to keep drawing spanning trees until a tree with a balanced cut is found. If True, a set of nodes will always be returned; if False, None will be returned if a valid spanning tree is not found on the first try. Defaults to True.
spanning_tree (Optional[Graph], optional) – The spanning tree for the algorithm to use (used when the algorithm chooses a new root and for testing). Defaults to None.
spanning_tree_fn (Callable, optional) – The random spanning tree algorithm to use if a spanning tree is not provided. Defaults to random_spanning_tree().
balance_edge_fn (Callable, optional) – The algorithm used to find balanced cut edges. Defaults to find_balanced_edge_cuts_memoization().
one_sided_cut (bool, optional) – Passed to the balance_edge_fn. Determines whether or not we are cutting off a single district when partitioning the tree. When set to False, we check if the node we are cutting and the remaining graph are both within epsilon of the ideal population. When set to True, we only check if the node we are cutting is within epsilon of the ideal population. Defaults to False.
choice (Callable, optional) – The random choice function. Can be substituted for testing. Defaults to random.choice().
max_attempts (Optional[int], optional) – The max number of attempts that should be made to bipartition. Defaults to None.

Returns:

A subset of nodes of graph (whose induced subgraph is connected) or None if a valid spanning tree is not found.

Return type:

Union[Set[Any], None]

gerrychain.tree.bipartition_tree_random_with_num_cuts(graph: ~gerrychain.graph.graph.Graph, pop_col: str, pop_target: int | float, epsilon: float, node_repeats: int = 1, repeat_until_valid: bool = True, spanning_tree: ~gerrychain.graph.graph.Graph | None = None, spanning_tree_fn: ~typing.Callable = <function random_spanning_tree>, balance_edge_fn: ~typing.Callable = <function find_balanced_edge_cuts_memoization>, one_sided_cut: bool = False, choice: ~typing.Callable = <bound method Random.choice of <random.Random object>>, max_attempts: int | None = 100000) → Set[Any] | None[source]

This is like bipartition_tree() except it chooses a random balanced cut, rather than the first cut it finds.

This function finds a balanced 2 partition of a graph by drawing a spanning tree and finding an edge to cut that leaves at most an epsilon imbalance between the populations of the parts. If a root fails, new roots are tried until node_repeats in which case a new tree is drawn.

Builds up a connected subgraph with a connected complement whose population is epsilon * pop_target away from pop_target.

Parameters:

graph (Graph) – The graph to partition.
pop_col (str) – The node attribute holding the population of each node.
pop_target (Union[int, float]) – The target population for the returned subset of nodes.
epsilon (float) – The allowable deviation from pop_target (as a percentage of pop_target) for the subgraph’s population.
node_repeats (int) – A parameter for the algorithm: how many different choices of root to use before drawing a new spanning tree. Defaults to 1.
repeat_until_valid (bool, optional) – Determines whether to keep drawing spanning trees until a tree with a balanced cut is found. If True, a set of nodes will always be returned; if False, None will be returned if a valid spanning tree is not found on the first try. Defaults to True.
spanning_tree (Optional[Graph], optional) – The spanning tree for the algorithm to use (used when the algorithm chooses a new root and for testing). Defaults to None.
spanning_tree_fn (Callable, optional) – The random spanning tree algorithm to use if a spanning tree is not provided. Defaults to random_spanning_tree().
balance_edge_fn (Callable, optional) – The algorithm used to find balanced cut edges. Defaults to find_balanced_edge_cuts_memoization().
one_sided_cut (bool, optional) – Passed to the balance_edge_fn. Determines whether or not we are cutting off a single district when partitioning the tree. When set to False, we check if the node we are cutting and the remaining graph are both within epsilon of the ideal population. When set to True, we only check if the node we are cutting is within epsilon of the ideal population. Defaults to False.
choice (Callable, optional) – The random choice function. Can be substituted for testing. Defaults to random.choice().
max_attempts (Optional[int], optional) – The max number of attempts that should be made to bipartition. Defaults to None.

Returns:

A subset of nodes of graph (whose induced subgraph is connected) or None if a valid spanning tree is not found.

Return type:

Union[Set[Any], None]

gerrychain.tree.epsilon_tree_bipartition(subgraph_to_split: ~gerrychain.graph.graph.Graph, parts: ~typing.Sequence, pop_target: float | int, pop_col: str, epsilon: float, node_repeats: int = 1, method: ~typing.Callable = functools.partial(<function bipartition_tree>, max_attempts=10000)) → Dict[source]

Uses bipartition_tree() to partition a tree into two parts of population pop_target (within epsilon).

param graph:

The graph to partition into two :math:`

arepsilon`-balanced parts.

type graph:: Graph
param parts:: Iterable of part (district) labels (like [0,1,2] or range(4)).
type parts:: Sequence
param pop_target:: Target population for each part of the partition.
type pop_target:: Union[float, int]
param pop_col:: Node attribute key holding population data.
type pop_col:: str
param epsilon:: How far (as a percentage of pop_target) from pop_target the parts of the partition can be.
type epsilon:: float
param node_repeats:: Parameter for bipartition_tree() to use. Defaults to 1.
type node_repeats:: int, optional
param method:: The partition method to use. Defaults to partial(bipartition_tree, max_attempts=10000).
type method:: Callable, optional
returns:: New assignments for the nodes of graph.
rtype:: dict

gerrychain.tree.find_balanced_edge_cuts_contraction(h: ~gerrychain.tree.PopulatedGraph, one_sided_cut: bool = False, choice: ~typing.Callable = <bound method Random.choice of <random.Random object>>) → List[Cut][source]

Find balanced edge cuts using contraction.

Parameters:

h (PopulatedGraph) – The populated graph.
one_sided_cut (bool, optional) – Whether or not we are cutting off a single district. When set to False, we check if the node we are cutting and the remaining graph are both within epsilon of the ideal population. When set to True, we only check if the node we are cutting is within epsilon of the ideal population. Defaults to False.
choice (Callable, optional) – The function used to make random choices.

Returns:

A list of balanced edge cuts.

Return type:

List[Cut]

gerrychain.tree.find_balanced_edge_cuts_memoization(h: ~gerrychain.tree.PopulatedGraph, one_sided_cut: bool = False, choice: ~typing.Callable = <bound method Random.choice of <random.Random object>>) → List[Cut][source]

Find balanced edge cuts using memoization.

This function takes a PopulatedGraph object and a choice function as input and returns a list of balanced edge cuts. A balanced edge cut is defined as a cut that divides the graph into two subsets, such that the population of each subset is close to the ideal population defined by the PopulatedGraph object.

Parameters:

h (PopulatedGraph) – The PopulatedGraph object representing the graph.
one_sided_cut (bool, optional) – Whether or not we are cutting off a single district. When set to False, we check if the node we are cutting and the remaining graph are both within epsilon of the ideal population. When set to True, we only check if the node we are cutting is within epsilon of the ideal population. Defaults to False.
choice (Callable, optional) – The choice function used to select the root node.

Returns:

A list of balanced edge cuts.

Return type:

List[Cut]

gerrychain.tree.get_max_prime_factor_less_than(n: int, ceil: int) → int | None[source]

Helper function for _recursive_seed_part_inner. Returns the largest prime factor of n less than ceil, or None if all are greater than ceil.

Parameters:

n (int) – The number to find the largest prime factor for.
ceil (int) – The upper limit for the largest prime factor.

Returns:

The largest prime factor of n less than ceil, or None if all are greater than ceil.

Return type:

Optional[int]

gerrychain.tree.random_spanning_tree(graph: Graph, region_surcharge: Dict | None = None) → Graph[source]

Builds a spanning tree chosen by Kruskal’s method using random weights.

Parameters:

graph (Graph) – The input graph to build the spanning tree from.
region_surcharge (Optional[Dict], optional) – Dictionary of surcharges to add to the random weights used in region-aware variants.

Returns:

The maximal spanning tree represented as a GerryChain Graph.

Return type:

Graph

gerrychain.tree.recursive_seed_part(graph: ~gerrychain.graph.graph.Graph, parts: ~typing.Sequence, pop_target: float | int, pop_col: str, epsilon: float, method: ~typing.Callable = functools.partial(<function bipartition_tree>, max_attempts=10000), node_repeats: int = 1, n: int | None = None, ceil: int | None = None) → Dict[source]

Returns a partition with num_dists districts balanced within epsilon of pop_target by recursively splitting graph using _recursive_seed_part_inner.

Parameters:

graph (Graph) – The graph
parts (Sequence) – Iterable of part labels (like [0,1,2] or range(4)
pop_target (Union[float, int]) – Target population for each part of the partition
pop_col (str) – Node attribute key holding population data
epsilon (float) – How far (as a percentage of pop_target) from pop_target the parts of the partition can be
method (Callable, optional) – Function used to find balanced partitions at the 2-district level Defaults to bipartition_tree()
node_repeats (int, optional) – Parameter for bipartition_tree() to use. Defaults to 1.
n (Optional[int], optional) – Either a positive integer (greater than 1) or None. If n is a positive integer, this function will recursively create a seed plan by either biting off districts from graph or dividing graph into n chunks and recursing into each of these. If n is None, this function prime factors ``num_dists``=n_1*n_2*…*n_k (n_1 > n_2 > … n_k) and recursively partitions graph into n_1 chunks. Defaults to None.
ceil (Optional[int], optional) – Either a positive integer (at least 2) or None. Relevant only if n is None. If ceil is a positive integer then finds the largest factor of num_dists less than or equal to ceil, and recursively splits graph into that number of chunks, or bites off a district if that number is 1. Defaults to None.

Returns:

New assignments for the nodes of graph.

Return type:

dict

gerrychain.tree.recursive_tree_part(graph: ~gerrychain.graph.graph.Graph, parts: ~typing.Sequence, pop_target: float | int, pop_col: str, epsilon: float, node_repeats: int = 1, method: ~typing.Callable = functools.partial(<function bipartition_tree>, max_attempts=10000)) → Dict[source]

Uses bipartition_tree() recursively to partition a tree into len(parts) parts of population pop_target (within epsilon). Can be used to generate initial seed plans or to implement ReCom-like “merge walk” proposals.

param graph:

The graph to partition into len(parts) :math:`

arepsilon`-balanced parts.

type graph:: Graph
param parts:: Iterable of part (district) labels (like [0,1,2] or range(4)).
type parts:: Sequence
param pop_target:: Target population for each part of the partition.
type pop_target:: Union[float, int]
param pop_col:: Node attribute key holding population data.
type pop_col:: str
param epsilon:: How far (as a percentage of pop_target) from pop_target the parts of the partition can be.
type epsilon:: float
param node_repeats:: Parameter for bipartition_tree() to use. Defaluts to 1.
type node_repeats:: int, optional
param method:: The partition method to use. Defaults to partial(bipartition_tree, max_attempts=10000).
type method:: Callable, optional
returns:: New assignments for the nodes of graph.
rtype:: dict

gerrychain.tree.uniform_spanning_tree(graph: ~gerrychain.graph.graph.Graph, choice: ~typing.Callable = <bound method Random.choice of <random.Random object>>) → Graph[source]

Builds a spanning tree chosen uniformly from the space of all spanning trees of the graph. Uses Wilson’s algorithm.

Parameters:

graph (Graph) – Graph
choice (Callable, optional) – random.choice(). Defaults to random.choice().

Returns:

A spanning tree of the graph chosen uniformly at random.

Return type:

Graph

Metrics 

gerrychain.metrics.efficiency_gap(election_results) → float[source]

Computes the efficiency gap for the given ElectionResults. A positive value indicates an advantage for the first party listed in the Election’s party_names_to_node_attribute_names dictionary.

Parameters:: election_results (ElectionResults) – An ElectionResults object
Returns:: The efficiency gap for the given ElectionResults
Return type:: float

gerrychain.metrics.mean_median(election_results) → float[source]

Computes the Mean-Median score for the given ElectionResults. A positive value indicates an advantage for the first party listed in the Election’s party_names_to_node_attribute_names dictionary.

Parameters:: election_results (ElectionResults) – An ElectionResults object
Returns:: The Mean-Median score for the given ElectionResults
Return type:: float

gerrychain.metrics.partisan_bias(election_results) → float[source]

Computes the partisan bias for the given ElectionResults. The partisan bias is defined as the number of districts with above-mean vote share by the first party divided by the total number of districts, minus 1/2.

Parameters:: election_results (ElectionResults) – An ElectionResults object
Returns:: The partisan bias for the given ElectionResults
Return type:: float

gerrychain.metrics.partisan_gini(election_results) → float[source]

Computes the partisan Gini score for the given ElectionResults. The partisan Gini score is defined as the area between the seats-votes curve and its reflection about (.5, .5).

For more information on the computation, see Definition 1 in: https://arxiv.org/pdf/2008.06930.pdf

Parameters:: election_results (ElectionResults) – An ElectionResults object
Returns:: The partisan Gini score for the given ElectionResults
Return type:: float

gerrychain.metrics.polsby_popper(partition) → Dict[int, float][source]

Computes Polsby-Popper compactness scores for each district in the partition.

Parameters:: partition (Partition) – The partition to compute scores for
Returns:: A dictionary mapping each district ID to its Polsby-Popper score
Return type:: Dict[int, float]

gerrychain.metrics.wasted_votes(party1_votes: int, party2_votes: int) → Tuple[int, int][source]

Computes the wasted votes for each party in the given race. :param party1_votes: the number of votes party1 received in the race :type party1_votes: int :param party2_votes: the number of votes party2 received in the race :type party2_votes: int

Returns:: a tuple of the wasted votes for each party
Return type:: Tuple[int, int]

Diversity stats 

Simple tooling to collect diversity stats on chain runs

class gerrychain.meta.diversity.DiversityStats(unique_plans: int, unique_districts: int, steps_taken: int)[source]

Lightweight stats object that reports the diversity of a given chain.

Variables:

unique_plans – The number of unique plans seen so far.
unique_districts – The number of unique districts seen so far.
steps_taken – The number of steps taken so far.

Example usage:

DiversityStats(unique_plans=44162, unique_districts=82992, steps_taken=100000)

gerrychain.meta.diversity.collect_diversity_stats(chain: Iterable[Partition]) → Iterable[Tuple[Partition, DiversityStats]][source]

Report the diversity of the chain being run, live, as a drop-in wrapper. Requires the cut_edges updater on each Partition object. Plans/districts are considered distinct if they are not isomorphic. That is, relabled plans and districts are considered non-unique and counted as duplicate.

Example usage:

for partition, stats in collect_diversity_stats(
    Replay(
        graph,
        "sample-run.chain"
        )
):
    print(stats)
    # normal chain stuff here

Parameters:: chain (Iterable[Partition]) – A chain object to collect stats on.
Returns:: An iterable of (partition, DiversityStat).
Return type:: Iterable[Tuple[Partition, DiversityStats]]