# Uniform Spanning Trees¶

The Uniform measure on Spanning Trees (UST) of a directed connected graph corresponds to a projection DPP with kernel the transfer current matrix of the graph. The later is actually the orthogonal projection matrix onto the row span of the vertex-edge incidence matrix. In fact, one can discard any row of the vertex-edge incidence matrix - note \(A\) the resulting matrix - to compute \(\mathbf{K}=A^{\top}[AA^{\top}]^{-1}A\).

Important

DPPy uses the `networkx`

library to handle DPPs related to trees and graphs, but `networkx`

is not installed by default when installing DPPy. Please refer to the installation instructions on GitHub for more details on how to install the necessary dependencies.

```
from networkx import Graph
from dppy.exotic_dpps import UST
# Build graph
g = Graph()
edges = [(0, 2), (0, 3), (1, 2), (1, 4), (2, 3), (2, 4), (3, 4)]
g.add_edges_from(edges)
# Initialize UST object
ust = UST(g)
```

```
# Display underlying kernel i.e. transfer current matrix
ust.plot_graph()
```

(Source code, png, hires.png, pdf)

```
# Display underlying kernel i.e. transfer current matrix
ust.plot_kernel()
```

(Source code, png, hires.png, pdf)

```
# Display some samples
for md in ('Wilson', 'Aldous-Broder', 'GS'):
ust.sample(md)
ust.plot()
```