列出 R 中图的所有邻居

Question

我在 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")

我有这个 R 代码，列出了每个节点的所有邻居：

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")
}

假设我想找出从特定节点开始的每个节点的一级邻居，例如（按顺序排列）：

• 列出节点 16 的邻居：6, 19
• 列出节点 6 的邻居：14、18、19、16
• 列出节点 19 的邻居：16,6,5
• 列出节点 14 的邻居：等
• 等等

我有这个函数，它列出每个节点的一级邻居（从初始节点开始）：

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)

结果如下所示：

  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 

问题是，当我到达节点18时，函数自然停止（尽管仍然没有达到最大步数）。我想更改此函数，以便当我遇到边界节点（例如节点 18）时 - 该函数将开始向后移动并列出另一个方向的邻居。

有人可以建议我如何修改这个函数来做到这一点吗？

Answer 1

这可能就是你所追求的

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

这给出了

[[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