CODEWITHSUNDEEP
rdistanceigraphgraph-theory
mikeck
mikeck

Reputation: 3788

Compute ALL spanning trees of a directed acyclic graph using igraph, network, or other R package

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.

Upvotes: 1

Views: 354

Answers (1)

Iago Carvalho
Iago Carvalho

Reputation: 410

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

Upvotes: 4

Related Questions