基于tidygraph与ggraph的独立树统计及下游最大边数计算

任务1：统计独立树的数量 #

在有向图中，我们通过弱连通组件识别独立树（示例中a0与b0属于同一连通树结构），利用tidygraph的分组功能直接统计数量：

library(tidygraph)
library(igraph)
library(ggraph)
library(tidyverse)

# 原始数据
edges <- tibble(from = c("a0","a1","a2","a3","b0","b1","c0","c1","a2","k1"),
                to = c("a1","a2","a3","a4","b1","a3","c1","c2","k1","k2"))
nodes <- tibble(node = unique(c(edges$from, edges$to)), label = unique(c(edges$from, edges$to)))

# 转换为tidygraph对象
routes_tidy <- as_tbl_graph(graph_from_data_frame(d = edges, vertices = nodes, directed = TRUE))

# 统计独立树数量（弱连通组件数）
tree_count <- routes_tidy %>%
  activate(nodes) %>%
  mutate(component = group_components(type = "weak")) %>%
  pull(component) %>%
  unique() %>%
  length()

cat("独立树数量：", tree_count, "\n")
# 输出：独立树数量：2

任务2：计算每个独立树的平均下游最大边数 #

核心逻辑：对每个独立树，先筛选根节点（入度为0的节点），再计算每个根到下游叶节点（出度为0的节点）的最长路径边数，最后对该树所有根的最长路径取平均值：

# 为节点标记所属组件、入度、出度
routes_tidy_processed <- routes_tidy %>%
  activate(nodes) %>%
  mutate(
    component = group_components(type = "weak"),
    in_degree = centrality_degree(mode = "in"),
    out_degree = centrality_degree(mode = "out")
  ) %>%
  activate(edges) %>%
  mutate(weight = 1) # 边权重设为1，用于计算路径长度

# 计算每个独立树的平均下游最大边数
tree_avg_max_path <- routes_tidy_processed %>%
  activate(nodes) %>%
  filter(in_degree == 0) %>% # 筛选根节点
  group_by(component) %>%
  group_modify(function(.x, .y) {
    root_node <- .x$node
    # 获取当前树的所有叶节点
    leaf_nodes <- routes_tidy_processed %>%
      activate(nodes) %>%
      filter(component == .y$component, out_degree == 0) %>%
      pull(node)
    # 计算根到每个叶节点的最长路径边数
    max_path_lengths <- map_dbl(leaf_nodes, function(leaf) {
      paths <- all_simple_paths(routes_tidy_processed, from = root_node, to = leaf, mode = "out")
      if(length(paths) == 0) 0 else max(map_dbl(paths, length)) - 1 # 节点数减1为边数
    })
    tibble(root = root_node, max_downstream_edges = max(max_path_lengths))
  }) %>%
  ungroup() %>%
  group_by(component) %>%
  summarise(avg_max_downstream_edges = mean(max_downstream_edges))

print(tree_avg_max_path)
# 输出：
# # A tibble: 2 × 2
#   component avg_max_downstream_edges
#       <int>                    <dbl>
# 1         1                      3.5
# 2         2                      2

结果说明 #

1. 独立树数量为2，对应示例中a0-b0所在的连通树，以及c0所在的独立树。
2. 两个独立树的平均下游最大边数分别为3.5和2：
   • 第一个树的根节点是a0和b0：a0到k2的最长路径对应4条边，b0到a4的最长路径对应3条边，平均为(4+3)/2=3.5。
   • 第二个树的根节点是c0：c0到c2的最长路径对应2条边，平均值为2。

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