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.

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

Add Tarjan's algorithm #103

Closed
ZigRazor opened this issue Oct 15, 2021 · 9 comments · Fixed by #322
Closed

Add Tarjan's algorithm #103

ZigRazor opened this issue Oct 15, 2021 · 9 comments · Fixed by #322
Assignees
@suncanghuai
Labels
core something about core development Development of new Functionalities enhancement New feature or request good first issue Good for newcomers hacktoberfest hacktoberfest issue Priority:Medium Priority Label for medium priority issue
Milestone
Algorithm Impleme...

Comments

@ZigRazor
Copy link
Owner

Tarjan's algorithm for finding strongly connected components in a directed graph
Uses two main attributes of each node to track reachability, the index of that node
within a component(index), and the lowest index reachable from that node(lowlink).
We then perform a dfs of the each component making sure to update these parameters
for each node and saving the nodes we visit on the way.
If ever we find that the lowest reachable node from a current node is equal to the
index of the current node then it must be the root of a strongly connected
component and so we save it and it's equireachable vertices as a strongly
connected component.
@ZigRazor ZigRazor added enhancement New feature or request good first issue Good for newcomers development Development of new Functionalities core something about core Priority:Medium Priority Label for medium priority issue hacktoberfest hacktoberfest issue labels Oct 15, 2021
@ZigRazor ZigRazor added this to the Algorithm Implementation milestone Oct 15, 2021
@gaurang7goel
Copy link

HI, i can do this. Can you assign it to me.

@gaurang7goel gaurang7goel mentioned this issue Oct 1, 2022
Closed
@gaurang7goel gaurang7goel removed their assignment Oct 2, 2022
@gaurang7goel
Copy link

@ZigRazor Please assign it someone else, as I was not able to understand the issue properly .

@ZigRazor
Copy link
Owner Author

ZigRazor commented Oct 3, 2022

ok @gaurang7goel

@thesmartdeveloperr
Copy link
Contributor

@ZigRazor i would like to work on this.. pls assign.

@ZigRazor
Copy link
Owner Author

ZigRazor commented Oct 6, 2022

@thesmartdeveloperr sure! Assigned!

@ZigRazor
Copy link
Owner Author

@thesmartdeveloperr are you working on it?

@thesmartdeveloperr
Copy link
Contributor

no @ZigRazor , please assign it to someone else.

@pradkrish pradkrish mentioned this issue Dec 31, 2022
Open
@ZigRazor ZigRazor pinned this issue Mar 1, 2023
@suncanghuai
Copy link
Contributor

@ZigRazor I'd like to work on this, pls assign it to me

@ZigRazor
Copy link
Owner Author

@suncanghuai sure!

suncanghuai added a commit to suncanghuai/CXXGraph that referenced this issue Jul 2, 2023
@suncanghuai
introduce tarjan's algorithm (ZigRazor#103)
facb4eb 
* implement tarjan's algorithm to find sccs for directed graphs
* implement tarjan's algorithm to find cut vertices/bridges/vdcc/edcc
  for undirected graphs
* formatting
suncanghuai added a commit to suncanghuai/CXXGraph that referenced this issue Jul 2, 2023
@suncanghuai
introduce tarjan's algorithm (ZigRazor#103)
4b2cb93 
* implement tarjan's algorithm to find sccs for directed graphs

* implement tarjan's algorithm to find cut vertices/bridges/vdcc/edcc
  for undirected graphs

* formatting
@ZigRazor ZigRazor linked a pull request Jul 2, 2023 that will close this issue
introduce tarjan's algorithm (#103) #322
Merged
suncanghuai pushed a commit to suncanghuai/CXXGraph that referenced this issue Jul 16, 2023
@suncanghuai
validate tarjan's algorithm for directed graphs(ZigRazor#103)
7754ff6 
* add test cases for Tarjan's algorithm

* fix bugs of Tarjan's algorithm for finding Sccs
suncanghuai pushed a commit to suncanghuai/CXXGraph that referenced this issue Aug 8, 2023
validate tarjan's algorithm for directed graphs(ZigRazor#103)
df36f40 
* add test cases for Tarjan's algorithm for finding sccs

* fix bugs of Tarjan's algorithm for finding sccs
suncanghuai pushed a commit to suncanghuai/CXXGraph that referenced this issue Aug 8, 2023
validate tarjan's algorithm for undirected graphs(ZigRazor#103)
0c383d1 
* add test cases for Tarjan's algorithm for finding cut-vertices/bridges/vbccs/ebccs

* fix a bug of Tarjan's algorithm for finding vbccs

* remove printf statements from TarjanTest.cpp
ZigRazor pushed a commit that referenced this issue Aug 9, 2023
@suncanghuai
introduce tarjan's algorithm (#103) (#322)
84603a5 
* introduce tarjan's algorithm (#103)

* implement tarjan's algorithm to find sccs for directed graphs

* implement tarjan's algorithm to find cut vertices/bridges/vdcc/edcc
  for undirected graphs

* formatting

* validate tarjan's algorithm for directed graphs(#103)

* add test cases for Tarjan's algorithm for finding sccs

* fix bugs of Tarjan's algorithm for finding sccs

* validate tarjan's algorithm for undirected graphs(#103)

* add test cases for Tarjan's algorithm for finding cut-vertices/bridges/vbccs/ebccs

* fix a bug of Tarjan's algorithm for finding vbccs

* remove printf statements from TarjanTest.cpp

---------

Co-authored-by: suncanghuai <suncanghuai@gmail.com>
@ZigRazor ZigRazor unpinned this issue Sep 1, 2023
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Assignees

@suncanghuai suncanghuai

Labels
core something about core development Development of new Functionalities enhancement New feature or request good first issue Good for newcomers hacktoberfest hacktoberfest issue Priority:Medium Priority Label for medium priority issue
Projects
@ZigRazor's issues
Status: Done
Milestone
Algorithm Implementation
Development

Successfully merging a pull request may close this issue.

introduce tarjan's algorithm (#103) suncanghuai/CXXGraph
4 participants
@ZigRazor @gaurang7goel @suncanghuai @thesmartdeveloperr