Graph Slicing based on connectivity #53
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
Milestone
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.
The text was updated successfully, but these errors were encountered: