0
# Constraints
1
2
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.
3
4
## Capabilities
5
6
### Constraint Validation System
7
8
The Validator class combines multiple constraint functions into a single validator that can efficiently check partition validity.
9
10
```python { .api }
11
class Validator:
12
def __init__(self, constraints: List[ConstraintFunction]) -> None:
13
"""
14
Create a validator from a list of constraint functions.
15
16
Parameters:
17
- constraints (List[ConstraintFunction]): List of functions that return bool
18
19
Returns:
20
None
21
"""
22
23
def __call__(self, partition: Partition) -> bool:
24
"""
25
Check if partition satisfies all constraints.
26
27
Parameters:
28
- partition (Partition): Partition to validate
29
30
Returns:
31
bool: True if all constraints pass, False otherwise
32
"""
33
34
@property
35
def constraints(self) -> List[ConstraintFunction]:
36
"""
37
Access the list of constraint functions.
38
39
Returns:
40
List[ConstraintFunction]: The constraint functions
41
"""
42
```
43
44
### Contiguity Constraints
45
46
Ensure all districts form connected components in the graph topology.
47
48
```python { .api }
49
def contiguous(partition: Partition) -> bool:
50
"""
51
Check if all districts in the partition are contiguous.
52
53
Parameters:
54
- partition (Partition): Partition to check
55
56
Returns:
57
bool: True if all districts are contiguous, False otherwise
58
"""
59
60
def contiguous_bfs(partition: Partition) -> bool:
61
"""
62
Check contiguity using breadth-first search algorithm.
63
64
Parameters:
65
- partition (Partition): Partition to check
66
67
Returns:
68
bool: True if all districts are contiguous, False otherwise
69
"""
70
71
def contiguous_components(partition: Partition) -> Dict[DistrictId, List[Set[NodeId]]]:
72
"""
73
Find connected components within each district.
74
75
Parameters:
76
- partition (Partition): Partition to analyze
77
78
Returns:
79
Dict[DistrictId, List[Set[NodeId]]]: Connected components by district
80
"""
81
82
def no_more_discontiguous(partition: Partition) -> bool:
83
"""
84
Ensure no new disconnected districts are created.
85
86
Parameters:
87
- partition (Partition): Partition to check
88
89
Returns:
90
bool: True if no new disconnected districts, False otherwise
91
"""
92
93
def single_flip_contiguous(partition: Partition) -> bool:
94
"""
95
Optimized contiguity check for single node flip proposals.
96
97
Parameters:
98
- partition (Partition): Partition to check
99
100
Returns:
101
bool: True if districts remain contiguous after single flip
102
"""
103
```
104
105
Usage example:
106
```python
107
from gerrychain.constraints import contiguous, Validator
108
109
# Single constraint
110
if contiguous(partition):
111
print("All districts are contiguous")
112
113
# Multiple constraints with validator
114
validator = Validator([contiguous, other_constraint])
115
if validator(partition):
116
print("Partition passes all constraints")
117
```
118
119
### Population Balance Constraints
120
121
Ensure districts have similar population sizes within specified tolerances.
122
123
```python { .api }
124
def within_percent_of_ideal_population(
125
initial_partition: Partition,
126
percent: float,
127
pop_key: str = "population"
128
) -> ConstraintFunction:
129
"""
130
Create a constraint requiring districts stay within percent of ideal population.
131
132
Parameters:
133
- initial_partition (Partition): Reference partition for ideal population
134
- percent (float): Maximum deviation as decimal (e.g., 0.05 for 5%)
135
- pop_key (str): Key for population data in partition
136
137
Returns:
138
ConstraintFunction: Constraint function checking population balance
139
"""
140
141
def deviation_from_ideal(
142
partition: Partition,
143
ideal_population: float,
144
pop_key: str = "population"
145
) -> Dict[DistrictId, float]:
146
"""
147
Calculate population deviation from ideal for each district.
148
149
Parameters:
150
- partition (Partition): Partition to analyze
151
- ideal_population (float): Target population per district
152
- pop_key (str): Key for population data in partition
153
154
Returns:
155
Dict[DistrictId, float]: Deviation from ideal by district
156
"""
157
158
def districts_within_tolerance(
159
partition: Partition,
160
attribute_name: str,
161
percentage: float,
162
metric: Callable = max
163
) -> bool:
164
"""
165
Check if all districts are within tolerance for an attribute.
166
167
Parameters:
168
- partition (Partition): Partition to check
169
- attribute_name (str): Name of attribute to check
170
- percentage (float): Maximum allowed deviation
171
- metric (Callable): Function to use for tolerance (max, min, etc.)
172
173
Returns:
174
bool: True if all districts within tolerance
175
"""
176
```
177
178
### Bounds Constraints
179
180
Generic constraints for numeric bounds on partition attributes.
181
182
```python { .api }
183
class Bounds:
184
def __init__(
185
self,
186
attr: str,
187
lower: float = None,
188
upper: float = None
189
) -> None:
190
"""
191
Create bounds constraint for a partition attribute.
192
193
Parameters:
194
- attr (str): Partition attribute name to constrain
195
- lower (float, optional): Lower bound (inclusive)
196
- upper (float, optional): Upper bound (inclusive)
197
198
Returns:
199
None
200
"""
201
202
class UpperBound(Bounds):
203
def __init__(self, attr: str, upper: float) -> None:
204
"""
205
Create upper bound constraint.
206
207
Parameters:
208
- attr (str): Partition attribute name
209
- upper (float): Upper bound (inclusive)
210
211
Returns:
212
None
213
"""
214
215
class LowerBound(Bounds):
216
def __init__(self, attr: str, lower: float) -> None:
217
"""
218
Create lower bound constraint.
219
220
Parameters:
221
- attr (str): Partition attribute name
222
- lower (float): Lower bound (inclusive)
223
224
Returns:
225
None
226
"""
227
228
class SelfConfiguringUpperBound(UpperBound):
229
def __init__(self, attr: str, factor: float = 1.0) -> None:
230
"""
231
Upper bound that configures itself from initial partition.
232
233
Parameters:
234
- attr (str): Partition attribute name
235
- factor (float): Multiplier for initial value
236
237
Returns:
238
None
239
"""
240
241
class SelfConfiguringLowerBound(LowerBound):
242
def __init__(self, attr: str, factor: float = 1.0) -> None:
243
"""
244
Lower bound that configures itself from initial partition.
245
246
Parameters:
247
- attr (str): Partition attribute name
248
- factor (float): Multiplier for initial value
249
250
Returns:
251
None
252
"""
253
254
class WithinPercentRangeOfBounds(Bounds):
255
def __init__(
256
self,
257
attr: str,
258
percent_range: float,
259
initial_partition: Partition = None
260
) -> None:
261
"""
262
Constraint requiring attribute stays within percentage range of initial value.
263
264
Parameters:
265
- attr (str): Partition attribute name
266
- percent_range (float): Allowed percentage variation
267
- initial_partition (Partition, optional): Reference partition
268
269
Returns:
270
None
271
"""
272
```
273
274
### Administrative Unit Constraints
275
276
Prevent splitting of administrative units like counties or municipalities.
277
278
```python { .api }
279
def refuse_new_splits(
280
col: str
281
) -> ConstraintFunction:
282
"""
283
Create constraint preventing new administrative unit splits.
284
285
Parameters:
286
- col (str): Column name for administrative units
287
288
Returns:
289
ConstraintFunction: Constraint function preventing new splits
290
"""
291
292
def no_vanishing_districts(partition: Partition) -> bool:
293
"""
294
Ensure no districts become empty (have zero population or units).
295
296
Parameters:
297
- partition (Partition): Partition to check
298
299
Returns:
300
bool: True if all districts are non-empty, False otherwise
301
"""
302
```
303
304
### Compactness Constraints
305
306
Require districts to meet minimum compactness standards.
307
308
```python { .api }
309
def L_minus_1_polsby_popper(
310
initial_partition: Partition,
311
threshold: float = 0.1
312
) -> ConstraintFunction:
313
"""
314
Compactness constraint using Polsby-Popper measure.
315
316
Parameters:
317
- initial_partition (Partition): Reference partition
318
- threshold (float): Minimum acceptable compactness
319
320
Returns:
321
ConstraintFunction: Polsby-Popper compactness constraint
322
"""
323
324
def L_minus_1_schwartzberg(
325
initial_partition: Partition,
326
threshold: float = 1.5
327
) -> ConstraintFunction:
328
"""
329
Compactness constraint using Schwartzberg measure.
330
331
Parameters:
332
- initial_partition (Partition): Reference partition
333
- threshold (float): Maximum acceptable Schwartzberg ratio
334
335
Returns:
336
ConstraintFunction: Schwartzberg compactness constraint
337
"""
338
339
def L1_polsby_popper(
340
initial_partition: Partition,
341
threshold: float = 0.1
342
) -> ConstraintFunction:
343
"""
344
L1 norm Polsby-Popper compactness constraint.
345
346
Parameters:
347
- initial_partition (Partition): Reference partition
348
- threshold (float): Minimum acceptable L1 compactness
349
350
Returns:
351
ConstraintFunction: L1 Polsby-Popper constraint
352
"""
353
354
def L1_reciprocal_polsby_popper(
355
initial_partition: Partition,
356
threshold: float = 10.0
357
) -> ConstraintFunction:
358
"""
359
L1 reciprocal Polsby-Popper compactness constraint.
360
361
Parameters:
362
- initial_partition (Partition): Reference partition
363
- threshold (float): Maximum acceptable reciprocal value
364
365
Returns:
366
ConstraintFunction: L1 reciprocal Polsby-Popper constraint
367
"""
368
369
def L2_polsby_popper(
370
initial_partition: Partition,
371
threshold: float = 0.1
372
) -> ConstraintFunction:
373
"""
374
L2 norm Polsby-Popper compactness constraint.
375
376
Parameters:
377
- initial_partition (Partition): Reference partition
378
- threshold (float): Minimum acceptable L2 compactness
379
380
Returns:
381
ConstraintFunction: L2 Polsby-Popper constraint
382
"""
383
384
def no_worse_L1_reciprocal_polsby_popper(
385
initial_partition: Partition
386
) -> ConstraintFunction:
387
"""
388
Ensure L1 reciprocal Polsby-Popper doesn't get worse.
389
390
Parameters:
391
- initial_partition (Partition): Reference partition
392
393
Returns:
394
ConstraintFunction: No-worse L1 reciprocal constraint
395
"""
396
397
def no_worse_L_minus_1_polsby_popper(
398
initial_partition: Partition
399
) -> ConstraintFunction:
400
"""
401
Ensure L(-1) Polsby-Popper doesn't get worse.
402
403
Parameters:
404
- initial_partition (Partition): Reference partition
405
406
Returns:
407
ConstraintFunction: No-worse L(-1) constraint
408
"""
409
```
410
411
### Complete Constraint Example
412
413
Example showing how to combine multiple constraints in a realistic scenario:
414
415
```python
416
from gerrychain.constraints import (
417
Validator, contiguous, within_percent_of_ideal_population,
418
refuse_new_splits, no_vanishing_districts, UpperBound
419
)
420
421
# Set up comprehensive constraints
422
constraints = Validator([
423
# Basic validity
424
contiguous,
425
no_vanishing_districts,
426
427
# Population balance (5% tolerance)
428
within_percent_of_ideal_population(initial_partition, 0.05),
429
430
# Don't split counties
431
refuse_new_splits("county"),
432
433
# Limit cut edges
434
UpperBound("cut_edges", 100)
435
])
436
437
# Use in Markov chain
438
chain = MarkovChain(
439
proposal=recom,
440
constraints=constraints, # Validator automatically handles the list
441
accept=always_accept,
442
initial_state=initial_partition,
443
total_steps=1000
444
)
445
446
# Check individual partition
447
if constraints(test_partition):
448
print("Partition passes all constraints")
449
else:
450
# Find which constraints failed
451
for i, constraint in enumerate(constraints.constraints):
452
if not constraint(test_partition):
453
print(f"Failed constraint {i}: {constraint.__name__}")
454
```
455
456
## Types
457
458
```python { .api }
459
ConstraintFunction = Callable[[Partition], bool]
460
DistrictId = int
461
NodeId = Union[int, str]
462
```