Find spanning tree using bfs in igraph

Question

I would like to find a spanning tree in a graph using igraph function graph.bfs. Could you show me how?

PS: I try to use the $father info of the returned value from graph.bfs, but the result confuses me. Here is an example:

g <- graph(c(1,2,2,6,1,4,4,6,5,6,1,5,5,3,3,4), directed=FALSE)
plot(g)

tmp <- graph.bfs(g, root=1, neimode='all', order=TRUE, father=TRUE,callback=f)

The result is : tmp$order = 1 2 4 5 6 3 and tmp$father=0 1 4 1 1 2

Can I use the $father info to find all the spanning tree?

Answer 1

I agree with the answer given by "Vincent Zoonekynd" above. However, it did not work as-it-is with me. So I made some modifications in order for it to work. Here is my code

library(igraph)
g2 <- graph(c(1,2,2,6,1,4,4,6,5,6,1,5,5,3,3,4), directed=FALSE)
r <- graph.bfs(g2, root=1, neimode='all', order=TRUE, father=TRUE)
a = as.integer(r$order)
aa = as.integer(r$father)
h <- graph( rbind(a, aa[a])[,-1], directed=FALSE )
plot(h)

It give a new matrix "h", which is based on the minimum spanning tree of original graph

Answer 2

I assume order is straightforward. For father,

> r$order
6/6 vertices, from 29ab0f7:
[1] 1 2 4 5 6 3
> r$father
+ 6/6 vertices, from 29ab0f7:
[1] NA  1  4  1  1  2

• node 1 (node with label 1) does not have a father -->NA

• node 2 has node 1 as a father

• node 3 has node 4 as a father

• node 4 has node 1 as a father

• node 5 has node 1 as a father

• node 6 has node 2 as a father*

There is easy confusion here in cases denoted by the asterisk. "Why is node 6 fathered by node 2 but not node 4?". The answer is that the father is not defined as the most recent element in the transversal sequence that node 6 is connected to, but the earliest element in the transversal sequence that node 6 is connected to. i.e. node 6 is connected to node 2 and node 4 (node 2 is earlier in the transversal sequence). Here is an example that makes this concept obvious

g <- sample_smallworld(1, 5, 5, 0.05)
plot(g)
r <- graph.bfs(g, root=1, neimode='all', order=TRUE, father=TRUE)

As you can see, node 1 fathers all the nodes because it is the earliest in the transversal sequence and it is connected to all the nodes.

$order
+ 5/5 vertices, from 0960d64:
[1] 1 2 3 4 5

$father
+ 5/5 vertices, from 0960d64:
[1] NA  1  1  1  1

Answer 3

To avoid errors like: Error in simple_vs_index(x, ii, na_ok) : Unknown vertex selected we need to change one of code statements as:

h <- graph( rbind(r$order, r$father[r$order, na_ok = TRUE])[,-1], directed=FALSE )

This allows for NA to be present in indices.

Answer 4

The father vector is indexed by the nodes, i.e., it is not in the same order as order.

library(igraph)
g <- graph(c(1,2,2,6,1,4,4,6,5,6,1,5,5,3,3,4), directed=FALSE)
r <- graph.bfs(g, root=1, neimode='all', order=TRUE, father=TRUE)
h <- graph( rbind(r$order, r$father[r$order])[,-1], directed=FALSE )
plot(h)

In this example, we have:

order:  1 2 4 5 6 3
father: 0 1 4 1 1 2.

The ith element of order is the name (or index) of ith node in the pre-traversal order.

The ith element of father is the name (or index) of the parent of the node with index i -- not of the ith element of order. The parent of the ith element of order is parent[order[i]]. This is what we need to define the edges.

The edges of the tree are therefore:

order:  1 2 4 5 6 3
        | | | | | |
father: 0 1 1 1 2 4.