Greedy graph-growing: start from `seed` and repeatedly absorb the boundary vertex most strongly connected (by net weight) to side 0 until side 0 reaches ~half the balance weight. Remaining vertices go to side 1.
(lv: Level<'_>, total_bw: u64, seed: usize)
| 680 | // balance weight, so the total is preserved at every level). |
| 681 | let wmax = ((0.5 + epsilon) * total_bw as f64).ceil() as u64; |
| 682 | let wmin = ((0.5 - epsilon) * total_bw as f64).floor() as u64; |
| 683 | |
| 684 | let levels = coarsen(sub); |
| 685 | let coarsest = levels.last().map_or_else(|| sub.level(), |l| l.level()); |
| 686 | let side = initial_partition(coarsest, wmin, wmax); |
| 687 | uncoarsen_refine(sub, &levels, side, wmin, wmax) |
| 688 | } |
| 689 | |
| 690 | /// Greedy graph-growing: start from `seed` and repeatedly absorb the boundary |
| 691 | /// vertex most strongly connected (by net weight) to side 0 until side 0 reaches |
| 692 | /// ~half the balance weight. Remaining vertices go to side 1. |
| 693 | fn greedy_grow(lv: Level<'_>, total_bw: u64, seed: usize) -> Vec<u8> { |
| 694 | let n = lv.num_vertices(); |
| 695 | let mut side = vec![1u8; n]; |
| 696 | |
| 697 | // connection[v] = total weight of nets that already touch side 0 and include v. |
| 698 | let mut connection = vec![0u64; n]; |
| 699 | let mut in_side0 = vec![false; n]; |
| 700 | // Whether a net already contributes to side 0. A net bumps its pins exactly |
| 701 | // once (on first connection), so growth is O(Σ net_size), not O(Σ net_size²) |
| 702 | // — essential on dense graphs (and it also stops over-counting connection). |
| 703 | let mut net_touched = vec![false; lv.nets.len()]; |
| 704 | let mut heap: BinaryHeap<(u64, Reverse<u32>)> = BinaryHeap::new(); |
| 705 | let mut side0_bw = 0u64; |
| 706 | let target = total_bw / 2; |
| 707 | // Forward cursor for the disconnected-fallback path (amortized O(n) total, |
| 708 | // vs. an O(n) max-scan per fallback which is O(n²) on delta-sparse envs). |
| 709 | let mut fallback_cursor = 0usize; |
| 710 | |
| 711 | let mut add = |v: usize, |
| 712 | side: &mut [u8], |
| 713 | in_side0: &mut [bool], |
| 714 | connection: &mut [u64], |
| 715 | heap: &mut BinaryHeap<(u64, Reverse<u32>)>, |
| 716 | side0_bw: &mut u64| { |
| 717 | side[v] = 0; |
| 718 | in_side0[v] = true; |
| 719 | *side0_bw += lv.bw[v]; |
| 720 | for &ni in &lv.vnets[v] { |
| 721 | let nis = ni as usize; |
| 722 | let (w, pins) = &lv.nets[nis]; |
| 723 | // Skip hub nets, and nets already counted toward side 0. |
| 724 | if pins.len() > FM_NET_CAP || net_touched[nis] { |
| 725 | continue; |
| 726 | } |
| 727 | net_touched[nis] = true; |
| 728 | for &u in pins { |
| 729 | let u = u as usize; |
| 730 | if !in_side0[u] { |
| 731 | connection[u] += *w; |
| 732 | heap.push((connection[u], Reverse(u as u32))); |
| 733 | } |
| 734 | } |
| 735 | } |
| 736 | }; |
| 737 | |
| 738 | add( |
| 739 | seed, |
no test coverage detected