title: Networkx: all Spanning Trees and their associated total weight
body: <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>