Selecting all neighbors of a set of nodes in a graph?

I have this network in R:

library(igraph)

set.seed(123)
n <- 20
g <- sample_gnm(n, m = n * 2, directed = FALSE)
while (!is_connected(g)) {
    components <- components(g)
    for (i in 2:components$no) {
        from <- sample(which(components$membership == i), 1)
        to <- sample(which(components$membership == 1), 1)
        g <- add_edges(g, c(from, to))
    }
}
g <- simplify(g, remove.multiple = FALSE, remove.loops = TRUE)
V(g)$weight <- runif(vcount(g))

V(g)$color <- "white"

I wrote some R code that simulates the following process:

• iteration 1: a single random node is selected (a), and all 1st degree neighbors (b) of this node are selected
• iteration 2: a single random node (c) is selected from (b), all 1st degree neighbors of (d) are selected (everything else from the previous iteration is deselected)
• iteration 3: a single random node (e) is selected from (d), all 1st degree neighbors of (e) are selected (everything else from the previous iteration is deselected)
• etc

Here is the simulation:

plot_graph <- function(graph, layout, current_node, current_neighbors, iteration) {
    vertex_colors <- rep("white", vcount(graph))
    vertex_colors[current_neighbors] <- "lightblue"
    vertex_colors[current_node] <- "yellow"
    
    edge_colors <- rep("gray", ecount(graph))
    edge_colors[incident(graph, current_node, mode="all")] <- "blue"
    
    plot(graph, layout = layout, vertex.color = vertex_colors, edge.color = edge_colors,
         edge.arrow.size = 0.1, vertex.label = V(graph)$name, vertex.size = 15,
         vertex.label.color = "black", edge.curved = 0,
         main = paste("Iteration:", iteration, "- Current Node:", V(graph)$name[current_node]))
    
    legend("topright", legend = c("Other Nodes", "Current Node", "Neighbors"),
           fill = c("white", "yellow", "lightblue"), border = "black", cex = 0.8)
}

traverse_graph <- function(graph, num_iterations = 100) {
    visited <- numeric(vcount(graph))
    layout <- layout_with_fr(graph)  # Calculate layout once
    
    current_node <- sample(1:vcount(graph), 1)  
    previous_node <- NA
    
    comm_df <- data.frame(
        iteration = integer(),
        from_node = integer(),
        to_node = integer(),
        neighbors = character(),
        stringsAsFactors = FALSE
    )
    
    for (iteration in 1:num_iterations) {
        visited[current_node] <- visited[current_node] + 1
        current_neighbors <- neighbors(graph, current_node)
        
        cat(sprintf("Iteration %d : node %s -> node %d\n", 
                    iteration, 
                    ifelse(is.na(previous_node), "START", as.character(previous_node)), 
                    current_node))
        
        cat("Current node neighbors:", paste(current_neighbors, collapse = ", "), "\n\n")
        
        comm_df <- rbind(comm_df, data.frame(
            iteration = iteration,
            from_node = ifelse(is.na(previous_node), NA, previous_node),
            to_node = current_node,
            neighbors = paste(current_neighbors, collapse = ", "),
            stringsAsFactors = FALSE
        ))
        
        plot_graph(graph, layout, current_node, current_neighbors, iteration)
        Sys.sleep(0.5)  
        
        previous_node <- current_node
        current_node <- sample(current_neighbors, 1)  # Randomly select next node from neighbors
    }
    
    return(list(visited = visited, comm_df = comm_df))

write.csv(result$comm_df, "communication_log.csv", row.names = FALSE)

I run the simulation like this- everything works well!:

result <- traverse_graph(g, 100)

I am trying to modify this R code to accomplish the following:

• iteration 1: a single random node is selected (a), and all 1st degree neighbors of (a) are selected (b)
• iteration 2: all nodes in (b) are selected and all 1st degree neighbors of all nodes in (b) are selected (c) (everything else from the previous iteration is deselected)
• iteration 3: all nodes in (c) are selected and all 1st degree neighbors of all nodes in (c) are selected (d) (everything else from previous iteration is deselected)
• etc

I tried the following logic to reset colors (i.e. deselection) and select all neighbors using the following logic:

plot_graph <- function(graph, layout, current_nodes, current_neighbors, iteration) {
    vertex_colors <- rep("white", vcount(graph))
    vertex_colors[current_neighbors] <- "lightblue"
    vertex_colors[current_nodes] <- "yellow"
    
    edge_colors <- rep("gray", ecount(graph))
    for (node in current_nodes) {
        edge_colors[incident(graph, node, mode="all")] <- "blue"
    }
    
    plot(graph, layout = layout, vertex.color = vertex_colors, edge.color = edge_colors,
         edge.arrow.size = 0.1, vertex.label = V(graph)$name, vertex.size = 15,
         vertex.label.color = "black", edge.curved = 0,
         main = paste("Iteration:", iteration, "- Current Nodes:", paste(V(graph)$name[current_nodes], collapse = ", ")))
    
    legend("topright", legend = c("Other Nodes", "Current Nodes", "Neighbors"),
           fill = c("white", "yellow", "lightblue"), border = "black", cex = 0.8)
}

traverse_graph <- function(graph, num_iterations = 100) {
    visited <- numeric(vcount(graph))
    layout <- layout_with_fr(graph)  
    
    current_nodes <- sample(1:vcount(graph), 1)  
    
    comm_df <- data.frame(
        iteration = integer(),
        current_nodes = character(),
        neighbors = character(),
        stringsAsFactors = FALSE
    )
    
    for (iteration in 1:num_iterations) {
        visited[current_nodes] <- visited[current_nodes] + 1
        current_neighbors <- unique(unlist(sapply(current_nodes, function(node) neighbors(graph, node))))
        current_neighbors <- setdiff(current_neighbors, current_nodes)  
        
        cat(sprintf("Iteration %d\n", iteration))
        cat("Current nodes:", paste(current_nodes, collapse = ", "), "\n")
        cat("Current node neighbors:", paste(current_neighbors, collapse = ", "), "\n\n")
        
        comm_df <- rbind(comm_df, data.frame(
            iteration = iteration,
            current_nodes = paste(current_nodes, collapse = ", "),
            neighbors = paste(current_neighbors, collapse = ", "),
            stringsAsFactors = FALSE
        ))
        
        plot_graph(graph, layout, current_nodes, current_neighbors, iteration)
        Sys.sleep(0.5)  
        
        current_nodes <- c(current_nodes, current_neighbors)  
    }
    
    return(list(visited = visited, comm_df = comm_df))
}


 result <- traverse_graph(g, 10)  

The problem with this logic is that after a few iterations, all nodes end up being selected in yellow (when there should still be white nodes):

How can I fix this?

I refactored your code a bit (using recursion instead of loops) and used dedicated functions from igraph (which avoid some of your loops):

library(glue)
library(dplyr)
library(cli)

layout <- layout_with_fr(g)
plot_graph <- function(graph, current_nodes, neighbor_nodes, title = "", 
                       graph_layout = layout) {
  vc <- rep("white", vcount(graph))
  vc[as_ids(neighbor_nodes)] <- "lightblue"
  vc[as_ids(current_nodes)] <- "yellow"
  
  ec <- rep("gray", ecount(graph))
  ec[as_ids(do.call(c, incident_edges(graph, current_nodes)))] <- "blue"
  
  plot(graph, layout = graph_layout, vertex.color = vc, edge.color = ec,
       edge.arrow.size = 0.1, vertex.label = V(graph)$name, vertex.size = 15,
       vertex.label.color = "black", edge.curved = 0,
       main = title)
  
  legend("topright", legend = c("Other Nodes", "Current Node", "Neighbors"),
         fill = c("white", "yellow", "lightblue"), border = "black", cex = 0.8)
}

visit_graph <- function(graph, max_iteration = 100, delay = .5) {
  traverse <- function(graph, current_nodes, iteration) {
    res <- NULL
    if (iteration <= max_iteration) {
      ## All 1st degree neighbors of the current_nodes
      adj <- adjacent_vertices(graph, current_nodes)
      if (length(adj) == 1) {
        ## add a dummy second element such that union will work
        adj <- c(adj, list(NULL))
      }
      nbs <- do.call(igraph::union, adj)
      nbs <- difference(nbs, current_nodes)
      cli_h1("Iteration {iteration}")
      cli_alert_info("Current Node{?s}: {.field {as.character(as_ids(current_nodes))}}")
      cli_alert_info("All Neighbor{?s}: {.field {as.character(as_ids(nbs))}}")
      plot_graph(graph, current_nodes, nbs, title = glue("Iteration {iteration}")
      Sys.sleep(delay)
      res <- tibble(
        iteration = iteration,
        from_node = paste(as_ids(current_nodes), collapse = ", "),
        to_nodes = paste(as_ids(nbs), collapse = ", ")
      )
      res <- bind_rows(res, Recall(graph, nbs, iteration + 1L))
    }
    res
  }
  traverse(graph, sample(V(g), 1L), 1L)
}

res <- visit_graph(g, 10)

BUT: As you are selecting all the neighbors, at some point the neighbors of these neighbors will simply span the whole graph. At this moment we reahc an alternating state: we select all neighbors (except the currently selected ones) and we reverse this selection in the next iteration.

But maybe I misunderstood your requirements about "deselecting". I read it as: "select all neighbors which are not anyways already in the current nodes".