pyfracval.cca.matching
======================

.. py:module:: pyfracval.cca.matching

.. autoapi-nested-parse::

   Matching-based alternatives to `_generate_pairs()`'s greedy first-fit.

   docs/source/pairing_frustration.md diagnosed the actual bottleneck in
   hard-regime CCA sticking: 97.4% of failures had a valid alternative
   pairing available in the same cluster pool that greedy first-fit never
   considered, because it commits to the first feasible partner it finds per
   cluster and never looks back. These functions replace that first-fit
   choice with an exact maximum-cardinality matching over the same cheap
   gamma-feasibility graph `_generate_pairs()` already computes - not the
   expensive "actually attempt sticking" graph
   `benchmarks/pairing_frustration_probe.py` builds for offline diagnosis
   (3 retries per edge), which would be far too slow and RNG-perturbing to
   run on the hot path.

   Pure functions, no ``self`` - unit-testable directly and reusable from
   both `_generate_pairs()` and any future caller.





Module Contents
---------------

.. py:function:: build_feasibility_graph(cluster_props, gamma_fn, pairing_factor)

   Cheap gamma-feasibility adjacency over non-empty cluster indices.

   Factors out the same strict/relaxed gamma gate `_generate_pairs()`'s
   greedy loop computes per pair (``gamma_real and gamma_pc < sum_rmax *
   pairing_factor``), so both the greedy and matching code paths share
   one feasibility test rather than duplicating it. Does not distinguish
   strict vs. relaxed matches the way the greedy path's logging does -
   both are simply "feasible" edges here.

   :param cluster_props: cluster_idx -> (mass, rg, cm, r_max, radii), the same cache shape
                         `_generate_pairs()` already builds. Clusters with mass 0.0 (empty)
                         are excluded from the returned graph's nodes.
   :type cluster_props: dict[int, tuple]
   :param gamma_fn: Bound `self._calculate_cca_gamma` - takes two (m, rg, cm, r_max,
                    radii)-shaped props tuples, returns (gamma_real, gamma_pc).
   :type gamma_fn: callable
   :param pairing_factor: The relaxation factor (e.g. 1.10) applied to sum_rmax.
   :type pairing_factor: float


.. py:function:: max_cardinality_matching(adj, nodes)

   Exact maximum-cardinality matching via memoized brute-force DP.

   Generalizes `benchmarks/pairing_frustration_probe.py::_max_matching_size`
   (which only counts a matching's size) into one that reconstructs the
   actual assignment. Round pool sizes are small - bounded by roughly
   ``1 / n_subcl_percentage``, empirically <=16 per the probe's own
   numbers - so ``2**n`` memoized states with O(n) work each is cheap
   relative to per-pair sticking cost; a real Blossom-algorithm
   implementation (O(n^3), handles arbitrary graphs including odd
   cycles a greedy DP can't) is unnecessary complexity at this scale.
   Do not "upgrade" this reflexively if round pool sizes ever grow
   significantly (e.g. a much smaller ``n_subcl_percentage`` default).

   Returns a list of (i, j) matched pairs; unmatched nodes are simply
   absent from the result (the odd-cluster-out / pass-through case is
   handled by the caller, same as the greedy path).


.. py:function:: leaf_weighted_matching(adj, nodes, edge_weight_fn)

   Maximum-cardinality matching, with total edge weight as a tiebreaker
   among cardinality-optimal solutions.

   Cardinality is optimized first rather than weight outright: sacrificing
   a matchable pair to chase a higher-weight edge elsewhere would directly
   contradict the diagnosed problem (rounds failing because too few
   clusters get paired at all, not because of which specific clusters get
   paired). Implemented by comparing ``(size, weight)`` tuples
   lexicographically at each DP step - Python's native tuple comparison
   already does exactly "maximize the first component, use the second as
   a tiebreaker," so this needs no separate two-pass DP.

   ``edge_weight_fn(i, j)`` should return the caller's per-edge weight
   (e.g. from a leaf-class classification of the cluster pair).


.. py:function:: cluster_leaf_fraction(leaf_mask)

   Fraction of leaf-classified (contact-degree <= 1) particles in a
   cluster, given its `_CandidatesMixin._leaf_mask_for_cluster` output.


.. py:function:: cluster_pair_leaf_class(leaf_fraction_i, leaf_fraction_j, threshold = 0.5)

   Classify an edge (i, j) as "LL"/"LN"/"NN" from each cluster's own
   leaf-fraction (mean of its per-particle leaf mask), using the same
   three-bucket structure as `candidates.py`'s per-particle
   `_candidate_leaf_class` for consistency - but operating on cluster
   pairs, not individual particles, which needed a new aggregation rule
   since none existed. The threshold (default 0.5, i.e. "more than half
   of this cluster's particles are surface-exposed leaves") is an
   unvalidated free parameter - treat it as such rather than asserting
   it's correct; see docs/source/matching_pairing.md for whether
   leaf-weighting shows any effect at all before tuning it further.