Content-Length: 575964 | pFad | https://github.com/TheAlgorithms/Go/pull/687

13 Feat: Add Union Find Algorithm, Test: Add test for Union Find Algorithm by MugdhaBehere · Pull Request #687 · TheAlgorithms/Go · GitHub
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

Feat: Add Union Find Algorithm, Test: Add test for Union Find Algorithm #687

Conversation

MugdhaBehere
Copy link
Contributor

@MugdhaBehere MugdhaBehere commented Oct 16, 2023

Added the Union Find(Dynamic Connectivity) Algorithm and the test file for that.

  • 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
  • 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.

@MugdhaBehere
Copy link
Contributor Author

If this pull request is mergeable, I request the reviewers or code owners to merge it by labeling it as hacktoberfest-accepted.

Copy link
Member

@tjgurwara99 tjgurwara99 left a 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?

@MugdhaBehere
Copy link
Contributor Author

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.

@siriak
Copy link
Member

siriak commented Oct 17, 2023

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?

@MugdhaBehere
Copy link
Contributor Author

MugdhaBehere commented Oct 17, 2023

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?

@siriak
Copy link
Member

siriak commented Oct 17, 2023

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

@MugdhaBehere
Copy link
Contributor Author

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.

@MugdhaBehere
Copy link
Contributor Author

@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.

Copy link
Member

@siriak siriak left a 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

@MugdhaBehere
Copy link
Contributor Author

I have removed the redundant union-find implementation from Kruskal's algorithm. Please check.

@siriak
Copy link
Member

siriak commented Oct 19, 2023

Now the implementation looks good. Please remove main functions both in UF and Kruskals to make CI pass

@MugdhaBehere
Copy link
Contributor Author

Main function has been removed from both the algorithms

Copy link
Member

@siriak siriak left a comment

Choose a reason for hiding this comment

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

image
The code looks good, could you please fix formatting so that PR checks pass?

@MugdhaBehere
Copy link
Contributor Author

I have tried to remove all errors. Sir, could you please check if there are any more errors/ problems with the code style?

Copy link
Member

@tjgurwara99 tjgurwara99 left a 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.

@tjgurwara99
Copy link
Member

Please also format your code with gofmt

@MugdhaBehere
Copy link
Contributor Author

MugdhaBehere commented Oct 19, 2023

The code has been changed as required. Please review the changes.

@MugdhaBehere
Copy link
Contributor Author

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.

@tjgurwara99
Copy link
Member

The gofmt command has many options

@tjgurwara99 ➜ /workspaces/Go/graph $ gofmt -h
usage: gofmt [flags] [path ...]
  -cpuprofile string
        write cpu profile to this file
  -d    display diffs instead of rewriting files
  -e    report all errors (not just the first 10 on different lines)
  -l    list files whose formatting differs from gofmt's
  -r string
        rewrite rule (e.g., 'a[b:len(a)] -> a[b:]')
  -s    simplify code
  -w    write result to (source) file instead of stdout

What you try to do is print the correctly formatted code into your terminal's stdout since you use the gofmt -s. You need to rewrite the files, and to do that you need to use the -w flag, for example:

@tjgurwara99 ➜ /workspaces/Go/graph $ gofmt -w .

And this changes the files that we have in the graph directory:

@tjgurwara99 ➜ /workspaces/Go/graph $ git status
On branch hacktoberfest2023_contribution_by_Mugdha_Behere
Your branch is up to date with 'origen/hacktoberfest2023_contribution_by_Mugdha_Behere'.

Changes not staged for commit:
  (use "git add <file>..." to update what will be committed)
  (use "git restore <file>..." to discard changes in working directory)
        modified:   kruskal.go
        modified:   kruskal_test.go
        modified:   unionfind.go
        modified:   unionfind_test.go

no changes added to commit (use "git add" and/or "git commit -a")

@MugdhaBehere
Copy link
Contributor Author

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,
gofmt -w -s graph/unionfind.go
Similarly, I wrote commands for all files.

@siriak siriak requested a review from tjgurwara99 October 19, 2023 20:04
Copy link
Member

@siriak siriak left a comment

Choose a reason for hiding this comment

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

Looks good, thanks!

@MugdhaBehere
Copy link
Contributor Author

I request the reviewers or code owners to review the changes for approval

@raklaptudirm
Copy link
Member

@tjgurwara99 I am waiting for your review since you already reviewed this pr once.

Copy link
Member

@tjgurwara99 tjgurwara99 left a 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.

@tjgurwara99 tjgurwara99 merged commit f2de286 into TheAlgorithms:master Oct 24, 2023
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
None yet
Projects
None yet
Development

Successfully merging this pull request may close these issues.

4 participants








ApplySandwichStrip

pFad - (p)hone/(F)rame/(a)nonymizer/(d)eclutterfier!      Saves Data!


--- a PPN by Garber Painting Akron. With Image Size Reduction included!

Fetched URL: https://github.com/TheAlgorithms/Go/pull/687

Alternative Proxies:

Alternative Proxy

pFad Proxy

pFad v3 Proxy

pFad v4 Proxy