BFS father attribute in igraph is wrong

user_8623468 0
Viewed 211

I am using the igraph package and I am uncertain whether it is a bug or not, but the $father output makes no sense sometimes. Specifically, when I rename the vertex attributes.

h<-make_tree(10)

#with normal vertex attributes
graph.bfs(h, root="1", neimode='out', order=TRUE, father=TRUE,unreachable=FALSE) #father output seems correct
plot(h,layout=layout_as_tree)

#with renamed vertex attributes
set.seed(1)
h<-set.vertex.attribute(h, "name", value=sample(1:10,10))
plot(h,layout=layout_as_tree)
graph.bfs(h, root="3", neimode='out', order=TRUE, father=TRUE,unreachable=FALSE)  #father output seems wrong

I obtain the output as below

#with normal vertex attributes
$order
+ 10/10 vertices, from ff55a96:
 [1]  1  2  3  4  5  6  7  8  9 10

$rank
NULL

$father
+ 10/10 vertices, from ff55a96:
 [1] NA  1  1  2  2  3  3  4  4  5

#with renamed vertex attributes
$order
+ 10/10 vertices, named, from 170f7a0:
 [1] 3  4  5  7  2  8  9  6  10 1 

$rank
NULL

$father
+ 10/10 vertices, named, from 170f7a0:
 [1] 3  4  5  7  2  8  9  6  10 1

I do not understand why the father for the renamed vertex attributes case is wrong. For example, the first element should be NA but its not.

Can someone explain what is happening? If so how do I fix this such that my father elements reflects something similar to the first case.

igraph r
1 Answers

It's a bit strange, but for some reason, the bfs function has a straight assignment of the vertex names to the names of the father vector. See the 54-55 line of code in the source code:

   if (father) 
      names(res$father) <- V(graph)$name

Clearly, this simply overwrites the names of res$father with the vector of names in the graph. Notice that this conditional statement requires the argument igraph_opt("add.vertex.names") to be true.

So we can avoid this behavior by setting the global option for adding vertex names to false.

> igraph_options()$add.vertex.names
[1] TRUE
> igraph_options(add.vertex.names=F)
> igraph_options()$add.vertex.names
[1] FALSE

Now it should work:

h<-make_tree(10)
set.seed(1)
h<-set_vertex_attr(h, "name", value=sample(1:10,10))
bfs(h, root=1, neimode='out', order=TRUE, rank=TRUE, father=TRUE,unreachable=FALSE)

Output: 

    $root
[1] 1

$neimode
[1] "out"

$order
+ 10/10 vertices, named:
 [1] 3  4  5  7  2  8  9  6  10 1 

$rank
 [1]  1  2  3  4  5  6  7  8  9 10

$father
+ 10/10 vertices, named:
 [1] <NA> 3    3    4    4    5    5    7    7    2   

$pred
NULL

$succ
NULL

$dist
NULL

Might be worth raising this on the igraph github, since this seems (at least to me) like undesirable behavior.

user_44881050
Related