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\).

See also

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.

histogram showing uniformity of the spanning trees generated by the different procedures
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)

(Source code)

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

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

../_images/ust-1.png

(Source code)

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

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

../_images/ust-2.png

(Source code)

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

(Source code)

../_images/ust-3_00.png

Fig. 45 (png, hires.png, pdf)

../_images/ust-3_01.png

Fig. 46 (png, hires.png, pdf)

../_images/ust-3_02.png

Fig. 47 (png, hires.png, pdf)