Remove edges from a graph using networkx
<p>I am trying to convert a <code>DiGraph</code> 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: </p>

<pre><code>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')])
</code></pre>

<p>Tree: borrowed the data from this <a href="http://stackoverflow.com/questions/21866902/networkx-graph-searches-dfs-successors-vs-dfs-predecessors">question</a> and modified it appropriately:</p>

<pre><code>n----&gt;n1---&gt;n11
 |     |---&gt;n12
 |     |---&gt;n13
 |-----------|---&gt;n131 
 |---&gt;n2              
 |     |----&gt;n21     
 |     |----&gt;n22     
 |------------|---&gt;n221 
 |---&gt;n3
</code></pre>

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

<p>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 <code>('n', 'n131')</code> and <code>('n', 'n221')</code> from the above graph. What is the best way to achieve this. </p>

<p>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: <a href="http://docs.scipy.org/doc/scipy-0.15.1/reference/generated/scipy.sparse.csgraph.minimum_spanning_tree.html" rel="nofollow">http://docs.scipy.org/doc/scipy-0.15.1/reference/generated/scipy.sparse.csgraph.minimum_spanning_tree.html</a></p>

python algorithm networkx