rustworkx
rustworkx copied to clipboard
Add planar layout to rustworkx
This draft PR adds the planar layout to the graph layout methods. This code incorporates and modifies the code from the open PR #475 for the Left/Right Planarity Test. It then creates the embedding that is ultimately converted to position coordinates for displaying the graph layout.
It follows the algorithms from Ulrik Brandes: The Left-Right Planarity Test 2009 http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.217.9208 and M. Chrobak and T.H. Payne: A Linear-time Algorithm for Drawing a Planar Graph on a Grid 1989 http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.51.6677 as well as the python code used in the networkx version of planar layout.
Remaining items include
- [x] Additional error checking
- [x] Docs
- [x] More tests
Pull Request Test Coverage Report for Build 2749795804
- 1 of 1082 (0.09%) changed or added relevant lines in 5 files are covered.
- No unchanged relevant lines lost coverage.
- Overall coverage decreased (-7.6%) to 89.516%
Changes Missing Coverage | Covered Lines | Changed/Added Lines | % |
---|---|---|---|
src/layout/mod.rs | 0 | 8 | 0.0% |
src/layout/planar.rs | 0 | 44 | 0.0% |
retworkx-core/src/planar/lr_planar.rs | 0 | 445 | 0.0% |
src/layout/embedding.rs | 0 | 584 | 0.0% |
<!-- | Total: | 1 | 1082 |
Totals | |
---|---|
Change from base Build 2691937771: | -7.6% |
Covered Lines: | 12364 |
Relevant Lines: | 13812 |
💛 - Coveralls
Pull Request Test Coverage Report for Build 2905132284
- 750 of 1103 (68.0%) changed or added relevant lines in 5 files are covered.
- No unchanged relevant lines lost coverage.
- Overall coverage decreased (-2.3%) to 94.805%
Changes Missing Coverage | Covered Lines | Changed/Added Lines | % |
---|---|---|---|
src/layout/planar.rs | 38 | 44 | 86.36% |
src/layout/embedding.rs | 481 | 581 | 82.79% |
rustworkx-core/src/planar/lr_planar.rs | 220 | 467 | 47.11% |
<!-- | Total: | 750 | 1103 |
Totals | |
---|---|
Change from base Build 2905042897: | -2.3% |
Covered Lines: | 13248 |
Relevant Lines: | 13974 |