tessl/pypi-gerrychain
Use Markov chain Monte Carlo to analyze districting plans and gerrymanders
—
Pending
constraints.mddocs/
Constraints
Ensure proposed partitions meet districting requirements including contiguity, population balance, and administrative unit preservation. Constraints are functions that validate partition properties and can be combined using the Validator class.
Capabilities
Constraint Validation System
The Validator class combines multiple constraint functions into a single validator that can efficiently check partition validity.
class Validator:
def __init__(self, constraints: List[ConstraintFunction]) -> None:
"""
Create a validator from a list of constraint functions.
Parameters:
- constraints (List[ConstraintFunction]): List of functions that return bool
Returns:
None
"""
def __call__(self, partition: Partition) -> bool:
"""
Check if partition satisfies all constraints.
Parameters:
- partition (Partition): Partition to validate
Returns:
bool: True if all constraints pass, False otherwise
"""
@property
def constraints(self) -> List[ConstraintFunction]:
"""
Access the list of constraint functions.
Returns:
List[ConstraintFunction]: The constraint functions
"""Contiguity Constraints
Ensure all districts form connected components in the graph topology.
def contiguous(partition: Partition) -> bool:
"""
Check if all districts in the partition are contiguous.
Parameters:
- partition (Partition): Partition to check
Returns:
bool: True if all districts are contiguous, False otherwise
"""
def contiguous_bfs(partition: Partition) -> bool:
"""
Check contiguity using breadth-first search algorithm.
Parameters:
- partition (Partition): Partition to check
Returns:
bool: True if all districts are contiguous, False otherwise
"""
def contiguous_components(partition: Partition) -> Dict[DistrictId, List[Set[NodeId]]]:
"""
Find connected components within each district.
Parameters:
- partition (Partition): Partition to analyze
Returns:
Dict[DistrictId, List[Set[NodeId]]]: Connected components by district
"""
def no_more_discontiguous(partition: Partition) -> bool:
"""
Ensure no new disconnected districts are created.
Parameters:
- partition (Partition): Partition to check
Returns:
bool: True if no new disconnected districts, False otherwise
"""
def single_flip_contiguous(partition: Partition) -> bool:
"""
Optimized contiguity check for single node flip proposals.
Parameters:
- partition (Partition): Partition to check
Returns:
bool: True if districts remain contiguous after single flip
"""Usage example:
from gerrychain.constraints import contiguous, Validator
# Single constraint
if contiguous(partition):
print("All districts are contiguous")
# Multiple constraints with validator
validator = Validator([contiguous, other_constraint])
if validator(partition):
print("Partition passes all constraints")Population Balance Constraints
Ensure districts have similar population sizes within specified tolerances.
def within_percent_of_ideal_population(
initial_partition: Partition,
percent: float,
pop_key: str = "population"
) -> ConstraintFunction:
"""
Create a constraint requiring districts stay within percent of ideal population.
Parameters:
- initial_partition (Partition): Reference partition for ideal population
- percent (float): Maximum deviation as decimal (e.g., 0.05 for 5%)
- pop_key (str): Key for population data in partition
Returns:
ConstraintFunction: Constraint function checking population balance
"""
def deviation_from_ideal(
partition: Partition,
ideal_population: float,
pop_key: str = "population"
) -> Dict[DistrictId, float]:
"""
Calculate population deviation from ideal for each district.
Parameters:
- partition (Partition): Partition to analyze
- ideal_population (float): Target population per district
- pop_key (str): Key for population data in partition
Returns:
Dict[DistrictId, float]: Deviation from ideal by district
"""
def districts_within_tolerance(
partition: Partition,
attribute_name: str,
percentage: float,
metric: Callable = max
) -> bool:
"""
Check if all districts are within tolerance for an attribute.
Parameters:
- partition (Partition): Partition to check
- attribute_name (str): Name of attribute to check
- percentage (float): Maximum allowed deviation
- metric (Callable): Function to use for tolerance (max, min, etc.)
Returns:
bool: True if all districts within tolerance
"""Bounds Constraints
Generic constraints for numeric bounds on partition attributes.
class Bounds:
def __init__(
self,
attr: str,
lower: float = None,
upper: float = None
) -> None:
"""
Create bounds constraint for a partition attribute.
Parameters:
- attr (str): Partition attribute name to constrain
- lower (float, optional): Lower bound (inclusive)
- upper (float, optional): Upper bound (inclusive)
Returns:
None
"""
class UpperBound(Bounds):
def __init__(self, attr: str, upper: float) -> None:
"""
Create upper bound constraint.
Parameters:
- attr (str): Partition attribute name
- upper (float): Upper bound (inclusive)
Returns:
None
"""
class LowerBound(Bounds):
def __init__(self, attr: str, lower: float) -> None:
"""
Create lower bound constraint.
Parameters:
- attr (str): Partition attribute name
- lower (float): Lower bound (inclusive)
Returns:
None
"""
class SelfConfiguringUpperBound(UpperBound):
def __init__(self, attr: str, factor: float = 1.0) -> None:
"""
Upper bound that configures itself from initial partition.
Parameters:
- attr (str): Partition attribute name
- factor (float): Multiplier for initial value
Returns:
None
"""
class SelfConfiguringLowerBound(LowerBound):
def __init__(self, attr: str, factor: float = 1.0) -> None:
"""
Lower bound that configures itself from initial partition.
Parameters:
- attr (str): Partition attribute name
- factor (float): Multiplier for initial value
Returns:
None
"""
class WithinPercentRangeOfBounds(Bounds):
def __init__(
self,
attr: str,
percent_range: float,
initial_partition: Partition = None
) -> None:
"""
Constraint requiring attribute stays within percentage range of initial value.
Parameters:
- attr (str): Partition attribute name
- percent_range (float): Allowed percentage variation
- initial_partition (Partition, optional): Reference partition
Returns:
None
"""Administrative Unit Constraints
Prevent splitting of administrative units like counties or municipalities.
def refuse_new_splits(
col: str
) -> ConstraintFunction:
"""
Create constraint preventing new administrative unit splits.
Parameters:
- col (str): Column name for administrative units
Returns:
ConstraintFunction: Constraint function preventing new splits
"""
def no_vanishing_districts(partition: Partition) -> bool:
"""
Ensure no districts become empty (have zero population or units).
Parameters:
- partition (Partition): Partition to check
Returns:
bool: True if all districts are non-empty, False otherwise
"""Compactness Constraints
Require districts to meet minimum compactness standards.
def L_minus_1_polsby_popper(
initial_partition: Partition,
threshold: float = 0.1
) -> ConstraintFunction:
"""
Compactness constraint using Polsby-Popper measure.
Parameters:
- initial_partition (Partition): Reference partition
- threshold (float): Minimum acceptable compactness
Returns:
ConstraintFunction: Polsby-Popper compactness constraint
"""
def L_minus_1_schwartzberg(
initial_partition: Partition,
threshold: float = 1.5
) -> ConstraintFunction:
"""
Compactness constraint using Schwartzberg measure.
Parameters:
- initial_partition (Partition): Reference partition
- threshold (float): Maximum acceptable Schwartzberg ratio
Returns:
ConstraintFunction: Schwartzberg compactness constraint
"""
def L1_polsby_popper(
initial_partition: Partition,
threshold: float = 0.1
) -> ConstraintFunction:
"""
L1 norm Polsby-Popper compactness constraint.
Parameters:
- initial_partition (Partition): Reference partition
- threshold (float): Minimum acceptable L1 compactness
Returns:
ConstraintFunction: L1 Polsby-Popper constraint
"""
def L1_reciprocal_polsby_popper(
initial_partition: Partition,
threshold: float = 10.0
) -> ConstraintFunction:
"""
L1 reciprocal Polsby-Popper compactness constraint.
Parameters:
- initial_partition (Partition): Reference partition
- threshold (float): Maximum acceptable reciprocal value
Returns:
ConstraintFunction: L1 reciprocal Polsby-Popper constraint
"""
def L2_polsby_popper(
initial_partition: Partition,
threshold: float = 0.1
) -> ConstraintFunction:
"""
L2 norm Polsby-Popper compactness constraint.
Parameters:
- initial_partition (Partition): Reference partition
- threshold (float): Minimum acceptable L2 compactness
Returns:
ConstraintFunction: L2 Polsby-Popper constraint
"""
def no_worse_L1_reciprocal_polsby_popper(
initial_partition: Partition
) -> ConstraintFunction:
"""
Ensure L1 reciprocal Polsby-Popper doesn't get worse.
Parameters:
- initial_partition (Partition): Reference partition
Returns:
ConstraintFunction: No-worse L1 reciprocal constraint
"""
def no_worse_L_minus_1_polsby_popper(
initial_partition: Partition
) -> ConstraintFunction:
"""
Ensure L(-1) Polsby-Popper doesn't get worse.
Parameters:
- initial_partition (Partition): Reference partition
Returns:
ConstraintFunction: No-worse L(-1) constraint
"""Complete Constraint Example
Example showing how to combine multiple constraints in a realistic scenario:
from gerrychain.constraints import (
Validator, contiguous, within_percent_of_ideal_population,
refuse_new_splits, no_vanishing_districts, UpperBound
)
# Set up comprehensive constraints
constraints = Validator([
# Basic validity
contiguous,
no_vanishing_districts,
# Population balance (5% tolerance)
within_percent_of_ideal_population(initial_partition, 0.05),
# Don't split counties
refuse_new_splits("county"),
# Limit cut edges
UpperBound("cut_edges", 100)
])
# Use in Markov chain
chain = MarkovChain(
proposal=recom,
constraints=constraints, # Validator automatically handles the list
accept=always_accept,
initial_state=initial_partition,
total_steps=1000
)
# Check individual partition
if constraints(test_partition):
print("Partition passes all constraints")
else:
# Find which constraints failed
for i, constraint in enumerate(constraints.constraints):
if not constraint(test_partition):
print(f"Failed constraint {i}: {constraint.__name__}")Types
ConstraintFunction = Callable[[Partition], bool]
DistrictId = int
NodeId = Union[int, str]Install with Tessl CLI
npx tessl i tessl/pypi-gerrychain