如何在R中用igraph/tidygraph找出满足条件的所有有效路径？

问题建模 #

把四个节点集合看作有向图的四层（nodes_set_1 → nodes_set_2 → nodes_set_3 → nodes_set_4），每个节点的核心属性是颜色。我们需要找的路径满足：每层选一个节点，且路径内所有颜色不重复。本质上就是在这个分层有向图中，寻找所有从第一层到第四层的颜色无重复的简单路径。

方法一：基于tidyverse的笛卡尔积过滤 #

适合集合规模较小的场景，直接生成所有可能的组合后过滤符合条件的路径：

library(tidyverse)

# 将集合转为带分层标记的数据框
nodes_set_1 <- tibble(layer = 1, color = c("red", "blue", "orange"))
nodes_set_2 <- tibble(layer = 2, color = c("green", "blue", "red", "yellow", "purple"))
nodes_set_3 <- tibble(layer = 3, color = c("blue", "green", "red", "orange", "purple"))
nodes_set_4 <- tibble(layer = 4, color = c("orange", "blue", "green"))

# 生成所有可能组合并过滤颜色不重复的路径
valid_paths <- nodes_set_1 %>%
  # 全连接相邻层的节点
  inner_join(nodes_set_2, by = character(), suffix = c("_1", "_2")) %>%
  inner_join(nodes_set_3, by = character(), suffix = c("", "_3")) %>%
  inner_join(nodes_set_4, by = character(), suffix = c("_3", "_4")) %>%
  # 过滤颜色无重复的组合
  filter(
    color_1 != color,
    color_1 != color_3,
    color_1 != color_4,
    color != color_3,
    color != color_4,
    color_3 != color_4
  ) %>%
  # 将颜色组合整理为路径格式
  transmute(path = pmap(list(color_1, color, color_3, color_4), c))

# 查看结果
print(valid_paths$path)

方法二：基于igraph的图路径搜索 #

适合集合规模较大的场景，通过构建有向图提前过滤无效边，再搜索合法路径：

library(igraph)
library(tidyverse)

# 构建节点列表（包含分层和颜色属性）
nodes <- bind_rows(
  tibble(layer = 1, color = c("red", "blue", "orange")),
  tibble(layer = 2, color = c("green", "blue", "red", "yellow", "purple")),
  tibble(layer = 3, color = c("blue", "green", "red", "orange", "purple")),
  tibble(layer = 4, color = c("orange", "blue", "green"))
) %>% mutate(node_id = row_number())

# 构建合法边：相邻层之间颜色不同的节点相连
edges <- expand.grid(
  from = filter(nodes, layer %in% 1:3)$node_id,
  to = filter(nodes, layer %in% 2:4)$node_id
) %>%
  left_join(nodes, by = c("from" = "node_id")) %>%
  left_join(nodes, by = c("to" = "node_id"), suffix = c("_from", "_to")) %>%
  filter(layer_from + 1 == layer_to, color_from != color_to) %>%
  select(from, to)

# 创建有向图
g <- graph_from_data_frame(edges, directed = TRUE, vertices = nodes)

# 定义起点（第一层节点）和终点（第四层节点）
start_nodes <- filter(nodes, layer == 1)$node_id
end_nodes <- filter(nodes, layer == 4)$node_id

# 搜索所有合法路径：长度为3（4个节点）且颜色无重复
valid_paths_igraph <- map(start_nodes, function(start) {
  all_paths <- all_simple_paths(g, from = start, to = end_nodes, mode = "out")
  keep(all_paths, function(path) {
    path_colors <- V(g)[path]$color
    length(unique(path_colors)) == 4
  })
}) %>%
  flatten() %>%
  map(function(path) V(g)[path]$color)

# 查看结果
print(valid_paths_igraph)

有效解存在性判断 #

直接检查结果是否为空即可：

# 方法一的判断
has_valid_solution <- length(valid_paths$path) > 0

# 方法二的判断
has_valid_solution_igraph <- length(valid_paths_igraph) > 0

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