Partitions¶

Partitions assign graph nodes to districts and expose the resulting plan statistics.

Bases: Partition

A Partition with areas, perimeters, and boundary information included. These additional data allow you to compute compactness scores like Polsby-Popper.

Initialize a Partition instance.

Parameters:

graph (Graph | FrozenGraph | networkx.Graph | None, optional) – Underlying graph. Required for a root partition. Defaults to None.
assignment (Mapping[Hashable, Hashable] | Assignment | str | None, optional) – Node to district assignment, or a node attribute containing it. Defaults to None.
updaters (Mapping[str, Callable[[Partition], Any]] | None, optional) – Named updater functions. Their result types vary by updater. Defaults to None.
parent (Partition | None, optional) – Parent partition for a child. Defaults to None.
flips (Mapping[Hashable, Hashable] | None, optional) – Reassignments relative to the parent. Defaults to None.
use_default_updaters (bool, optional) – Whether to include default updaters. Defaults to True.

Bases: object

The Partition class represents a partition of the nodes of the graph into districts (parts). Every iteration of MarkovChain creates a new Partition object from the previous Partition object by performing the set of flips (changes in association of a node to a district (perhaps confusingly called a “part”).

Perhaps the primary class attribute is “assignment” which stores the set of nodes in each district (“part”).

Note that the “parts” class attribute is actually a function that returns the “parts” of the assignment class attribute.

A Partition object also provides access (via __getitem__()) to the values computed by updater functions (see comment on updaters in the file updaters/flows.py).

Note that by default the constructor for a Partition object will convert the underlying graph in a Graph object from NetworkX to RustworkX - because RustworkX is so much faster than NetworkX. This is done in the _first_time() function below.

It is perhaps worth noting that when we convert the underlying graph object from NX to RX, we create a mapping dict that records the “original” NX node_ids and the new RX node_ids. It is stored as a class attribute of the new Graph object: Graph.nx_to_rx_node_id_map. We use this mapping to update the “assignment” class to use the new RX node_ids.

Lastly the “subgraphs” class attribute stores a subgraph for each district (“part”). Note that this is done for efficiency reasons because creating a subgraph is expensive - so subgraphs are created lazily (on demand) and subsequently cached.

graph¶

The underlying graph.

Type:: Graph

assignment¶

Maps node IDs to district IDs.

Type:: Assignment

parts¶

Maps district IDs to the set of nodes in that district.

Type:: dict[Hashable, frozenset[Hashable]]

subgraphs¶

Maps district IDs to the induced subgraph of that district.

Type:: SubgraphView

Initialize a Partition instance.

Parameters:

graph (Graph | FrozenGraph | networkx.Graph | None, optional) – Underlying graph. Required for a root partition. Defaults to None.
assignment (Mapping[Hashable, Hashable] | Assignment | str | None, optional) – Node to district assignment, or a node attribute containing it. Defaults to None.
updaters (Mapping[str, Callable[[Partition], Any]] | None, optional) – Named updater functions. Their result types vary by updater. Defaults to None.
parent (Partition | None, optional) – Parent partition for a child. Defaults to None.
flips (Mapping[Hashable, Hashable] | None, optional) – Reassignments relative to the parent. Defaults to None.
use_default_updaters (bool, optional) – Whether to include default updaters. Defaults to True.

property assignment_vector: ndarray¶

The part (district) label of each node, as an array indexed by internal node id.

Computed lazily and cached. When this partition’s parent has already emitted its vector, the child’s is built by copying it and rewriting only the flipped entries, so emitting the vector at every step of a chain costs an array copy (C-speed) plus the handful of flips rather than an O(n) rebuild from the assignment mapping.

The returned array is read-only, since child partitions build their vectors from it; call .copy() on it if you need a mutable version. Positions are internal node ids; use Graph.original_nx_node_id_for_internal_node_id() to translate back to the original node labels.

Returns:: Array of length n whose i-th entry is the part of node i.
Return type:: numpy.ndarray

crosses_parts(edge: tuple[Hashable, Hashable]) → bool[source]¶

Return True if the edge crosses from one part of the partition to another.

This method returns True if the edge crosses from one part of the partition to another. It returns true if the edge crosses from one part of the partition to another.

Parameters:: edge (tuple) – tuple of node IDs
Returns:: True if the edge crosses from one part of the partition to another
Return type:: bool

flip(flips: Mapping[NodeT, PartT], flips_passed_in_use_original_nx_node_ids: bool = False) → Partition[source]¶

Returns the new partition obtained by performing the given flips on this partition.

This method returns the new partition obtained by performing the given flips on this partition. It returns new Partition.

Parameters:

flips (dict) – dictionary assigning nodes of the graph to their new districts
flips_passed_in_use_original_nx_node_ids (bool) – Denotes whether the node_ids in the flips are original NX node_ids or whether they are internal RX node_ids. The only time this is set to True is for testing when the test wants to provide explicit flips using NX node_ids (because the test cannot know what node_ids RX will choose when we convert the underlying graph object).

Returns:

the new Partition

Return type:

Partition

classmethod from_districtr_file(graph: Graph, districtr_file: str | PathLike[str], updaters: Mapping[str, Callable[[Partition], Any]] | None = None) → Partition[source]¶

Return partition created from the Districtr file.

Create a Partition from a districting plan created with Districtr, a free and open-source web app created by MGGG for drawing districts.

The provided graph should be created from the same shapefile as the Districtr module used to draw the districting plan. These shapefiles may be found in a repository in the mggg-states GitHub organization, or by request from MGGG.

Parameters:

graph (Graph) – The graph to create the Partition from
districtr_file (str | os.PathLike) – the path to the .json file exported from Districtr
updaters (Mapping[str, Callable] | None, optional) – Dictionary of updaters.

Returns:

The partition created from the Districtr file

Return type:

Partition

classmethod from_random_assignment(graph: ~gerrychain.graph.graph.Graph, n_parts: int, epsilon: float, pop_col: str, updaters: ~collections.abc.Mapping[str, ~collections.abc.Callable[[~gerrychain.partition.partition.Partition], ~typing.Any]] | None = None, use_default_updaters: bool = True, partition_fn: ~gerrychain.partition.initial_partition_generators.PartitionFn = <function recursive_tree_part>, *, rng: ~random.Random | int | None = None) → Partition[source]¶

Create a Partition with a random assignment of nodes to districts.

This method creates a Partition with a random assignment of nodes to districts. It returns partition created with a random assignment.

Parameters:

graph (Graph) – The graph to create the Partition from.
n_parts (int) – The number of districts to divide the nodes into.
epsilon (float) – The maximum relative population deviation from the ideal
pop_col (str) – The column of the graph’s node data that holds the population data.
updaters (Mapping[str, Callable] | None, optional) – Dictionary of updaters.
use_default_updaters (bool, optional) – If False, do not include default updaters.
partition_fn (PartitionFn, optional) – The function to use to partition the graph into n_parts; it returns the full node-to-part assignment dict. It is called with this method’s normalized rng, which takes precedence over an rng partially bound to the partition_fn parameter. Defaults to gerrychain.partition.recursive_tree_part.
rng (random.Random | int | None, optional) – Source of randomness. An integer creates a reproducible RNG; None creates an independent RNG from system entropy.

Returns:

The partition created with a random assignment

Return type:

Partition

keys() → KeysView[str][source]¶

Return the names of this partition’s updaters.

Important: a Partition’s mapping/[] interface is over its updaters, not its nodes. So partition["population"] evaluates the "population" updater, and keys() returns the updater names (e.g. ["cut_edges", "population", ...]) - not node_ids or part_ids. This often surprises people who think of a Partition as a node-to-district map.

The actual node-to-part data lives in assignment (partition.assignment, a node_id -> part_id mapping), and the inverse part-to-nodes view is parts (partition.parts).

Returns:: A view of the updater names available on this partition.
Return type:: KeysView[str]

plot(geometries: geopandas.GeoDataFrame | geopandas.GeoSeries | None = None, **kwargs: Any) → matplotlib.axes.Axes[source]¶

Plot the partition, using the provided geometries.

This method plots the partition, using the provided geometries. It returns matplotlib axes object. Which plots the Partition.

Parameters:

geometries (geopandas.GeoDataFrame or geopandas.GeoSeries) – A GeoDataFrame or GeoSeries holding the geometries to use for plotting. Its Index should match the node labels of the partition’s underlying Graph.
**kwargs (Any) – Additional arguments to pass to geopandas.GeoDataFrame.plot to adjust the plot.

Returns:

The matplotlib axes object. Which plots the Partition.

Return type:

matplotlib.axes.Axes

gerrychain.partition.recursive_seed_part(graph: ~gerrychain.graph.graph.Graph, parts: ~collections.abc.Sequence[~collections.abc.Hashable], pop_target: float | int, pop_col: str, epsilon: float, bipartition_tree_fn: ~gerrychain.tree.bipartition_tree.BipartitionTreeFn = functools.partial(<function bipartition_tree>, max_attempts=100000), node_repeats: int = 0, n: int | None = None, ceil: int | None = None, *, rng: ~random.Random | int | None = None) → dict[Hashable, Hashable][source]¶

Returns an assignment dictionary with num_dists districts balanced within epsilon.

Returns an assignment dictionary with num_dists districts balanced within epsilon of. pop_target by recursively splitting graph using _recursive_seed_part_inner.

Parameters:

graph (Graph) – The graph
parts (Sequence) – Iterable of part labels (like [0,1,2] or range(4)).
pop_target (float | int) – Target population for each part of the partition
pop_col (str) – Node attribute key holding population data
epsilon (float) – How far (as a percentage of pop_target) from pop_target the parts of the partition can be
bipartition_tree_fn (BipartitionTreeFn, optional) – Function used to find balanced partitions at the 2-district level. Defaults to gerrychain.tree.bipartition_tree.
node_repeats (int, optional) – Additional roots to try on each spanning tree before drawing a new tree. Defaults to 0.
n (int | None, optional) – Either a positive integer (greater than 1) or None. If n is a positive integer, this function will recursively create a seed plan by either biting off districts from graph or dividing graph into n chunks and recursing into each of these. If n is None, this function prime factors num_dists = n_1*n_2*...*n_k (n_1 > n_2 > … n_k) and recursively partitions graph into n_1 chunks. Defaults to None.
ceil (int | None, optional) – Either a positive integer (at least 2) or None. Relevant only if n is None. If ceil is a positive integer then finds the largest factor of num_dists less than or equal to ceil, and recursively splits graph into that number of chunks, or bites off a district if that number is 1. Defaults to None.
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:

New assignments for the nodes of graph.

Return type:

dict

gerrychain.partition.recursive_tree_part(graph: ~gerrychain.graph.graph.Graph, parts: ~collections.abc.Sequence[~collections.abc.Hashable], pop_target: float | int, pop_col: str, epsilon: float, node_repeats: int = 0, bipartition_tree_fn: ~gerrychain.tree.bipartition_tree.BipartitionTreeFn = functools.partial(<function bipartition_tree>, max_attempts=100000), *, rng: ~random.Random | int | None = None) → dict[Hashable, Hashable][source]¶

Return new assignments for the nodes of graph.

Uses gerrychain.tree.bipartition_tree recursively to partition a tree into len(parts) parts of population pop_target (within epsilon).

Can be used to generate initial seed plans (partition assignments) or to implement ReCom-like “merge walk” proposals.

Parameters:

graph (Graph) – The graph to partition into len(parts) \(\varepsilon\)-balanced parts.
parts (Sequence) – Iterable of part (district) labels (like [0,1,2] or range(4)).
pop_target (float | int) – Target population for each part of the partition.
pop_col (str) – Node attribute key holding population data.
epsilon (float) – How far (as a percentage of pop_target) from pop_target the parts of the partition can be.
node_repeats (int, optional) – Additional roots to try on each spanning tree before drawing a new tree. Defaults to 0.
bipartition_tree_fn (BipartitionTreeFn, optional) – The partition method to use. Defaults to partial(bipartition_tree, max_attempts=100000).
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:

New assignments for the nodes of graph.

Return type:

dict