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

Return Type of Kosaraju Proposal #261

Closed
ZigRazor opened this issue Feb 9, 2023 · 7 comments · Fixed by #365
Closed

Return Type of Kosaraju Proposal #261

ZigRazor opened this issue Feb 9, 2023 · 7 comments · Fixed by #365
Assignees
Labels
core something about core development Development of new Functionalities enhancement New feature or request hacktoberfest hacktoberfest issue help wanted Extra attention is needed Priority:Low Priority Label for low priority issue

Comments

@ZigRazor
Copy link
Owner

ZigRazor commented Feb 9, 2023

I'm still not completely convinced about the return type though. Specifically:

  • Wouldn't it be better if the returned connected components contained pointers to the vertex in the graph, instead of (subgraph) copies? I mean, if one wants to check which component a given vertex of the graph belongs to, I think it would make more sense to refer to vertices in the original graph than to vertices in a graph isomorphic/identical to the original. But this question applies to other algorithms in the library too (e.g. BFS, DFS). In some cases (e.g. Max flow, MST algorithms) we return vectors of pairs of strings for the edges, why don't we return vectors of pointers to edges instead? I general, I feel that the interface is a bit too heterogeneous concerning algorithms returns type.

  • With this choice of data structure (i.e. std::vector) it is kind of hard to get the strongly connected component for a given vertex (linear time search). Maybe doing something like what has been done for DialResult (i.e. unordered_map) could simplify this. And providing hashing for single vertices is not really a problem since they already have an id attribute.

Originally posted by @dvd2000 in #260 (comment)

@ZigRazor ZigRazor added enhancement New feature or request help wanted Extra attention is needed development Development of new Functionalities core something about core Priority:Low Priority Label for low priority issue labels Mar 1, 2023
@ZigRazor ZigRazor added the hacktoberfest hacktoberfest issue label Sep 26, 2023
@guru2396
Copy link
Contributor

Hello. The new return type of this algorithm should be the one suggested as below??

I took a look at the approach used in the Boost graph library and they are using a map with vertices as keys and distinct labels for every strongly connected component as values. We can maybe do something similar here? But I think it would be important to keep consistency with the rest of the library.

Originally posted by @dvd2000 in #251

@ZigRazor
Copy link
Owner Author

Yes, we can do something similar in this library

@guru2396
Copy link
Contributor

okay. Can I take this up?

@ZigRazor
Copy link
Owner Author

sure

@guru2396
Copy link
Contributor

@ZigRazor, one more thing that can be modified. I think the adjacency matrix can be used to populate the nodeSet in getNodeSet() method instead of using edgeSet. This method is used many times in the code, so may be there can be some benefit.

@ZigRazor
Copy link
Owner Author

@ZigRazor, one more thing that can be modified. I think the adjacency matrix can be used to populate the nodeSet in getNodeSet() method instead of using edgeSet. This method is used many times in the code, so may be there can be some benefit.

Yes @guru2396 but open a new issue for this improvement

@guru2396
Copy link
Contributor

okay sure, will open

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
core something about core development Development of new Functionalities enhancement New feature or request hacktoberfest hacktoberfest issue help wanted Extra attention is needed Priority:Low Priority Label for low priority issue
Projects
None yet
Development

Successfully merging a pull request may close this issue.

2 participants