Skip to content

Add Prim's Algorithm for Minimum Spanning Tree #625

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.

Sign up for GitHub

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Jump to bottom
Merged
ABorgna merged 34 commits into from
Feb 5, 2025
Merged

Add Prim's Algorithm for Minimum Spanning Tree #625

ABorgna merged 34 commits into from
Feb 5, 2025

Conversation

@BryanCruz
Copy link
Contributor

@BryanCruz BryanCruz commented Apr 2, 2024

Prim's algorithm: https://en.wikipedia.org/wiki/Prim%27s_algorithm

This PR adds another algorithm to find the Minimum Spanning Tree of a graph, an alternative to Kruskal's.

  1. Prim's algorithm has some limitations, such as the input graph must be undirected and it should not have disconnected components.
    I'm wondering if this can be enforced with traits, if anyone can help on this.

  2. I would like to suggest adding another algorithm as well, min_spanning_forest_prim, that iterates through this algorithm to find min spanning tree for all input graph components. min_spanning_forest_kruskal would be trivial to implement, since current min_spanning_tree function, using Kruskal's algorithm, already finds a min spanning forest. Any thoughts on this?

This PR also aims to fix current min_spanning_tree benches, since they currently do not iterate through the created MinSpanningTree structure, not giving the actual bench for Kruskal algorithm.

  1. I added a simple function to iterate through the generated tree elements, but I'm not very familiar with Rust ecosystem, so I would appreciate if anyone knows a better way to force the iteration:
// Current Bench:
bench.iter(|| (min_spanning_tree(&a), min_spanning_tree(&b)));

// Suggested Bench:
bench.iter(|| (iterate_mst_kruskal(&a), iterate_mst_kruskal(&b)));

// Force Tree Iteration:
fn iterate_mst_kruskal<G>(g: G) -> bool
where
    G: Data + IntoEdges + IntoNodeReferences + IntoEdgeReferences + NodeIndexable,
    G::NodeWeight: Clone,
    G::EdgeWeight: Clone + PartialOrd,
{
    let mst = min_spanning_tree(g);
    mst.into_iter().all(|_| true)
}

@ABorgna
Copy link
Member

ABorgna commented Apr 27, 2024

Thanks for the PR!

  1. Kruskal's doc states
    The input graph is treated as if undirected.
    perhaps we could do the same here
  2. That could be useful.
    It is a bit inconsistent that Kruscal always returns a forest, but leaving it as undefined behaviour if there is more than one component sounds OK.

ABorgna
ABorgna reviewed Apr 27, 2024
View reviewed changes
benches/min_spanning_tree.rs Outdated
Comment on lines 90 to 107
fn iterate_mst_kruskal<G>(g: G) -> bool
where
G: Data + IntoEdges + IntoNodeReferences + IntoEdgeReferences + NodeIndexable,
G::NodeWeight: Clone,
G::EdgeWeight: Clone + PartialOrd,
{
let mst = min_spanning_tree(g);
mst.into_iter().all(|_| true)
}

fn iterate_mst_prim<G>(g: G) -> bool
where
G: Data + IntoEdges + IntoNodeReferences + IntoEdgeReferences + NodeIndexable,
G::NodeWeight: Clone,
G::EdgeWeight: Clone + PartialOrd,
{
let mst = min_spanning_tree_prim(g);
mst.into_iter().all(|_| true)
Copy link
Member

@ABorgna ABorgna Apr 27, 2024

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Good catch. Using black_box is the best bet to avoid it getting optimised away.

Suggested change
fn iterate_mst_kruskal<G>(g: G) -> bool
where
G: Data + IntoEdges + IntoNodeReferences + IntoEdgeReferences + NodeIndexable,
G::NodeWeight: Clone,
G::EdgeWeight: Clone + PartialOrd,
{
let mst = min_spanning_tree(g);
mst.into_iter().all(|_| true)
}
fn iterate_mst_prim<G>(g: G) -> bool
where
G: Data + IntoEdges + IntoNodeReferences + IntoEdgeReferences + NodeIndexable,
G::NodeWeight: Clone,
G::EdgeWeight: Clone + PartialOrd,
{
let mst = min_spanning_tree_prim(g);
mst.into_iter().all(|_| true)
fn iterate_mst_kruskal<G>(g: G)
where
G: Data + IntoEdges + IntoNodeReferences + IntoEdgeReferences + NodeIndexable,
G::NodeWeight: Clone,
G::EdgeWeight: Clone + PartialOrd,
{
for e in min_spanning_tree(g) {
std::hint::black_box(e);
}
}
fn iterate_mst_prim<G>(g: G)
where
G: Data + IntoEdges + IntoNodeReferences + IntoEdgeReferences + NodeIndexable,
G::NodeWeight: Clone,
G::EdgeWeight: Clone + PartialOrd,
{
for e in min_spanning_tree_prim(g) {
std::hint::black_box(e);
}

@BryanCruz
Copy link
Contributor Author

BryanCruz commented May 15, 2024

  1. Kruskal's doc states
    The input graph is treated as if undirected.
    perhaps we could do the same here

Thanks for the review @ABorgna :)

I updated the docs to let more explicit what will happen if input graph is directed or has more than 1 component, and applied the suggested change for benches.

I think we would need to convert a directed graph to an undirected one in order to Prim behave correctly on it. For example, a graph where edges are: (I) A-5->B , (II) B-10->C and (III) C-15->A, the valid MST computed by Prim would be {I and II} (undirected), but in order to actually implement this behavior we would need some sort of inverse of IntoEdgeReferences, to access edges that goes to a certain node

So I don't think it's worth the complexity, since there are other algorithms specifically for directed graphs that could be implemented.

What do you think?

BryanCruz and others added 21 commits May 22, 2024 18:39
@BryanCruz
optimization
17b306f
@BryanCruz
add graph6 parser from graph
f7e108e
@BryanCruz
change graph6 struct to trait
a1e9bc0
@BryanCruz
add test cases
2aeb603
@BryanCruz
docs and refactors
d503174
@BryanCruz
move graph6 impl to graph6 mod
06a6d83
@BryanCruz
add graph6 impl for graph types
f43982d
@BryanCruz
add config flags
23d31ba
@BryanCruz
add config flags in tests
c105cd4
@BryanCruz
add graph6 benches
182b035
@msambinelli
Update src/graph_impl/stable_graph/mod.rs
eae9c18
@msambinelli
Merge pull request #4 from BryanCruz/feat/add-graph6-parser
80f65fd 
feat: add graph6 encoder
@BryanCruz
feat: add graph6 decoder (#5)
3934e24 
* rename graph6 file to encoder

* feat: impl graph6 decoder for common graph traits
@BryanCruz
Merge branch 'master' into add-mst-prim
d1fc458
@BryanCruz
add more benches and rand graph generator
ca1f8d2
@BryanCruz
add more test cases
82fa57e
@BryanCruz
remove random-graph-generator resources
3a709c6
@BryanCruz
fix doc
3426502
@BryanCruz
Merge pull request #6 from BryanCruz/add-mst-prim-random
1bac4e9 
Add mst prim random
@BryanCruz
rename test
af4dbfa
@BryanCruz
small doc improvement
ceaa3ab
@daehiff
Copy link
Contributor

daehiff commented Oct 10, 2024

Hey, since we can use this feature in a different project:
Is there any due date to this feature or any open points that need to addressed, if yes, do you need help with that?

@keefehuang keefehuang mentioned this pull request Nov 12, 2024
Open
@BryanCruz
Copy link
Contributor Author

BryanCruz commented Nov 13, 2024

Thanks for the interest in this feature @daehiff 😄

I cleaned up this PR, it had some extra stuff from another PR I was working on.

I don't think there are any open points to be addressed, just waiting for a review now.

@BryanCruz
Copy link
Contributor Author

BryanCruz commented Nov 13, 2024

Limited indexmap version in project config since its latest release broke petgraph MSRV

@BryanCruz BryanCruz requested a review from ABorgna November 13, 2024 03:04
ABorgna
ABorgna approved these changes Feb 5, 2025
View reviewed changes
Copy link
Member

@ABorgna ABorgna left a comment

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Thanks!

Perhaps we should rename Kruskal to min_spanning_tree_kruskal to be more consistent, but that should be done later in a breaking release.

@ABorgna ABorgna merged commit 278c53b into petgraph:master Feb 5, 2025
7 checks passed
This was referenced Apr 5, 2025
Merged
Draft
@RaoulLuque RaoulLuque mentioned this pull request Jun 21, 2025
Closed
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Reviewers

@ABorgna ABorgna ABorgna approved these changes

Assignees

No one assigned

Labels

None yet

Projects

None yet

Milestone

No milestone

Development

Successfully merging this pull request may close these issues.

4 participants

@BryanCruz @ABorgna @daehiff @msambinelli