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

Graph Slicing based on connectivity #53

Closed
ZigRazor opened this issue Sep 16, 2021 · 6 comments · Fixed by #82
Closed

Graph Slicing based on connectivity #53

ZigRazor opened this issue Sep 16, 2021 · 6 comments · Fixed by #82
Assignees
Labels
development Development of new Functionalities enhancement New feature or request good first issue Good for newcomers hacktoberfest hacktoberfest issue help wanted Extra attention is needed Priority:High Priority Label for high priority issue

Comments

@ZigRazor
Copy link
Owner

Add graph slicing based on connectivity.
E.g. given
A -> B -> C <- D
A -> E -> C -> F
and the starting node A: A, B, and E can be sliced off.
Mathematical definition of the problem:
Let G be the set of nodes in a graph and n be a given node in that set. Let C be the non-strict subset of G containing both n and all nodes reachable from n, and let C' be its complement. There's a third set M, which is the non-strict subset of C containing all nodes that are reachable from any node in C'.
The problem consists of finding all nodes that belong to C but not to M.

The reason why this problem is relevant is because it's used in garbage collection systems to decide which other objects need to be released, given that one object is about to be released.

@ZigRazor ZigRazor added enhancement New feature or request help wanted Extra attention is needed good first issue Good for newcomers development Development of new Functionalities Priority:Medium Priority Label for medium priority issue labels Sep 16, 2021
@ZigRazor ZigRazor added this to the Algorithm Implementation milestone Sep 16, 2021
@ZigRazor ZigRazor added the hacktoberfest hacktoberfest issue label Sep 30, 2021
@ZigRazor ZigRazor pinned this issue Oct 1, 2021
@ZigRazor ZigRazor added Priority:High Priority Label for high priority issue and removed Priority:Medium Priority Label for medium priority issue labels Oct 12, 2021
@sidml
Copy link
Contributor

sidml commented Oct 12, 2021

@ZigRazor
I can work on this if it's okay. I was wondering if there is any specific algorithm for this or an optimized way of doing this ?
I was thinking of doing the following:

  • Use DFS or BFS to find all nodes reachable from n. These are elements of set C.
  • Initialize C' to be complement of C (i.e. all nodes - nodes that are in C)
  • For all nodes in C', apply DFS/BFS and get the list of reachable nodes. This is set M.
  • Finally removes nodes from C that belong to M. This is our solution.

@ZigRazor
Copy link
Owner Author

@sidml
I think is OK as a first implementation, then if someone knows a better implementation, we can ever review this implementation.
So if you are ok, i assign this issue to you!

@ZigRazor
Copy link
Owner Author

@sidml remember that you have assigned also the issue #70

@ZigRazor
Copy link
Owner Author

@sidml given your contributions to the repository, I would like to invite you as a contributor to the repository. I am sending you the invitation!

@sidml
Copy link
Contributor

sidml commented Oct 12, 2021

@ZigRazor Thanks! I hope to keep working on new functionalities.

@ZigRazor
Copy link
Owner Author

@ZigRazor Thanks! I hope to keep working on new functionalities.

If you have more suggestion, you can open issue and implement the functionalities, or eventually wait someone contribute to the project!
Don't forget to spread the words, over every channel you know.
I want to create a community to grow up this project!
Thank you !

@ZigRazor ZigRazor linked a pull request Oct 13, 2021 that will close this issue
@ZigRazor ZigRazor unpinned this issue Oct 13, 2021
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
development Development of new Functionalities enhancement New feature or request good first issue Good for newcomers hacktoberfest hacktoberfest issue help wanted Extra attention is needed Priority:High Priority Label for high priority issue
Projects
None yet
Development

Successfully merging a pull request may close this issue.

2 participants