Networkx: all Spanning Trees and their associated total weight
<p>Given a simple undirected grid network like this:</p>

<pre><code>import networkx as nx
from pylab import *
import matplotlib.pyplot as plt
%pylab inline

ncols=3
N=3 
G=nx.grid_2d_graph(N,N)
labels = dict( ((i,j), i + (N-1-j) * N ) for i, j in G.nodes() )
nx.relabel_nodes(G,labels,False)
inds=labels.keys()
vals=labels.values()
inds=[(N-j-1,N-i-1) for i,j in inds]
pos2=dict(zip(vals,inds))
nx.draw_networkx(G, pos=pos2, with_labels=True, node_size = 200, node_color='orange',font_size=10)
plt.axis('off')
plt.title('grid')
plt.show()
</code></pre>

<p>And given that each edge has a weight corresponding to its length:</p>

<pre><code>#Weights
from math import sqrt

weights = dict()
for source, target in G.edges():
    x1, y1 = pos2[source]
    x2, y2 = pos2[target]
    weights[(source, target)] = round((math.sqrt((x2-x1)**2 + (y2-y1)**2)),3) 

for e in G.edges():
    G[e[0]][e[1]] = weights[e] #Assigning weights to G.edges()
</code></pre>

<p><strong>How could it be possible to compute all spanning trees in the grid, and their associated total weight?</strong></p>

<p>NB: this is a trivial case where all weights=1.</p>