如何高效利用sfnetwork与igraph构建全连通道路网络？

问题背景 #

我正在处理存储道路网络的sf文件（每行代表一段道路），目标是构建全连通网络。使用sfnetwork和igraph创建网络后，发现生成的网络被分割为3749个不连通组件，尝试用空间网格法识别组件间最近点来连接，但效率极低且未完成边的创建。

原创建网络代码：

strade_net <- strade_snapped %>%
  as_sfnetwork() %>%
  activate("edges") %>%
  arrange(edge_length()) %>%
  filter(!edge_is_multiple()) %>%
  filter(!edge_is_loop()) %>%
  activate("edges") %>%
  mutate(weight = edge_length()) %>%
  activate("nodes") %>%
  mutate(bc = centrality_betweenness(weights = weight, directed = FALSE)) %>%
  mutate(id = as.character(seq_along(.)))

nodes_strade <- sf::st_as_sf(strade_net, "nodes") 
edges_strade <- sf::st_as_sf(strade_net, "edges")

nodes <- st_transform(nodes_strade, crs = 32632)
edges <- st_transform(edges_strade, crs = 32632)

# Create the graph
graph <- graph_from_data_frame(d = edges, vertices = nodes$id, directed = FALSE)

组件情况：

print(components(graph)$no)
[1] 3749
print(components(graph)$csize[1:50])
 [1]   2   5   5   4  41   7  20  92   2  18 245  11   4   6 308   4  19   2   2   2   4   2   2   2   2
[26]   2   2   2   2   2   2   2   2   2   2   2   2   2   2   2   2   2   2   2   2 101   5   2   2   2
print(components(graph)$membership[1:50])
 1  2  3  4  5  6  7  8  9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 
 1  1  2  2  3  3  4  4  5  5  6  6  7  7  8  8  8  8  9  9 10 10 11 11 12 12 13 13 14 14 15 15 16 16 17 
36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 
17 18 18 19 19 20 20 21 21 22 22 23 23 24 24 

高效解决方案 #

方案一：利用空间索引快速匹配跨组件最近节点 #

直接在sfnetwork生态内操作，借助nngeo::st_nn的空间索引功能，快速找到跨组件的最近节点对，避免手动循环网格的低效问题。

library(sfnetwork)
library(nngeo)
library(dplyr)

# 1. 在sfnetwork中标记每个节点所属组件
strade_net <- strade_net %>%
  activate("nodes") %>%
  mutate(component = group_components()) # 内置函数直接生成组件分组

# 2. 提取带组件信息的节点sf对象
nodes_with_comp <- st_as_sf(strade_net, "nodes")

# 3. 用空间索引找每个节点的跨组件最近邻（最大距离10米）
nn_pairs <- st_nn(
  nodes_with_comp, nodes_with_comp,
  k = 1,
  maxdist = 10,
  progress = FALSE,
  returnDist = TRUE
)

# 4. 过滤出有效跨组件配对，去重避免双向重复边
valid_pairs <- lapply(seq_along(nn_pairs$nn), function(i) {
  neighbor <- nn_pairs$nn[[i]]
  if (length(neighbor) == 0) return(NULL)
  if (nodes_with_comp$component[i] != nodes_with_comp$component[neighbor]) {
    data.frame(
      from = nodes_with_comp$id[i],
      to = nodes_with_comp$id[neighbor],
      weight = nn_pairs$dist[[i]]
    )
  } else {
    NULL
  }
}) %>% bind_rows() %>%
  mutate(pair_id = paste(pmin(from, to), pmax(from, to), sep = "-")) %>%
  distinct(pair_id, .keep_all = TRUE) %>%
  select(-pair_id)

# 5. 生成连接边的LINESTRING几何并加入sfnetwork
edges_to_add <- st_sf(
  from = valid_pairs$from,
  to = valid_pairs$to,
  weight = valid_pairs$weight,
  geometry = st_nearest_points(
    nodes_with_comp[nodes_with_comp$id %in% valid_pairs$from, ],
    nodes_with_comp[nodes_with_comp$id %in% valid_pairs$to, ]
  )
)

# 6. 合并到原网络得到全连通网络
strade_net_connected <- strade_net %>%
  activate("edges") %>%
  bind_edges(edges_to_add)

# 验证连通性：组件数应为1
strade_net_connected %>%
  activate("nodes") %>%
  mutate(component = group_components()) %>%
  pull(component) %>%
  unique() %>%
  length()

方案二：优先合并小组件（优化性能） #

如果存在大量极小组件（如size<=2），可以只处理小组件与大组件的连接，进一步减少计算量：

# 1. 统计组件大小，筛选极小组件
component_sizes <- strade_net %>%
  activate("nodes") %>%
  as_tibble() %>%
  count(component, name = "size")

small_components <- component_sizes %>% filter(size <= 2) %>% pull(component)

# 2. 分离小组件节点和其他节点
small_nodes <- nodes_with_comp %>% filter(component %in% small_components)
large_nodes <- nodes_with_comp %>% filter(!component %in% small_components)

# 3. 找每个小节点的最近大节点
nn_small_large <- st_nn(
  small_nodes, large_nodes,
  k = 1,
  maxdist = 10,
  returnDist = TRUE,
  progress = FALSE
)

# 4. 生成有效配对并创建连接边
valid_small_pairs <- lapply(seq_along(nn_small_large$nn), function(i) {
  neighbor <- nn_small_large$nn[[i]]
  if (length(neighbor) == 0) return(NULL)
  data.frame(
    from = small_nodes$id[i],
    to = large_nodes$id[neighbor],
    weight = nn_small_large$dist[[i]]
  )
}) %>% bind_rows()

# 后续生成边、合并网络步骤同方案一

关键优化点 #

• 空间索引加速：st_nn默认使用R-tree空间索引，比手动网格循环效率提升几个数量级
• sfnetwork原生操作：避免在sfnetwork和igraph之间来回转换，保留空间属性的同时简化流程
• 去重逻辑：通过配对ID去重，避免重复添加双向边
• 优先处理小组件：减少不必要的组件间配对计算，适合组件数量极多的场景

内容的提问来源于stack exchange，提问作者sawu