Skip to content
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 our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Boruvkas Algorithm #1984

Merged
merged 23 commits into from
Jan 24, 2023
Merged

Boruvkas Algorithm #1984

merged 23 commits into from
Jan 24, 2023

Conversation

JNardoni
Copy link
Contributor

Description of Change

Implemented Boruvkas Algorithm, a greedy algorithm for finding a graphs minimums spanning tree.

Checklist

  • Added description of change
  • Added file name matches File name guidelines
  • Added tests and example, test must pass
  • Added documentation so that the program is self-explanatory and educational - Doxygen guidelines
  • Relevant documentation/comments is changed or added
  • PR title follows semantic commit guidelines
  • Search previous suggestions before making a new one, as yours may be a duplicate.
  • I acknowledge that all my contributions will be made under the project's license.

Notes: Implementation to greedily finds the Minimum Spanning Tree of a graph using Boruvka's algorithm.

Implemented Boruvkas Algorithm under graphs as a means for finding the minimums spanning tree
Implemented Boruvkas algorithm, a greedy algorithm to find a graphs minimum spanning tree.
Copy link
Member

@Panquesito7 Panquesito7 left a comment

Choose a reason for hiding this comment

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

Great work! 🚀
There are still a few other pending things to do. If you need any help, let us know here or in our Discord community. 🙂

greedy_algorithms/boruvkas_minumum_spanning_tree.cpp Outdated Show resolved Hide resolved
greedy_algorithms/boruvkas_minumum_spanning_tree.cpp Outdated Show resolved Hide resolved
greedy_algorithms/boruvkas_minumum_spanning_tree.cpp Outdated Show resolved Hide resolved
greedy_algorithms/boruvkas_minumum_spanning_tree.cpp Outdated Show resolved Hide resolved
greedy_algorithms/boruvkas_minumum_spanning_tree.cpp Outdated Show resolved Hide resolved
greedy_algorithms/boruvkas_minumum_spanning_tree.cpp Outdated Show resolved Hide resolved
greedy_algorithms/boruvkas_minumum_spanning_tree.cpp Outdated Show resolved Hide resolved
@Panquesito7 Panquesito7 added enhancement New feature or request automated tests are failing Do not merge until tests pass requested changes changes have been requested Proper Documentation Required requested to write the documentation properly labels Aug 24, 2022
JNardoni and others added 2 commits August 24, 2022 16:50
limits.h to climits

Co-authored-by: David Leal <halfpacho@gmail.com>
Made changes as recommended by Panquesito7 for maintainability and security
@JNardoni JNardoni requested a review from Panquesito7 August 25, 2022 19:10
JNardoni and others added 2 commits August 31, 2022 17:25
Made suggested changes

Co-authored-by: David Leal <halfpacho@gmail.com>
Copy link
Member

@Panquesito7 Panquesito7 left a comment

Choose a reason for hiding this comment

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

Almost there! 😄

greedy_algorithms/boruvkas_minumum_spanning_tree.cpp Outdated Show resolved Hide resolved
greedy_algorithms/boruvkas_minumum_spanning_tree.cpp Outdated Show resolved Hide resolved
greedy_algorithms/boruvkas_minumum_spanning_tree.cpp Outdated Show resolved Hide resolved
greedy_algorithms/boruvkas_minumum_spanning_tree.cpp Outdated Show resolved Hide resolved
greedy_algorithms/boruvkas_minumum_spanning_tree.cpp Outdated Show resolved Hide resolved
greedy_algorithms/boruvkas_minumum_spanning_tree.cpp Outdated Show resolved Hide resolved
greedy_algorithms/boruvkas_minumum_spanning_tree.cpp Outdated Show resolved Hide resolved
greedy_algorithms/boruvkas_minumum_spanning_tree.cpp Outdated Show resolved Hide resolved
greedy_algorithms/boruvkas_minumum_spanning_tree.cpp Outdated Show resolved Hide resolved
@Panquesito7 Panquesito7 removed the Proper Documentation Required requested to write the documentation properly label Sep 7, 2022
JNardoni and others added 3 commits September 8, 2022 19:02
Changed from graph to greedy algorithm, removed the extra main(), general fixes
JNardoni and others added 2 commits September 29, 2022 16:27
General readability changes, change push_back to implace_back
Copy link
Member

@Panquesito7 Panquesito7 left a comment

Choose a reason for hiding this comment

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

Please fix the clang-tidy warnings here.
Let us know if you need any help with that! 🙂

Added pre-allocation of memory for the parent vector of Boruvkas
Copy link
Member

@Panquesito7 Panquesito7 left a comment

Choose a reason for hiding this comment

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

Please change the filename: there's a spelling error (u -> i).

Old: boruvkas_minumum_spanning_tree.cpp
New: boruvkas_minimum_spanning_tree.cpp

greedy_algorithms/boruvkas_minumum_spanning_tree.cpp Outdated Show resolved Hide resolved
greedy_algorithms/boruvkas_minumum_spanning_tree.cpp Outdated Show resolved Hide resolved
greedy_algorithms/boruvkas_minumum_spanning_tree.cpp Outdated Show resolved Hide resolved
greedy_algorithms/boruvkas_minumum_spanning_tree.cpp Outdated Show resolved Hide resolved
greedy_algorithms/boruvkas_minumum_spanning_tree.cpp Outdated Show resolved Hide resolved
greedy_algorithms/boruvkas_minumum_spanning_tree.cpp Outdated Show resolved Hide resolved
Fixed file name, added Boruvkas namespace, made suggested changes
Fixed spacing hopefully
Fixing weird tabs
Finally done with spacing i think
Triplle checked tabs/spaces
@JNardoni JNardoni requested a review from Panquesito7 November 14, 2022 20:06
@Panquesito7 Panquesito7 added approved Approved; waiting for merge and removed automated tests are failing Do not merge until tests pass requested changes changes have been requested labels Jan 9, 2023
Copy link
Member

@Panquesito7 Panquesito7 left a comment

Choose a reason for hiding this comment

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

Great work. Thanks! 🚀

@Panquesito7 Panquesito7 merged commit f093837 into TheAlgorithms:master Jan 24, 2023
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
approved Approved; waiting for merge enhancement New feature or request
Projects
None yet
Development

Successfully merging this pull request may close these issues.

3 participants