Fiduccia–Mattheyses refinement (boundary variant): up to `max_passes` passes, each moving every vertex at most once in decreasing-gain order subject to the balance window, tracking the lowest-cut prefix and rolling back to it. Stops when a pass yields no improvement. Only **boundary** vertices (incident to a cut net) are seeded into the gain heap: an interior vertex has non-positive gain (moving
( lv: Level<'_>, side: &mut [u8], wmin: u64, wmax: u64, max_passes: u32, )
| 839 | } |
| 840 | |
| 841 | /// Fiduccia–Mattheyses refinement (boundary variant): up to `max_passes` passes, |
| 842 | /// each moving every vertex at most once in decreasing-gain order subject to the |
| 843 | /// balance window, tracking the lowest-cut prefix and rolling back to it. Stops |
| 844 | /// when a pass yields no improvement. |
| 845 | /// |
| 846 | /// Only **boundary** vertices (incident to a cut net) are seeded into the gain |
| 847 | /// heap: an interior vertex has non-positive gain (moving it can only newly-cut |
| 848 | /// nets), so it never improves the cut; vertices exposed to the boundary by an |
| 849 | /// applied move are added as that move's neighbors. This bounds a pass at |
| 850 | /// roughly `O(boundary + moves·degree)` rather than `O(V·degree)`, which is what |
| 851 | /// makes full refinement affordable even on the finest (≈`V`-sized) level. |
| 852 | fn fm_refine( |
| 853 | lv: Level<'_>, |
| 854 | side: &mut [u8], |
| 855 | wmin: u64, |
| 856 | wmax: u64, |
| 857 | max_passes: u32, |
| 858 | ) { |
| 859 | let n = lv.num_vertices(); |
| 860 | if n <= 1 { |
| 861 | return; |
| 862 | } |
| 863 | // Contribution of one net (counts `ca` on the vertex's side, `cb` on the |
| 864 | // other, weight `w`) to the gain of moving that vertex: `+w` if it is the last |
| 865 | // pin on its side (the move uncuts the net), `−w` if its side is full with ≥2 |
| 866 | // pins (the move newly cuts it), else 0. |
| 867 | let contrib = |ca: u32, cb: u32, w: i128| -> i128 { |
| 868 | if cb >= 1 && ca == 1 { |
| 869 | w |
| 870 | } else if cb == 0 && ca >= 2 { |
| 871 | -w |
| 872 | } else { |
| 873 | 0 |
| 874 | } |
| 875 | }; |
| 876 | // Buffers reused across passes (no per-move allocation). |
| 877 | let mut gain = vec![0i128; n]; |
| 878 | let mut queued = vec![false; n]; |
| 879 | let mut locked = vec![false; n]; |
| 880 | let mut heap: BinaryHeap<(i128, Reverse<u32>)> = BinaryHeap::new(); |
| 881 | let mut moves: Vec<usize> = Vec::new(); |
| 882 | let mut pass = 0u32; |
| 883 | loop { |
| 884 | let (mut ns, mut cut) = NetState::new(lv, side); |
| 885 | let mut side0_bw: u64 = |
| 886 | (0..n).filter(|&v| side[v] == 0).map(|v| lv.bw[v]).sum(); |
| 887 | |
| 888 | // Full gain initialization (O(pins), cheap) so the incremental neighbor |
| 889 | // updates below — which only adjust the changed net's contribution — stay |
| 890 | // exact for interior vertices that later reach the boundary. |
| 891 | for (v, g) in gain.iter_mut().enumerate() { |
| 892 | *g = fm_gain(lv, &ns, side, v); |
| 893 | } |
| 894 | heap.clear(); |
| 895 | moves.clear(); |
| 896 | queued.fill(false); |
| 897 | locked.fill(false); |
| 898 | // Seed the cut frontier only (interior vertices have non-positive gain). |