rustworkx icon indicating copy to clipboard operation
rustworkx copied to clipboard

Add planar layout to rustworkx

Open enavarro51 opened this issue 2 years ago • 4 comments

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

enavarro51 avatar Jul 26 '22 21:07 enavarro51

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 Coverage Status
Change from base Build 2691937771: -7.6%
Covered Lines: 12364
Relevant Lines: 13812

💛 - Coveralls

coveralls avatar Jul 27 '22 19:07 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 Coverage Status
Change from base Build 2905042897: -2.3%
Covered Lines: 13248
Relevant Lines: 13974

💛 - Coveralls

coveralls avatar Aug 17 '22 16:08 coveralls