Iteratively and efficiently adding elements to a list attribute of vertices in R igraph

Question

I'm working on a signal-propagation algorithm in R, using igraph (a library for random graphs) which involves working with a 2-level nested list.

Igraph allows to attach attributes to vertices (nodes of the graph), these can be vectors or lists, butin my application I need nested lists.

To see, try:

library("igraph")
g <- graph.full(10) # create a fully connected graph with 10 vertices
V(g)$letters <- list(NULL) # adds a list called "letters" to every vertex
V(g)$letters # results in a nested list

I would like to add, in different stages, some pre-determined elements stored in a vector to a given subset of 2nd-level lists, where the subsetted list is the same size as the vector.

The problem is to find an efficient way to add elements to the 2nd-level lists.

The simpler (and so far only) way to go is to write a loop:

set.seed(1234)

# every iteration represents a "round" of element addition ,
# followed by other operations. 
# So the attribute "letters" should not be populated in one sitting.
for (i in 1:10){

  # select randomly five 2nd-level lists (vertices) from the 1st-level list
  # the selected vertices are generated randomly for exposition, 
  # but I need to be able to select them from a well-defined vector (sel.ver)

  sel.vert <- sample(1:10, 5)

  # generate elements to add to the lists in the 2nd-level list (vertices)
  # again, i generate them randomly just to fill the vector, 
  #but the vector could be pre-determined

  add.elem <- sample(letters, 5)

  # now add add each element to its own list
  # notice that the first ELEMENT of add.elem (add.elem[1]) is added
  # to the attribute of the first SELECTED vertex (V(g)[sel.vert[1]]$letters,
  # the second element of add.elem with the second SELECTED vertex, and so on..

  for (l in 1:5){
    V(g)[sel.vert[l]]$letters <- list(c(V(g)[sel.vert[l]]$letters, add.elem[l]))    
  }
}

(I apologise to the experienced reader if this was a horror show of bad programming practices)

As the size of the initial network grows larger and more vertices are selected at every iteration (a random number, instead of 5), the loops become much slower. This should be a "workhorse" function, so I would like to speed it up.

I read the answer given to " Efficiently adding or removing elements to a vector or list in R? " , namely, working with vectors whenever possible and preallocating their size, but I think it doesn't apply to my case, because:

1. I think that with igraph I have no choice but to use lists (at least at the first level)
2. at the second level, the lists will have different final lengths, depending on which vertices are randomly selected. So, it is difficult to preallocate a vector of the correct size. Even if I put very large vectors at the second level, initially filled with NAs (resulting in a list of vectors), I wouldn't know in which position to add elements (because the length of the list at any iteration is random), not to mention that I would need to remove NAs later.

This should be a particular case of adding elements (working with) nested list. As such, I would think that maybe a faster implementation could be achieved by replacing the inner loop with ddply in plyr or do.call, but I couldn't manage to write the function to apply: get the elements of the (inner) list and add this new element (itself a subset of a vector)

Any comment or suggestion is appreciated. Hope the post is clear.

Answer 1

# number of vertices to add elements to at a time
nv <- 5

# selected vertices and elements
sel.ver <- sample(V(g), nv)
add.elem <- sample(letters, nv)

V(g)$letters[sel.ver] <- lapply(1:nv, function(x) {
  c(add.elem[x], unlist(V(g)$letters[sel.ver[x]]))
})