rustworkx
rustworkx copied to clipboard
Qiskit
Implement biparition_graph_mst and bipartition_tree functions
Note: this is a followup from email correspondence that @mtreinish and I had a few months ago. This is a draft PR, so feedback is welcome and it's not ready for merging (yet). It's fairly non-performant (but enough to beat Python/networkx solidly).
This function takes in a graph with population assigned to each node and draws a minimum spanning tree and finds a cut edge that splits the tree into two partitions that have total populations within some epsilon.
To explain the motivation behind this PR, this function is the main workhorse behind the ReCom algorithm detailed in this paper, which has been used in many litigation and civil rights projects to challenge racial and partisan gerrymandered maps and determine VRA compliance (see the recent cases in Alabama, North Carolina, Pennsylvania, etc.). I'm working on a rewrite of MGGG's main gerrymandering analysis software/engine (GerryChain, written in Python) and have achieved a ~15x speedup by naively rewriting the core graph operations in retworkx.
You can still see my messy debugging, but the rough idea is here.
Pull Request Test Coverage Report for Build 2402224991
- 94 of 96 (97.92%) changed or added relevant lines in 2 files are covered.
- 1 unchanged line in 1 file lost coverage.
- Overall coverage decreased (-0.002%) to 97.159%
| Changes Missing Coverage | Covered Lines | Changed/Added Lines | % |
|---|---|---|---|
| src/tree.rs | 92 | 94 | 97.87% |
| <!-- | Total: | 94 | 96 |
| Files with Coverage Reduction | New Missed Lines | % |
|---|---|---|
| src/shortest_path/all_pairs_dijkstra.rs | 1 | 98.54% |
| <!-- | Total: | 1 |
| Totals | |
|---|---|
| Change from base Build 2373810364: | -0.002% |
| Covered Lines: | 12277 |
| Relevant Lines: | 12636 |
💛 - Coveralls
@mtreinish I just gave this a rebase and cleaned up the code a bit -- should be ready for your review. Let me know what you think!
@IvanIsCoding @mtreinish Ok, I've added tests, made a release note with reno, and added a new entry of the function in the docs. Is there anything else you'd like me to do?
@mtreinish @IvanIsCoding I think I addressed all of the feedback you two gave (thanks, by the way!). Let me know if I should re-open any of the comments or address any other concerns/feedback you have.
FYI, I just rebased this off main since this PR appeared to be out of date from main.