binary_ensemble.graph

The graph module exposes the same reordering algorithms used by BendlEncoder.add_graph() and relabel_bundle(). Use it when you want to inspect or manage the graph order yourself before writing assignments.

Each function returns (reordered_graph, node_permutation_map).

Function	Ordering
reorder(graph, sort="mlc")	Dispatch helper for all orderings
reorder_multi_level_cluster(graph)	Recursive topology-based clustering
reorder_reverse_cuthill_mckee(graph)	Reverse Cuthill-McKee bandwidth reduction
reorder_by_key(graph, key)	Sort by a node attribute, or "id" for node id

Graph reordering utilities used by ben sort-graph and bundle relabeling.

Reordering a dual graph before building a chain (or a bundle) can dramatically improve BEN/XBEN compression. Each function takes a graph (a live networkx.Graph, or adjacency-format JSON as a dict/list, raw bytes, a file-like with .read(), or a path) and returns (reordered_graph, node_permutation_map):

• reordered_graph is a live NetworkX graph in its new node ordering (the same shape binary_ensemble.bundle.BendlEncoder.add_graph() and binary_ensemble.bundle.BendlDecoder.read_graph() return).

• node_permutation_map is the parsed node_permutation_map.json payload, an object with a node_permutation_old_to_new field mapping original zero-based node positions to their new positions.

To reorder and embed the result in a bundle in one step, pass sort / key to binary_ensemble.bundle.BendlEncoder.add_graph().

Reordering functions

import networkx as nx

from binary_ensemble import graph

dual_graph = nx.convert_node_labels_to_integers(nx.grid_2d_graph(4, 4))
for node in dual_graph.nodes:
    dual_graph.nodes[node]["GEOID20"] = f"{node:04d}"

adjacency = nx.adjacency_data(dual_graph)
reordered, permutation_map = graph.reorder(adjacency, sort="key", key="GEOID20")

assert reordered.number_of_nodes() == dual_graph.number_of_nodes()
assert "node_permutation_old_to_new" in permutation_map

The returned reordered graph is a NetworkX graph in the new node order. If you write an assignment stream against this graph, emit assignment values in list(reordered.nodes) order.

Tip

If you are creating a bundle, BendlEncoder.add_graph(..., sort=...) is usually simpler: it reorders the graph, stores graph.json, stores node_permutation_map.json, and returns the reordered graph in one call.

reorder(graph, sort='mlc', key=None)

Reorder graph and return (reordered_graph, node_permutation_map).

Parameters:

• graph (GraphInput) – The dual graph (GraphInput): a live networkx.Graph (subclasses such as gerrychain.Graph count), or adjacency-format JSON as a parsed dict or list, raw bytes, a file-like object with .read(), or a str / os.PathLike path to a JSON file. A plain str is a path here.

• sort (SortMethod, optional) – The ordering (SortMethod): "mlc" (multi-level clustering), "rcm" (reverse Cuthill-McKee), or "key" (sort by the node attribute named in key). Default is "mlc".

• key (str | None, optional) – Node attribute to sort by, e.g. key="GEOID"; key="id" sorts by the NetworkX node id. Required with (and only valid with) sort="key". Default is None.

Returns:

tuple[networkx.Graph, NodePermutationMap] – The reordered graph (a live NetworkX graph, the shape BendlEncoder.add_graph and BendlDecoder.read_graph return) and the parsed permutation map (NodePermutationMap), whose node_permutation_old_to_new field maps original zero-based node positions to their new positions.

Raises:

ValueError – If sort / key is invalid.

Return type:

tuple[nx.Graph, NodePermutationMap]

reorder_multi_level_cluster(graph)

Reorder graph using recursive multi-level clustering.

Equivalent to reorder() with sort="mlc".

Parameters:

graph (GraphInput) – The dual graph (GraphInput): a live networkx.Graph, or adjacency-format JSON as a parsed dict or list, raw bytes, a file-like object with .read(), or a str / os.PathLike path to a JSON file.

Returns:

tuple[networkx.Graph, NodePermutationMap] – The reordered graph and the parsed permutation map (see reorder()).

Return type:

tuple[nx.Graph, NodePermutationMap]

reorder_reverse_cuthill_mckee(graph)

Reorder graph using Reverse Cuthill-McKee.

Equivalent to reorder() with sort="rcm".

Parameters:

graph (GraphInput) – The dual graph (GraphInput): a live networkx.Graph, or adjacency-format JSON as a parsed dict or list, raw bytes, a file-like object with .read(), or a str / os.PathLike path to a JSON file.

Returns:

tuple[networkx.Graph, NodePermutationMap] – The reordered graph and the parsed permutation map (see reorder()).

Return type:

tuple[nx.Graph, NodePermutationMap]

reorder_by_key(graph, key)

Reorder graph by sorting on a node attribute.

Equivalent to reorder() with sort="key".

Parameters:

• graph (GraphInput) – The dual graph (GraphInput): a live networkx.Graph, or adjacency-format JSON as a parsed dict or list, raw bytes, a file-like object with .read(), or a str / os.PathLike path to a JSON file.

• key (str) – Node attribute to sort by, e.g. key="GEOID"; the special key="id" sorts by the NetworkX node id.

Returns:

tuple[networkx.Graph, NodePermutationMap] – The reordered graph and the parsed permutation map (see reorder()).

Return type:

tuple[nx.Graph, NodePermutationMap]