使用networkx从图上删除边 [英] Remove edges from a graph using networkx

问题描述

我试图将DiGraph转换为n元树，并以级别顺序或BFS显示节点.我的树与此相似，但更大，为了简单起见，使用以下示例:

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.

我想从树上删除不必要的边缘，这样，如果父对象对孩子有边缘，孙子边缘对孙子有边缘，而父母对孙子也有边缘.我简单地想删除孙子项与父项(根)之间的边缘，因为这会使我的图形复杂化. 例如:我想从上图中删除('n', 'n131')和('n', 'n221').实现此目标的最佳方法是什么.

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.

推荐答案

看起来像您想找到图G的最小生成树，可以使用Prim或Kruskal算法的实现:这是scipy中的一种: http://docs.scipy.org/doc/scipy-0.15.1/reference/generation/scipy.sparse.csgraph.minimum_spanning_tree.html

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

这篇关于使用networkx从图上删除边的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！