-
Notifications
You must be signed in to change notification settings - Fork 12
API Reference
The following methods are used to "run" the chain; i.e., initiate the process of sequentially generating and evaluating districting plans. We highly recommend using the ReCom plan proposal method.
recom_chain(graph::BaseGraph, partition::Partition, pop_constraint::PopulationConstraint, num_steps::Int,scores::Array{S, 1}; num_tries::Int=3, acceptance_fn::F=always_accept, rng::AbstractRNG=Random.default_rng()) where {F<:Function, S<:AbstractScore}
Runs a Markov Chain for num_steps steps using ReCom. In summary, the ReCom proposal method works as follows: merge two districts in the plan, generate a minimum spanning tree for the precincts in the merged district, then "split" the merged district into two new districts by finding a population-balanced cut of the MST. This method could potentially be used to merge/split an arbitrary number of districts, but currently, our implementation only supports merging 2 districts and splitting into 2 new districts.
| Required Arguments | Description |
|---|---|
| graph (BaseGraph) | |
| partition (Partition) | |
| pop_constraint (PopulationConstraint) | Population constraint that contains the maximum/minimum district population count |
| num_steps (Int) | Number of steps to run the chain for |
| scores (Array{S,1} where S<:AbstractScore) | Array of AbstractScores that will be evaluated on the newly generated plan at each step |
| Optional Arguments | Default Value | Description |
|---|---|---|
| num_tries (Int) | 3 | The number times to try getting a population-balanced cut (in accordance with pop_constraint) from a subgraph before giving up. |
| acceptance_fn (F where F<:Function) | always_accept | A function generating a number in [0, 1] representing the probability of accepting the proposal. Should accept a Partition as input. |
| rng (AbstractRNG) | Random.default_rng() | Random number generator. The user can pass in their own; otherwise, we use the default RNG from the Julia Random library. |
| Return type | Description |
|---|---|
| Array{Dict{String, Any},1} | An array of length num_steps+1. The entry at index i in the array is a Dictionary that maps the name of a score to the value of the score for the plan at step i, where the original partition is considered to be step 0. |
The flip_chain method is quite similar to the recom_chain method. The only difference is how new plans are generated at each step of the chain. Out of the set of cut edges in a given plan, where a cut edge is defined to be an edge in the dual graph that crosses from a node in one district to a node in a different district, one cut edge is randomly selected, and one of the two precincts is "flipped" to the district of the other precinct.
flip_chain(graph::BaseGraph, partition::Partition,pop_constraint::PopulationConstraint, cont_constraint::ContiguityConstraint, num_steps::Int, scores::Array{S, 1}; acceptance_fn::F=always_accept) where {F<:Function, S<:AbstractScore}
Runs a Markov Chain for num_steps steps using Flip proposals.
| Required Arguments | Description |
|---|---|
| graph (BaseGraph) | |
| partition (Partition) | |
| pop_constraint (PopulationConstraint) | Population constraint that contains the maximum/minimum district population count |
| cont_constraint (ContiguityConstraint) | Contiguity constraint that requires that a flip proposal does not break district contiguity (i.e., all nodes in the same district must be part of the same connected component) |
| num_steps (Int) | Number of steps to run the chain for |
| scores (Array{S,1} where S<:AbstractScore) | Array of AbstractScores that will be evaluated on the newly generated plan at each step |
| Optional Arguments | Default Value | Description |
|---|---|---|
| acceptance_fn (F where F<:Function) | always_accept | A function generating a number in [0, 1] representing the probability of accepting the proposal. Should accept a Partition as input. |
| Return type | Description |
|---|---|
| Array{Dict{String, Any},1} | An array of length num_steps+1. The entry at index i in the array is a Dictionary that maps the name of a score to the value of the score for the plan at step i, where the original partition is considered to be step 0. |
Acceptance functions are user-defined functions passed to recom_chain/flip_chain that are used to evaluate a proposal for the next state in a chain and generate a probability for "accepting" the new plan. If the plan is rejected, then the step in the Markov chain is considered to be a "self-loop." Note that acceptance functions are conceptually different from constraints, which are hard, deterministic requirements on every plan in a chain. If a plan is generated that does not satisfy a constraint, then new plans are generated until the constraint is satisfied, at which point the chain makes a step to the constraint-satisfying plan. Contrast this to acceptance functions, which generate probabilities for accepting a plan, and when a plan is not accepted, produce a self-loop in the chain.
Practically, acceptance functions are expected to accept a Partition object and return a probability between 0 and 1. The reason for this is that acceptance functions are really most useful in cases like the Metropolis-Hasting algorithm and "burning in". If, for some reason, you need a deterministic acceptance function, you can simply have it return 0 or 1.
The following is a sample acceptance function included in the GerryChain library:
function always_accept(partition::Partition)
""" Accepts new partition with probability 1.
"""
return 1
end
Read more about how to pass in your acceptance function to a chain by referring to the API for ReCom chains and Flip chains.