Heavy-edge matching pass: pair each still-unmatched vertex (visited in id order) with the unmatched neighbor it co-occurs with in the heaviest small nets, subject to the cluster-weight cap. A vertex with no such neighbor (delta-sparse, or only in hub nets) is instead paired with the next unmatched vertex — a cut-neutral merge (they share no tracked net) that keeps the graph shrinking ~2× per pass
(lv: Level<'_>, max_cluster: u64)
| 1051 | levels |
| 1052 | } |
| 1053 | |
| 1054 | /// Heavy-edge matching pass: pair each still-unmatched vertex (visited in id |
| 1055 | /// order) with the unmatched neighbor it co-occurs with in the heaviest small |
| 1056 | /// nets, subject to the cluster-weight cap. A vertex with no such neighbor |
| 1057 | /// (delta-sparse, or only in hub nets) is instead paired with the next |
| 1058 | /// unmatched vertex — a cut-neutral merge (they share no tracked net) that keeps |
| 1059 | /// the graph shrinking ~2× per pass so coarsening reaches [`COARSEST_TARGET`] |
| 1060 | /// instead of stalling far above it (which would make the initial partition |
| 1061 | /// expensive). Returns `(super_id, num_super)` where `super_id[v]` is `v`'s |
| 1062 | /// supervertex in the next-coarser level. Deterministic — ties break to lowest |
| 1063 | /// id. |
| 1064 | fn match_vertices(lv: Level<'_>, max_cluster: u64) -> (Vec<u32>, usize) { |
| 1065 | let n = lv.num_vertices(); |
| 1066 | let mut super_id = vec![u32::MAX; n]; |
| 1067 | let mut next: u32 = 0; |
| 1068 | // Dense score accumulator, reset per vertex via the `touched` list. |
| 1069 | let mut score = vec![0u64; n]; |
| 1070 | let mut touched: Vec<u32> = Vec::new(); |
| 1071 | // Forward cursor over still-unmatched vertices for the fallback pairing |
| 1072 | // (advances monotonically → amortized O(n) over the whole pass). |
| 1073 | let mut fb = 0usize; |
| 1074 | for v in 0..n { |
| 1075 | if super_id[v] != u32::MAX { |
| 1076 | continue; // already claimed as an earlier vertex's partner |
| 1077 | } |
| 1078 | for &ni in &lv.vnets[v] { |
| 1079 | let (w, pins) = &lv.nets[ni as usize]; |
| 1080 | let deg = pins.len(); |
| 1081 | if !(2..=MATCH_NET_CAP).contains(°) { |
| 1082 | continue; // singleton or hub: no clustering signal worth scanning |
| 1083 | } |
| 1084 | let contrib = w / (deg as u64 - 1); |
| 1085 | if contrib == 0 { |
| 1086 | continue; |
| 1087 | } |
| 1088 | for &u in pins { |
| 1089 | let u = u as usize; |
| 1090 | if u == v || super_id[u] != u32::MAX { |
| 1091 | continue; // self, or already-matched vertex |
| 1092 | } |
| 1093 | if score[u] == 0 { |
| 1094 | touched.push(u as u32); |
| 1095 | } |
| 1096 | score[u] = score[u].saturating_add(contrib); |
| 1097 | } |
| 1098 | } |
| 1099 | // Pick the best-scoring partner that fits the cluster-weight cap. The |
| 1100 | // explicit `u < best_u` tie-break makes the result independent of the |
| 1101 | // (net/pin) iteration order. |
| 1102 | let mut best_u = usize::MAX; |
| 1103 | let mut best_score = 0u64; |
| 1104 | for &ut in &touched { |
| 1105 | let u = ut as usize; |
| 1106 | let s = score[u]; |
| 1107 | let fits = lv.bw[v].saturating_add(lv.bw[u]) <= max_cluster; |
| 1108 | if fits && (s > best_score || (s == best_score && u < best_u)) { |
| 1109 | best_score = s; |
| 1110 | best_u = u; |