This is part of my Master thesis which is about designing hydrogen pipeline networks.

For a particular graph of 135 nodes and 157 edges and (see figure below), I need to compute the number of spanning trees (spanning all nodes). I used the Kirchhoff's theorem and implemented it (using scipy and networkx) this way:

import networkx as nx
from scipy import linalg


def nbr_spanning_trees(a_G):
    L = nx.laplacian_matrix(a_G)  # compute the laplacian matrix which is equal to degree matrix - adjacency matrix
    L = L.toarray()  # convert the sparse matrix output of the previous line to an array
    L_cof = L[1:, 1:]  # extract the submatrix associated with the (1,1)-entry's cofactor from the Laplacian matrix
    # (any cofactor can be taken)
    det = linalg.det(L_cof)  # calculate the cofactor
    return det

The returned result is: 1.879759212930661e+16 spanning trees.

This number seems gigantesque, is it reasonable/correct? Is my implementation correct?

As an addition, the graph has at least 23 cycles (but not much more I think). I know this since I have identified the minimum spanning tree and it has 23 edges less than the underlying graph.