search

python-graphblas / graphblas-algorithms

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

Add floyd_warshall_predecessor_and_distance #43

Closed eriknw closed 1 year ago

eriknw commented 1 year ago

This follows up on #42 to also compute predecessors with floyd_warshall.

CC @jim22k @SultanOrazbayev @LuisFelipeRamos

I came up with the algorithm for computing predecessors via trial and error--i.e., a lot of guessing :). The outcome seems reasonable/plausible, and it passes tests.

As the comments indicate, by adding the use of Mask, we increase memory usage, but it computes faster. I don't have a great feel for when we should trade memory for speed or vice versa. So, let's go with the simple option, which happens to be the faster option.

Also, instead of converting the output Matrix to a dict of dicts, I convert it to a new object NodeNodeMap that behaves similarly and is backed by the matrix. I updated other uses of fill_value with NodeMap to keep the output sparse (i.e., don't fill with fill_value).

I wonder how we can/should optimize for undirected graphs (i.e., symmetric adjacency matrix). Perhaps we can only compute the lower or upper triangular portion of the results while iterating.

Our original floyd_warshall was nice, because it looked a lot more like a typical floyd-warshall implementation. The new version that can also compute predecessors is nice b/c it's more capable without duplicating a bunch of code, but less nice b/c it's more complicated. Please let me know if anything in floyd_warshall_predecessor_and_distance can be more clear.

codecov-commenter commented 1 year ago

Codecov Report

Base: 72.25% // Head: 69.57% // Decreases project coverage by -2.69% :warning:

Coverage data is based on head (9388982) compared to base (6dd93bd). Patch coverage: 32.03% of modified lines in pull request are covered.

:mega: This organization is not using Codecov’s GitHub App Integration. We recommend you install it so Codecov can continue to function properly for your repositories. Learn more

Additional details and impacted files ```diff @@ Coverage Diff @@ ## main #43 +/- ## ========================================== - Coverage 72.25% 69.57% -2.69% ========================================== Files 72 72 Lines 2617 2777 +160 Branches 479 516 +37 ========================================== + Hits 1891 1932 +41 - Misses 557 675 +118 - Partials 169 170 +1 ``` | [Impacted Files](https://codecov.io/gh/python-graphblas/graphblas-algorithms/pull/43?src=pr&el=tree&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=python-graphblas) | Coverage Δ | | |---|---|---| | [...blas\_algorithms/algorithms/shortest\_paths/dense.py](https://codecov.io/gh/python-graphblas/graphblas-algorithms/pull/43?src=pr&el=tree&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=python-graphblas#diff-Z3JhcGhibGFzX2FsZ29yaXRobXMvYWxnb3JpdGhtcy9zaG9ydGVzdF9wYXRocy9kZW5zZS5weQ==) | `7.93% <8.51%> (-8.20%)` | :arrow_down: | | [graphblas\_algorithms/classes/nodemap.py](https://codecov.io/gh/python-graphblas/graphblas-algorithms/pull/43?src=pr&el=tree&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=python-graphblas#diff-Z3JhcGhibGFzX2FsZ29yaXRobXMvY2xhc3Nlcy9ub2RlbWFwLnB5) | `42.12% <28.44%> (-7.61%)` | :arrow_down: | | [graphblas\_algorithms/nxapi/shortest\_paths/dense.py](https://codecov.io/gh/python-graphblas/graphblas-algorithms/pull/43?src=pr&el=tree&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=python-graphblas#diff-Z3JhcGhibGFzX2FsZ29yaXRobXMvbnhhcGkvc2hvcnRlc3RfcGF0aHMvZGVuc2UucHk=) | `45.45% <33.33%> (-11.69%)` | :arrow_down: | | [graphblas\_algorithms/classes/\_utils.py](https://codecov.io/gh/python-graphblas/graphblas-algorithms/pull/43?src=pr&el=tree&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=python-graphblas#diff-Z3JhcGhibGFzX2FsZ29yaXRobXMvY2xhc3Nlcy9fdXRpbHMucHk=) | `63.63% <56.52%> (-1.52%)` | :arrow_down: | | [graphblas\_algorithms/classes/digraph.py](https://codecov.io/gh/python-graphblas/graphblas-algorithms/pull/43?src=pr&el=tree&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=python-graphblas#diff-Z3JhcGhibGFzX2FsZ29yaXRobXMvY2xhc3Nlcy9kaWdyYXBoLnB5) | `40.00% <100.00%> (+0.29%)` | :arrow_up: | | [graphblas\_algorithms/classes/graph.py](https://codecov.io/gh/python-graphblas/graphblas-algorithms/pull/43?src=pr&el=tree&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=python-graphblas#diff-Z3JhcGhibGFzX2FsZ29yaXRobXMvY2xhc3Nlcy9ncmFwaC5weQ==) | `59.54% <100.00%> (+0.37%)` | :arrow_up: | | [graphblas\_algorithms/interface.py](https://codecov.io/gh/python-graphblas/graphblas-algorithms/pull/43?src=pr&el=tree&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=python-graphblas#diff-Z3JhcGhibGFzX2FsZ29yaXRobXMvaW50ZXJmYWNlLnB5) | `97.50% <100.00%> (+0.03%)` | :arrow_up: | | [...raphblas\_algorithms/nxapi/centrality/degree\_alg.py](https://codecov.io/gh/python-graphblas/graphblas-algorithms/pull/43?src=pr&el=tree&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=python-graphblas#diff-Z3JhcGhibGFzX2FsZ29yaXRobXMvbnhhcGkvY2VudHJhbGl0eS9kZWdyZWVfYWxnLnB5) | `100.00% <100.00%> (ø)` | | | [graphblas\_algorithms/nxapi/cluster.py](https://codecov.io/gh/python-graphblas/graphblas-algorithms/pull/43?src=pr&el=tree&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=python-graphblas#diff-Z3JhcGhibGFzX2FsZ29yaXRobXMvbnhhcGkvY2x1c3Rlci5weQ==) | `77.55% <100.00%> (-0.67%)` | :arrow_down: | | [...aphblas\_algorithms/nxapi/link\_analysis/hits\_alg.py](https://codecov.io/gh/python-graphblas/graphblas-algorithms/pull/43?src=pr&el=tree&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=python-graphblas#diff-Z3JhcGhibGFzX2FsZ29yaXRobXMvbnhhcGkvbGlua19hbmFseXNpcy9oaXRzX2FsZy5weQ==) | `100.00% <100.00%> (ø)` | | | ... and [2 more](https://codecov.io/gh/python-graphblas/graphblas-algorithms/pull/43?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 1 year ago

I wonder how we can/should optimize for undirected graphs (i.e., symmetric adjacency matrix). Perhaps we can only compute the lower or upper triangular portion of the results while iterating.

Implemented (via upper triangles)! This wasn't too hard or invasive to do, but it does make the implementation a little more complicated. We still symmetrize the results at the end--maybe someday we'll be able to avoid this step.