1

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)

find spanning tree

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?

Shuai Zhang
  • 2,011
  • 3
  • 22
  • 23

4 Answers4

3

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.
Vincent Zoonekynd
  • 31,893
  • 5
  • 69
  • 78
  • Looks correct. But could you please explain "The father vector is indexed by the nodes"? I don't get it. Thanks! – Shuai Zhang Aug 01 '13 at 11:29
  • I have attempted to add a few explanations. – Vincent Zoonekynd Aug 01 '13 at 11:45
  • I think I understand. But is it a bad design? If you don't have `$order`, so `$father` becomes useless. – Shuai Zhang Aug 01 '13 at 12:39
  • It is not a bad design. You need either `order` and `father`, or `order` and `father[order]`, and you can easily switch from one representation to another. Building the tree turns out to be more straightforward with the latter representation. – Vincent Zoonekynd Aug 01 '13 at 12:54
1

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.

vinaymk
  • 84
  • 5
0

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)

enter image description here

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
Justin Thong
  • 321
  • 3
  • 12
0

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

Sarwan Ali
  • 151
  • 1
  • 1
  • 11