Grids and Spanning Trees¶

Grids¶

The Grid class provides a partition of a grid graph for experiments that do not require external geographic data.

class gerrychain.grid.Grid(dimensions: tuple[int, int] | None = None, with_diagonals: bool = False, assignment: dict[tuple[int, int], int] | None = None, updaters: dict[str, Callable[[Partition], object]] | None = None, parent: Grid | None = None, flips: dict[tuple[int, int], int] | None = None)[source]¶

The Grid class is a subclass of Partition. It represents a grid graph with some node data and some edge data and that has been partitioned into districts (parts). It is a quick way to get a Partition that you can then experiment with.

It is useful for running little experiments with GerryChain without needing to do any data processing or cleaning to get started.

In a real GerryChain task, one would typically need to find data, clean that data (for instance to get rid of islands), make sure that the data you wanted for your analysis exists for every node (for instance, population), and then create an initial assignment of nodes to districts (parts). The Grid class allows you to obtain a Partition object that has all of those tasks already done.

The following node and edge data are set:

Node Data:

“population” set to 1,
“area” set to 1
“boundary_node” set to True iff a boundary node - see _get_boundary_perim()
“boundary_perim” set to perimeter touching the boundary - see _get_boundary_perim()

Edge Data:

“shared_perim” set to 1 except for diagonal edges (if any)

The number of districts (parts) is set to be half the number of columns (rounded down)

Example usage:

grid = Grid((10,10))

Note that 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.

Initialize a Grid instance.

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. Note that flips are a dict of the form: {node_id: part}. In the case of a Grid, a node_id is a tuple indicating its position in the grid, so for a Grid the flips look like: {(row_node_id, col_node_id): part}

Raises:

Exception – If neither dimensions nor parent is provided.

Spanning tree methods¶

The recom() proposal operates on spanning trees to generate new contiguous districting plans with balanced population.

The gerrychain.tree module exposes functions for partitioning graphs with spanning trees. These can implement proposal functions or generate initial plans, as described in MGGG’s 2018 Virginia House of Delegates report.

GerryChain creates district plans where a district is a set of nodes in a graph that satisfy the specified conditions - for example, having an appropriate population.

This module implements the algorithms that decide what nodes belong in a district (often called a “part” in the code).

There are two sub-modules that provide these implementations:

spanning_tree.py implements functions to create a spanning tree for a graph (or subgraph). Spanning trees are fundamental to how GerryChain works - they convert a graph into a tree that can then be traversed bottom up to compute population totals for each subtree, which then allows the code to identify subtrees that can form a district (part).

bipartition.py implements the code that walks spanning trees to identify sets of nodes that are candidates for becoming a district (part).

There is additional documentation in each of these sub-modules.

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

class gerrychain.tree.BipartitionTreeFn(*args, **kwargs)[source]¶

The bipartitioning step used by seed-plan generators.

Called with the subgraph to split and keyword configuration; returns the node set of one side of the bipartition. bipartition_tree() (or a functools.partial of it, to bind extra options like max_attempts) matches this shape.

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

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

class gerrychain.tree.ReComBipartitionTreeFn(*args, **kwargs)[source]¶

The bipartitioning step used by ReCom proposals.

This extends the seed-plan call shape with region_surcharge and returns the node set on one side of the bipartition.

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 | ~gerrychain.graph.graph.FrozenGraph, pop_col: str, pop_target: int | float, epsilon: float, node_repeats: int = 0, spanning_tree: ~gerrychain.graph.graph.Graph | ~gerrychain.graph.graph.FrozenGraph | None = None, spanning_tree_fn: ~collections.abc.Callable[[...], ~gerrychain.graph.graph.Graph] = <function random_spanning_tree>, region_surcharge: dict[str, float] | None = None, spanning_tree_fn_kwargs: ~collections.abc.Mapping[str, object] | None = None, find_balanced_edge_cuts_fn: ~gerrychain.tree.bipartition_tree.FindBalancedEdgeCutsFn = <function find_balanced_edge_cuts_memoization>, single_district_cut: bool = False, rootnode_choice_fn: ~collections.abc.Callable[[~collections.abc.Sequence[~collections.abc.Hashable]], ~collections.abc.Hashable] | None = None, repeat_until_valid: bool = True, max_attempts: int = 100000, warn_attempts: int = 1000, allow_pair_reselection: bool = False, cut_choice_fn: ~gerrychain.tree.bipartition_tree.CutChoiceFn | ~gerrychain.tree.bipartition_tree.RegionAwareCutChoiceFn = <function _region_preferred_max_weight_choice>, *, rng: ~random.Random | int | None = None) → Set[Hashable][source]¶

Find a population-balanced connected subset of nodes.

The returned subset induces a connected subgraph, and its complement forms the other part of the partition.

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.

Each spanning tree is searched once plus node_repeats additional times before 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:

subgraph_to_split (Graph | FrozenGraph) – The graph to partition.
pop_col (str) – The node attribute holding the population of each node.
pop_target (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) – Additional roots to try on each spanning tree before drawing a new tree. Defaults to 0. Positive values are useful with contraction or custom cut-edge finders, but not with the default memoized finder.
spanning_tree (Graph | None, 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 (dict | None, optional) – A dictionary of surcharges for the spanning tree algorithm. Defaults to None.
spanning_tree_fn_kwargs (dict | None, optional) – Extra keyword arguments forwarded verbatim to spanning_tree_fn. Use this to set function-specific options that are not named here, e.g. {"treat_unassigned_as_single_region": True} for random_spanning_tree. Defaults to None.
find_balanced_edge_cuts_fn (FindBalancedEdgeCutsFn, optional) – The function to find balanced edge cuts. Defaults to find_balanced_edge_cuts_memoization. A custom finder must accept single_district_cut, rootnode_choice_fn, and rng as keyword arguments; see FindBalancedEdgeCutsFn.
single_district_cut (bool, optional) – Passed to the find_balanced_edge_cuts_fn. Determines whether 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.
repeat_until_valid (bool, optional) – Whether to keep drawing trees until a valid cut is found. Defaults to True.
rootnode_choice_fn (Callable | None) – The function to make a random choice of root node for the population tree. Passed to find_balanced_edge_cuts_fn. Can be substituted for testing. Defaults to the supplied RNG’s choice.
max_attempts (int, optional) – The maximum number of attempts that should be made to bipartition. Defaults to 100000.
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_fn (CutChoiceFn | RegionAwareCutChoiceFn, optional) – Function used to select the cut edge. Defaults to _region_preferred_max_weight_choice. Note that this function should gracefully handle the case when the edges in the list of possible balanced cuts do not have edge weights - in this case, it should default to a uniform random choice.
rng (random.Random | int | None, optional) – Source of randomness. Pass a shared Random for repeated standalone calls; an integer restarts the stream each call.

Returns:

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

Return type:

set[Hashable] | frozenset[Hashable]

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(*args: Any, **kwargs: Any) → Any¶

Compatibility wrapper for the renamed random bipartition function.

The canonical function returns (num_cuts, nodes). This wrapper warns and returns only the selected nodes, or None when no cut was found, matching bipartition_tree_random.

Parameters:

*args (Any) – Positional arguments forwarded to bipartition_tree_random_with_num_cuts.
**kwargs (Any) – Keyword arguments forwarded to bipartition_tree_random_with_num_cuts.

Returns:

The selected node set when at least one cut was found; otherwise, None.

Return type:

Any

gerrychain.tree.bipartition_tree_random_with_num_cuts(subgraph_to_split: ~gerrychain.graph.graph.Graph | ~gerrychain.graph.graph.FrozenGraph, pop_col: str, pop_target: int | float, epsilon: float, node_repeats: int = 0, repeat_until_valid: bool = True, spanning_tree: ~gerrychain.graph.graph.Graph | ~gerrychain.graph.graph.FrozenGraph | None = None, spanning_tree_fn: ~collections.abc.Callable[[...], ~gerrychain.graph.graph.Graph] = <function random_spanning_tree>, find_balanced_edge_cuts_fn: ~gerrychain.tree.bipartition_tree.FindBalancedEdgeCutsFn = <function find_balanced_edge_cuts_memoization>, single_district_cut: bool = False, rootnode_choice_fn: ~collections.abc.Callable[[~collections.abc.Sequence[~collections.abc.Hashable]], ~collections.abc.Hashable] | None = None, max_attempts: int = 100000, cut_choice_fn: ~gerrychain.tree.bipartition_tree.CutChoiceFn | ~gerrychain.tree.bipartition_tree.RegionAwareCutChoiceFn | None = None, *, rng: ~random.Random | int | None = None) → tuple[int, Set[Hashable]][source]¶

This is like bipartition_tree except it always chooses a random balanced cut.

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. Each spanning tree is searched once plus node_repeats additional times before 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:

subgraph_to_split (Graph) – The graph to partition.
pop_col (str) – The node attribute holding the population of each node.
pop_target (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) – Additional roots to try on each spanning tree before drawing a new tree. Defaults to 0.
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, an empty set is returned when no valid cut is found on the first try. Defaults to True.
spanning_tree (Graph | None, 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.
find_balanced_edge_cuts_fn (FindBalancedEdgeCutsFn, optional) – The algorithm used to find balanced cut edges. Defaults to find_balanced_edge_cuts_memoization. A custom finder must accept single_district_cut, rootnode_choice_fn, and rng as keyword arguments; see FindBalancedEdgeCutsFn.
single_district_cut (bool, optional) – Passed to the find_balanced_edge_cuts_fn. Determines whether 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.
rootnode_choice_fn (Callable | None) – The random choice function. Can be substituted for testing. Defaults to the supplied RNG’s choice.
max_attempts (int) – The max number of attempts that should be made to bipartition. Defaults to 100,000.
cut_choice_fn (CutChoiceFn | RegionAwareCutChoiceFn | None) – Function used to select a cut. Defaults to the supplied RNG’s choice.
rng (random.Random | int | None, optional) – Source of randomness. Pass a shared Random for repeated standalone calls; an integer restarts the stream each call.

Returns:

The number of possible cuts and the selected connected: subset of nodes.

Return type:

tuple[int, AbstractSet[Hashable]]

gerrychain.tree.epsilon_tree_bipartition(*args: Any, **kwargs: Any) → Any¶

Compatibility entry point for the function moved out of gerrychain.tree.

Parameters:

*args (Any) – Positional arguments forwarded to the canonical function.
**kwargs (Any) – Keyword arguments forwarded to the canonical function.

Returns:

The canonical function’s return value.

Return type:

Any

gerrychain.tree.find_balanced_edge_cuts_contraction(h: _PopulatedGraph, single_district_cut: bool = False, rootnode_choice_fn: Callable[[Sequence[Hashable]], Hashable] | None = None, *, rng: Random | int | None = None) → list[_Cut][source]¶

Find balanced edge cuts using contraction.

Parameters:

h (_PopulatedGraph) – The populated graph.
single_district_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.
rootnode_choice_fn (Callable | None) – The function used to select the root node_id. Defaults to the supplied RNG’s choice.
rng (random.Random | int | None, optional) – Source of randomness. Pass a shared Random for repeated standalone calls; an integer restarts the stream each call.

Returns:

A list of balanced edge cuts.

Return type:

list[_Cut]

gerrychain.tree.find_balanced_edge_cuts_memoization(h: _PopulatedGraph, single_district_cut: bool = False, rootnode_choice_fn: Callable[[Sequence[Hashable]], Hashable] | None = None, *, rng: Random | int | None = None) → 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.
single_district_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.
rootnode_choice_fn (Callable | None) – The choice function used to select the root node_id. Defaults to the supplied RNG’s choice.
rng (random.Random | int | None, optional) – Source of randomness. Pass a shared Random for repeated standalone calls; an integer restarts the stream each call.

Returns:

A list of balanced edge cuts.

Return type:

list[_Cut]

gerrychain.tree.predecessors(graph: Any, root: Any) → dict[Any, Any]¶

Compatibility wrapper for Graph.predecessors.

Parameters:

graph (Any) – Graph providing a predecessors method.
root (Any) – Root node passed to that method.

Returns:

Mapping from each reached node to its predecessor.

Return type:

dict[Any, Any]

gerrychain.tree.random_spanning_tree(graph: Graph | FrozenGraph, region_surcharge: dict[str, float] | None = None, treat_unassigned_as_single_region: bool = False, *, rng: Random | int | None = None) → Graph[source]¶

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

Kruskal’s method chooses the edges with the lowest weight first, so edges with high weights will be selected last - with the highest weights not chosen at all (once all the nodes are in the tree, the algorithm stops adding edges). If no region_surcharge is provided, every edge just gets a plain random weight, so the result is an ordinary random spanning tree.

Region surcharge (keeping regions together):

The region_surcharge parameter lets you bias the spanning tree - and therefore the districts eventually cut from it - so that a chosen kind of region (a county, municipality, precinct, or any other group of nodes that share a node attribute) tends to be kept whole.

Surcharges are passed as a dict mapping a node-attribute name to a numeric surcharge, e.g. {"county": 0.5}. For each edge, the surcharge for an attribute is added to that edge’s random weight when the edge crosses a boundary for that attribute - that is, when the two endpoints do NOT share the same non-null value of the attribute. So edges inside a region keep their plain random weight, while edges on the boundary of a region are made heavier.

Since this function builds a minimum spanning tree, making the boundary edges heavier biases the MST toward connecting each region through its cheap interior edges. Therefore, the region tends to appear as a single connected subtree of the spanning tree. Because the bipartition step cuts exactly one edge, a region small enough to fit inside one district then tends to be kept whole. A region larger than a district cannot be kept whole: it still has to be cut enough times to break it into district-sized pieces (a region holding roughly k districts’ worth of population needs at least k - 1 cuts, so a populous county like Los Angeles must be split a dozen or more times no matter how large the surcharge). What a dominating surcharge buys in that case is splitting the region only as many times as its population forces (possibly plus 1 depending on the rest of the plan), rather than carving it up arbitrarily.

Choosing surcharge values: the random weights are drawn uniformly from [0, 1), so the surcharge should be sized relative to that range. A surcharge well below 1 is a soft bias that competes with the random weights (regions are kept together more often, but not always); a surcharge of 1 or more dominates the random weights, so boundary edges are effectively always chosen last and the bias is strong. Larger values mean a stronger preference to keep the region whole.

Multiple region types: region_surcharge may contain several attributes (for example {"county": 0.5, "muni": 0.5}). The surcharges are independent and additive per edge: an edge that crosses both a county boundary and a municipality boundary receives both surcharges. This lets you weight different kinds of region differently, but be aware that with several attributes the surcharges can stack, so keep the combined magnitudes in mind.

Nodes with no region value (selectable via treat_unassigned_as_single_region): an edge is surcharged whenever its endpoints do not share the same non-null attribute value. This always includes an edge between a region node and a region-less node (e.g. a node in no county). The one case you get to choose is an edge between two region-less nodes (both values None), which decides how the “unassigned” territory for that attribute is treated:

Region-less nodes individually splittable (treat_unassigned_as_single_region=False, the default): edges among region-less nodes are also surcharged, so the unassigned area gets no “keep whole” bias and may be divided freely among districts. This is usually the right behavior when region-less nodes are scattered (water, unincorporated areas, etc.), where forcing them to stay together would make little sense.
Unassigned area kept whole (treat_unassigned_as_single_region=True): edges between two region-less nodes are left cheap (since they share the value None), so all region-less nodes are treated like one additional region and biased to stay whole.

The flag is applied per attribute, so for a given attribute its region-less nodes are treated consistently. It has no effect unless some nodes actually lack a value for a surcharged attribute.

Parameters:

graph (Graph) – The input graph to build the spanning tree from.
region_surcharge (dict | None, optional) – Dictionary mapping a node-attribute name to the numeric surcharge added to the random weight of edges that cross a boundary for that attribute. Defaults to None (no surcharge - an ordinary random spanning tree).
treat_unassigned_as_single_region (bool, optional) – How to treat edges between two nodes that both have no value for a surcharged attribute. When False (default), such edges are surcharged, so the region-less (“unassigned”) area may be split freely. When True, such edges are not surcharged, so the region-less area is biased to be kept whole, like any other region. Has no effect when region_surcharge is empty or every node has a value.
rng (random.Random | int | None, optional) – Source of randomness. Pass a shared Random for repeated standalone calls; an integer restarts the stream each call.

Returns:

The minimum spanning tree represented as a GerryChain Graph.

Return type:

Graph

Example

Draw a region-aware spanning tree of the bundled “Gerrymandria” example graph, biased to keep each county connected (and therefore split across as few districts as possible):

from gerrychain.examples import gerrymandria
from gerrychain.tree import random_spanning_tree

graph = gerrymandria()  # 8x8 graph with node attributes "county" and "water_dist"

# A surcharge >= 1 dominates the [0, 1) random weights, strongly preferring to keep
# whole counties together in the spanning tree. We also add a small surcharge for
# water district boundaries to also indicate a preference to keep water together,
# but the county surcharge is the main driver of the bias.
tree = random_spanning_tree(graph, region_surcharge={"county": 2.0, "water_dist": 0.1})

A spanning tree always has len(graph.nodes) - 1 edges; with no region_surcharge you get an ordinary random spanning tree instead.

gerrychain.tree.successors(graph: Any, root: Any) → dict[Any, list[Any]]¶

Compatibility wrapper for Graph.successors.

Parameters:

graph (Any) – Graph providing a successors method.
root (Any) – Root node passed to that method.

Returns:

Mapping from each reached node to its successor nodes.

Return type:

dict[Any, list[Any]]

gerrychain.tree.uniform_spanning_tree(graph: Graph | FrozenGraph, region_surcharge: dict[str, float] | None = None, *, rng: Random | int | None = None) → Graph[source]¶

Builds a spanning tree chosen uniformly from the space of all spanning trees of the graph.

Uses Wilson’s algorithm. If interested, there is a nice animated description of Wilson’s algorithm here:

https://weblog.jamisbuck.org/2011/1/20/maze-generation-wilson-s-algorithm

A brief description of Wilson’s Alorithm follows:

Pick a node at random for the root node of the spanning tree. Then pick any other node and do a random walk until you end up at the root node, but as you go remember the last move you made at each node - which will overwrite any previous move. When you end up at the root node, go back to the starting node and follow the path left behind, which will cleverly contain no cycles because the paths for any cycles were overwritten.

Add the nodes in the path (remembering child and parent) to the list of nodes you have added to the tree. Then pick another node at random that is not already in the tree and do another random walk, ending when you fall on a node already in the tree. Then add the nodes for that random walk to the tree.

Rinse and repeat until all nodes have been added to the tree.

Parameters:

graph (Graph) – The graph from which to sample a spanning tree.
region_surcharge (dict | None, optional) – Not used in this function. It exists in the function signature so that all spanning tree functions will share the same signature.
rng (random.Random | int | None, optional) – Source of randomness. Pass a shared Random for repeated standalone calls; an integer restarts the stream each call.

Returns:

A spanning tree of the graph chosen uniformly at random.

Return type:

Graph