QMETIS¶

Python interface to Asunder’s bundled QMETIS native library.

exception asunder.load_balancing.algorithms.qmetis.QMETISApproximationWarning¶

Bases: UserWarning

Warn that QMETIS candidate generation omits unsupported graph data.

asunder.load_balancing.algorithms.qmetis._native_library_name()¶

Return the bundled QMETIS filename for the running operating system.

Returns:: libqmetis.so on Linux, qmetis.dll on Windows, or libqmetis.dylib on macOS.
Return type:: str
Raises:: RuntimeError – If the running operating system has no supported QMETIS wheel.

asunder.load_balancing.algorithms.qmetis._bundle_metadata()¶

Read metadata describing the QMETIS binary staged in the wheel.

Returns:: Parsed bundle metadata, or an empty dictionary when running from a source installation without a staged native library.
Return type:: dict[str, Any]

asunder.load_balancing.algorithms.qmetis.bundled_qmetis_release()¶

Return the release tag recorded for the bundled QMETIS binary.

Returns:: Immutable QMETIS release tag, or None when no bundle metadata is present.
Return type:: str or None

asunder.load_balancing.algorithms.qmetis._import_qmetis()¶

Import and cache the Python wrapper against Asunder’s QMETIS library.

The loader configures the wrapper’s library path and integer/real ABI widths before importing metis.

Returns:

Imported metis wrapper bound to the bundled QMETIS binary.

Return type:

module

Raises:

ImportError – If the platform wheel has no native binary or its ABI metadata does not match this loader.
RuntimeError – If metis was already imported against another native library.

asunder.load_balancing.algorithms.qmetis.quantize_metis_weights(weights, *, relative_resolution=1e-07, safe_total=1125899906842624)¶

Quantize loop-free QMETIS edge weights within an idx_t budget.

Already integer-valued weights are preserved when their directed total is within safe_total. Otherwise, the scale preserves approximately relative_resolution of the largest edge while respecting that budget. The released idx64-real32 ABI motivates keeping the total well inside signed 64-bit range and double’s exact-integer range.

Parameters:

weights (numpy.ndarray) – Square, finite, nonnegative edge-weight matrix. Asymmetric entries are averaged. Nonzero diagonal entries are removed because the QMETIS adapter cannot represent self-loops or contraction-generated internal mass.
relative_resolution (float, default=1e-7) – Target resolution relative to the largest positive off-diagonal edge.
safe_total (int, default=2**50) – Maximum sum of the directed quantized adjacency weights.

Return type:

tuple[ndarray, float]

Returns:

quantized (numpy.ndarray) – Symmetric int64 matrix with a zero diagonal.
scale (float) – Multiplicative scale applied before rounding.

Warns:

QMETISApproximationWarning – If a nonzero diagonal is discarded. For contracted graphs this means candidate generation is approximate, although callers can still rescore the candidate with the exact objective.

Raises:

ValueError – If the matrix, resolution, or safety budget is invalid; if no positive off-diagonal edge remains; or if quantization loses excessive mass.
OverflowError – If an individual edge or accumulated adjacency exceeds its integer safety limit.

asunder.load_balancing.algorithms.qmetis._integer_weight_graph(adjacency)¶

Build a loop-free NetworkX graph from an integer adjacency matrix.

Parameters:: adjacency (numpy.ndarray) – Square integer adjacency matrix. Only nonzero upper-triangular entries are emitted as undirected edges.
Returns:: Graph containing every matrix row as a node and no self-loops.
Return type:: networkx.Graph

asunder.load_balancing.algorithms.qmetis.to_stable_weighted_adjlist(H, edge_weight_attr=None, node_weight_attr=None)¶

Convert a graph to the deterministic adjacency format used by QMETIS.

Parameters:

H (networkx.Graph) – Graph whose node insertion order defines the integer node mapping.
edge_weight_attr (str or None) – Edge attribute to emit as an integer weight. If None, emit unweighted neighbor indices.
node_weight_attr (str, sequence of str, or None) – One node-balance attribute or multiple constraint attributes.

Returns:

nodes (list) – Nodes in the stable order used by the adjacency representation.
adjacency (list[list]) – Neighbor indices, optionally paired with integer edge weights.
node_weights (list or None) – Integer node weights in matching order, or None.

asunder.load_balancing.algorithms.qmetis._validate_integer_weights(G, node_weight_attr, edge_weight_attr)¶

Validate integer node and edge weights before calling QMETIS.

Parameters:

G (networkx.Graph) – Graph containing the attributes to validate.
node_weight_attr (str, sequence of str, or None) – Node attributes interpreted as balance weights.
edge_weight_attr (str or None) – Edge attribute interpreted as the QMETIS edge weight.

Raises:

ValueError – If a selected weight is negative or not an integer.

Return type:

None

asunder.load_balancing.algorithms.qmetis._epsilon_to_ubvec(balance_epsilon, node_weight_attr)¶

Translate imbalance epsilon values into QMETIS ubvec factors.

Parameters:

balance_epsilon (float, sequence of float, or None) – Nonnegative relative imbalance tolerance. 0 requests an upper factor of exactly 1.
node_weight_attr (str, sequence of str, or None) – Node-weight constraints used to validate a multi-constraint vector.

Returns:

QMETIS upper-balance factors 1 + epsilon, or None.

Return type:

list[float] or None

Raises:

ValueError – If an epsilon is negative or its vector length does not match the number of node-weight constraints.

asunder.load_balancing.algorithms.qmetis.qmetis_load_balanced_partition(G, nparts, balance_epsilon=0.03, node_weight_attr=None, edge_weight_attr=None, recursive=False, contig=False, seed=None, **metis_options)¶

Partition an integer-weighted NetworkX graph with bundled QMETIS.

Parameters:

G (networkx.Graph) – Loop-free graph to partition.
nparts (int) – Requested number of nonempty parts.
balance_epsilon (float, sequence of float, or None) – Relative upper imbalance tolerance for each balance constraint.
node_weight_attr (str, sequence of str, or None) – Node attributes used only for QMETIS load-balancing constraints.
edge_weight_attr (str or None) – Integer edge-weight attribute used by the modularity objective.
recursive (bool, default=False) – Use recursive partitioning instead of direct k-way partitioning.
contig (bool, default=False) – Request contiguous parts from QMETIS.
seed (int or None) – QMETIS random seed.
**metis_options (Any) – Additional options accepted by metis.part_graph().

Returns:

Native objective, part IDs, node-to-part mapping, grouped nodes, and the effective upper-balance vector.

Return type:

dict[str, Any]

Raises:

ValueError – If the requested part count or graph weights are invalid.
ImportError – If the installed package has no compatible QMETIS binary.

asunder.load_balancing.algorithms.qmetis.run_qmetis(modified_A, K, balance_epsilon=None, node_weight_attr=None, edge_weight_attr='weight', seed=None, relative_resolution=1e-07, safe_total=1125899906842624, **metis_options)¶

Partition a nonnegative matrix using bundled modularity QMETIS.

Parameters:

modified_A (numpy.ndarray) – Square edge-weight matrix supplied to the QMETIS heuristic. Nonzero diagonal entries are discarded with QMETISApproximationWarning.
K (int) – Number of requested parts.
balance_epsilon (float, sequence of float, or None) – Relative upper imbalance tolerance.
node_weight_attr (str, sequence of str, or None) – Optional node-balance attributes.
edge_weight_attr (str or None, default="weight") – Integer graph edge attribute passed to QMETIS.
seed (int or None) – QMETIS random seed.
relative_resolution (float, default=1e-7) – Relative precision target used during integer quantization.
safe_total (int, default=2**50) – Maximum directed adjacency sum after quantization.
**metis_options (Any) – Additional options forwarded to QMETIS.

Return type:

tuple[ndarray, float]

Returns:

partition (numpy.ndarray) – Binary co-association matrix for the generated partition.
modularity (float) – Native QMETIS modularity after undoing its fixed return-value scale.

Warns:

QMETISApproximationWarning – If nonzero diagonal weights are omitted.