How to remove all related nodes in a directed graph using networkx?

Question

I’m not sure exactly what the correct terminology is for my question, so I’ll just explain what I want to do. I have a directed graph, and after deleting the node, I want all independently connected nodes to be deleted as well.

Here is an example:

Let's say I delete node '11', I want node '2' too (and in my own example, they will be nodes under 2, which now also have to be deleted), because it is no longer associated with the main graph. Note that node '9' or '10' should not be deleted because node '8' and '3' are not yet connected to them.

I am using python libraryx library. I was looking for documentation, but I'm not sure of the terminology, so I'm not sure what this is called. If possible, I would like to use the function provided by the library than to create my own recursion through the graph (since my graph is quite large).

Any help or suggestions on how to do this would be great.

Thanks!

Answer 1

I assume the following is true:

• The graph is acyclic . You mentioned this in your comment, but I would like to clearly indicate that this is an initial assumption.
• A known set of root nodes . We need to have some way of knowing which nodes are always considered accessible, and I assume that (somehow) this information is known.
• The initial graph does not contain extra nodes . That is, if the initial graph contains any nodes that need to be deleted, they have already been deleted. This allows the algorithm to work while maintaining the invariant that the node should be there.

If so, then, given the initial setup, the only reason that a node on the graph will be either

• node is in the root set of nodes available for access, or
• node has a parent located in the root set of nodes.

Therefore, every time you remove a node from the graph, the only nodes that can be deleted are the descendants of the node. If the node you are deleting is in the root set, you may need to crop a lot of the graph, and if the node you are deleting is a descendant of a node with several of its descendants, then you may need to do very little.

Given this setting, after deleting the node, you will need to scan all of these node children to see if any of them have other parents who will keep them on the chart. Since we assume that the only nodes in the graph are the nodes that should be there, if the child of the remote w630 has at least one other parent, it should still be on the graph. Otherwise, you must remove the node. Thus, one of the ways to make the delete step is the following recursive algorithm:

• For each of the children of a node to remove:
  • If this node has exactly one parent: (it should be the node we are going to remove)
    • Recursively remove a node from the graph.
• Remove the specified node from the graph.

This is probably not a very good algorithm to implement directly, though, since recursion can get quite deep if you have a large graph. Thus, you can implement it using a worklist algorithm such as:

• Create a worklist W.
• Add v, node to remove, before W.
• Until W is empty:
  • Delete the first entry from W; name it w.
  • For each of the children:
    • If this child has only one parent, add it to W.
  • Remove w from the graph.

This ends with the worst-case time O (m), where m is the number of edges in the graph, since theoretically each scan should be scanned. However, it can be much faster assuming your schedule has some excesses in it.

Hope this helps!

Answer 2

Let me provide you with python networkX code that solves your problem:

import networkx as nx import matplotlib.pyplot as plt#for the purpose of drawing the graphs DG=nx.DiGraph() DG.add_edges_from([(3,8),(3,10),(5,11),(7,11),(7,8),(11,2),(11,9),(11,10),(8,9)]) DG.remove_node(11) 

The connected_components method unexpectedly does not work on oriented graphs, so we rotate the graph to undirected, detect unconnected nodes and then remove them from the oriented graph

 UG=DG.to_undirected() not_connected_nodes=[] for component in nx.connected_components(UG): if len(component)==1:#if it not connected, there only one node inside not_connected_nodes.append(component[0]) for node in not_connected_nodes: DG.remove_node(node)#delete non-connected nodes 

If you want to see the result, add the following two lines to the script:

 nx.draw(DG) plt.show()