feat: Add Kou's algorithm for finding a MST#682
Merged
ABorgna merged 19 commits intopetgraph:masterfrom Mar 19, 2025
Merged
Conversation
e0d8b6b to
ca0f4c2
Compare
ca0f4c2 to
5a27486
Compare
XVilka
previously requested changes
Dec 23, 2024
Member
XVilka
left a comment
There was a problem hiding this comment.
Please fix this:
---- src/algo/floyd_warshall.rs - algo::floyd_warshall::floyd_warshall_path (line 127) stdout ----
error[E0432]: unresolved import `petgraph::algo::floyd_warshall_path`
--> src/algo/floyd_warshall.rs:130:5
|
6 | use petgraph::algo::floyd_warshall_path;
| ^^^^^^^^^^^^^^^^-------------------
| | |
| | help: a similar name exists in the module: `floyd_warshall`
| no `floyd_warshall_path` in `algo`
error: aborting due to 1 previous error
For more information about this error, try `rustc --explain E0432`.
Couldn't compile the test.
failures:
src/algo/floyd_warshall.rs - algo::floyd_warshall::floyd_warshall_path (line 127)
Contributor
Author
|
I always get the following issue when trying to run the pipeline: At least |
Member
It is a restriction by GitHub to avoid malicious CI runs from external contributors. Once the first PR of you will get merged, it wont happen anymore on any subsequent PRs. |
Member
|
@daehiff it still happens |
Contributor
Author
Ohh, sorry about that. |
5149ec5 to
398820c
Compare
ABorgna
reviewed
Feb 1, 2025
Member
ABorgna
left a comment
There was a problem hiding this comment.
Looks great!
I ran the benchmarks to see if the extra code made the old floyd_warshal impl slower, but it actually seems to be sightly faster now :)
You mentioned you'll add a quickcheck test, I'll wait for that before merging.
Signed-off-by: David Winderl <winderl13@gmail.com>
Simplify compute_shortest_path_length, compute_shortest_path and format compute_metric_closure.
Format reconstruct_metric_closure, my_node_ids to simplify them. Add basic tests for first stages of steiner tree. Implement integration tests in test folder.
Signed-off-by: David Winderl <winderl13@gmail.com>
Signed-off-by: David Winderl <winderl13@gmail.com>
Signed-off-by: David Winderl <winderl13@gmail.com>
Signed-off-by: David Winderl <winderl13@gmail.com>
…l floyd warshall algorithm
Signed-off-by: David Winderl <winderl13@gmail.com>
Signed-off-by: David Winderl <winderl13@gmail.com>
Signed-off-by: David Winderl <winderl13@gmail.com>
Signed-off-by: daehiff <winderl13@gmail.com>
Signed-off-by: daehiff <winderl13@gmail.com>
0f84f2c to
22747e8
Compare
Signed-off-by: daehiff <winderl13@gmail.com> Remove build errors Signed-off-by: daehiff <winderl13@gmail.com> Update src/algo/floyd_warshall.rs Co-authored-by: Agustín Borgna <agustinborgna@gmail.com> Fix PR: Update code such that steiner_trees requires stable graph Signed-off-by: daehiff <winderl13@gmail.com> Fix PR: Update module description Signed-off-by: daehiff <winderl13@gmail.com> Disable steiner_tree Signed-off-by: daehiff <winderl13@gmail.com> Add conditional build in quickcheck tests Signed-off-by: daehiff <winderl13@gmail.com> Fix PR: Fix formatting Signed-off-by: daehiff <winderl13@gmail.com> Fix PR: fix quickcheck tests Signed-off-by: daehiff <winderl13@gmail.com> Fix PR. Fix Clippy Signed-off-by: daehiff <winderl13@gmail.com> Fix PR: Fix Clippy Signed-off-by: daehiff <winderl13@gmail.com> Fix PR: Fix build Signed-off-by: daehiff <winderl13@gmail.com> Fix PR: Adjust typehints Signed-off-by: daehiff <winderl13@gmail.com> Fix PR: Fix clippy by adding typedefs Signed-off-by: daehiff <winderl13@gmail.com> Fix PR: Fix formatting Signed-off-by: daehiff <winderl13@gmail.com>
102b322 to
705c658
Compare
ABorgna
approved these changes
Mar 19, 2025
This was referenced Apr 5, 2025
Merged
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
3 participants
Add this suggestion to a batch that can be applied as a single commit.This suggestion is invalid because no changes were made to the code.Suggestions cannot be applied while the pull request is closed.Suggestions cannot be applied while viewing a subset of changes.Only one suggestion per line can be applied in a batch.Add this suggestion to a batch that can be applied as a single commit.Applying suggestions on deleted lines is not supported.You must change the existing code in this line in order to create a valid suggestion.Outdated suggestions cannot be applied.This suggestion has been applied or marked resolved.Suggestions cannot be applied from pending reviews.Suggestions cannot be applied on multi-line comments.Suggestions cannot be applied while the pull request is queued to merge.Suggestion cannot be applied right now. Please check back later.
Motivation
This PR implements a generic Steiner Tree algorithm for undirected graphs based on Kou's algorithm. The algorithm leverages Dijkstra's shortest path, Floyd-Warshall path reconstruction, and minimum spanning tree computation to determine the Steiner tree for a set of terminal nodes.
The implementation follows the implementation in the networkx library. A detailed description can be found in A fast algorithm for Steiner trees.
petgraphhas no algorithm to approximate a minimal steiner tree. The algorithm melhorn in the networkx documentation, seems to be only different by the complexity class and apperently is an extension. So this could be implemented at a later point.Runtime
Further Notes
Floyd-warshall implementation is adjusted to also allow path reconstruction (see here) this is required in the function
subgraph_edges_from_metric_closure