I have a directed acyclic graph where edge (A,B) means that vertex A depends on vertex B.
Vertex deletions have the following restrictions:
- When vertex B is removed, all dependent vertexes should also be removed.
- When vertex A is removed and vertex A was the only vertex that depends on B, vertex B should also be removed.
I need to list the vertixes which are deleted when
Vertex B is deleted. My solution is B, E and J because
- B -- deleted
- E -- because of condition 2, B is removed and B was the only vertex that depends on E
- J -- because of condition 2
Vertex C is deleted. My solution is C, F, A, G, ... ?
- C -- deleted
- F -- because of condition 2 (C is the only vertex to F)
- A -- condition 1 (depends on C)
- G -- condition 2 (C is the only vertex to G)
- I think here the process goes on and cascades. Is that correct?
What could be an algorithm for such vertexes dependency network which allows for the vertex deletion?
PS: this is an old exam exercise (2008/09); I use it as exercise for my one middle of June.