List all spanning trees with networkx in Python

Question

I need a way to get all the spanning trees of a given graph in Python. I'm using networkx, it can get the minimum weight tree, but I need all the possible spanning trees (as a list, or generator, or whatever). Is there a straightforward way to do so?

EDIT: To clarify, I know it's computationally expensive, I only need it for small graphs (7-10 vertices at most).

How big your graph can be? For a six-branch net of a tetrahedron you'll get about 16 trees. For bigger graphs the number may grow quickly. .... — CiaPan
Not very big, I'd be happy to manage for graphs with 8-9 vertices, 10 at most. That would be 1.000.000 spanning trees for the complete graph IIRC. — Sasha
According to geeksforgeeks.org/total-number-spanning-trees-graph it's N^(N-2), which makes a hundred million for N=10. — CiaPan
Fun thing, I knew that it's n^(n-2) but I can't count to 8 apparently. Anyway, even n = 8 would probably be enough for my purpose, but I need the code to be efficient otherwise it becomes too computationally expensive. — Sasha

Sasha Sasha · Accepted Answer · 2020-06-21T09:17:16

I ended up writing the following code.

def spanning_trees(G):
        
        def build_tree(H, edges):
            if H.is_connected():
                yield H
            else:
                for i in range(len(edges)):
                    if edges[i][1] not in nx.algorithms.descendants(H, edges[i][0]):
                        H1 = Graph(H)
                        H1.add_edge(*edges[i])
                        for H2 in build_tree(H1, edges[i+1:]):
                            yield H2

        E = Graph()
        E.add_nodes_from(G)
        return build_tree(E, [e for e in G.edges])

It can handle the complete graph on 8 vertices quite easily, but I'm not an expert in coding, so there is probably some space for optimisation. Any suggestion?

List all spanning trees with networkx in Python

1 Answers