Graphs

Adjacency graphs represent the geographic units and neighborhood relationships used by a plan.

class gerrychain.graph.graph.Graph

This class closely mirrors the interface of a NetworkX Graph object, but with additions specific to GerryChain. It was created initially to represent geographical data (such as voting precincts) that would support the creation of voting district plans, but it can be used for general graph operations. For a more detailed description of the kinds of operations this class supports, please refer to the NetworkX documentation (https://networkx.org/documentation/stable/)

Note that this class encapsulates / wraps an underlying graph object which can either be a NetworkX graph or a RustworkX graph. The intent is that this class provides the same external interface as a NetworkX graph (for all of the uses that GerryChain cares about, at least) so that legacy GerryChain code that operated on NetworkX based Graph objects can mostly continue to work unchanged.

When a graph is added to a partition, however, the NX graph will be converted into an RX graph and the NX graph will become inaccessible to the user. The RX graph may also be “frozen” the way the NX graph was “frozen” in the legacy code, but we have not yet gotten that far in the implementation.

The reason for converting to an underlying RX graph is to gain the performance gains of the RustworkX library vis-a-vis NetworkX. The reason to continue to support NetworkX is because NetworkX has many user-friendly convenience functions that a user might want to use to create a graph.

So, the usage paradigm is to create a graph using NetworkX and to then convert to RustworkX for the compute intensive work done by MarkovChain().

Note that the conversion from NX to RX is done automatically when the user creates a Partition object.

add_data(df: DataFrame, columns: Iterable[str] | None = None) → None

Add columns of a DataFrame to a graph as node attributes by matching the DataFrame’s.

Parameters:

• df (DataFrame) – Dataframe containing given columns.

• columns (Iterable[str] | None, optional) – list of dataframe column names to add. Default is None.

add_edge(node_id1: Hashable, node_id2: Hashable) → None

Add an edge to the graph from node_id1 to node_id2.

Note that both nodes need to already be members of the graph

Parameters:

• node_id1 (Hashable) – One node ID in the edge.

• node_id2 (Hashable) – The other node ID in the edge.

convert_from_nx_to_rx() → Graph

Convert an NX-based graph object to be an RX-based graph object.

The primary use case for this routine is support for users constructing a graph using NetworkX functionality and then converting that NetworkX graph to RustworkX when creating a Partition object.

Returns:

An RX-based graph that is “the same” as the given NX-based graph

Return type:

‘Graph’

degree(node_id: Hashable) → int

Return the degree of the given node, that is, the number of other nodes directly.

This method returns the degree of the given node, that is, the number of other nodes directly. It returns number of nodes directly connected to the given node.

Parameters:

node_id (Hashable) – A node ID.

Returns:

Number of nodes directly connected to the given node

Return type:

int

edge_data(edge_id: Hashable) → dict[str, Any]

Return the data dictionary that contains the data for the given edge.

Note that in NetworkX an edge_id can be almost anything, for instance, a string or even a tuple. However, in RustworkX, an edge_id is an integer. This method handles both kinds.

Parameters:

edge_id (Hashable) – An edge ID.

Returns:

The edge’s data.

Return type:

dict[str, Any]

property edge_indices: set[Hashable]

Return a set of the edge ids in the graph.

Unlike nodes/node_indices (which carry the same content up to a permutation), edge_indices and edges are genuinely different: edge_indices returns edge ids (opaque integers under RustworkX), while edges returns the edges themselves as (u, v) tuples of node_ids. Use an edge id with get_edge_from_edge_id() / get_edge_id_from_edge() to convert between the two.

Returns:

The edge IDs in the graph.

Return type:

set[Hashable]

property edges: set[tuple[Hashable, Hashable]]

Return a set of all of the edges in the graph, where each edge is a (u, v) tuple of node_ids.

This returns the edges themselves, which may not be the same as their ids (in fact, for RustworkX backed graphs, they are guaranteed to be different). For the edge ids (opaque integers under RustworkX) see edge_indices.

Returns:

One (u, v) node ID tuple per edge.

Return type:

set[tuple[Hashable, Hashable]]

classmethod from_file(filename: str, adjacency: str = 'rook', cols_to_add: list[str] | None = None, reproject: bool = False, ignore_errors: bool = False) → Graph

Create a Graph from a shapefile, GeoPackage, GeoJSON, or similar source.

This method reads any format that geopandas can load and builds a graph from it.

See from_geodataframe for more details.

Parameters:

• filename (str) – Path to the shapefile / GeoPackage / GeoJSON / etc.

• adjacency (str, optional) – The adjacency type to use (“rook” or “queen”). Default is “rook”

• cols_to_add (list[str] | None, optional) – The names of the columns that you want to add to the graph as node attributes. Default is None.

• reproject (bool, optional) – Whether to reproject to a UTM projection before creating the graph. Default is False.

• ignore_errors (bool, optional) – Whether to ignore all invalid geometries and try to continue creating the graph. Default is False.

Returns:

The Graph object of the geometries from filename.

Return type:

Graph

Warning

This method requires the optional geopandas dependency. Install gerrychain with the geo extra via pip install gerrychain[geo], or install geopandas separately.

classmethod from_geodataframe(dataframe: GeoDataFrame, adjacency: str = 'rook', cols_to_add: list[str] | None = None, reproject: bool = False, ignore_errors: bool = False, crs_override: str | int | None = None) → Graph

Create the adjacency Graph of geometries described by dataframe.

The areas of the polygons are included as node attributes (with key area). The shared perimeter of neighboring polygons are included as edge attributes (with key shared_perim).

Nodes corresponding to polygons on the boundary of the union of all the geometries (e.g., the state, if your dataframe describes VTDs) have a boundary_node attribute (set to True) and a boundary_perim attribute with the length of this “exterior” boundary.

By default, areas and lengths are computed in a UTM projection suitable for the geometries. This prevents the bizarro area and perimeter values that show up when you accidentally do computations in Longitude-Latitude coordinates. If the user specifies reproject=False, then the areas and lengths will be computed in the GeoDataFrame’s current coordinate reference system. This option is for users who have a preferred CRS they would like to use.

Parameters:

• dataframe (GeoDataFrame) – The GeoDateFrame to convert

• adjacency (str, optional) – The adjacency type to use (“rook” or “queen”). Default is “rook”.

• cols_to_add (list[str] | None, optional) – The names of the columns that you want to add to the graph as node attributes. Default is None.

• reproject (bool, optional) – Whether to reproject to a UTM projection before creating the graph. Default is False.

• ignore_errors (bool, optional) – Whether to ignore all invalid geometries and attept to create the graph anyway. Default is False.

• crs_override (str | int | None, optional) – Value to override the CRS of the GeoDataFrame. Default is None.

Returns:

The adjacency graph of the geometries from dataframe. Note that the returned

Graph object has an embedded NetworkX graph (not a RustworkX graph).

Return type:

Graph

classmethod from_json(json_file_name: str) → Graph

Create a Graph from a JSON file in NetworkX “adjacency” format.

This is the standard way to load a dual graph that has already been built and saved to disk; it is the inverse of to_json(). To build a graph from geospatial data instead (a shapefile or a GeoDataFrame), use from_file() or from_geodataframe().

Expected file format:

The file must contain a single JSON object in the node-link “adjacency” format produced by networkx.readwrite.json_graph.adjacency_data - which is exactly what to_json() writes, so a file written by to_json round-trips back through from_json. The top-level object has these keys:

• "directed" / "multigraph": booleans. GerryChain graphs are undirected and not multigraphs, so both are normally false.

• "graph": graph-level attributes as a list of [key, value] pairs (often empty, []); e.g. a coordinate reference system might live here.

• "nodes": a list of node objects. Each has an "id" plus any number of arbitrary attributes (population, district, county, geometry, …).

• "adjacency": a list parallel to "nodes". adjacency[i] is the list of edges incident to node i; each edge object has the neighbor’s "id" plus any edge attributes (e.g. "shared_perim").

A minimal two-node example:

{
  'directed': false, "multigraph": false, "graph": [],
  'nodes': [{"pop": 5, "id": 0}, {"pop": 3, "id": 1}],
  'adjacency': [[{"id": 1}], [{"id": 0}]]
}

Node and edge attributes are preserved and become accessible as graph.node_data(node_id)[attr] and graph.edge_data(edge_id)[attr]. Anything you intend to use later (a population column for pop_col, a region_surcharge attribute, an election column, …) must already be present as a node attribute here.

Backend:

The returned Graph is NetworkX-backed, which is convenient for inspection and editing. When you later wrap it in a Partition, GerryChain converts it to the faster RustworkX backend automatically. Node ids are taken verbatim from the "id" fields; note that the RustworkX conversion reassigns node ids to a contiguous integer range, so do not rely on a node’s id carrying semantic meaning.

Side effect (data warnings):

After loading, this calls issue_warnings(), which warns about “islands” - degree-0 nodes. An island usually indicates a problem with the dual graph (a unit with no recorded adjacencies) and will break contiguity-based proposals, so the warning is worth heeding.

Parameters:

json_file_name (str) – Path to the JSON file to read. This is an ordinary filesystem path; the file is opened and parsed directly.

Returns:

A NetworkX-backed GerryChain Graph containing the nodes, edges, and attributes described by the file.

Return type:

Graph

Raises:

• FileNotFoundError – If json_file_name does not exist.

• json.JSONDecodeError – If the file does not contain valid JSON.

• KeyError – If the JSON is valid but is not in the expected adjacency format.

Example

>>> from gerrychain import Graph
>>> graph = Graph.from_json("./my_state.json")

If you just want a graph to experiment with, GerryChain bundles a ready-made example, which needs no file at all:

from gerrychain.examples import gerrymandria
graph = gerrymandria()

classmethod from_networkx(nx_graph: networkx.Graph[_NodeT, _NodeDataT, _EdgeDataT]) → Graph

Create a Graph from a NetworkX.Graph object.

This supports the use case of users creating a graph using NetworkX which is convenient - both for users of the previous implementation of a GerryChain object which was a subclass of NetworkX.Graph and for users more generally who are familiar with NetworkX.

Note that most users will not ever call this function directly, because they can create a GerryChain Partition object directly from a NetworkX graph, and the Partition initialization code will use this function to convert the NetworkX graph to a GerryChain Graph object.

Parameters:

nx_graph (networkx.Graph) – A NetworkX.Graph object with node and edge data to be converted into a GerryChain Graph object.

Returns:

A Graph object embedding the given NetworkX Graph

Return type:

Graph

classmethod from_null_networkx() → Graph

Create a Graph that has an empty embedded NetworkX Graph.

This was originally implemented as a way to encapsulate NetworkX dependencies in GerryChain code to this module (graph.py).

It supports the use case of a user who wants to build a graph from scratch without reference to NetworkX.

Returns:

A Graph object with no nodes

Return type:

Graph

classmethod from_rustworkx(rx_graph: PyGraph[_NodeDataT, Any] | PyDiGraph[_NodeDataT, Any]) → Graph

Create a Graph from a RustworkX.PyGraph object.

There are three primary use cases for this routine: 1) converting an NX-based Graph to be an RX-based Graph, 2) creating a subgraph of an RX-based Graph, and 3) creating a Graph whose node_ids do not need to be mapped to some previous graph’s node_ids.

In a little more detail:

1) A typical way to use GerryChain is to create a graph using NetworkX functionality and to then rely on the initialization code in the Partition class to create an RX-based Graph object. That initialization code constructs a RustworkX PyGraph and then uses this routine to create an RX-based Graph object, and it then creates maps from the node_ids of the resulting RX-based Graph back to the original NetworkX.Graph’s node_ids.

2) When creating a subgraph of a RustworkX PyGraph object, the node_ids of the subgraph are (in general) different from those of the parent graph. So we create a mapping from the subgraph’s node_ids to the node_ids of the parent. The subgraph() routine creates a RustworkX PyGraph subgraph, then uses this routine to create an RX-based Graph using that subgraph, and it then creates the mapping of subgraph node_ids to the parent (RX) graph’s node_ids.

3) In those cases where no node_id mapping is needed this routine provides a simple way to create an RX-based GerryChain graph object.

Parameters:

rx_graph (rustworkx.PyGraph | rustworkx.PyDiGraph) – a RustworkX graph object. A directed PyDiGraph is rejected with GraphValidationError.

Returns:

a GerryChain Graph object with an embedded RustworkX.PyGraph object

Return type:

‘Graph’

generic_bfs_predecessors(root_node_id: Hashable) → dict[Hashable, Hashable]

Return A dict mapping each node_id to the node_id of its parent node.

Returns a dict mapping each node_id in the graph to its predecessor node_id where the parent/child relationship is created by doing a breadth-first traversal of the graph starting at the root_node_id.

Note that this works for both NX and RX based Graph objects.

Parameters:

root_node_id (Hashable) – Root node of the breadth-first traversal.

Returns:

Node IDs mapped to their parent node IDs.

Return type:

dict[Hashable, Hashable]

generic_bfs_successors(root_node_id: Hashable) → dict[Hashable, list[Hashable]]

Return the BFS successors mapping for root_node_id.

The returned dictionary maps each parent node_id to a list of child node_ids.

Does a breadth-first traversal of the given graph, starting at the node specified by “root_node_id”, and returns a dict mapping parent node_ids to a list of the node_ids for that node’s children.

Parameters:

root_node_id (Hashable) – Node ID at which to start the BFS traversal.

Returns:

Parent node IDs mapped to their

node’s children.

Return type:

dict[Hashable, list[Hashable]]

generic_bfs_successors_generator(root_node_id: Hashable) → Generator[tuple[Hashable, list[Hashable]], None, None]

Yield BFS (parent, children) pairs starting from root_node_id.

Each yielded tuple contains a parent node and its children in breadth-first traversal order.

Does a breadth-first traversal of the given graph, starting at the node specified by “root_node_id”, and yields (in breadth-first order) a tuple consisting of each of the nodes traversed along with the children of that node.

Parameters:

root_node_id (Hashable) – Node ID at which to start the BFS traversal.

Returns:

Parent and children pairs

in breadth-first order, with the first parent specified by the “root_node_id”

Return type:

Generator[tuple[Hashable, list[Hashable]], None, None]

get_edge_from_edge_id(edge_id: Hashable) → tuple[Hashable, Hashable]

Return the edge (tuple of node_ids) corresponding to the given edge_id.

Note that in NX, an edge_id is the same as an edge - it is just a tuple of node_ids. However, in RX, an edge_id is an integer, so if you want to get the tuple of node_ids you need to use the edge_id to get that tuple…

Parameters:

edge_id (Hashable) – The desired edge ID.

Returns:

The edge’s node IDs.

Return type:

tuple[Hashable, Hashable]

get_edge_id_from_edge(edge: tuple[Hashable, Hashable]) → Hashable

Get the edge_id that corresponds to the given edge.

In RX an edge_id is an integer that designates an edge (an edge is a tuple of node_ids). In NX, an edge_id IS the tuple of node_ids. So, in general, to support both NX and RX, if you want to get access to the edge data for an edge (tuple of node_ids), you need to ask for the edge_id.

Parameters:

edge (tuple[Hashable, Hashable]) – A tuple of node IDs.

Returns:

The ID associated with the edge.

Return type:

Hashable

get_nx_graph() → networkx.Graph[Hashable, _AttributeDict, _AttributeDict]

Return the embedded NX graph object.

Return type:

networkx.Graph

get_nx_to_rx_node_id_map() → dict[Hashable, Hashable]

Return the dict that maps NX node_ids to RX node_ids.

The primary use case for this routine is to support automatically converting NX-based graph objects to be RX-based when creating a Partition object. The issue is that when you convert from NX to RX the node_ids change and so you need to update the Partition object’s Assignment to use the new RX node_ids. This routine is used to translate those NX node_ids to the new RX node_ids when initializing a Partition object.

Returns:

NetworkX node IDs mapped to RustworkX node IDs.

Return type:

dict[Hashable, Hashable]

get_rx_graph() → PyGraph[dict[str, Any], dict[str, Any]]

Return the embedded RX graph object.

Return type:

rustworkx.PyGraph

internal_node_id_for_original_nx_node_id(original_nx_node_id: Hashable) → Hashable

Return corresponding “internal” node_id.

Discover the “internal” node_id in the current GerryChain graph that corresponds to the “original” node_id in the top-level graph (presumably an NX-based graph object).

This was originally created to facilitate testing where it was convenient to express the test success criteria in terms of “original” node_ids, but the actual test needed to be made using the “internal” (RX) node_ids.

Parameters:

original_nx_node_id (Hashable) – The original node ID.

Returns:

The corresponding internal node ID.

Return type:

Hashable

is_a_tree() → bool

Return whether the current graph is a tree - meaning that it is connected and that it.

This method returns whether the current graph is a tree - meaning that it is connected and that it. It returns whether the current graph is a tree.

Returns:

Whether the current graph is a tree

Return type:

bool

is_connected() → bool

Return whether the (undirected) graph is connected.

Delegates to the backend’s native connectivity routine - rustworkx.is_connected for an RX graph, networkx.is_connected for an NX graph - which are faster than hand-rolled Python traversal.

A graph with 0 or 1 nodes is treated as trivially connected. This also guards the backend calls, both of which raise on an empty graph (rustworkx NullGraph / networkx NetworkXPointlessConcept).

Returns:

True if the graph is connected (or has at most one node).

Return type:

bool

is_directed() → bool

Returns False, because GerryChain graphs are not directed.

This is used by low level routines that can operate on both directed and un-directed graphs, that is, it exists so that we can use off-the-shelf code that needs to know if the graph is directed or not.

Returns:

False

Return type:

bool

is_node_set_connected(nodes: Iterable[Hashable]) → bool

Return whether the given set of nodes induces a connected subgraph of this graph.

This is a fast path for connectivity checks. It hands the node set straight to the backend’s subgraph constructor and runs the native connectivity routine on the result, skipping the Graph wrapper and the node-id translation maps that subgraph() builds - none of which are needed to answer a yes/no connectivity question.

A set of 0 or 1 nodes is treated as trivially connected, mirroring is_connected().

Parameters:

nodes (Iterable[Hashable]) – Node IDs to check.

Returns:

True if the nodes induce a connected subgraph (or there are at most one

of them).

Return type:

bool

is_nx_graph() → bool

Determine if the graph is NX-based.

is_rx_graph() → bool

Determine if the graph is RX-based.

property islands: set[Hashable]

Return A set of all node_ids for nodes of degree 0.

Return a set of all node_ids that are not connected via an edge to any other node in the graph - that is, nodes with degree = 0

Returns:

Node IDs for nodes of degree zero.

Return type:

set[Hashable]

issue_warnings() → None

Issue any warnings concerning the content or structure of the graph.

join(dataframe: DataFrame, columns: list[str] | None = None, left_index: str | None = None, right_index: str | None = None) → None

Add data from a dataframe to the graph, matching nodes to rows when the node’s.

Add data from a dataframe to the graph, matching nodes to rows when the node’s left_index attribute equals the row’s right_index value.

Parameters:

• dataframe (DataFrame) – DataFrame.

• columns (list[str] | None, optional) – The columns whose data you wish to add to the graph. If not provided, all columns are added. Default is None.

• left_index (str | None, optional) – The node attribute used to match nodes to rows. If not provided, node IDs are used. Default is None.

• right_index (str | None, optional) – The DataFrame column name to use to match rows to nodes. If not provided, the DataFrame’s index is used. Default is None.

laplacian_matrix() → csr_array

Return a SciPy sparse array containing the Laplacian matrix for the given graph.

For more details on the Graph Laplacian matrix, please refer to - https://fanchung.ucsd.edu/research/cb/ch1.pdf - https://en.wikipedia.org/wiki/Laplacian_matrix

Returns:

A SciPy sparse array containing the Laplacian matrix

Return type:

scipy.sparse.csr_array

minimum_spanning_tree_from_edge_weight(edge_weight_attribute_name: str) → Graph

Computes and returns the minimum spanning tree give the edge weights.

This method computes and returns the minimum spanning tree give the edge weights. It returns a Graph object containing the miniumum spanning tree given the edge weights.

Parameters:

edge_weight_attribute_name (str) – The name of the edge attribute containing the weight of the edge

Returns:

A Graph object containing the miniumum spanning tree given the edge weights.

Return type:

Graph

neighbors(node_id: Hashable) → Sequence[Hashable]

Return a sequence of neighbor node_ids.

Return a sequence of the node_ids of the nodes that are neighbors of the given node - that is, all of the nodes that are directly connected to the given node by an edge.

The result supports iteration (repeatedly), len(), and indexing, but it is not guaranteed to be a list. Callers that need list methods should wrap it in list().

The neighbors are returned in a deterministic order. RX collects neighbors into a randomly seeded HashSet, so the raw rustworkx.NodeIndices order varies call to call; any seeded algorithm that maps RNG draws over neighbor order (a random walk, a BFS feeding a random choice) would otherwise be unreproducible.

Parameters:

node_id (Hashable) – A node ID.

Returns:

The neighboring node IDs.

Return type:

Sequence[Hashable]

node_data(node_id: Hashable) → dict[str, Any]

Return the data dictionary that contains the given node’s data.

As docmented elsewhere, in GerryChain code before the conversion to RustworkX, users could access node data using the syntax:

graph.nodes[node_id][attribute_name]

This was because a GerryChain Graph object in that codebase was a subclass of NetworkX.Graph, and NetworkX was clever and implemented dict-like behavior for the syntax graph.nodes[]…

This Python cleverness was not carried over to the RustworkX implementation, so in the current GerryChain Graph implementation users need to access node data using the syntax:

graph.node_data(node_id)[attribute_name]

Parameters:

node_id (Hashable) – A node ID.

Returns:

The node’s data.

Return type:

dict[str, Any]

property node_indices: set[Hashable]

Return a set of the node_ids in the graph.

This is the canonical accessor for the graph’s node_ids. It returns a set, so it is suited to membership tests (node in graph.node_indices) and de-duplication, but it is unordered. If you need an ordered, indexable sequence of the same node_ids, use nodes (which returns a list). Prefer node_indices unless list semantics are specifically required.

Returns:

An unordered set of node IDs in the graph.

Return type:

set[Hashable]

property nodes: list[Hashable]

Return a list of all of the node_ids in the graph.

This returns the same node_ids as node_indices, the difference being only the container type: nodes returns an ordered, indexable list maintaining the backend’s node insertion order while node_indices returns an unordered set. Prefer node_indices unless you specifically need list semantics (ordering or indexing).

Note the related distinction for edges: edges returns the edges themselves (tuples of node_ids), whereas edge_indices returns edge ids (integers under RustworkX). That object-vs-id distinction is load-bearing for edges, but for nodes the node and its id coincide, which is why nodes and node_indices carry the same content.

There is also a minor subtlety that users are unlikely to encounter unless accessing the graph attribute off of a Partition object, but it is worth noting: the node_ids in the graph attribute of a Partition object are not necessarily the same as the node_ids in the original graph that was used to create the Partition object. Before the move to RustworkX it was common to create nodes whose ids were either meaningful (e.g., the FIPS code of a VTD), a subset of node ids of another graph (when the graph was a subgraph), or some coordinate pairs (common with grid graphs). That is not true of RustworkX node_ids, so any code that relies on the semantics of a node’s id (treating it like a name) is suspect in the RustworkX world.

Returns:

An ordered list of node IDs in the graph.

Return type:

list[Hashable]

normalized_laplacian_matrix() → csr_array

Return a SciPy sparse array containing the normalized Laplacian matrix for the given.

graph. For more details on the normalized Graph Laplacian matrix, please refer to - https://fanchung.ucsd.edu/research/cb/ch1.pdf - https://en.wikipedia.org/wiki/Laplacian_matrix#Laplacian_matrix_normalization_2

Returns:

A SciPy sparse array containing the normalized Laplacian matrix

Return type:

scipy.sparse.csr_array

num_connected_components() → int

Return the number of connected components.

Note: A connected component is a maximal subgraph where every vertex is reachable from every other vertex in that same subgraph. In a graph that is not fully connected, connected components are the separate, distinct “islands” of connected nodes. Every node in a graph belongs to exactly one connected component.

Returns:

The number of connected components

Return type:

int

original_nx_node_id_for_internal_node_id(internal_node_id: Hashable) → Hashable

Translate a node_id to its “original” node_id.

Parameters:

internal_node_id (Hashable) – A node ID to translate.

Returns:

The translated node ID.

Return type:

Hashable

original_nx_node_ids_for_list(list_of_node_ids: list[Hashable]) → list[Hashable]

Translate a list of node_ids to their “original” node_ids.

Parameters:

list_of_node_ids (list[Hashable]) – Node IDs to translate.

Returns:

The translated node IDs.

Return type:

list[Hashable]

original_nx_node_ids_for_set(set_of_node_ids: set[Hashable]) → set[Hashable]

Translate a set of node_ids to their “original” node_ids.

Parameters:

set_of_node_ids (set[Hashable]) – Node IDs to translate.

Returns:

The translated node IDs.

Return type:

set[Hashable]

predecessors(root_node_id: Hashable) → dict[Hashable, Hashable]

Return A dict mapping each node_id to the node_id of its parent node.

Returns a dict mapping each node_id in the graph to its predecessor node_id where the parent/child relationship is created by doing a breadth-first traversal of the graph starting at the root_node_id.

Note that the description above is exactly the same description as the description for generic_bfs_predecessors().

The only difference between this routine and generic_bfs_predecessors() is that this routine delegates to a built-in NetworkX routine in the case when the embedded graph object is NX-based. The assumption is that the built-in NetworkX implementation is faster.

In the case of an RX-based graph, this code delegates to generic_bfs_predecessors().

Parameters:

root_node_id (Hashable) – Root node of the breadth-first traversal.

Returns:

Node IDs mapped to their parent node IDs.

Return type:

dict[Hashable, Hashable]

subgraph(nodes: Iterable[Hashable]) → Graph

Create a subgraph that contains the given nodes.

Note that creating a subgraph of an RustworkX (RX) graph renumbers the nodes, so that a node that had node_id: 4 in the parent graph might have node_id: 2 in the subgraph. This is a HUGE difference from the NX world where the node_ids in a subgraph do not change from those in the parent graph.

In order to make sense of the nodes in a subgraph in the RX world, we need to maintain mappings from the node_ids in the subgraph to the node_ids of the immediate parent graph and to the “original” top-level graph that contains all of the nodes. You will notice the creation of those maps in the code below.

Parameters:

nodes (Iterable[Hashable]) – Nodes to include in the subgraph.

Returns:

A subgraph containing the given nodes.

Return type:

‘Graph’

subgraphs_for_connected_components() → list[Graph]

Create and return a list of subgraphs for each set of nodes in the given graph that are.

connected. Note that a connected graph is one in which there is a path from every node in the graph to every other node in the graph.

Note also that each of the subgraphs returned is a maximal subgraph of connected components, meaning that there is no other larger subgraph of connected components that includes it as a subset.

Returns:

A list of “maximal” subgraphs each of which contains nodes that are

connected.

Return type:

list[‘Graph’]

successors(root_node_id: Hashable) → dict[Hashable, list[Hashable]]

Return a dictionary mapping each node to a list of its children.

Does a breadth-first traversal of the given graph, starting at the node specified by “root_node_id”, and returns a dict mapping parent node_ids to a list of the node_ids for that node’s children.

Note that the above is the exact same description as the description for generic_bfs_successors(). In fact, for NX-based graphs, this routine just delegates to NetworkX for the result.

The reason for the delegation to NetworkX is the presumption that the NX version would be faster - which may or may not actually be the case.

Parameters:

root_node_id (Hashable) – Node ID at which to start the breadth-first traversal of the graph.

Returns:

Nodes mapped to their children.

Return type:

dict[Hashable, list[Hashable]]

to_json(json_file_name: str, include_geometries_as_geojson: bool = False) → None

Write this Graph to disk as a JSON file in NetworkX “adjacency” format.

This is the inverse of from_json(): it serializes the graph - every node and edge, with all of their attributes - to the node-link “adjacency” format produced by networkx.readwrite.json_graph.adjacency_data, so a file written here can be read back with from_json(). See from_json() for a description of the on-disk structure.

Backend requirement (NetworkX only):

to_json currently only works on a NetworkX-backed graph and raises TypeError otherwise. This matters in practice because wrapping a graph in a Partition converts it to the RustworkX backend, so the graph reached via partition.graph cannot be serialized directly - keep a reference to the original NetworkX Graph (e.g. the one returned by from_json() / from_file()) if you need to write it out. (Serializing an RX-backed graph is a planned enhancement.)

Geometries:

Graphs built from geospatial data (from_file() / from_geodataframe()) carry a shapely geometry object on each node, which is not JSON-serializable. The include_geometries_as_geojson flag decides what happens to those geometry attributes (it has no effect on graphs that have no geometry):

• False (default): geometry attributes are dropped from the output. The file is smaller, but the geometry is not saved, so a round-trip through from_json() will not recover it.

• True: each geometry is converted to GeoJSON (its __geo_interface__) and written into the file, preserving it. Note that reading the file back returns those attributes as GeoJSON dicts, not as shapely objects.

Non-JSON-native values:

Attribute values that the standard JSON encoder cannot handle are passed through json_serialize(), which converts pandas / numpy integer values to plain Python int (a common result of building a graph from a GeoDataFrame).

Parameters:

• json_file_name (str) – Path of the JSON file to write. An existing file is overwritten.

• include_geometries_as_geojson (bool, optional) – Whether to write node geometries to the file as GeoJSON (True) or strip them out (False, the default). See “Geometries” above.

Returns:

The graph is written to json_file_name.

Return type:

None

Raises:

• TypeError – If this graph is not NetworkX-backed (e.g. an RX-backed graph, such as the one inside a Partition).

• OSError – If the file cannot be opened or written.

Example

>>> from gerrychain import Graph
>>> graph = Graph.from_json("./my_state.json")
>>> graph.to_json("./my_state_copy.json")

to_networkx_graph() → networkx.Graph[Hashable, _AttributeDict, _AttributeDict]

Create a NetworkX.Graph object that has the same nodes, edges, node_data, and edge_data. as the GerryChain Graph object.

The intended purpose of this routine is to allow a user to run a MarkovChain - which uses an embedded RustworkX graph and then extract an equivalent version of that graph with all of its data as a NetworkX.Graph object - in order to use NetworkX routines to access and manipulate the graph.

In short, this routine allows users to use NetworkX functionality on a graph after running a MarkovChain.

If the GerryChain graph object is NX-based, then this routine merely returns the embedded NetworkX.Graph object.

Returns:

A NetworkX.Graph object that is equivalent to the GerryChain Graph

object (nodes, edges, node_data, edge_data)

Return type:

networkx.Graph

translate_subgraph_node_ids_for_flips(flips: dict[Hashable, Hashable]) → dict[Hashable, Hashable]

Translate the given flips so that the subgraph node_ids in the flips correspond to the appropriate node_ids in the parent graph.

The flips parameter is a dict mapping node_ids to parts (districts).

This routine is used when a computation that creates flips is made on a subgraph, but those flips want to be translated into the context of the parent graph at the end of the computation.

For more details, refer to the larger comment on subgraphs…

Parameters:

flips (dict[Hashable, Hashable]) – A dictionary associating nodes with new part in a partition (a “part” is the same as a district in common parlance).

Returns:

Flips translated to use node IDs

appropriate for the parent graph

Return type:

dict[Hashable, Hashable]

translate_subgraph_node_ids_for_set_of_nodes(set_of_nodes: Set[Hashable]) → set[Hashable]

Translate the given set_of_nodes to have the appropriate node_ids for the parent graph.

This routine is used when a computation that creates a set of nodes is made on a subgraph, but those nodes want to be translated into the context of the parent graph at the end of the computation.

For more details, refer to the larger comment on subgraphs…

Parameters:

set_of_nodes (AbstractSet[Hashable]) – Node IDs in a subgraph.

Returns:

Node IDs translated to have the IDs appropriate

for the parent graph

Return type:

set[Hashable]

verify_graph_is_valid(thorough: bool | None = None) → bool

Verify that the graph is internally consistent.

Two levels of checking are performed:

• An always-on, O(1) structural invariant: a Graph must embed exactly one backing graph - either NetworkX or RustworkX, never both or neither. This runs automatically at every construction boundary and costs nothing measurable, so it is never gated.

• An opt-in, O(nodes + edges) thorough audit (see _verify_graph_thoroughly). This is expensive enough to matter inside a chain, so it is off by default and controlled by the global runtime-checks switch (gerrychain.set_runtime_checks / gerrychain.runtime_checks). The test suite enables it.

Parameters:

thorough (bool | None) – Whether to run the expensive audit. If None (default), follows the global runtime-checks setting. Pass True to force it on or False to force it off (e.g. on hot construction paths that build many short-lived subgraphs).

Returns:

True if the graph is valid.

Return type:

bool

Raises:

GraphValidationError – If the graph fails a check.

warn_for_islands() → None

Issue a warning if there are any islands in the graph.

Raises:

Warning – If there are any islands in the graph, a warning is issued with the indices of the islands.