- Notifications
You must be signed in to change notification settings - Fork5
Add floyd_warshall_predecessor_and_distance#43
New issue
Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.
By clicking “Sign up for GitHub”, you agree to ourterms of service andprivacy statement. We’ll occasionally send you account related emails.
Already on GitHub?Sign in to your account
Add floyd_warshall_predecessor_and_distance#43
Uh oh!
There was an error while loading.Please reload this page.
Conversation
codecov-commenter commentedFeb 7, 2023 • edited
Loading Uh oh!
There was an error while loading.Please reload this page.
edited
Uh oh!
There was an error while loading.Please reload this page.
Codecov ReportBase:72.25% // Head:69.57% // Decreases project coverage by
📣 This organization is not using Codecov’sGitHub App Integration. We recommend you install it so Codecov can continue to function properly for your repositories.Learn more Additional details and impacted files@@ 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
Help us with your feedback. Take ten seconds to tell ushow you rate us. Have a feature suggestion?Share it here. ☔ View full report at Codecov. |
| ifis_directed: | ||
| Mask<<indexunary.offdiag(Outer) | ||
| else: | ||
| Mask<<indexunary.triu(Outer,1) | ||
| Mask(binary.second)<<binary.lt(Outer&D) | ||
| Outer(Mask.V,replace)<<Outer |
There was a problem hiding this comment.
Choose a reason for hiding this comment
The reason will be displayed to describe this comment to others.Learn more.
An alternative is
Mask<<binary.ge(Outer&D)ifis_directed:Outer(~Mask.V,replace)<<select.offdiag(Outer)else:Outer(~Mask.V,replace)<<select.triu(Outer,1)
which may be preferred, because this keepsMask smaller. However, I think complemented masks withreplace is potentially confusing.
eriknw commentedFeb 7, 2023
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. |
| ifnotcompute_predecessors: | ||
| # It is faster (approx 10%-30%) to use a mask as is done below when computing | ||
| # predecessors, but we choose to use less memory here by not using a mask. | ||
| ifis_directed: | ||
| D(binary.min)<<select.offdiag(Outer) | ||
| else: | ||
| D(binary.min)<<select.triu(Outer,1) |
There was a problem hiding this comment.
Choose a reason for hiding this comment
The reason will be displayed to describe this comment to others.Learn more.
I added the core of the original implementation back in for when we only compute distances. Even though this is consistently slower, it should use less memory, which I think is worth it, b/c floyd_warshall is memory-intensive.
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
NodeNodeMapthat behaves similarly and is backed by the matrix. I updated other uses offill_valuewithNodeMapto keep the output sparse (i.e., don't fill withfill_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_warshallwas 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 infloyd_warshall_predecessor_and_distancecan be more clear.