networkxを使用してグラフからエッジを削除する

Question

DiGraphをn-aryツリーに変換し、レベル順またはBFSでノードを表示しようとしています。私の木は、この例を使用して簡単にするために、はるかに大きいこれに似ていますが、：

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')]) 

ツリー：このquestionからデータを借用し、適切に修正：

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

今私の実際のデータセットがあります上記の図を使用して、シンプルに保つために、何百ものノードでより複雑になっています。

親が子にエッジを持ち、孫に別のエッジを持ち、親も孫にエッジを持つように、不要なエッジをツリーから削除します。私は単純に孫と親（根）の間のエッジを削除したい、これは私のグラフを複雑にしているので。 例：上のグラフから('n', 'n131')と('n', 'n221')を削除します。これを達成する最良の方法は何ですか？あなたは、グラフGの最小スパニングツリーを見つけたいよう

Answer 1

は、ルックスあなたはプリムのか、クラスカルのアルゴリズムの実装を使用することができます：ここにscipyのダウンロードから1である：努力のためhttp://docs.scipy.org/doc/scipy-0.15.1/reference/generated/scipy.sparse.csgraph.minimum_spanning_tree.html