How to generate and plot all spanning trees?

Question

I have a toy graph g, then I have found the number of spanning trees by cofactor of the Laplacian. The number is 11.

library(igraph)
set.seed(2)
n <- 5   #  n=5
m <- 6   #  m=6
g <- erdos.renyi.game(n, p.or.m=m, type="gnm" , directed=FALSE, loops=FALSE)

lap_mat <- laplacian_matrix(g)   
print(paste("number of spanning trees by cofactor = ", det(lap_mat[-1,-1])))
# 11

I have n=5 verteces, and I plot the original graph:

par(mfrow=c(2, 3))
layout <- layout.fruchterman.reingold(g)
plot(g, main="Original graph", vertex.size = 40, layout = layout)

then 5 spanning trees were created with the graph.bfs() function:

for (i in 1:n) {
  r <- graph.bfs(g, root=i, order=TRUE, father=TRUE)
  h <- graph(rbind(r$order, r$father[r$order, na_ok = TRUE])[, -1], directed=FALSE)
  plot(h, main=paste("Spanning tree for root=", i), vertex.size = 40, layout = layout)
}

I need to plot all spanning trees. For example, the next tree with root = 5 is not created:

Question. What is a possible way to generate all trees for small random graph?

Answer 1

First of all, I would say, my solution below is a brute-force method, thus only working well for graphs of small size, i.e., not many vertices or arcs.

If you have large networks, you should refer to some more advanced algorithms, e.g., https://link.springer.com/article/10.1007/s40747-018-0079-7

---

Since you have 6 arcs and 5 vertices, you only need to remove 2 arcs out of 6 to find the spanning tree. There would be combn(6,2) options, and you can delete those edge combinations one by one to check if a spanning tree remains

Filter(
  function(x) length(decompose(x)) == 1,
  combn(
    ecount(g),
    ecount(g) - vcount(g) + 1,
    FUN = function(x) delete.edges(g, E(g)[x]),
    simplify = FALSE
  )
)

which gives all 11 spanning trees

[[1]]
IGRAPH 9692f3d U--- 5 4 -- Erdos renyi (gnm) graph
+ attr: name (g/c), type (g/c), loops (g/l), m (g/n)
+ edges from 9692f3d:
[1] 2--4 3--4 1--5 2--5

[[2]]
IGRAPH 969368e U--- 5 4 -- Erdos renyi (gnm) graph
+ attr: name (g/c), type (g/c), loops (g/l), m (g/n)
+ edges from 969368e:
[1] 1--3 3--4 1--5 2--5

[[3]]
IGRAPH 969368e U--- 5 4 -- Erdos renyi (gnm) graph
+ attr: name (g/c), type (g/c), loops (g/l), m (g/n)
+ edges from 969368e:
[1] 1--3 2--4 1--5 2--5

[[4]]
IGRAPH 96938fa U--- 5 4 -- Erdos renyi (gnm) graph
+ attr: name (g/c), type (g/c), loops (g/l), m (g/n)
+ edges from 96938fa:
[1] 1--3 2--4 3--4 2--5

[[5]]
IGRAPH 96938fa U--- 5 4 -- Erdos renyi (gnm) graph
+ attr: name (g/c), type (g/c), loops (g/l), m (g/n)
+ edges from 96938fa:
[1] 1--3 2--4 3--4 1--5

[[6]]
IGRAPH 9693ded U--- 5 4 -- Erdos renyi (gnm) graph
+ attr: name (g/c), type (g/c), loops (g/l), m (g/n)
+ edges from 9693ded:
[1] 1--2 2--4 3--4 2--5

[[7]]
IGRAPH 969404b U--- 5 4 -- Erdos renyi (gnm) graph
+ attr: name (g/c), type (g/c), loops (g/l), m (g/n)
+ edges from 969404b:
[1] 1--2 2--4 3--4 1--5

[[8]]
IGRAPH 96942b7 U--- 5 4 -- Erdos renyi (gnm) graph
+ attr: name (g/c), type (g/c), loops (g/l), m (g/n)
+ edges from 96942b7:
[1] 1--2 1--3 3--4 2--5

[[9]]
IGRAPH 9694527 U--- 5 4 -- Erdos renyi (gnm) graph
+ attr: name (g/c), type (g/c), loops (g/l), m (g/n)
+ edges from 9694527:
[1] 1--2 1--3 3--4 1--5

[[10]]
IGRAPH 9694527 U--- 5 4 -- Erdos renyi (gnm) graph
+ attr: name (g/c), type (g/c), loops (g/l), m (g/n)
+ edges from 9694527:
[1] 1--2 1--3 2--4 2--5

[[11]]
IGRAPH 9694797 U--- 5 4 -- Erdos renyi (gnm) graph
+ attr: name (g/c), type (g/c), loops (g/l), m (g/n)
+ edges from 9694797:
[1] 1--2 1--3 2--4 1--5

Answer 2

First let's notice the following:

1. For the original graph G, we have |V(G)| = 5, |E(G)| = 6

   

2. A spanning tree T of graph G will have exactly V(G)-1=4 vertices.

3. But that does not mean that we can arbitrarily select and delete any 2 edges from G to obtain a spanning tree T. For example, if we choose to remove the edges (1,5) and (2,5), we shall obtain the following disconnected graph, which is not a tree:

   

4. Let's find the cycles in the graph starting from vertex 1. Note that since there is an edge from vertex 1 to 2, finding all possible paths (of length >1) starting from 1 and ending on vertex 2. Now, if we extend each of the paths by adding the edge (2,1) in the end, we shall find all possible cycles in the simple graph G, starting/ending on vertex 1, as it's done in the next code block:

   cycle_edges <- c()
   C <- list() # all possible cycles staring / ending on vertex 1
   for (path in all_simple_paths(g, 1, 2, mode="out")) {
      pn <- length(path)
      if (pn > 2) { # not a single edge
         cycle <- c(as.vector(path), 1)
         name <- paste(cycle, collapse='')
         C[[name]] <- c()
         for (i in 1:pn) {
            C[[name]] <- c(C[[name]], paste(cycle[i], cycle[i+1], sep='|'))    
         }
      } 
   }
   

   Two of the cycles found in the graph are shown below:

   C
   # $`13421`
   # [1] "1|3" "3|4" "4|2" "2|1"    
   # $`1521`
   # [1] "1|5" "5|2" "2|1"
   

5. Now select one edge from each cycle to delete and generate a unique spanning tree:

   par(mfrow=c(4,3))
   count <- 1
   for (e1 in C[[1]]) {
      for (e2 in C[[2]]) {
         if (e1 != e2) { # make sure not to remove same edge twice
            g1 <- g %>% delete_edges(c(e1, e2))
            plot(g1, main=paste("spanning tree", count), layout = layout)
            count <- count + 1
          }
       }
    }