rigraph

Listing all neighbors of a graph in R


I have this graph in R:

library(igraph)

set.seed(123)

n <- 20
g <- sample_gnm(n, m = n * 2, directed = FALSE)

while (!is_connected(g)) {
    # Find disconnected components
    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))

layout <- layout_with_fr(g)


plot(g, layout = layout, edge.arrow.size = 0.1, 
     vertex.label = V(g)$name, vertex.size = 15, 
     vertex.label.color = "black", edge.curved = 0,
     vertex.color = "white", edge.color = "black")

enter image description here

I have this R code that lists all the neighbors of each node:

get_neighbors <- function(graph, vertex) {
    neighbors(graph, vertex)
}

neighbor_list <- list()

for (v in V(g)) {
    neighbor_list[[as.character(v)]] <- get_neighbors(g, v)
}

for (v in names(neighbor_list)) {
    cat("Neighbors of vertex", v, ":", neighbor_list[[v]], "\n")
}

Suppose I want to find out the first degree neighbors of each node starting from a specific node, e.g. (goes in order):

I have this function which lists the first degree neighbors of each node (starting from an initial node):

explore_first_degree_neighbors <- function(graph, start_node, max_steps = 5) {
    visited <- vector("logical", vcount(graph))
    queue <- c(start_node)
    results <- list()
    step <- 1
    
    while (length(queue) > 0 && step <= max_steps) {
        current_node <- queue[1]
        queue <- queue[-1]
        
        if (!visited[current_node]) {
            visited[current_node] <- TRUE
            
            neighbors <- as.numeric(neighbors(graph, current_node))
            results[[as.character(current_node)]] <- neighbors
            
            cat("Neighbors of node", current_node, ":", neighbors, "\n")
            
            # Add unvisited neighbors to the queue
            queue <- c(queue, neighbors[!visited[neighbors]])
            
            step <- step + 1
        }
    }
    
    return(results)
}

start_node <- 16
max_steps <- 100

cat("Starting exploration from node", start_node, "for", max_steps, "steps:\n\n")
exploration_results <- explore_first_degree_neighbors(g, start_node, max_steps)

The results look like this:

  Neighbors of node 16 : 6 19 
Neighbors of node 6 : 9 14 16 19 
Neighbors of node 19 : 4 6 16 
Neighbors of node 9 : 1 5 6 11 17 
Neighbors of node 14 : 4 5 6 8 11 12 
Neighbors of node 4 : 3 8 10 14 15 17 19 
Neighbors of node 1 : 3 5 8 9 
Neighbors of node 5 : 1 2 8 9 14 20 
Neighbors of node 11 : 9 10 13 14 
Neighbors of node 17 : 2 3 4 7 9 18 
Neighbors of node 8 : 1 4 5 14 15 
Neighbors of node 12 : 7 14 15 20 
Neighbors of node 3 : 1 4 17 
Neighbors of node 10 : 2 4 7 11 
Neighbors of node 15 : 2 4 8 12 
Neighbors of node 2 : 5 10 15 17 
Neighbors of node 20 : 5 12 13 
Neighbors of node 13 : 11 20 
Neighbors of node 7 : 10 12 17 
Neighbors of node 18 : 17 

The problem is that when I reach node 18, the function naturally stops (even though the maximum number of steps has still not been reached). I want to change this function so that when I encounter a boundary node (e.g. node 18) - the function will starting moving backwards and listing the neighbors in the other direction.

Can someone please suggest how I can modify this function to do this?



Solution

  • Probably this is what you are after

    root <- "18"
    lapply(
        seq.int(diameter(g)),
        \(k) {
            ego(g, nodes = root, order = k, mindist = k)[[1]]
        }
    )
    

    which gives

    [[1]]
    + 1/20 vertex, from 77b07cd:
    [1] 17
    
    [[2]]
    + 5/20 vertices, from 77b07cd:
    [1] 2 3 4 7 9
    
    [[3]]
    + 10/20 vertices, from 77b07cd:
     [1]  5 10 15  1  8 14 19 12  6 11
    
    [[4]]
    + 3/20 vertices, from 77b07cd:
    [1] 20 16 13