FalcomChain API

falcomchain.graph

class falcomchain.graph.Graph(*args, backend=None, **kwargs)[source]

Represents a graph to be partitioned, extending the networkx.Graph.

This class includes additional class methods for constructing graphs from shapefiles, and for saving and loading graphs in JSON format.

classmethod from_networkx(graph)[source]

Create a Graph instance from a networkx.Graph object.

Parameters:

graph (networkx.Graph) – The networkx graph to be converted.

Returns:

The converted graph as an instance of this class.

Return type:

Graph

classmethod create(source, **kwargs)[source]

Smart constructor that dispatches based on the type of source.

  • str (filename ending in .shp, .geojson, .gpkg, etc.) -> from_file

  • geopandas.GeoDataFrame -> from_geodataframe

  • networkx.Graph -> from_networkx

  • dict with key edges -> from_data

  • existing Graph -> returned as-is

Parameters:

  • source – Input data of various types.

  • kwargs – Forwarded to the underlying constructor.

Returns:

A Graph object.

Return type:

Graph

Example:

graph = Graph.create("districts.shp", demand_col="POP")
graph = Graph.create(my_geodataframe, candidate_col="is_candidate")
graph = Graph.create({"edges": [(1,2),(2,3)], "demand": {1:10, 2:20, 3:30},
                      "candidates": [1, 3]})
classmethod from_data(edges, demand, candidates=None, super_candidates=None, coordinates=None, area=None, extra_attributes=None, validate=True)[source]

Build a Graph from raw data dictionaries. The recommended entry point for users who don’t have a GeoDataFrame.

Parameters:

  • edges – Iterable of (u, v) tuples defining the adjacency.

  • demand – Dict mapping node -> demand value.

  • candidates – Iterable of node IDs that are level-1 facility candidates (F^1 ⊂ V^1), or dict node -> bool. Defaults to no candidates.

  • super_candidates – Iterable of node IDs that are level-2 (super-) facility candidates (F^2 ⊂ V^1), or dict node -> bool. Independent of candidates — a node can be in either, both, or neither. Defaults to no super-candidates.

  • coordinates – Dict mapping node -> (x, y). Defaults to (0, 0).

  • area – Dict mapping node -> area. Defaults to 1.0.

  • extra_attributes – Dict of {attribute_name: {node: value}} for additional node attributes (e.g., custom features).

  • validate (bool)

Returns:

A Graph with node attributes demand, area, candidate, super_candidate, C_X, C_Y, plus any extras.

Return type:

Graph

Example:

graph = Graph.from_data(
    edges=[(1, 2), (2, 3), (3, 1)],
    demand={1: 100, 2: 150, 3: 80},
    candidates=[1, 3],          # level-1 candidates
    super_candidates=[3],        # level-2 candidate (must be V^1)
    coordinates={1: (0, 0), 2: (1, 0), 3: (0.5, 1)},
)
set_partition(assignment, teams_per_district=None, capacity_level=None)[source]

Write partition state into the graph as node and graph attributes. After calling this, the graph IS the partition — you can serialize it as a single artifact.

Parameters:

  • assignment – Dict mapping node -> district ID.

  • teams_per_district – Optional dict district -> team count.

  • capacity_level – Optional max teams per district.

get_partition_data()[source]

Read partition state from graph attributes. Returns None if no district attribute is present.

Returns:

Dict with assignment, teams_per_district, capacity_level, or None if no partition data exists.

classmethod from_json(json_file)[source]

Load a graph from a JSON file in the NetworkX json_graph format.

Parameters:

json_file (str) – Path to JSON file.

Returns:

The loaded graph as an instance of this class.

Return type:

Graph

to_json(json_file, *, include_geometries_as_geojson=False)[source]

Save a graph to a JSON file in the NetworkX json_graph format.

Parameters:

  • json_file (str) – Path to target JSON file.

  • include_geometry_as_geojson (bool) – Whether to include any shapely geometry objects encountered in the graph’s node attributes as GeoJSON. The default (False) behavior is to remove all geometry objects because they are not serializable. Including the GeoJSON will result in a much larger JSON file.

  • include_geometries_as_geojson (bool, optional)

Returns:

None

Return type:

None

classmethod from_file(filename, adjacency='rook', demand_col='demand', candidate_col='candidate', super_candidate_col='super_candidate', area_col=None, cols_to_add=None, reproject=False, ignore_errors=False, validate=True)[source]

Create a Graph from a shapefile (or GeoPackage, or GeoJSON, or any other library that geopandas can read. 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 (Optional[List[str]], 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.

  • demand_col (str)

  • candidate_col (str)

  • super_candidate_col (str | None)

  • area_col (str | None)

  • validate (bool)

Returns:

The Graph object of the geometries from filename.

Return type:

Graph

Warning

This method requires the optional geopandas dependency. This method requires geopandas. Install it with:

pip install geopandas
classmethod from_geodataframe(dataframe, adjacency='rook', demand_col='demand', candidate_col='candidate', super_candidate_col='super_candidate', area_col=None, cols_to_add=None, reproject=False, ignore_errors=False, crs_override=None, validate=True)[source]

Creates 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 (geopandas.GeoDataFrame) – The GeoDataFrame to convert.

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

  • demand_col (str) – Name of the column holding demand values. The column is renamed to demand on the resulting graph. Default “demand”.

  • candidate_col (str) – Name of the column holding level-1 facility candidate flags (0/1 or True/False). Renamed to candidate. Default “candidate”.

  • super_candidate_col (str | None) – Name of the column holding level-2 (super-) facility candidate flags. Renamed to super_candidate. Optional — if the column is absent from the dataframe, every node gets super_candidate=0. Default “super_candidate”.

  • area_col (str | None) – Name of the column holding pre-computed areas. If None, areas are computed from geometry. Default None.

  • cols_to_add (List[str] | None) – Additional columns to copy as node attributes.

  • reproject (bool) – Reproject to a UTM projection before creating the graph.

  • ignore_errors (bool) – Ignore invalid geometries.

  • crs_override (str | int | None) – Override the CRS of the GeoDataFrame.

  • validate (bool) – Verify required FalcomChain attributes after construction.

Returns:

A Graph with required attributes demand and candidate, plus computed area, boundary_node, boundary_perim, and edge shared_perim.

Return type:

Graph

Raises:

SchemaValidationError – If validate=True and required attributes are missing or invalid.

lookup(node, field)[source]

Lookup a node/field attribute.

Parameters:

  • node (Any) – Node to look up.

  • field (Any) – Field to look up.

Returns:

The value of the attribute field at node.

Return type:

Any

property node_indices
property edge_indices
add_data(df, columns=None)[source]

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

Parameters:

  • df (pandas.DataFrame) – Dataframe containing given columns.

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

Returns:

None

Return type:

None

join(dataframe, columns=None, left_index=None, right_index=None)[source]

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 (pandas.DataFrame) – DataFrame.

  • columns (Optional[List[str]], optional)

  • left_index (Optional[str], optional)

  • right_index (Optional[str], optional)

Columns:

The columns whose data you wish to add to the graph. If not provided, all columns are added. Default is None.

Left_index:

The node attribute used to match nodes to rows. If not provided, node IDs are used. Default is None.

Right_index:

The DataFrame column name to use to match rows to nodes. If not provided, the DataFrame’s index is used. Default is None.

Returns:

None

Return type:

None

property islands: Set

The set of degree-0 nodes. :rtype: Set

Type:

returns

warn_for_islands()[source]
Returns:

None

Raises:

UserWarning if the graph has any islands (degree-0 nodes).

Return type:

None

issue_warnings()[source]
Returns:

None

Raises:

UserWarning if the graph has any red flags (right now, only islands).

Return type:

None

class falcomchain.graph.FrozenGraph(graph)[source]

Represents an immutable graph to be partitioned. It is based off Graph.

This speeds up chain runs and prevents having to deal with cache invalidation issues. This class behaves slightly differently than Graph or networkx.Graph.

Not intended to be a part of the public API.

Variables:

  • graph – The underlying graph.

  • size – The number of nodes in the graph.

Parameters:

graph (Graph)

Note

The class uses __slots__ for improved memory efficiency.

class falcomchain.graph.Grid(dimensions, num_candidates, density, threshold=None, candidate_ignore=None)[source]

Synthetic grid graph generator for testing and demonstrations.

Note

This is a testing/demo utility, not a primary entry point. For production use cases, build your graph with Graph.from_geodataframe() (geographic data) or Graph.from_data() (raw data).

Creates an m x n grid graph with all required FalcomChain node attributes (demand, area, C_X, C_Y, candidate) plus boundary information.

Example usage:

grid = Grid(dimensions=(10, 10), num_candidates=20, density="uniform")
graph = grid.graph  # the underlying Graph object
Parameters:

  • dimensions (Tuple[int, int]) – (rows, cols) grid size.

  • num_candidates (int) – Number of nodes randomly selected as facility candidates.

  • density (str) – Demand pattern: ‘uniform’, ‘opposite’, or ‘corners’.

  • threshold (tuple | None) – For non-uniform density, threshold tuple.

  • candidate_ignore (int | None) – Optional region to exclude from candidate sampling.

Node attributes set: demand, area, C_X, C_Y, candidate, boundary_node, boundary_perim. Edge attributes set: shared_perim.

create_grid_graph(dimensions)[source]

Creates a grid graph with the specified dimensions. Optionally includes diagonal connections between nodes.

Parameters:

  • dimensions (Tuple[int, int]) – The grid dimensions (rows, columns).

  • with_diagonals (bool) – If True, includes diagonal connections.

Returns:

A grid graph.

Return type:

Graph

Raises:

ValueError – If the dimensions are not a tuple of length 2.

assign_coordinates()[source]

Sets the specified attribute to the specified value for all nodes in the graph.

Parameters:

  • graph (Graph) – The graph to modify.

  • attribute (Any) – The attribute to set.

  • value (Any) – The value to set the attribute to.

Returns:

None

Return type:

None

assign_candidates()[source]

Sets self.num_candidates many nodes as candidates uniformly random on permitted region

Return type:

None

tag_boundary_nodes(dimensions)[source]

Adds the boolean attribute boundary_node to each node in the graph. If the node is on the boundary of the grid, that node also gets the attribute boundary_perim which is determined by the function get_boundary_perim().

Parameters:

  • graph (Graph) – The graph to modify.

  • dimensions (Tuple[int, int]) – The dimensions of the grid.

Returns:

None

Return type:

None

get_boundary_perim(dimensions)[source]

Determines the boundary perimeter of a node on the grid. The boundary perimeter is the number of sides of the node that are on the boundary of the grid.

Parameters:

  • node (Tuple[int, int]) – The node to check.

  • dimensions (Tuple[int, int]) – The dimensions of the grid.

Returns:

The boundary perimeter of the node.

Return type:

int

assign_population(dimensions, threshold)[source]

Assigns a color (as an integer) to a node based on its x-coordinate.

This function is used to partition the grid into two parts based on a given threshold. Nodes with an x-coordinate less than or equal to the threshold are assigned one color, and nodes with an x-coordinate greater than the threshold are assigned another.

Parameters:

  • node (Tuple[int, int]) – The node to color, represented as a tuple of coordinates (x, y).

  • threshold (int) – The x-coordinate value that determines the color assignment.

  • dimensions (tuple)

Returns:

An integer representing the color of the node. Returns 0 for nodes with x-coordinate less than or equal to the threshold, and 1 otherwise.

Return type:

int

Attribute schema for FalcomChain graphs.

Defines exactly what node, edge, and graph-level attributes the hierarchical capacitated facility location algorithms read and write.

This is the single source of truth — every constructor, validator, and documentation page references this schema.

class falcomchain.graph.schema.AttributeSpec(name, required, type, default, purpose, validator=None)[source]

Specification for a single attribute.

Parameters:
exception falcomchain.graph.schema.SchemaValidationError[source]

Raised when a graph’s attributes don’t match the FalcomChain schema.

falcomchain.graph.schema.required_node_attributes()[source]

List of node attribute names that MUST be present.

Return type:

list

falcomchain.graph.schema.validate_graph(graph, strict=True)[source]

Validate that a graph satisfies the FalcomChain attribute schema.

Parameters:

  • graph – A networkx-like Graph.

  • strict (bool) – If True, raise SchemaValidationError on failure. If False, return a list of error strings.

Returns:

List of error messages (empty if valid).

Raises:

SchemaValidationError – If strict=True and validation fails.

Return type:

list

falcomchain.graph.schema.describe_schema()[source]

Return a human-readable description of the schema.

Return type:

str

falcomchain.partition

class falcomchain.partition.Partition(capacity_level=None, graph=None, flip=None, superflip=None, parent=None, assignment=None)[source]

Partition represents a partition of the nodes of the graph. It will perform the first layer of computations at each step in the Markov chain - basic aggregations and calculations that we want to optimize.

Variables:

  • graph – The underlying graph.

  • assignment – Maps node IDs to district IDs.

  • parts – Maps district IDs to the set of nodes in that district.

  • subgraphs – Maps district IDs to the induced subgraph of that district.

Parameters:

capacity_level (int | None)

subgraphs
classmethod from_random_assignment(graph, epsilon, demand_target, assignment_class, capacity_level=1, density=None, super_assignment=None, init_super_partition=False, epsilon_super=None, c_min=1, c_min_super=1, c_max_super=None, min_districts_super=1, rule='per_team', enforce_global_balance=False, psi_fn=None, super_psi_fn=None)[source]

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

Parameters:

  • graph (Graph) – The graph to create the Partition from.

  • teams (int) – The total of number of doctor-nurse teams to hire at centers

  • capacity_level (int) – The maximum number of doctor nurse teams at a facility

  • epsilon (float) – The maximum relative population deviation from the ideal population. Should be in [0,1].

  • demand_col (str) – The column of the graph’s node data that holds the demand data.

  • updaters (Optional[Dict[str, Callable]], optional) – Dictionary of updaters

  • use_default_updaters (bool, optional) – If False, do not include default updaters.

  • method (Callable, optional) – The function to use to partition the graph into n_parts. Defaults to capacitated_recursive_tree().

  • super_assignment (Dict | None) – Optional dict mapping each base node to a superdistrict ID (e.g. health-zone). When provided, level-1 districts are formed by partitioning each superdistrict independently — every level-1 district lives entirely inside one superdistrict, and the resulting super_assignment on the Partition reflects this fixed grouping. When None (default), the graph is partitioned globally and each level-1 district becomes its own superdistrict (identity level-2).

  • init_super_partition (bool) – When True (and super_assignment is not provided), additionally call recursive partitioning on the supergraph to produce a non-trivial initial level-2 partition (paper Section 5.1, “Initialization”). Default False keeps the cheap identity grouping. Ignored when super_assignment is provided (the user-supplied grouping is already a real level-2 partition).

  • epsilon_super (float | None) – Level-2 demand-balance tolerance ε² used by init_super_partition. Defaults to epsilon when not set.

  • c_min (int) – Minimum capacity per district (paper’s c^ℓ_min). Default 1. With c_min > 1 no district has fewer than c_min teams; the chain explores a smaller state space and Assumption 6.1 relaxes by a factor of c_min.

  • demand_target (int)

  • assignment_class (Assignment)

  • density (float | None)

  • c_min_super (int)

  • c_max_super (int | None)

  • min_districts_super (int)

  • rule (str)

  • enforce_global_balance (bool)

  • psi_fn (Callable | None)

  • super_psi_fn (Callable | None)

Returns:

The partition created with a random assignment

Return type:

Partition

perform_flip(flipp, superflipp)[source]

Returns the new partition obtained by performing the given flips and new_teams. on this partition. :param flip: :param superflip: :returns: the new Partition

Parameters:
Return type:

Partition

crosses_parts(edge)[source]
Parameters:

edge (Tuple) – tuple of node IDs

Returns:

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

Return type:

bool

part_demand(part)[source]
part_area(part)[source]
property parts
property teams
property candidates
property super_parts

Maps superdistrict ID to the frozenset of level-1 district IDs in it.

property super_teams

Maps superdistrict ID to the total number of teams in it.

save(path)[source]

Serializes the partition’s assignment, team allocations, and metadata to a pickle file.

Parameters:

path (str) – File path to write to.

save_json(path)[source]

Save the partition as a human-readable JSON file.

The file contains the full assignment (node -> district), team allocations (district -> teams), per-district demand, and metadata. Node and district IDs are converted to strings for JSON compatibility.

Parameters:

path (str) – File path to write to.

write_to_graph(graph=None)[source]

Write this partition’s state into the graph as node and graph attributes. After this, the graph alone fully describes the partition.

Parameters:

graph – Optional Graph (or networkx.Graph) to write to. Defaults to self.graph.graph (the underlying mutable graph).

classmethod from_graph(graph)[source]

Construct a Partition from a graph that has district node attributes and teams_per_district graph attribute. This is the inverse of write_to_graph().

Parameters:

graph – A Graph (or networkx.Graph) with partition state stored as attributes.

Returns:

A Partition instance.

Return type:

Partition

Raises:

ValueError – If the graph lacks the required district attribute.

classmethod load_json(json_path, graph)[source]

Load a partition from a JSON file and a graph.

Parameters:

  • json_path (str) – Path to the JSON partition file.

  • graph – The graph this partition belongs to.

Returns:

A restored Partition instance.

Return type:

Partition

classmethod load_partition(graph_path, partition_path)[source]

Loads a partition from saved graph and partition pickle files.

Parameters:

  • graph_path (str) – Path to the saved graph pickle file.

  • partition_path (str) – Path to the saved partition pickle file.

Returns:

A restored Partition instance.

Return type:

Partition

graph
capacity_level
supergraph
assignment
super_assignment
parent
superflip
flip
flow
step
class falcomchain.partition.assignment.Assignment(parts, candidates, teams, mapping=None, validate=True)[source]

An assignment of nodes into parts.

The goal of Assignment is to provide an interface that mirrors a dictionary (what we have been using for assigning nodes to districts) while making it convenient/cheap to access the set of nodes in each part.

An Assignment has a parts property that is a dictionary of the form {part: <frozenset of nodes in part>}.

Parameters:
copy()[source]

Returns a copy of the assignment. Does not duplicate the frozensets of nodes, just the parts dictionary.

Return type:

Assignment

facility_assignment(part)[source]

Find the best facility center for part by minimising the maximum travel time from the candidate to any node in the part (minimax radius).

Returns:

(best_candidate, radius)

Return type:

tuple

update_flows(flow, team_flips)[source]

Update the assignment using the given Flow object.

Parameters:

  • flow (Flow) – The Flow computed from the parent partition.

  • team_flips (Dict) – Maps district IDs to updated team counts.

items()[source]

Iterate over (node, part) tuples, where node is assigned to part.

keys() → a set-like object providing a view on D's keys[source]
values() → an object providing a view on D's values[source]
to_series()[source]
Returns:

The assignment as a pandas.Series.

Return type:

pandas.Series

to_dict()[source]
Returns:

The assignment as a {node: part} dictionary.

Return type:

Dict

classmethod from_dict(assignment, graph, teams)[source]

Create an Assignment from a dictionary. This is probably the method you want to use to create a new assignment.

This also works for pandas.Series.

Parameters:

  • assignment (Dict) – dictionary mapping nodes to partition assignments

  • graph (Graph)

  • teams (Dict)

Returns:

A new instance of Assignment with the same assignments as the passed-in dictionary.

Return type:

Assignment

class falcomchain.partition.flows.Flow(node_flows, part_flows, candidate_flows)[source]

Groups the three incremental flow dictionaries computed between successive Partition steps. Avoids recomputing the full partition from scratch each step.

Variables:

  • node_flows – Maps each part to {“in”: set of nodes that joined, “out”: set that left}.

  • part_flows – {“in”: set of new district IDs, “out”: set of removed district IDs}.

  • candidate_flows – Maps each part to {“in”: set of candidate nodes that joined, “out”: set that left}.

Parameters:

  • node_flows (Dict | None)

  • part_flows (Dict)

  • candidate_flows (Dict | None)

classmethod initial(flip)[source]

Flow for the very first partition (no parent).

Return type:

Flow

classmethod from_parent(parent, new_partition, superflip, flip)[source]

Compute all three flows from parent → new_partition in one call.

Return type:

Flow

falcomchain.tree

class falcomchain.tree.tree.SpanningTree(graph, params, supergraph=False)[source]

A class representing a spanning tree with population and density information of its subtrees.

Variables:

  • graph – The underlying graph structure.

  • subsets – A dictionary mapping nodes to their subsets.

  • population – A dictionary mapping nodes to their populations.

  • total_demand – The total demand of the graph.

  • ideal_demand – The ideal demand for each district.

  • epsilon – The tolerance for demand deviation from the ideal demand within each district.

  • predecessors – A dictionary mapping nodes to their BFS predecessors.

  • successors – A dictionary mapping nodes to their BFS successors.

Parameters:
has_ideal_density(node)[source]

Checks if the subtree beneath a node has an ideal density up to tolerance ‘density’.

psi(node)[source]

Candidate-awareness score for the subtree rooted at node:

psi(T_u) = phi(u) * exp(-gamma * r(T_u))

where phi(u) is the facility indicator (number of candidates in subtree) and r(T_u) = min_{f in F_H ∩ T_u} e(f, T_u) is the demand radius — the minimum eccentricity over all facility candidates in T_u.

When gamma = 0 this reduces to phi(u) (pure feasibility score). When travel_times is None, uses 1/phi as a proxy for r(T_u).

Return type:

float

class falcomchain.tree.tree.CutParams(ideal_demand, epsilon, capacity_level, n_teams, two_sided=False, gamma=0.0, travel_times=None, psi_fn=None, c_min=1, super_psi_fn=None, recorder=None, rule='per_team', debt=0.0, min_districts_super=1)[source]

Cut parameters for a spanning tree bipartition. Separates algorithmic settings from the tree structure itself.

Variables:

  • ideal_demand – Target demand per team.

  • epsilon – Allowed relative deviation from ideal_demand.

  • capacity_level – Maximum teams per district.

  • n_teams – Total teams to allocate across the graph.

  • two_sided – If True, both sides of the cut must be balanced.

  • gamma – Tuning parameter for psi score. 0 -> psi = phi (feasibility count only).

  • travel_times – Dict (facility, node) -> travel time. None falls back to proxy.

  • psi_fn – Optional custom psi scoring function(phi, gamma, radius) -> float.

Parameters:

  • ideal_demand (float)

  • epsilon (float)

  • capacity_level (int)

  • n_teams (int)

  • two_sided (bool)

  • gamma (float)

  • travel_times (Dict | None)

  • psi_fn (Any | None)

  • c_min (int)

  • super_psi_fn (Any | None)

  • recorder (Any | None)

  • rule (str)

  • debt (float)

  • min_districts_super (int)

class falcomchain.tree.tree.Cut(node, subnodes, assigned_teams, demand, psi)

Represents one admissible cut of a spanning tree.

Fields:

node – root node of the cut subtree subnodes – frozenset of nodes on one side of the cut assigned_teams – number of doctor-nurse teams for this side demand – total demand of subnodes psi – candidate-awareness score ψ(e) = φ(u) · exp(-γ · r(T_u))

assigned_teams

Alias for field number 2

demand

Alias for field number 3

node

Alias for field number 0

psi

Alias for field number 4

subnodes

Alias for field number 1

class falcomchain.tree.tree.Flip(flips: Dict[Any, Any]=<factory>, team_flips: Dict[Any, Any]=<factory>, new_ids: frozenset = <factory>, merged_ids: frozenset = <factory>, log_proposal_ratio: float = 0.0)[source]
Parameters:
falcomchain.tree.tree.uniform_spanning_tree(graph)[source]

Builds a spanning tree chosen uniformly from the space of all spanning trees of the graph using Wilson’s algorithm (loop-erased random walk).

Parameters:

graph (nx.Graph) – Networkx Graph

Returns:

A spanning tree of the graph chosen uniformly at random.

Return type:

nx.Graph

falcomchain.tree.tree.random_spanning_tree(graph)[source]

Builds a spanning tree chosen by Kruskal’s method using random weights.

Parameters:

graph (nx.Graph) – The input graph to build the spanning tree from. Should be a Networkx Graph.

Returns:

The minimum spanning tree represented as a Networkx Graph.

Return type:

nx.Graph

falcomchain.tree.tree.bipartition_tree(graph, demand_target, epsilon, capacity_level, n_teams, two_sided, supergraph, iteration=0, density=None, max_attempts=5000, allow_pair_reselection=False, initial=False, tree_sampler=None, gamma=0.0, travel_times=None, psi_fn=None, super_psi_fn=None, recorder=None, c_min=1, rule='per_team', debt=0.0, enforce_global_balance=False, tau_global=None, d_bar_orig=None, min_districts_super=1)[source]

Finds a balanced 2-partition of a graph by drawing a spanning tree and finding an edge to cut that leaves at most an epsilon imbalance between the demands of the parts. If no valid cut exists, a new tree is drawn.

Parameters:

  • graph (Graph) – The graph to partition.

  • demand_target (int | float) – The target demand for the returned subset of nodes.

  • epsilon (float) – The allowable deviation from demand_target.

  • capacity_level (int) – Maximum teams per district.

  • n_teams (int) – Total teams for the subgraph.

  • two_sided (bool) – If True, both sides of the cut must be balanced.

  • supergraph (bool) – If True, use supergraph admissibility conditions.

  • tree_sampler – Callable(nx.Graph) -> nx.Graph that produces a spanning tree. Defaults to uniform_spanning_tree (Wilson’s algorithm).

  • gamma (float) – Candidate-awareness tuning parameter (>= 0). Default 0 (uniform).

  • travel_times – Dict (facility, node) -> travel time for psi computation.

  • psi_fn – Optional level-1 scoring function (phi, gamma, radius) -> float.

  • super_psi_fn – Optional level-2 scoring function (subnodes, teams) -> float used by find_superedge_cuts when supergraph=True. Defaults to ϕ²(T_u) = teams (paper γ=0 case). See falcomchain.markovchain.super_scoring for the paper’s Eq. 27 hub-coherence factory.

  • max_attempts – Maximum spanning tree samples before giving up.

  • allow_pair_reselection (bool) – If True, raise ReselectException instead of RuntimeError.

  • iteration (int)

  • density (float | None)

  • c_min (int)

  • rule (str)

  • debt (float)

  • enforce_global_balance (bool)

  • tau_global (float | None)

  • d_bar_orig (float | None)

  • min_districts_super (int)

Returns:

A (Cut, log_cut_ratio) tuple.

Raises:

RuntimeError – If no valid cut found after max_attempts.

Return type:

Cut

falcomchain.tree.tree.capacitated_recursive_tree(graph, n_teams, demand_target, epsilon, capacity_level, density=None, supergraph=False, assignments=None, merged_ids=None, max_id=0, iteration=0, recorder=None, super_psi_fn=None, c_min=1, max_attempts=5000, gamma=0.0, travel_times=None, psi_fn=None, rule='per_team', enforce_global_balance=False, min_districts_super=1)[source]

Recursively partitions a graph into balanced districts using bipartition_tree.

Parameters:

  • graph (Graph) – The graph to partition into len(parts) \(epsilon\)-balanced parts.

  • filtered_parts

  • n_parts

  • n_teams (int) – Total number of doctor-nurse teams for all facilities.

  • demand_target (int) – Target demand for each part of the partition.

  • column_names

  • epsilon (float) – How far (as a percentage of demand_target) from demand_target the parts of the partition can be.

  • capacity_level (int) – The maximum number of doctor-nurse teams in a facility, If it is 1, n_teams many districts are created.

  • density – Defaluts to None.

  • ids – set of ids whose districts are merged

  • assignments – Old assignments for the nodes of graph.

  • max_id – maximum district id that has been used before

  • c_min (int)

  • max_attempts (int)

  • gamma (float)

  • rule (str)

  • enforce_global_balance (bool)

  • min_districts_super (int)

Returns:

New assignments for the nodes of graph.

Return type:

dict

class falcomchain.tree.snapshot.Recorder(output_dir, record_substeps=False)[source]

Records chain iterations in a compact binary format.

The format uses delta encoding: only changed nodes are stored per step. Substep data (spanning trees, cuts) is stored in a separate file.

Parameters:

  • output_dir (str) – Directory for output files.

  • record_substeps (bool) – If True, capture tree data from bipartition calls.

write_header(graph, initial_partition, params)[source]

Write the file header, node ID table, and initial assignment. Must be called before any record_step calls.

Parameters:

  • graph – The base graph.

  • initial_partition – The initial Partition object.

  • params (Dict[str, Any]) – Chain parameters dict.

record_step(state, accepted, parent_energy=None)[source]

Record one chain iteration as a delta from the previous assignment.

Parameters:

  • state – Current ChainState after this step.

  • accepted (bool) – Whether the proposal was accepted.

  • parent_energy (float | None) – Energy of the previous state.

begin_step()[source]

Begin recording a new chain step.

begin_level(level, partition=None)[source]

Begin recording tree cuts for a level. :param level: “supergraph” or “base” :param partition: The current partition (used to compute supergraph node coordinates).

Parameters:

level (str)

record_tree_cut(tree_edges, root, cut_node, psi_chosen, psi_total, n_cuts, spanning_tree_obj=None, extracted_nodes=None)[source]

Record one Phase 3: Capacitated Tree Cut.

end_level(centers=None)[source]

Finish recording a level. Packs tree cuts into Phase 2 + Phase 4. :param centers: Dict of facility centers for this level.

record_select(supergraph, selected_superdistricts, merged_base_nodes, partition=None)[source]

Record the superdistrict selection between upper and lower levels.

record_accept_reject(proposed_state, current_state, accepted)[source]

Record the accept/reject decision.

record_substep(tree_edges, root, cut_node, psi_chosen, psi_total, n_cuts, spanning_tree_obj=None)[source]

Delegates to record_tree_cut.

close()[source]

Finalize and close all files. Updates the step count in the header.

static export_to_json(input_dir, output_dir)[source]

Read a binary chain record and export step JSON files + manifest for FalcomPlot visualization.

Parameters:

  • input_dir (str) – Directory containing chain.fcrec (and optionally .sub).

  • output_dir (str) – Directory to write manifest.json, blocks.json, step_NNNN.json.

falcomchain.markovchain

class falcomchain.markovchain.MarkovChain(proposal, constraints, accept, initial_state, total_steps, recorder=None, callbacks=None)[source]

MarkovChain is a class that creates an iterator for iterating over the states of a Markov chain run in a gerrymandering analysis context.

It allows for the generation of a sequence of partitions (states) of a political districting plan, where each partition represents a possible state in the Markov chain.

Example usage:

chain = MarkovChain(proposal, constraints, accept, initial_state, total_steps)
for state in chain:
    # Do whatever you want - print output, compute scores, ...
Parameters:
property constraints: Validator

Read_only alias for the is_valid property. Returns the constraints of the Markov chain.

Returns:

The constraints of the Markov chain.

Return type:

String

with_progress_bar()[source]

Wraps the Markov chain in a tqdm progress bar.

Useful for long-running Markov chains where you want to keep track of the progress. Requires the tqdm package to be installed.

Returns:

A tqdm-wrapped Markov chain.

class falcomchain.markovchain.state.ChainState(partition, facility, energy, log_proposal_ratio, beta, feasible, super_facility=None, energy_fn=None, super_facility_fn=None)[source]

Wraps a Partition with the MCMC context needed for the Metropolis-Hastings acceptance step.

The proposal step is responsible for setting energy, log_proposal_ratio, and feasible before returning a ChainState. beta is set once at chain initialisation and copied forward.

Variables:

  • partition – The underlying partition state.

  • energy – E(s) — access energy of this state.

  • log_proposal_ratio – log( q(s|s') / q(s'|s) ) from the proposal.

  • beta – Inverse temperature (>= 0).

  • feasible – R(s’) — hard constraint indicator.

Parameters:
classmethod initial(partition, energy, beta, energy_fn=None, super_facility_fn=None)[source]

Construct the initial ChainState at the start of the chain. The proposal ratio is 0 (log 1) and the state is always feasible. FacilityAssignment is computed eagerly for all districts.

Parameters:

  • partition (Partition) – The initial partition.

  • energy (float) – E(s_0) of the initial partition.

  • beta (float) – Inverse temperature.

  • energy_fn – Optional custom energy function(state) -> float. Defaults to compute_energy (demand-weighted travel time).

  • super_facility_fn – Optional callable (state) -> SuperFacilityAssignment that produces the level-2 facility assignment. None (default) means level-2 facilities are not computed; state.super_facility is None for the entire chain. Pass SuperFacilityAssignment.from_state to enable the default Eq. 18 minimax selector, or any custom callable.

Return type:

ChainState

next(partition, energy, log_proposal_ratio, feasible)[source]

Construct the proposed ChainState from the current one. Carries beta, energy_fn, super_facility_fn forward and incrementally updates FacilityAssignment.

Parameters:

  • partition (Partition) – Proposed partition.

  • energy (float) – E(s’) of the proposed state.

  • log_proposal_ratio (float) – log( q(s|s') / q(s'|s) ).

  • feasible (bool) – Whether s’ passes all hard constraints.

Return type:

ChainState

class falcomchain.markovchain.facility.FacilityAssignment(travel_times, demands=None)[source]

Computes and caches the best facility center and access cost for each district, given a ChainState.

The optimal center is the demand-weighted 1-median: the candidate that minimises the total demand-weighted travel time

cost(D, f) = sum_{v in D} d_v * dist(f, v)

from the facility to every node in the district. This matches the base-level term of the disaggregated hierarchical median objective (paper Eq. for the MILP benchmark) and is the optimization analogue that the chain’s facility-assignment rule (paper Section 5.4) targets.

Centers and costs are computed eagerly and cached. Only districts that changed (via flow.node_flows and flow.part_flows) are recomputed in updated().

Variables:

  • centers – Maps district ID → demand-weighted 1-median node.

  • radii – Maps district ID → 1-median access cost sum_v d_v * dist(center, v) (NOT a covering radius). The name is retained for backward compatibility of accessors.

Parameters:

  • travel_times (Dict)

  • demands (Dict | None)

classmethod from_state(state)[source]

Build a fully computed FacilityAssignment from a ChainState. All districts are evaluated eagerly.

Parameters:

state – A ChainState whose assignment has travel_times set.

Return type:

FacilityAssignment

classmethod updated(previous, state)[source]

Build a FacilityAssignment for state by copying the previous one and recomputing only the districts that changed.

Parameters:

  • previous (FacilityAssignment) – FacilityAssignment from the parent ChainState.

  • state – The proposed ChainState.

Return type:

FacilityAssignment

class falcomchain.markovchain.facility.SuperFacilityAssignment[source]

Computes level-2 (super-) facility centers for each superdistrict.

For each superdistrict D^2, the level-2 facility is selected from F^2 ∩ V(G^1[D^2]) — the super-candidates (super_candidate=1 nodes) that lie in the base-level subgraph induced by D^2’s constituent level-1 districts. Selection is delegated to a pluggable callable (see selection_fn); the default is minimax_super_selector() (Eq. 18).

Soft constraint at level 2. If a superdistrict contains no super-candidates, no level-2 facility is assigned for it — the entry is simply absent from centers and radii. The chain is not rejected. Callers can iterate state.partition.super_parts to detect superdistricts without a level-2 facility.

Variables:

  • centers – Maps superdistrict ID -> selected super-candidate node. May not contain an entry for every superdistrict (soft constraint).

  • radii – Maps superdistrict ID -> covering radius (matches the keys of centers).

classmethod from_state(state, selection_fn=None)[source]

Build a SuperFacilityAssignment from a ChainState.

Iterates state.partition.super_parts (superdistrict ID -> set of level-1 district IDs), gathers super-candidates and base nodes for each, and delegates the actual selection to selection_fn.

Parameters:

  • state – A ChainState whose partition has super_assignment populated and whose assignment.travel_times is set. The level-1 facility centers in state.facility must already be populated (they are the “spokes” the L2 facility serves).

  • selection_fn – Callable (super_id, super_candidates, base_nodes, demands, travel_times) -> (node, cost). Defaults to minimax_super_selector() (demand-weighted 1-median over base nodes).

Return type:

SuperFacilityAssignment

classmethod updated(previous, state, selection_fn=None)[source]

Build a SuperFacilityAssignment incrementally from previous.

Mirrors FacilityAssignment.updated() at level 2: copies previous’s centers and radii and recomputes only the super-districts that changed this step. Unchanged super-districts keep their cached center / radius.

Cheaper than from_state() when the partition’s superflip only touches a few super-districts (which is the common case under hierarchical_recom — exactly one super-district is merged and re-partitioned per step).

Parameters:
Return type:

SuperFacilityAssignment

falcomchain.markovchain.proposals.hierarchical_recom(state, epsilon_base, epsilon_super, demand_target, density=None, super_partitioner=<function resample_super_partition>, gamma_base=0.0, gamma_super=0.0, psi_fn=None, super_psi_fn=None, travel_times=None, c_min_base=1, c_min_super=None, c_max_super=None, min_districts_super=1, max_attempts_super=1000, rule='per_team', enforce_global_balance=False)[source]

Proposes a new ChainState via two-level hierarchical ReCom.

The upper-level (supergraph) partitioning is delegated to super_partitioner. The default resample_super_partition() samples a fresh level-2 partition each step. Pass fixed_super_partition() (or any custom callable with the same signature) for alternative behavior such as fixed superdistricts.

Once the upper level returns the chosen superdistrict’s level-1 IDs, those base nodes are re-partitioned via recursive partitioning to produce the new level-1 districts. Recording (if enabled) is driven by the Recorder attached to the chain via state._recorder.

Parameters:

  • state – The current ChainState.

  • epsilon_base (float) – Level-1 demand-balance tolerance ε¹ (paper). Used for the lower-level recursive partitioning of the chosen superdistrict.

  • epsilon_super (float) – Level-2 demand-balance tolerance ε² (paper). Used by the upper-level super_partitioner.

  • demand_target (float) – Per-team workload d̄ (paper).

  • density (float | None) – Optional density parameter.

  • super_partitioner (Callable) – Callable with signature (state, epsilon_super, demand_target, density, recorder, super_psi_fn, gamma_super) -> (super_flip, merge, super_teams, super_demand, log_super_ratio). Defaults to resample_super_partition().

  • gamma_super (float) – Inverse temperature γ² for the level-2 hub-coherence score (paper Eq. 22, 27). When > 0 and super_psi_fn is None, a hub-coherence scorer is built from state. Default 0.

  • super_psi_fn (Callable | None) – Optional precomputed level-2 scorer (subnodes, teams) -> float. Overrides the default factory built from gamma_super.

  • c_min_base (int) – Minimum level-1 capacity per district (default 1).

  • c_min_super (int | None) – Minimum level-2 capacity (number of level-1 districts per super-district). Defaults to 2 · c_min_base — the standard choice that keeps super-districts non-trivial and aligns the supergraph’s leaf demand range with the actual super-node weights (≈ c¹·w).

  • c_max_super (int | None) – Maximum level-2 capacity (paper §6.4 default: 3). Required.

  • gamma_base (float)

  • psi_fn (Callable | None)

  • travel_times (dict | None)

  • min_districts_super (int)

  • max_attempts_super (int)

  • rule (str)

  • enforce_global_balance (bool)

Returns:

The proposed ChainState.

falcomchain.markovchain.accept.always_accept(_proposed, _current)[source]

Acceptance function that accepts every proposed state unconditionally.

This is the paper’s intended acceptance rule (Section 6.3): a proposal is feasible iff every cut has ψ > 0, and feasible proposals are accepted unconditionally. Use this for ensemble sampling.

Parameters:

  • proposed – The proposed chain state.

  • current – The current chain state (unused).

  • _proposed (ChainState)

  • _current (ChainState)

Returns:

Always True.

Return type:

bool

falcomchain.markovchain.accept.boltzmann(state, parent)[source]

Boltzmann acceptance rule for energy-biased optimization.

Accepts the proposed state with probability

alpha(s -> s’) = min(1, R(s’) * exp(-beta * (E(s’) - E(s))))

where:

  • R(s') is the hard feasibility indicator → state.feasible

  • E(s') is the energy of the proposed state → state.energy

  • E(s) is the energy of the current state → parent.energy

  • beta is the inverse temperature → state.beta

Requires the user to have explicitly opted into an objective by passing energy_fn=... to ChainState.initial(). Without an energy function FalCom is a sampler — call this only when you’ve decided to optimize.

Note

This is not a true Metropolis-Hastings sampler. It omits the proposal-density ratio q(s|s')/q(s'|s) because that ratio is intractable for FalCom (paper Section 6.3): it depends on the number of admissible cuts across all spanning trees of the merged subgraph in both the current and proposed states, which is #P-hard to compute (Jerrum & Sinclair). As a result this function is a heuristic optimizer that drives the chain toward low-energy states, not a sampler from a Boltzmann distribution. For sampling with convergence guarantees, use always_accept().

Parameters:
Returns:

True if the proposal is accepted, False otherwise.

Return type:

bool

Raises:

RuntimeError – If state.energy_fn is None — this would mean Boltzmann is being called without an objective, which would silently degrade to always_accept. Set energy_fn on ChainState.initial (e.g. energy_fn=falcomchain.markovchain.energy.compute_energy).

falcomchain.markovchain.energy.compute_energy(state)[source]

Disaggregated hierarchical median energy (the FalCom optimization objective; matches the MILP benchmark objective of the experiments section):

E(s) = Σ_D Σ_{v∈D} d_v·dist(v, f¹(D)) (base-level access)

  • Σ_S Σ_{v∈V¹[S]} d_v·dist(v, f²(S)) (upper-level coordination)

where D ranges over level-1 districts with level-1 facility f¹(D), S ranges over superdistricts with level-2 facility f²(S), d_v is node demand, and dist is read from Assignment.travel_times. The two terms are separable across levels: each facility is the demand-weighted 1-median of the units it serves.

The level-2 term is included only when state.super_facility is populated (i.e. a super_facility_fn was supplied); otherwise the energy is the base-level access term alone.

Parameters:

state (ChainState) – The current chain state.

Returns:

Disaggregated median (lower is better).

Return type:

float

falcomchain.markovchain.energy.compute_energy_delta(proposed, current)[source]

Compute E(proposed) - E(current) efficiently by re-evaluating only the districts that changed (those in proposed.partition.flow.node_flows).

Parameters:

  • proposed (ChainState) – The proposed chain state.

  • current (ChainState) – The current chain state.

Returns:

Delta energy E(s’) - E(s).

Return type:

float

falcomchain.constraints

class falcomchain.constraints.Validator(constraints)[source]

A single callable for checking that a partition passes a collection of constraints. Intended to be passed as the is_valid parameter when instantiating MarkovChain.

This class is meant to be called as a function after instantiation; its return is True if all validators pass, and False if any one fails.

Example usage:

is_valid = Validator([constraint1, constraint2, constraint3])
chain = MarkovChain(proposal, is_valid, accept, initial_state, total_steps)
Variables:

constraints – List of validator functions that will check partitions.

Parameters:

constraints (List[Callable])

falcomchain.random

Isolated random number generator for reproducible chain runs.

All stochastic operations in the library use falcomchain.random.rng instead of the global random module. This ensures that external library calls (numpy, networkx, etc.) cannot perturb the chain’s random state.

Usage:

from falcomchain.random import rng, set_seed

set_seed(2025)        # deterministic from here
rng.choice([1, 2, 3]) # use rng instead of random

To reproduce a chain: call set_seed(s) before constructing the initial partition. The same seed + same library versions = identical chain.

falcomchain.random.rng: Random = <random.Random object>

Dedicated RNG instance used by all FalcomChain stochastic operations.

falcomchain.random.set_seed(seed)[source]

Seed the library’s RNG for reproducible runs.

Parameters:

seed (int) – Integer seed.

Return type:

None