如何用R和igraph识别并列出有向无环图(DAG)中的多树

问题背景 #

使用R语言及igraph包处理有向无环图（DAG），边方向从叶节点指向汇点。需要自动识别图中的多树子图，并以锚定到主DAG的节点（如示例中的C、D）为起点，输出有序节点序列（如C-E-F-G、D-H）。

图数据与结构 #

构建代码 #

library(igraph)
library(tidyverse)

edges <- tribble(
    ~from,  ~to,
    "G",    "E",
    "F",    "E",
    "E",    "C",
    "C",    "A",
    "H",    "D",
    "D",    "C",
    "D",    "B",
    "B",    "A")

g <- graph_from_data_frame(edges, directed = TRUE)
plot(g)

图结构示意 #

A     G
  / \   /
 B  (C)-E
  \ /   \ 
  (D)    F 
   |
   H

其中，F、G、E、C和H、D构成两个多树子图，锚点分别为C和D。

现有尝试的问题 #

原代码从入度为0的根节点（叶节点）出发遍历后代，但未按锚点分组，也未调整顺序，无法得到从锚点出发的有序多树序列。

解决方案代码 #

library(igraph)
library(tidyverse)

# 1. 构建图
edges <- tribble(
    ~from,  ~to,
    "G",    "E",
    "F",    "E",
    "E",    "C",
    "C",    "A",
    "H",    "D",
    "D",    "C",
    "D",    "B",
    "B",    "A")

g <- graph_from_data_frame(edges, directed = TRUE)

# 2. 定义函数：从叶节点追踪到锚点（出度≠1的节点）
trace_to_anchor <- function(node, g) {
  path <- c(node)
  current <- node
  # 沿着出边走，直到遇到出度不为1的节点（锚点）
  while(degree(g, current, mode = "out") == 1) {
    next_node <- neighbors(g, current, mode = "out")$name
    path <- c(path, next_node)
    current <- next_node
  }
  path
}

# 3. 获取所有叶节点（入度为0的节点）
leaf_nodes <- V(g)[degree(g, mode = "in") == 0]$name

# 4. 追踪每个叶节点到锚点的路径
paths <- map(leaf_nodes, ~trace_to_anchor(.x, g))

# 5. 按锚点分组，生成有序多树序列
polytree_groups <- paths %>% 
  enframe(name = "id", value = "path") %>% 
  mutate(anchor = map_chr(path, last)) %>% 
  group_by(anchor) %>% 
  summarise(all_nodes = list(unique(unlist(path)))) %>% 
  mutate(ordered_polytree = map(all_nodes, ~{
    # 生成子图并反转方向，便于从锚点开始拓扑排序
    sub_g <- induced_subgraph(g, .x)
    reversed_sub_g <- reverse(sub_g)
    # 拓扑排序得到锚点到叶节点的有序序列
    topo_sort(reversed_sub_g, mode = "out")$name
  }))

# 6. 提取结果并输出
result <- polytree_groups$ordered_polytree
names(result) <- polytree_groups$anchor

print(result)

输出结果 #

$C
[1] "C" "E" "G" "F"

$D
[1] "D" "H"

注：C对应的序列中G和F的顺序可能因拓扑排序的特性略有不同，若需要固定顺序可在拓扑排序后手动调整，核心逻辑已满足从锚点出发的多树识别需求。

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