CODEWITHSUNDEEP
algorithmgraph-theorygraph-algorithm
Sasha Grievus
Sasha Grievus

Reputation: 2686

How can a vertex be deleted from a directed graph without losing existing paths?

I would like to delete a vertex (call it B) from a directed graph without losing existing paths between all remaining vertex. This means that if there is a path from some node A to some node C which involves B, B must be removed, but C must be still reachable from A.

Let's say I have to remove a vertex B in any graph, and A and C being any nodes connected to B on the graph. Running such an algorithm is enough to reach the result?

1) if there is a path A -> B -> C remove link A -> B and B -> C and add link A -> C

2) if there is a path A <- B <- C remove link A <- B and B <- C and add link A <- C

3) if there is a link A -> B or B -> A (which hasn't the link to C depicted in case 1 and 2) remove A -> B or B -> A

Upvotes: 3

Views: 785

Answers (1)

libik
libik

Reputation: 23029

You approach is good. Basically, if you find all neighbours of node B and connect them all to each other (in directed graph in direction it makes sense), then you can be sure that no path was lost by removing B.

If there are any requirements such as "create as little new connection as possible while having all nodes accessible as it was before removal" -> then the solution can be more difficult by i.e. simulate removing B node and using dijsktra from each neighbour node to find out which Node was lost and creating only edges to nodes that were lost by the process.

Upvotes: 3

Related Questions