Proposals and Constraints¶

Proposals¶

class gerrychain.proposals.MultiMemberReCom(*args: object, **kwargs: object)[source]¶

Ready-made builders for ReCom with fixed member counts by district label.

The methods mirror the four non-reversible ReCom variants. They use a target population per member and do not provide reversible or letter-named variants. This class is a namespace and cannot be instantiated.

static A(pop_col: str, pop_target: int | float, epsilon: float, members_per_district: Mapping[Hashable, int], region_surcharge: dict[str, float] | None = None, allow_pair_reselection: bool = False) → ProposalFn¶

Build multi-member ReCom with cut-edge pair selection and a minimum spanning tree.

A cut edge is selected uniformly at random, so district pairs are weighted by the number of boundary edges they share. The merged pair is split using a minimum spanning tree on random edge weights. Each district’s target population is pop_target multiplied by its fixed member count in members_per_district.

Parameters:

pop_col (str) – Node attribute containing population data.
pop_target (int | float) – Target population for one elected member.
epsilon (float) – Allowed deviation from each district’s member-adjusted target. Must be in [0, 1).
members_per_district (Mapping[Hashable, int]) – Positive member count for every district label. Member counts remain attached to these labels throughout the chain.
region_surcharge (dict[str, float] | None, optional) – Surcharges used to discourage the spanning tree from crossing specified region boundaries. Defaults to None.
allow_pair_reselection (bool, optional) – Whether to try a different adjacent district pair when tree splitting fails for the selected pair. Defaults to False.

Returns:

A proposal function for use with MarkovChain.

Return type:

ProposalFn

static B(pop_col: str, pop_target: int | float, epsilon: float, members_per_district: Mapping[Hashable, int], region_surcharge: dict[str, float] | None = None, allow_pair_reselection: bool = False) → ProposalFn¶

Build multi-member ReCom with district-pair selection and a minimum spanning tree.

An adjacent district pair is selected uniformly, independent of shared boundary length and member count. The merged pair is split using a minimum spanning tree on random edge weights. Each district’s target population is pop_target multiplied by its fixed member count in members_per_district.

Parameters:

pop_col (str) – Node attribute containing population data.
pop_target (int | float) – Target population for one elected member.
epsilon (float) – Allowed deviation from each district’s member-adjusted target. Must be in [0, 1).
members_per_district (Mapping[Hashable, int]) – Positive member count for every district label. Member counts remain attached to these labels throughout the chain.
region_surcharge (dict[str, float] | None, optional) – Surcharges used to discourage the spanning tree from crossing specified region boundaries. Defaults to None.
allow_pair_reselection (bool, optional) – Whether to try a different adjacent district pair when tree splitting fails for the selected pair. Defaults to False.

Returns:

A proposal function for use with MarkovChain.

Return type:

ProposalFn

static C(pop_col: str, pop_target: int | float, epsilon: float, members_per_district: Mapping[Hashable, int], allow_pair_reselection: bool = False) → ProposalFn¶

Build multi-member ReCom with cut-edge pair selection and a uniform spanning tree.

A cut edge is selected uniformly at random, so district pairs are weighted by the number of boundary edges they share. The merged pair is split using a spanning tree drawn uniformly with Wilson’s algorithm. Each district’s target population is pop_target multiplied by its fixed member count in members_per_district. Region surcharges are not supported because a uniform spanning tree does not use edge weights.

Parameters:

pop_col (str) – Node attribute containing population data.
pop_target (int | float) – Target population for one elected member.
epsilon (float) – Allowed deviation from each district’s member-adjusted target. Must be in [0, 1).
members_per_district (Mapping[Hashable, int]) – Positive member count for every district label. Member counts remain attached to these labels throughout the chain.
allow_pair_reselection (bool, optional) – Whether to try a different adjacent district pair when tree splitting fails for the selected pair. Defaults to False.

Returns:

A proposal function for use with MarkovChain.

Return type:

ProposalFn

static D(pop_col: str, pop_target: int | float, epsilon: float, members_per_district: Mapping[Hashable, int], allow_pair_reselection: bool = False) → ProposalFn¶

Build multi-member ReCom with district-pair selection and a uniform spanning tree.

An adjacent district pair is selected uniformly, independent of shared boundary length and member count. The merged pair is split using a spanning tree drawn uniformly with Wilson’s algorithm. Each district’s target population is pop_target multiplied by its fixed member count in members_per_district. Region surcharges are not supported because a uniform spanning tree does not use edge weights.

Parameters:

pop_col (str) – Node attribute containing population data.
pop_target (int | float) – Target population for one elected member.
epsilon (float) – Allowed deviation from each district’s member-adjusted target. Must be in [0, 1).
members_per_district (Mapping[Hashable, int]) – Positive member count for every district label. Member counts remain attached to these labels throughout the chain.
allow_pair_reselection (bool, optional) – Whether to try a different adjacent district pair when tree splitting fails for the selected pair. Defaults to False.

Returns:

A proposal function for use with MarkovChain.

Return type:

ProposalFn

static cut_edges_mst(pop_col: str, pop_target: int | float, epsilon: float, members_per_district: Mapping[Hashable, int], region_surcharge: dict[str, float] | None = None, allow_pair_reselection: bool = False) → ProposalFn[source]¶

Build multi-member ReCom with cut-edge pair selection and a minimum spanning tree.

Parameters:

pop_col (str) – Node attribute containing population data.
pop_target (int | float) – Target population for one elected member.
epsilon (float) – Allowed deviation from each district’s member-adjusted target. Must be in [0, 1).
members_per_district (Mapping[Hashable, int]) – Positive member count for every district label. Member counts remain attached to these labels throughout the chain.
region_surcharge (dict[str, float] | None, optional) – Surcharges used to discourage the spanning tree from crossing specified region boundaries. Defaults to None.
allow_pair_reselection (bool, optional) – Whether to try a different adjacent district pair when tree splitting fails for the selected pair. Defaults to False.

Returns:

A proposal function for use with MarkovChain.

Return type:

ProposalFn

static cut_edges_ust(pop_col: str, pop_target: int | float, epsilon: float, members_per_district: Mapping[Hashable, int], allow_pair_reselection: bool = False) → ProposalFn[source]¶

Build multi-member ReCom with cut-edge pair selection and a uniform spanning tree.

Parameters:

pop_col (str) – Node attribute containing population data.
pop_target (int | float) – Target population for one elected member.
epsilon (float) – Allowed deviation from each district’s member-adjusted target. Must be in [0, 1).
members_per_district (Mapping[Hashable, int]) – Positive member count for every district label. Member counts remain attached to these labels throughout the chain.
allow_pair_reselection (bool, optional) – Whether to try a different adjacent district pair when tree splitting fails for the selected pair. Defaults to False.

Returns:

A proposal function for use with MarkovChain.

Return type:

ProposalFn

static district_pairs_mst(pop_col: str, pop_target: int | float, epsilon: float, members_per_district: Mapping[Hashable, int], region_surcharge: dict[str, float] | None = None, allow_pair_reselection: bool = False) → ProposalFn[source]¶

Build multi-member ReCom with district-pair selection and a minimum spanning tree.

Parameters:

pop_col (str) – Node attribute containing population data.
pop_target (int | float) – Target population for one elected member.
epsilon (float) – Allowed deviation from each district’s member-adjusted target. Must be in [0, 1).
members_per_district (Mapping[Hashable, int]) – Positive member count for every district label. Member counts remain attached to these labels throughout the chain.
region_surcharge (dict[str, float] | None, optional) – Surcharges used to discourage the spanning tree from crossing specified region boundaries. Defaults to None.
allow_pair_reselection (bool, optional) – Whether to try a different adjacent district pair when tree splitting fails for the selected pair. Defaults to False.

Returns:

A proposal function for use with MarkovChain.

Return type:

ProposalFn

static district_pairs_ust(pop_col: str, pop_target: int | float, epsilon: float, members_per_district: Mapping[Hashable, int], allow_pair_reselection: bool = False) → ProposalFn[source]¶

Build multi-member ReCom with district-pair selection and a uniform spanning tree.

Parameters:

pop_col (str) – Node attribute containing population data.
pop_target (int | float) – Target population for one elected member.
epsilon (float) – Allowed deviation from each district’s member-adjusted target. Must be in [0, 1).
members_per_district (Mapping[Hashable, int]) – Positive member count for every district label. Member counts remain attached to these labels throughout the chain.
allow_pair_reselection (bool, optional) – Whether to try a different adjacent district pair when tree splitting fails for the selected pair. Defaults to False.

Returns:

A proposal function for use with MarkovChain.

Return type:

ProposalFn

class gerrychain.proposals.ProposalFn(*args, **kwargs)[source]¶: Propose a new partition, called as proposal_fn(partition, rng=rng).

class gerrychain.proposals.ReCom(*args: object, **kwargs: object)[source]¶

Ready-made builders for the standard ReCom proposal variants.

Each method returns a proposal function ready to hand to MarkovChain, so instead of the functools.partial incantation:

from functools import partial
proposal_fn = partial(recom, pop_col="TOTPOP", pop_target=ideal_pop, epsilon=0.01)

you can write:

proposal_fn = ReCom.district_pairs_mst(pop_col="TOTPOP", pop_target=ideal_pop, epsilon=0.01)

This class is a namespace, not a type: it cannot be instantiated.

The variants differ along two axes:

Pair selection: cut_edges_* picks a cut edge uniformly at random and merges the two districts on either side of it, so a pair’s chance is proportional to the number of cut edges the districts share. district_pairs_* picks uniformly among the adjacent district pairs themselves.
Spanning tree: *_mst draws a minimum spanning tree on random edge weights using Kruskal’s algorithm. *_ust draws a uniform spanning tree using Wilson’s algorithm.

reversible() is the Reversible ReCom proposal, which samples exactly from the spanning-tree distribution; see reversible_recom().

The aliases A, B, C, D, and R name the same builders after the variants in “Spanning Tree Methods for Sampling Graph Partitions” (Cannon et al., 2022, https://arxiv.org/abs/2210.01401), to ease replication of results from that paper.

These builders expose only the most common options. For anything else (a custom bipartition or spanning-tree function, node_repeats, …), use build_recom_proposal_fn() or build_reversible_recom_proposal_fn(), which these methods wrap, or bind functools.partial(recom, ...) yourself.

static A(pop_col: str, pop_target: int | float, epsilon: float, region_surcharge: dict[str, float] | None = None, allow_pair_reselection: bool = False) → ProposalFn¶

ReCom variant A: cut-edges pair selection, minimum spanning tree.

A cut edge is selected at random and the two districts on either side of it are merged. The merged region is split back into two districts by drawing a minimum spanning tree on random edge weights (Kruskal’s algorithm) and finding a population-balanced cut.

Parameters:

pop_col (str) – The name of the population column.
pop_target (int | float) – The target population for each district.
epsilon (float) – Allowed population deviation as a percentage of the target population.
region_surcharge (dict | None, optional) – Surcharge dictionary for region-aware chains; see random_spanning_tree(). Default is None.
allow_pair_reselection (bool, optional) – Whether to fall back to a cut edge between a different district pair if bipartitioning the merged pair fails. Default is False.

Returns:

A proposal function for use with MarkovChain.

Return type:

ProposalFn

static B(pop_col: str, pop_target: int | float, epsilon: float, region_surcharge: dict[str, float] | None = None, allow_pair_reselection: bool = False) → ProposalFn¶

ReCom variant B: district-pairs pair selection, minimum spanning tree.

A pair of adjacent districts is selected uniformly at random and merged. The merged region is split back into two districts by drawing a minimum spanning tree on random edge weights (Kruskal’s algorithm) and finding a population-balanced cut.

Parameters:

pop_col (str) – The name of the population column.
pop_target (int | float) – The target population for each district.
epsilon (float) – Allowed population deviation as a percentage of the target population.
region_surcharge (dict | None, optional) – Surcharge dictionary for region-aware chains; see random_spanning_tree(). Default is None.
allow_pair_reselection (bool, optional) – Whether to allow reselection of the same district pair if bipartitioning fails. Default is False.

Returns:

A proposal function for use with MarkovChain.

Return type:

ProposalFn

static C(pop_col: str, pop_target: int | float, epsilon: float, allow_pair_reselection: bool = False) → ProposalFn¶

ReCom variant C: cut-edges pair selection, uniform spanning tree.

Like cut_edges_mst(), except the merged region is split using a spanning tree drawn uniformly at random (Wilson’s algorithm). Region surcharges are not supported: a uniform spanning tree ignores edge weights.

Parameters:

pop_col (str) – The name of the population column.
pop_target (int | float) – The target population for each district.
epsilon (float) – Allowed population deviation as a percentage of the target population.
allow_pair_reselection (bool, optional) – Whether to fall back to a cut edge between a different district pair if bipartitioning the merged pair fails. Default is False.

Returns:

A proposal function for use with MarkovChain.

Return type:

ProposalFn

static D(pop_col: str, pop_target: int | float, epsilon: float, allow_pair_reselection: bool = False) → ProposalFn¶

ReCom variant D: district-pairs pair selection, uniform spanning tree.

Like district_pairs_mst(), except the merged region is split using a spanning tree drawn uniformly at random (Wilson’s algorithm). Region surcharges are not supported: a uniform spanning tree ignores edge weights.

Parameters:

pop_col (str) – The name of the population column.
pop_target (int | float) – The target population for each district.
epsilon (float) – Allowed population deviation as a percentage of the target population.
allow_pair_reselection (bool, optional) – Whether to allow reselection of the same district pair if bipartitioning fails. Default is False.

Returns:

A proposal function for use with MarkovChain.

Return type:

ProposalFn

static R(pop_col: str, pop_target: int | float, epsilon: float, max_balanced_edge_cuts: int, repeat_until_valid: bool = False) → ProposalFn¶

ReCom variant R: the reversible ReCom proposal.

Samples exactly from the spanning-tree distribution rather than an approximation of it; see reversible_recom() and the paper “Spanning Tree Methods for Sampling Graph Partitions” (https://arxiv.org/abs/2210.01401) for details.

Parameters:

pop_col (str) – The name of the population column.
pop_target (int | float) – The target population for each district.
epsilon (float) – Allowed population deviation as a percentage of the target population.
max_balanced_edge_cuts (int) – The number of balanced edge cuts to draw from the spanning tree before selecting one, used to make the proposal reversible.
repeat_until_valid (bool, optional) – Whether to repeat until a valid partition is found. Default is False.

Returns:

A proposal function for use with MarkovChain.

Return type:

ProposalFn

static cut_edges_mst(pop_col: str, pop_target: int | float, epsilon: float, region_surcharge: dict[str, float] | None = None, allow_pair_reselection: bool = False) → ProposalFn[source]¶

ReCom variant A: cut-edges pair selection, minimum spanning tree.

Parameters:

pop_col (str) – The name of the population column.
pop_target (int | float) – The target population for each district.
epsilon (float) – Allowed population deviation as a percentage of the target population.
region_surcharge (dict | None, optional) – Surcharge dictionary for region-aware chains; see random_spanning_tree(). Default is None.
allow_pair_reselection (bool, optional) – Whether to fall back to a cut edge between a different district pair if bipartitioning the merged pair fails. Default is False.

Returns:

A proposal function for use with MarkovChain.

Return type:

ProposalFn

static cut_edges_ust(pop_col: str, pop_target: int | float, epsilon: float, allow_pair_reselection: bool = False) → ProposalFn[source]¶

ReCom variant C: cut-edges pair selection, uniform spanning tree.

Parameters:

pop_col (str) – The name of the population column.
pop_target (int | float) – The target population for each district.
epsilon (float) – Allowed population deviation as a percentage of the target population.
allow_pair_reselection (bool, optional) – Whether to fall back to a cut edge between a different district pair if bipartitioning the merged pair fails. Default is False.

Returns:

A proposal function for use with MarkovChain.

Return type:

ProposalFn

static district_pairs_mst(pop_col: str, pop_target: int | float, epsilon: float, region_surcharge: dict[str, float] | None = None, allow_pair_reselection: bool = False) → ProposalFn[source]¶

ReCom variant B: district-pairs pair selection, minimum spanning tree.

Parameters:

pop_col (str) – The name of the population column.
pop_target (int | float) – The target population for each district.
epsilon (float) – Allowed population deviation as a percentage of the target population.
region_surcharge (dict | None, optional) – Surcharge dictionary for region-aware chains; see random_spanning_tree(). Default is None.
allow_pair_reselection (bool, optional) – Whether to allow reselection of the same district pair if bipartitioning fails. Default is False.

Returns:

A proposal function for use with MarkovChain.

Return type:

ProposalFn

static district_pairs_ust(pop_col: str, pop_target: int | float, epsilon: float, allow_pair_reselection: bool = False) → ProposalFn[source]¶

ReCom variant D: district-pairs pair selection, uniform spanning tree.

Parameters:

pop_col (str) – The name of the population column.
pop_target (int | float) – The target population for each district.
epsilon (float) – Allowed population deviation as a percentage of the target population.
allow_pair_reselection (bool, optional) – Whether to allow reselection of the same district pair if bipartitioning fails. Default is False.

Returns:

A proposal function for use with MarkovChain.

Return type:

ProposalFn

static reversible(pop_col: str, pop_target: int | float, epsilon: float, max_balanced_edge_cuts: int, repeat_until_valid: bool = False) → ProposalFn[source]¶

ReCom variant R: the reversible ReCom proposal.

Parameters:

pop_col (str) – The name of the population column.
pop_target (int | float) – The target population for each district.
epsilon (float) – Allowed population deviation as a percentage of the target population.
max_balanced_edge_cuts (int) – The number of balanced edge cuts to draw from the spanning tree before selecting one, used to make the proposal reversible.
repeat_until_valid (bool, optional) – Whether to repeat until a valid partition is found. Default is False.

Returns:

A proposal function for use with MarkovChain.

Return type:

ProposalFn

gerrychain.proposals.build_multi_member_recom_proposal_fn(pop_col: str, pop_target: int | float, epsilon: float, members_per_district: ~collections.abc.Mapping[~collections.abc.Hashable, int], node_repeats: int = 0, region_surcharge: dict[str, float] | None = None, bipartition_tree_fn: ~gerrychain.tree.bipartition_tree.ReComBipartitionTreeFn = <function bipartition_tree>, pair_selection: ~typing.Literal['district_pairs', 'cut_edges'] = 'district_pairs') → ProposalFn[source]¶

Build a multi-member ReCom proposal with fixed member counts by district label.

Parameters:

pop_col (str) – The name of the population column.
pop_target (int | float) – Target population for one member.
epsilon (float) – Allowed deviation from each district’s own target. Must be in [0, 1).
members_per_district (Mapping[Hashable, int]) – Positive member count for every district.
node_repeats (int, optional) – Additional roots to try per spanning tree. Defaults to 0.
region_surcharge (dict | None, optional) – Surcharges for region-aware spanning trees.
bipartition_tree_fn (ReComBipartitionTreeFn, optional) – Tree bipartition function.
pair_selection ("district_pairs" | "cut_edges", optional) – Adjacent-pair selection mode.

Returns:

A proposal function for use with MarkovChain.

Return type:

ProposalFn

gerrychain.proposals.build_recom_proposal_fn(pop_col: str, pop_target: int | float, epsilon: float, node_repeats: int = 0, region_surcharge: dict[str, float] | None=None, bipartition_tree_fn: ReComBipartitionTreeFn = <function bipartition_tree>, pair_selection: Literal['district_pairs', 'cut_edges']='district_pairs') → ProposalFn[source]¶

Build a ReCom proposal function with its configuration bound.

This is the configurable form of the ReCom namespace methods: it exposes every recom() option except partition and rng, which MarkovChain supplies at each step.

Parameters:

pop_col (str) – The name of the population column.
pop_target (int | float) – The target population for each district.
epsilon (float) – Allowed population deviation as a percentage of the target population.
node_repeats (int, optional) – Additional roots to try on each spanning tree before drawing a new tree. Defaults to 0. Positive values help only with cut finders whose result depends on the root; see bipartition_tree().
region_surcharge (dict | None, optional) – Surcharges for region-aware chains; see random_spanning_tree(). Default is None.
bipartition_tree_fn (ReComBipartitionTreeFn, optional) – The function used to split the merged district pair. To configure the bipartition or spanning-tree step (for example max_attempts, allow_pair_reselection, or a uniform spanning tree), pass a pre-bound function such as partial(bipartition_tree, max_attempts=100).
pair_selection ("district_pairs" | "cut_edges", optional) – How to choose the adjacent district pair to merge. "district_pairs" (default) draws uniformly among adjacent pairs; "cut_edges" weights each pair by the number of cut edges it shares.

Returns:

A proposal function for use with MarkovChain.

Return type:

ProposalFn

gerrychain.proposals.build_reversible_recom_proposal_fn(pop_col: str, pop_target: int | float, epsilon: float, max_balanced_edge_cuts: int, find_balanced_edge_cuts_fn: FindBalancedEdgeCutsFn = <function find_balanced_edge_cuts_memoization>, repeat_until_valid: bool = False) → ProposalFn[source]¶

Build a reversible ReCom proposal function with its configuration bound.

Reversible ReCom samples exactly from the spanning-tree distribution rather than an approximation of it; see reversible_recom(). This builder exposes every option except partition and rng, which MarkovChain supplies at each step.

Parameters:

pop_col (str) – The name of the population column.
pop_target (int | float) – The target population for each district.
epsilon (float) – Allowed population deviation as a percentage of the target population.
max_balanced_edge_cuts (int) – The number of balanced edge cuts to draw from the spanning tree before selecting one, which is what makes the proposal reversible. The proposal raises ReversibilityError if a tree exceeds this bound.
find_balanced_edge_cuts_fn (FindBalancedEdgeCutsFn, optional) – The balanced-cut finder. Default is find_balanced_edge_cuts_memoization().
repeat_until_valid (bool, optional) – Whether to keep drawing until a valid partition is found. Default is False.

Returns:

A proposal function for use with MarkovChain.

Return type:

ProposalFn

gerrychain.proposals.multi_member_recom(partition: ~gerrychain.partition.partition.Partition, pop_col: str, pop_target: int | float, epsilon: float, members_per_district: ~collections.abc.Mapping[~collections.abc.Hashable, int], node_repeats: int = 0, region_surcharge: dict[str, float] | None = None, bipartition_tree_fn: ~gerrychain.tree.bipartition_tree.ReComBipartitionTreeFn = <function bipartition_tree>, pair_selection: ~typing.Literal['district_pairs', 'cut_edges'] = 'district_pairs', *, rng: ~random.Random | int | None = None) → Partition[source]¶

Return a ReCom proposal for districts with fixed, unequal member counts.

pop_target is the target population for one member. Each district’s target is pop_target * members_per_district[label]. Member counts remain attached to district labels while ReCom changes their geography.

Parameters:

partition (Partition) – The current partition.
pop_col (str) – The name of the population column.
pop_target (int | float) – Target population for one member.
epsilon (float) – Allowed deviation from each district’s own target. Must be in [0, 1).
members_per_district (Mapping[Hashable, int]) – Positive member count for every district.
node_repeats (int, optional) – Additional roots to try per spanning tree. Defaults to 0.
region_surcharge (dict | None, optional) – Surcharges for region-aware spanning trees.
bipartition_tree_fn (ReComBipartitionTreeFn, optional) – Tree bipartition function.
pair_selection ("district_pairs" | "cut_edges", optional) – Adjacent-pair selection mode.
rng (random.Random | int | None, optional) – Source of randomness.

Returns:

The proposed partition.

Return type:

Partition

gerrychain.proposals.propose_chunk_flip(partition: Partition, *, rng: Random | int | None = None) → Partition[source]¶

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

This function chooses a random boundary node and proposes to flip it and all of its neighbors. It returns a possible next ~gerrychain.Partition.

Parameters:

partition (Partition) – The current partition to propose a flip from.
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 possible next ~gerrychain.Partition

Return type:

Partition

gerrychain.proposals.propose_random_flip(partition: Partition, *, rng: Random | int | None = None) → Partition[source]¶

Proposes a random boundary flip from the partition.

This function proposes a random boundary flip from the partition. It returns a possible next ~gerrychain.Partition.

Parameters:

partition (Partition) – The current partition to propose a flip from.
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 possible next ~gerrychain.Partition

Return type:

Partition

gerrychain.proposals.recom(partition: Partition, pop_col: str, pop_target: int | float, epsilon: float, node_repeats: int = 0, region_surcharge: dict[str, float] | None=None, bipartition_tree_fn: ReComBipartitionTreeFn = <function bipartition_tree>, pair_selection: Literal['district_pairs', 'cut_edges']='district_pairs', *, rng: Random | int | None = None) → Partition[source]¶

Return new partition resulting from the ReCom algorithm.

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, acceptance_fn, partition, total_steps here…

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

proposal_fn = partial(recom, pop_col=”POP10”, pop_target=pop_target, epsilon=.05)

chain = MarkovChain(proposal_fn, constraints, acceptance_fn, partition, total_steps)

Parameters:

partition (Partition) – The initial partition.
pop_col (str) – The name of the population column.
pop_target (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) – 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.
region_surcharge (dict | None, optional) – The surcharge dictionary for the graph used for region-aware partitioning of the grid. Default is None.
bipartition_tree_fn (ReComBipartitionTreeFn, optional) – The method used for bipartitioning the tree. Default is gerrychain.tree.bipartition_tree. To configure the bipartition or spanning-tree step (e.g. max_attempts, or spanning_tree_fn_kwargs for spanning-tree options), pass a pre-bound function, e.g. partial(bipartition_tree, spanning_tree_fn_kwargs={...}).
pair_selection ("district_pairs" | "cut_edges", optional) – How to choose the pair of adjacent districts to merge. "district_pairs" (default) draws uniformly among the adjacent district pairs; "cut_edges" draws uniformly among the cut edges, so a pair’s chance is proportional to the number of cut edges the two districts share.
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 new partition resulting from the ReCom algorithm.

Return type:

Partition

gerrychain.proposals.reversible_recom(partition: Partition, pop_col: str, pop_target: int | float, epsilon: float, max_balanced_edge_cuts: int, find_balanced_edge_cuts_fn: FindBalancedEdgeCutsFn = <function find_balanced_edge_cuts_memoization>, repeat_until_valid: bool = False, *, rng: Random | int | None = None) → 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 (int | float) – The target population for each district.
epsilon (float) – The epsilon value for population deviation as a percentage of the target population.
max_balanced_edge_cuts (int) – The number of balanced edge cuts to draw from the spanning tree before selecting one, used to make the proposal reversible.
find_balanced_edge_cuts_fn (Callable, optional) – The balance edge function. Default is find_balanced_edge_cuts_memoization.
repeat_until_valid (bool, optional) – Flag indicating whether to repeat until a valid partition is found. Default is False.
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 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', *, rng: Random | int | None = None) → 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, acceptance_fn, partition, total_steps here...

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

chain = MarkovChain(proposal_fn, constraints, acceptance_fn, partition, total_steps)

Parameters:

partition (Partition) – The initial partition.
weight_type (str | None, 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”.
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 new partition resulting from the spectral ReCom algorithm.

Return type:

Partition

Constraints¶

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

Helper classes include Validator for collections of constraints, numeric Bounds and UpperBound/LowerBound classes, self-configuring bounds, and percentage bounds.

Binary constraint functions include contiguity checks, no_vanishing_districts, and lower bounds on reciprocal Polsby-Popper scores.

Each new step proposed to the chain is passed off to the constraint 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 constraint function should take in a Partition instance, and should return whether or not the instance is valid according to its rules (the ConstraintFn alias). Many top-level functions in this module follow this signature.

class gerrychain.constraints.Bounds(value_fn: Callable[[P], Iterable[float]], 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.

Initialize a Bounds instance.

This initializer sets up Bounds with the provided arguments and validates required state.

Parameters:

value_fn (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: 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 Polsby-Popper scores
Return type:: float

class gerrychain.constraints.LowerBound(value_fn: Callable[[P], float], 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.

Initialize a LowerBound instance.

This initializer sets up LowerBound with the provided arguments and validates required state.

Parameters:

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

class gerrychain.constraints.SelfConfiguringLowerBound(value_fn: Callable[[Partition], float], 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.

Initialize a SelfConfiguringLowerBound instance.

This initializer sets up SelfConfiguringLowerBound with the provided arguments and validates required state.

Parameters:

value_fn (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(value_fn: Callable[[Partition], float])[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.

Initialize a SelfConfiguringUpperBound instance.

This initializer sets up SelfConfiguringUpperBound with the provided arguments and validates required state.

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

class gerrychain.constraints.UpperBound(value_fn: Callable[[P], float], 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.

Initialize a UpperBound instance.

This initializer sets up UpperBound with the provided arguments and validates required state.

Parameters:

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

class gerrychain.constraints.Validator(constraints: Iterable[Callable[[Partition], bool]])[source]¶

A single callable that bundles a collection of constraint functions.

This is a callable class used to check partition satisfies a set of constraints, and it is intended to be passed as the constraints parameter when instantiating a MarkovChain.

Example usage:

validator = Validator([constraint1, constraint2, constraint3])
chain = MarkovChain(proposal, validator, accept, initial_partition, total_steps)

constraints¶

List of constraint functions that will check partitions.

Type:: list[ConstraintFn]

Initialize a Validator instance.

Parameters:: constraints (Iterable[ConstraintFn]) – Constraint functions that will check partitions.

class gerrychain.constraints.WithinPercentRangeOfBounds(value_fn: Callable[[Partition], float], 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.

Initialize a WithinPercentRangeOfBounds instance.

This initializer sets up WithinPercentRangeOfBounds with the provided arguments and validates required state.

Parameters:

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

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.

This function checks if the parts of a partition are connected. It returns whether the all components of the partition are contiguous.

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

gerrychain.constraints.contiguous_bfs(partition: Partition) → bool¶

Check if the parts of a partition are connected.

This function checks if the parts of a partition are connected. It returns whether the all components of the partition are contiguous.

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

gerrychain.constraints.deviation_from_ideal(partition: Partition, attribute: str = 'population') → dict[Hashable, float][source]¶

Determine the deviation of the given attribute from the ideal value among parts of the partition.

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[Hashable, float]

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

Return whether the districts are within specified tolerance.

Check if all districts are within a certain percentage of the “smallest” district, as defined by the given attribute. For example, if the attribute is population, this function checks if all districts are within a certain percentage of the smallest population district.

Parameters:

partition (Partition) – Partition class instance
attribute_name (str, optional) – Name of an updater in partition. Defaults to "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. Can happen in flip proposal.

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.

This function refuse all proposals that split a county that was previous unsplit. It returns function that returns True if the proposal does not split any new counties.

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.

This optimized check assumes that the parent partition is contiguous and that the proposal changes one node. Use contiguous() when either assumption does not hold.

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

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

Construct a bounds object to ensure all districts are closed to a target population.

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

gerrychain.constraints.within_percent_of_ideal_population_per_member(initial_partition: Partition, members_per_district: Mapping[Hashable, int], percent: float = 0.01, pop_key: str = 'population') → Partition'>,)][source]¶

Bound each district’s population per member around the plan-wide ideal.

The ideal population is the total population divided by the total number of members. Member counts are copied when the constraint is constructed, so they remain fixed to district labels.

Parameters:

initial_partition (Partition) – Starting partition used to compute the ideal population.
members_per_district (Mapping[Hashable, int]) – Positive member count for every district.
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 each district’s population divided by its member count.

Return type:

Bounds