0
# Proposal Algorithms
1

2
Generate new districting plans through various algorithms including ReCom (recombination), random flips, and tree-based partitioning. Proposal functions are the core mechanism for exploring the space of possible redistricting plans.
3

4
## Capabilities
5

6
### ReCom (Recombination) Algorithm
7

8
The primary proposal method that creates new plans by merging adjacent districts and repartitioning them using spanning trees.
9

10
```python { .api }
11
def recom(
12
    partition: Partition,
13
    pop_col: str,
14
    pop_target: Union[int, float],
15
    epsilon: float,
16
    node_repeats: int = 1,
17
    region_surcharge: Optional[Dict] = None,
18
    method: Callable = bipartition_tree
19
) -> Partition:
20
    """
21
    Generate new partition using ReCom (recombination) algorithm.
22
    
23
    The algorithm:
24
    1. Selects a random edge that crosses district boundaries
25
    2. Merges the two districts connected by that edge
26
    3. Generates a random spanning tree of the merged area
27
    4. Cuts the tree to create two balanced districts
28
    
29
    Parameters:
30
    - partition (Partition): Current partition to propose from
31
    - pop_col (str): Column name for population data
32
    - pop_target (Union[int, float]): Target population per district
33
    - epsilon (float): Population balance tolerance (e.g., 0.05 for 5%)
34
    - node_repeats (int): Number of spanning tree attempts per node
35
    - region_surcharge (Optional[Dict]): Additional constraints by region
36
    - method (Callable): Tree bipartition method to use
37
    
38
    Returns:
39
    Partition: New partition with recombined districts
40
    """
41
```
42

43
Usage example:
44
```python
45
from gerrychain.proposals import recom
46

47
# Use in Markov chain
48
chain = MarkovChain(
49
    proposal=recom,
50
    constraints=constraints,
51
    accept=always_accept,
52
    initial_state=partition,
53
    total_steps=1000
54
)
55

56
# Single proposal
57
new_partition = recom(current_partition)
58
```
59

60
### ReCom Class Implementation
61

62
The ReCom algorithm is also available as a class for more advanced usage:
63

64
```python { .api }
65
class ReCom:
66
    def __init__(
67
        self,
68
        pop_col: str,
69
        ideal_pop: Union[int, float],
70
        epsilon: float,
71
        node_repeats: int = 1
72
    ) -> None:
73
        """
74
        ReCom proposal class for reusable configuration.
75
        
76
        Parameters:
77
        - pop_col (str): Population column name
78
        - ideal_pop (Union[int, float]): Ideal population per district
79
        - epsilon (float): Population balance tolerance
80
        - node_repeats (int): Number of spanning tree attempts per node
81
        
82
        Returns:
83
        None
84
        """
85

86
    def __call__(self, partition: Partition) -> Partition:
87
        """
88
        Apply ReCom proposal to partition.
89
        
90
        Parameters:
91
        - partition (Partition): Current partition
92
        
93
        Returns:
94
        Partition: New partition from ReCom
95
        """
96

97
def reversible_recom(
98
    partition: Partition,
99
    pop_col: str,
100
    pop_target: Union[int, float],
101
    epsilon: float,
102
    node_repeats: int = 1,
103
    method: Callable = bipartition_tree
104
) -> Partition:
105
    """
106
    Reversible ReCom proposal maintaining detailed balance.
107
    
108
    Parameters:
109
    - partition (Partition): Current partition
110
    - pop_col (str): Population column name  
111
    - pop_target (Union[int, float]): Target population per district
112
    - epsilon (float): Population balance tolerance
113
    - node_repeats (int): Number of spanning tree attempts per node
114
    - method (Callable): Tree bipartition method to use
115
    
116
    Returns:
117
    Partition: New partition with reversible ReCom
118
    """
119

120
def spectral_recom(
121
    partition: Partition,
122
    pop_col: str,
123
    pop_target: Union[int, float],
124
    epsilon: float,
125
    node_repeats: int = 1
126
) -> Partition:
127
    """
128
    ReCom proposal using spectral clustering for tree cuts.
129
    
130
    Parameters:
131
    - partition (Partition): Current partition
132
    - pop_col (str): Population column name
133
    - pop_target (Union[int, float]): Target population per district  
134
    - epsilon (float): Population balance tolerance
135
    - node_repeats (int): Number of spanning tree attempts per node
136
    
137
    Returns:
138
    Partition: New partition using spectral ReCom
139
    """
140
```
141

142
### Random Flip Proposals
143

144
Simple proposals that flip individual units or small groups between adjacent districts.
145

146
```python { .api }
147
def propose_random_flip(partition: Partition) -> Partition:
148
    """
149
    Propose flipping a single random unit to an adjacent district.
150
    
151
    Parameters:
152
    - partition (Partition): Current partition
153
    
154
    Returns:
155
    Partition: New partition with one unit flipped
156
    """
157

158
def propose_several_flips(partition: Partition, k: int = 2) -> Partition:
159
    """
160
    Propose flipping several units simultaneously.
161
    
162
    Parameters:
163
    - partition (Partition): Current partition
164
    - k (int): Number of units to flip
165
    
166
    Returns:
167
    Partition: New partition with k units flipped
168
    """
169

170
def propose_chunk_flip(partition: Partition, k: int = 3) -> Partition:
171
    """
172
    Propose flipping a connected chunk of k units to adjacent district.
173
    
174
    Parameters:
175
    - partition (Partition): Current partition
176
    - k (int): Size of chunk to flip
177
    
178
    Returns:
179
    Partition: New partition with chunk flipped
180
    """
181

182
def slow_reversible_propose(partition: Partition) -> Partition:
183
    """
184
    Reversible proposal method with detailed balance properties.
185
    
186
    Parameters:
187
    - partition (Partition): Current partition
188
    
189
    Returns:
190
    Partition: New partition maintaining detailed balance
191
    """
192
```
193

194
### Tree-Based Partitioning
195

196
Low-level tree algorithms used by ReCom and other proposal methods.
197

198
```python { .api }
199
def recursive_tree_part(
200
    graph: Graph, 
201
    parts: List[Set[NodeId]], 
202
    pop_target: float,
203
    pop_col: str = "population",
204
    epsilon: float = 0.05
205
) -> Dict[NodeId, int]:
206
    """
207
    Recursively partition graph into balanced parts using spanning trees.
208
    
209
    Parameters:
210
    - graph (Graph): Graph to partition
211
    - parts (List[Set[NodeId]]): Target partition structure
212
    - pop_target (float): Target population per part
213
    - pop_col (str): Population attribute name
214
    - epsilon (float): Population balance tolerance
215
    
216
    Returns:
217
    Dict[NodeId, int]: Assignment of nodes to parts
218
    """
219

220
def bipartition_tree(
221
    graph: Graph,
222
    pop_col: str = "population", 
223
    pop_target: float = None,
224
    epsilon: float = 0.05
225
) -> Dict[NodeId, int]:
226
    """
227
    Partition graph into two balanced parts using spanning tree.
228
    
229
    Parameters:
230
    - graph (Graph): Graph to partition
231
    - pop_col (str): Population attribute name
232
    - pop_target (float, optional): Target population per part
233
    - epsilon (float): Population balance tolerance
234
    
235
    Returns:
236
    Dict[NodeId, int]: Assignment of nodes to two parts (0 or 1)
237
    """
238

239
def bipartition_tree_random(
240
    graph: Graph,
241
    pop_col: str = "population",
242
    epsilon: float = 0.05,
243
    node_repeats: int = 1
244
) -> Dict[NodeId, int]:
245
    """
246
    Random bipartition using spanning tree with multiple attempts.
247
    
248
    Parameters:
249
    - graph (Graph): Graph to partition
250
    - pop_col (str): Population attribute name  
251
    - epsilon (float): Population balance tolerance
252
    - node_repeats (int): Number of random attempts per node
253
    
254
    Returns:
255
    Dict[NodeId, int]: Assignment of nodes to two parts
256
    """
257
```
258

259
### Spanning Tree Operations
260

261
Generate and manipulate spanning trees for tree-based partitioning algorithms.
262

263
```python { .api }
264
def random_spanning_tree(graph: Graph) -> Graph:
265
    """
266
    Generate a random spanning tree using Wilson's algorithm.
267
    
268
    Parameters:
269
    - graph (Graph): Input graph
270
    
271
    Returns:
272
    Graph: Random spanning tree as NetworkX graph
273
    """
274

275
def uniform_spanning_tree(graph: Graph) -> Graph:
276
    """
277
    Generate uniformly random spanning tree.
278
    
279
    Parameters:
280
    - graph (Graph): Input graph
281
    
282
    Returns:
283
    Graph: Uniformly random spanning tree
284
    """
285

286
def wilson_algorithm(graph: Graph, root: NodeId = None) -> Graph:
287
    """
288
    Wilson's algorithm for uniform random spanning trees.
289
    
290
    Parameters:
291
    - graph (Graph): Input graph
292
    - root (NodeId, optional): Root node for tree
293
    
294
    Returns:
295
    Graph: Random spanning tree generated by Wilson's algorithm
296
    """
297

298
def find_balanced_edge_cuts(
299
    tree: Graph,
300
    parts: int,
301
    pop_col: str = "population",
302
    epsilon: float = 0.05
303
) -> List[Tuple[NodeId, NodeId]]:
304
    """
305
    Find edge cuts that create balanced partitions of spanning tree.
306
    
307
    Parameters:
308
    - tree (Graph): Spanning tree
309
    - parts (int): Number of parts to create
310
    - pop_col (str): Population attribute name
311
    - epsilon (float): Population balance tolerance
312
    
313
    Returns:
314
    List[Tuple[NodeId, NodeId]]: Edges to cut for balanced partition
315
    """
316

317
def predecessors(graph: Graph, root: NodeId) -> Dict[NodeId, NodeId]:
318
    """
319
    Find predecessor relationships in tree rooted at given node.
320
    
321
    Parameters:
322
    - graph (Graph): Tree graph
323
    - root (NodeId): Root node
324
    
325
    Returns:
326
    Dict[NodeId, NodeId]: Predecessor mapping for each node
327
    """
328

329
def successors(graph: Graph, root: NodeId) -> Dict[NodeId, List[NodeId]]:
330
    """
331
    Find successor relationships in tree rooted at given node.
332
    
333
    Parameters:
334
    - graph (Graph): Tree graph
335
    - root (NodeId): Root node
336
    
337
    Returns:
338
    Dict[NodeId, List[NodeId]]: Successor mapping for each node
339
    """
340

341
def wilson_algorithm(graph: Graph, root: NodeId = None) -> Graph:
342
    """
343
    Wilson's algorithm for uniform random spanning trees.
344
    
345
    Parameters:
346
    - graph (Graph): Input graph
347
    - root (NodeId, optional): Root node for tree
348
    
349
    Returns:
350
    Graph: Random spanning tree generated by Wilson's algorithm
351
    """
352

353
def get_seed_chunks(
354
    graph: Graph,
355
    num_chunks: int,
356
    pop_target: float,
357
    pop_col: str = "population",
358
    epsilon: float = 0.05,
359
    node_repeats: int = 1
360
) -> List[Set[NodeId]]:
361
    """
362
    Generate seed districts for recursive partitioning.
363
    
364
    Parameters:
365
    - graph (Graph): Graph to partition
366
    - num_chunks (int): Number of seed chunks to create
367
    - pop_target (float): Target population per chunk
368
    - pop_col (str): Population attribute name
369
    - epsilon (float): Population balance tolerance
370
    - node_repeats (int): Number of attempts per node
371
    
372
    Returns:
373
    List[Set[NodeId]]: List of seed district node sets
374
    """
375
```
376

377
### Advanced Proposal Patterns
378

379
Examples of how to create custom proposal functions and use advanced features:
380

381
```python
382
from gerrychain.proposals import recom, propose_random_flip
383
import random
384

385
# Custom proposal combining multiple methods
386
def mixed_proposal(partition):
387
    """Custom proposal that uses ReCom 80% of time, random flip 20%."""
388
    if random.random() < 0.8:
389
        return recom(partition)
390
    else:
391
        return propose_random_flip(partition)
392

393
# Proposal with custom parameters
394
def chunked_recom(partition, chunk_size=5):
395
    """ReCom followed by chunk flip for fine-tuning."""
396
    step1 = recom(partition)
397
    return propose_chunk_flip(step1, k=chunk_size)
398

399
# Use in analysis
400
chain = MarkovChain(
401
    proposal=mixed_proposal,  # Custom proposal function
402
    constraints=constraints,
403
    accept=always_accept,
404
    initial_state=partition,
405
    total_steps=10000
406
)
407

408
# Sequential proposals for multi-step changes
409
def multi_step_proposal(partition, steps=3):
410
    """Apply multiple proposal steps."""
411
    current = partition
412
    for _ in range(steps):
413
        current = propose_random_flip(current)
414
    return current
415
```
416

417
## Types
418

419
```python { .api }
420
ProposalFunction = Callable[[Partition], Partition]
421
NodeId = Union[int, str]
422
DistrictId = int
423
```