Remove edges from a graph using networkx

问题:

I am trying to convert a DiGraph into n-ary tree and displaying the nodes in level order or BFS. My tree is similar to this, but much larger, for simplicity using this example:

G = networkx.DiGraph()
G.add_edges_from([('n', 'n1'), ('n', 'n2'), ('n', 'n3')])
G.add_edges_from([('n4', 'n41'), ('n1', 'n11'), ('n1', 'n12'), ('n1', 'n13')])
G.add_edges_from([('n2', 'n21'), ('n2', 'n22'), ('n', 'n22')])
G.add_edges_from([('n13', 'n131'), ('n22', 'n221'), ('n', 'n131'), ('n', 'n221')])

Tree: borrowed the data from this question and modified it appropriately:

n---->n1--->n11
 |     |--->n12
 |     |--->n13
 |-----------|--->n131 
 |--->n2              
 |     |---->n21     
 |     |---->n22     
 |------------|--->n221 
 |--->n3

Now my real data set is much more complicated with hundreds of node, to keep it simple I have used the above diagram.

I want remove the unnecessary edges from the tree, such that if a parent has an edge to the child, which has another edge to a grandchild AND the parent also has an edge to the grandchild. I simple want to remove the edge between the grandchild and the parent (root), since this is complicating my graph. ex: I want to remove ('n', 'n131') and ('n', 'n221') from the above graph. What is the best way to achieve this.

回答1:

Looks like you want to find the minimum spanning tree of the graph G, you can use Prim's or Kruskal's algorithm's implementation: here is one from scipy: http://docs.scipy.org/doc/scipy-0.15.1/reference/generated/scipy.sparse.csgraph.minimum_spanning_tree.html