1

I want to compute the complete set of spanning trees for a graph. The graphs I'm working with are small (usually less than 10 nodes).

I see functionality for computing the minimum spanning tree with igraph:

library(igraph)
g <- sample_gnp(100, 3/100)
g_mst <- mst(g)

and I see a previous StackOverflow post that described how to compute a spanning tree using a breadth-first search. The code below is adapted from the accepted answer:

r <- graph.bfs(g, root=1, neimode='all', order = TRUE, father = TRUE)
h <- graph(rbind(r$order, r$father[r$order, na_ok = TRUE])[,-1], directed = FALSE)

However, I don't know how to adapt this to compute multiple spanning trees. How would one adapt this code to compute all spanning trees? I'm thinking that one piece of this would be to loop through each node to use as the "root" of each tree, but I don't think that takes me all the way there (since there could still be multiple spanning trees associated with a given root node).

EDIT

The end-goal is to compute the distortion of a graph, which is defined as follows (link, see page 5):

Consider any spanning tree T on a graph G, and compute the average distance t = E[HT] on T between any two nodes that share a link in G. The distortion measures how T distorts links in G, i.e. it measures how many extra hops are required to go from one side of a link in G to the other, if we are restricted to using T. The distortion is defined [13] to be the smallest such average over all possible Ts. Intuitively distortion measures how tree-like a graph is.

[13] R. G. H. Tagmunarunkit and S. Jamin, “Network topology generators: degree-based vs. structural,” in SIGMCOMM, 2002.

Community
  • 1
  • 1
mikeck
  • 3,534
  • 1
  • 26
  • 39

1 Answers1

4

I don't think you will find a function to do that on an R package.

There are n^{n-2} spanning trees on a graph (according to the Cayley's formula). Even on your graph with 10 nodes, there may exist 1,000,000,000 different spanning trees, which is a big number.

Furthermore, the problem of counting or enumerating all spanning trees of a given graph is #P-Complete, which is as harder as NP-Complete problems.

If you are really willing to do that, I recommend dropping R and start using C or C++, which can compute your problem much faster than any R code can do.
Have a look on this paper for a survey on algorithms for computing all spanning trees of a connected graph (which I think is your case).

Iago Carvalho
  • 410
  • 1
  • 5
  • 15
  • Thanks, this makes sense but leaves me confused as to how the *distortion* graph metric is typically computed (which is my end goal). Are you familiar with this metric? I edited my post to include the definition. – mikeck Apr 17 '19 at 21:28
  • 1
    Also worth mentioning that my use case is restricted to DAGs (directed acyclic graphs). Which now that I think about it more... maybe this metric doesn't make sense here. – mikeck Apr 17 '19 at 21:31
  • Since you have directed graphs, then the number of spanning arborescences (yes, the name changes) is n^{(n-2)/2}. However, it's still a big number :( – Iago Carvalho Apr 17 '19 at 21:38
  • I never saw this metric before. However, we may look at the literature. Probably there are better options (and some graph properties) that allow you to compute that without computing all spanning arborescences of the graph – Iago Carvalho Apr 17 '19 at 21:40