python-graphblas / graphblas-algorithms

Graph algorithms written in GraphBLAS
Apache License 2.0
76 stars 4 forks source link

Add algorithms for boundary.py and cuts.py #21

Closed eriknw closed 2 years ago

eriknw commented 2 years ago

10 more algorithms :tada:

I was looking for low-lying fruit and found these.

Although we don't yet have MultiGraph classes, I was able to get the networkx tests on multigraphs to pass. edge_boundary is the one that's probably not completely correct when operating on multi-attribute graphs (which we also don't support yet).

codecov-commenter commented 2 years ago

Codecov Report

Base: 61.01% // Head: 69.73% // Increases project coverage by +8.71% :tada:

Coverage data is based on head (cc83c31) compared to base (b56db6b). Patch coverage: 92.25% of modified lines in pull request are covered.

Additional details and impacted files ```diff @@ Coverage Diff @@ ## main #21 +/- ## ========================================== + Coverage 61.01% 69.73% +8.71% ========================================== Files 21 43 +22 Lines 1393 1784 +391 Branches 347 382 +35 ========================================== + Hits 850 1244 +394 + Misses 416 396 -20 - Partials 127 144 +17 ``` | [Impacted Files](https://codecov.io/gh/python-graphblas/graphblas-algorithms/pull/21?src=pr&el=tree&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=python-graphblas) | Coverage Δ | | |---|---|---| | [graphblas\_algorithms/algorithms/regular.py](https://codecov.io/gh/python-graphblas/graphblas-algorithms/pull/21/diff?src=pr&el=tree&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=python-graphblas#diff-Z3JhcGhibGFzX2FsZ29yaXRobXMvYWxnb3JpdGhtcy9yZWd1bGFyLnB5) | `71.42% <71.42%> (ø)` | | | [graphblas\_algorithms/algorithms/isolate.py](https://codecov.io/gh/python-graphblas/graphblas-algorithms/pull/21/diff?src=pr&el=tree&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=python-graphblas#diff-Z3JhcGhibGFzX2FsZ29yaXRobXMvYWxnb3JpdGhtcy9pc29sYXRlLnB5) | `80.64% <80.64%> (ø)` | | | [graphblas\_algorithms/classes/\_utils.py](https://codecov.io/gh/python-graphblas/graphblas-algorithms/pull/21/diff?src=pr&el=tree&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=python-graphblas#diff-Z3JhcGhibGFzX2FsZ29yaXRobXMvY2xhc3Nlcy9fdXRpbHMucHk=) | `73.72% <83.33%> (+2.01%)` | :arrow_up: | | [graphblas\_algorithms/algorithms/smetric.py](https://codecov.io/gh/python-graphblas/graphblas-algorithms/pull/21/diff?src=pr&el=tree&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=python-graphblas#diff-Z3JhcGhibGFzX2FsZ29yaXRobXMvYWxnb3JpdGhtcy9zbWV0cmljLnB5) | `85.71% <85.71%> (ø)` | | | [graphblas\_algorithms/algorithms/structuralholes.py](https://codecov.io/gh/python-graphblas/graphblas-algorithms/pull/21/diff?src=pr&el=tree&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=python-graphblas#diff-Z3JhcGhibGFzX2FsZ29yaXRobXMvYWxnb3JpdGhtcy9zdHJ1Y3R1cmFsaG9sZXMucHk=) | `85.71% <85.71%> (ø)` | | | [graphblas\_algorithms/conftest.py](https://codecov.io/gh/python-graphblas/graphblas-algorithms/pull/21/diff?src=pr&el=tree&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=python-graphblas#diff-Z3JhcGhibGFzX2FsZ29yaXRobXMvY29uZnRlc3QucHk=) | `92.50% <85.71%> (-3.66%)` | :arrow_down: | | [graphblas\_algorithms/algorithms/simple\_paths.py](https://codecov.io/gh/python-graphblas/graphblas-algorithms/pull/21/diff?src=pr&el=tree&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=python-graphblas#diff-Z3JhcGhibGFzX2FsZ29yaXRobXMvYWxnb3JpdGhtcy9zaW1wbGVfcGF0aHMucHk=) | `90.90% <90.90%> (ø)` | | | [graphblas\_algorithms/algorithms/dag.py](https://codecov.io/gh/python-graphblas/graphblas-algorithms/pull/21/diff?src=pr&el=tree&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=python-graphblas#diff-Z3JhcGhibGFzX2FsZ29yaXRobXMvYWxnb3JpdGhtcy9kYWcucHk=) | `95.23% <95.23%> (ø)` | | | [graphblas\_algorithms/algorithms/boundary.py](https://codecov.io/gh/python-graphblas/graphblas-algorithms/pull/21/diff?src=pr&el=tree&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=python-graphblas#diff-Z3JhcGhibGFzX2FsZ29yaXRobXMvYWxnb3JpdGhtcy9ib3VuZGFyeS5weQ==) | `95.91% <95.91%> (ø)` | | | [graphblas\_algorithms/algorithms/cuts.py](https://codecov.io/gh/python-graphblas/graphblas-algorithms/pull/21/diff?src=pr&el=tree&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=python-graphblas#diff-Z3JhcGhibGFzX2FsZ29yaXRobXMvYWxnb3JpdGhtcy9jdXRzLnB5) | `97.77% <97.77%> (ø)` | | | ... and [24 more](https://codecov.io/gh/python-graphblas/graphblas-algorithms/pull/21/diff?src=pr&el=tree-more&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=python-graphblas) | | Help us with your feedback. Take ten seconds to tell us [how you rate us](https://about.codecov.io/nps?utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=python-graphblas). Have a feature suggestion? [Share it here.](https://app.codecov.io/gh/feedback/?utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=python-graphblas)

:umbrella: View full report at Codecov.
:loudspeaker: Do you have feedback about the report comment? Let us know in this issue.

eriknw commented 2 years ago

I found a few more "easy" algorithms while looking through NetworkX. This PR now adds 25 new algorithms (CC @MridulS):

  1. edge_boundary
  2. node_boundary
  3. cut_size
  4. volume
  5. normalized_cut_size
  6. conductance
  7. edge_expansion
  8. mixing_expansion
  9. node_expansion
  10. boundary_expansion
  11. descendants
  12. ancestors
  13. is_dominating_set
  14. is_isolate
  15. isolates
  16. number_of_isolates
  17. is_regular
  18. is_k_regular
  19. is_simple_path
  20. s_metric
  21. mutual_weight
  22. is_tournament
  23. score_sequence
  24. tournament_matrix
  25. is_triad

There are still lots of easy/doable algorithms left.

Hopefully adding these doesn't slow down refactoring too much--I think refactoring (as needed) will be straightforward.