-
-
Notifications
You must be signed in to change notification settings - Fork 2.7k
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
Feat: Add Union Find Algorithm, Test: Add test for Union Find Algorithm #687
Feat: Add Union Find Algorithm, Test: Add test for Union Find Algorithm #687
Conversation
If this pull request is mergeable, I request the reviewers or code owners to merge it by labeling it as hacktoberfest-accepted. |
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 believe we already have the DisjointSetUnion
in this repository - I can't quire remember if that is exactly the same as Union Find but I do remember them being the same. @raklaptudirm @siriak any opinions on this?
Yes, a similar or same algorithm has been applied to implement Kruskal's Algorithm. This is a separate implementation if required, though. That is an example where the union-find algorithm has been applied. I did not find a separate implementation of the Union-find algorithm in this repository. If you find the contribution considerable and if this algorithm is required and the pull request is mergeable, I request the code owners or reviewers to merge it with the hacktoberfest-accepted label. |
So, disjoint set union (DSU) and union-find (UF) are the same. Could you remove DSU from Kruskals algorithm and use your UF there? Or merge DSU and UF so that they are the same and separate from Kruskals algorithm? |
Disjoint Set Union data structure is a variation of the union-find data structure, according to what I have read. They share similarities. The Kruskal's algorithm in this repository has been implemented with the help of the Disjoint Set Union data structure. Do you want me to change the implementation of Kruskal's algorithm and implement it with the help of the union-find data structure instead? If yes, should I raise a new pull request for that purpose? |
…ps://github.com/MugdhaBehere/Go into hacktoberfest2023_contribution_by_Mugdha_Behere
Yes, please use it in Kruskal's algo. Let's do it in this PR so that we don't have 2 implementations at once |
Kruskal's algorithm has been updated as required by you. I request the reviewers to go through the pull request and if it is mergeable, merge it by labeling it as hacktoberfest-accepted. |
@siriak @tjgurwara99 Sir, could you please go through the pull request and the changes I made? I have updated Kruskal's algorithm as required by you. And, I have also removed the errors I got in the unionfind_test.go file. |
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.
Please reuse the implementation of UF in graph/unionfind.go
by calling it in graph/kruskal.go
. No need to implement it twice
I have removed the redundant union-find implementation from Kruskal's algorithm. Please check. |
Now the implementation looks good. Please remove |
Main function has been removed from both the algorithms |
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 have tried to remove all errors. Sir, could you please check if there are any more errors/ problems with the code style? |
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.
Please read the documentation conventions for Go - https://tip.golang.org/doc/comment and make the necessary changes.
Please also format your code with |
The code has been changed as required. Please review the changes. |
I had previously formatted the code with gofmt. According to the error message I could see now, I formatted it again, with gofmt -s, but there were no new changes to commit even after formatting it again with gofmt -s. Please check. |
The
What you try to do is print the correctly formatted code into your terminal's stdout since you use the
And this changes the files that we have in the graph directory:
|
I have tried to change the files as required by you. I request the reviewers to go through the changes. I have formatted the files with the help of -w and -s flags at the same time. For example, to format unionfind.go, I wrote the command, |
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.
Looks good, thanks!
I request the reviewers or code owners to review the changes for approval |
@tjgurwara99 I am waiting for your review since you already reviewed this pr once. |
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.
Looks alright to me - the tests are not blackbox tested. But not requesting the author to change this - might change it myself soon since I'm a bit concerned about its API but that's fine - I'll check that. This PR can be merged.
Added the Union Find(Dynamic Connectivity) Algorithm and the test file for that.