如何在R中找到图上所有可能的有效路径？

问题描述 投票：0回答：1

我正在 R 中解决一个有趣的问题（可能使用 

igraph
和/或 
tidygraph
库），我需要在图表上找到满足某些条件的所有可能路径。问题可以简化为：

我有 16 个不同的节点，可以分为 4 组，每个节点都有一个特征，称之为颜色。 *注意：以下可能不是表示数据的最佳方式，但希望它能传达情况。

nodes_set_1 <- c("red", "blue", "orange")
nodes_set_2 <- c("green", "blue", "red", "yellow", "purple")
nodes_set_3 <- c("blue", "green", "red", "orange", "purple")
nodes_set_4 <- c("orange", "blue", "green")

我现在需要找到这些节点之间满足以下三个条件的所有可能路径： (1) 每条路径必须恰好包含每组中的一个节点。 (2) 图形从

nodes_set_1
到
nodes_set_2
到
nodes_set_3
到
nodes_set_4
(3) 单一路径内颜色不能重复。

因此，例如以下路径是有效的：

path_1 <- c(nodes_set_1[1], nodes_set_2[1], nodes_set_3[1], nodes_set_4[1])

下面的路径将无效，因为颜色“蓝色”重复：

path_2 <- c(nodes_set_1[2], nodes_set_2[2], nodes_set_3[2], nodes_set_4[2])

我希望得到一些关于设置和解决这个问题的建议。找到一种有效确定是否不存在有效解决方案的方法也将令人惊奇。

谢谢！

r performance igraph combinatorics tidygraph
1个回答
3
投票

基础 R 选项

以下有两个选项：

- 
expand.grid
+ 
Filter

使用 

expand.grid
生成所有组合，然后根据标准对其进行子集化

nodes_lst <- list(nodes_set_1, nodes_set_2, nodes_set_3, nodes_set_4)
ps <- Filter(Negate(anyDuplicated), asplit(unname(expand.grid(nodes_lst)), 1))

你会看到

> ps
[[1]]
[1] "red"    "green"  "blue"   "orange"

[[2]]
[1] "red"    "yellow" "blue"   "orange"

[[3]]
[1] "red"    "purple" "blue"   "orange"

[[4]]
[1] "red"    "blue"   "green"  "orange"

[[5]]
[1] "blue"   "red"    "green"  "orange"

[[6]]
[1] "red"    "yellow" "green"  "orange"

[[7]]
[1] "blue"   "yellow" "green"  "orange"

[[8]]
[1] "red"    "purple" "green"  "orange"

[[9]]
[1] "blue"   "purple" "green"  "orange"

[[10]]
[1] "blue"   "green"  "red"    "orange"

[[11]]
[1] "blue"   "yellow" "red"    "orange"

[[12]]
[1] "blue"   "purple" "red"    "orange"

[[13]]
[1] "red"    "green"  "purple" "orange"

[[14]]
[1] "blue"   "green"  "purple" "orange"

[[15]]
[1] "red"    "blue"   "purple" "orange"

[[16]]
[1] "blue"   "red"    "purple" "orange"

[[17]]
[1] "red"    "yellow" "purple" "orange"

[[18]]
[1] "blue"   "yellow" "purple" "orange"

[[19]]
[1] "orange" "red"    "green"  "blue"  

[[20]]
[1] "red"    "yellow" "green"  "blue"

[[21]]
[1] "orange" "yellow" "green"  "blue"

[[22]]
[1] "red"    "purple" "green"  "blue"

[[23]]
[1] "orange" "purple" "green"  "blue"

[[24]]
[1] "orange" "green"  "red"    "blue"

[[25]]
[1] "orange" "yellow" "red"    "blue"

[[26]]
[1] "orange" "purple" "red"    "blue"

[[27]]
[1] "red"    "green"  "orange" "blue"

[[28]]
[1] "red"    "yellow" "orange" "blue"

[[29]]
[1] "red"    "purple" "orange" "blue"

[[30]]
[1] "red"    "green"  "purple" "blue"

[[31]]
[1] "orange" "green"  "purple" "blue"

[[32]]
[1] "orange" "red"    "purple" "blue"

[[33]]
[1] "red"    "yellow" "purple" "blue"

[[34]]
[1] "orange" "yellow" "purple" "blue"

[[35]]
[1] "orange" "red"    "blue"   "green"

[[36]]
[1] "red"    "yellow" "blue"   "green"

[[37]]
[1] "orange" "yellow" "blue"   "green"

[[38]]
[1] "red"    "purple" "blue"   "green"

[[39]]
[1] "orange" "purple" "blue"   "green"

[[40]]
[1] "orange" "blue"   "red"    "green"

[[41]]
[1] "blue"   "yellow" "red"    "green"

[[42]]
[1] "orange" "yellow" "red"    "green"

[[43]]
[1] "blue"   "purple" "red"    "green"

[[44]]
[1] "orange" "purple" "red"    "green"

[[45]]
[1] "red"    "blue"   "orange" "green" 

[[46]]
[1] "blue"   "red"    "orange" "green"

[[47]]
[1] "red"    "yellow" "orange" "green"

[[48]]
[1] "blue"   "yellow" "orange" "green"

[[49]]
[1] "red"    "purple" "orange" "green"

[[50]]
[1] "blue"   "purple" "orange" "green"

[[51]]
[1] "red"    "blue"   "purple" "green"

[[52]]
[1] "orange" "blue"   "purple" "green"

[[53]]
[1] "blue"   "red"    "purple" "green"

[[54]]
[1] "orange" "red"    "purple" "green"

[[55]]
[1] "red"    "yellow" "purple" "green" 

[[56]]
[1] "blue"   "yellow" "purple" "green"

[[57]]
[1] "orange" "yellow" "purple" "green"

- 递归

可能更有效的方法是使用递归，通过定义自定义函数，以便在生成路径的过程中跳过所有可能的重复项

nodes_lst <- list(nodes_set_1, nodes_set_2, nodes_set_3, nodes_set_4)

f <- function(k = length(nodes_lst)) {
    if (k == 1) {
        return(as.list(nodes_lst[[k]]))
    }
    p <- nodes_lst[[k]]
    unlist(
        lapply(
            Recall(k - 1),
            \(x) Map(`c`, list(x), setdiff(p, x))
        ),
        recursive = FALSE
    )
}

您只需运行

f()
即可获得

> f()
[[1]]
[1] "red"    "green"  "blue"   "orange"

[[2]]
[1] "red"    "green"  "orange" "blue"

[[3]]
[1] "red"    "green"  "purple" "orange"

[[4]]
[1] "red"    "green"  "purple" "blue"

[[5]]
[1] "red"    "blue"   "green"  "orange"

[[6]]
[1] "red"    "blue"   "orange" "green"

[[7]]
[1] "red"    "blue"   "purple" "orange"

[[8]]
[1] "red"    "blue"   "purple" "green"

[[9]]
[1] "red"    "yellow" "blue"   "orange"

[[10]]
[1] "red"    "yellow" "blue"   "green"

[[11]]
[1] "red"    "yellow" "green"  "orange"

[[12]]
[1] "red"    "yellow" "green"  "blue"

[[13]]
[1] "red"    "yellow" "orange" "blue"

[[14]]
[1] "red"    "yellow" "orange" "green"

[[15]]
[1] "red"    "yellow" "purple" "orange"

[[16]]
[1] "red"    "yellow" "purple" "blue"

[[17]]
[1] "red"    "yellow" "purple" "green"

[[18]]
[1] "red"    "purple" "blue"   "orange"

[[19]]
[1] "red"    "purple" "blue"   "green"

[[20]]
[1] "red"    "purple" "green"  "orange"

[[21]]
[1] "red"    "purple" "green"  "blue"

[[22]]
[1] "red"    "purple" "orange" "blue"

[[23]]
[1] "red"    "purple" "orange" "green"

[[24]]
[1] "blue"   "green"  "red"    "orange"

[[25]]
[1] "blue"   "green"  "purple" "orange"

[[26]]
[1] "blue"   "red"    "green"  "orange"

[[27]]
[1] "blue"   "red"    "orange" "green"

[[28]]
[1] "blue"   "red"    "purple" "orange"

[[29]]
[1] "blue"   "red"    "purple" "green"

[[30]]
[1] "blue"   "yellow" "green"  "orange"

[[31]]
[1] "blue"   "yellow" "red"    "orange"

[[32]]
[1] "blue"   "yellow" "red"    "green"

[[33]]
[1] "blue"   "yellow" "orange" "green"

[[34]]
[1] "blue"   "yellow" "purple" "orange"

[[35]]
[1] "blue"   "yellow" "purple" "green"

[[36]]
[1] "blue"   "purple" "green"  "orange"

[[37]]
[1] "blue"   "purple" "red"    "orange"

[[38]]
[1] "blue"   "purple" "red"    "green"

[[39]]
[1] "blue"   "purple" "orange" "green"

[[40]]
[1] "orange" "green"  "red"    "blue"

[[41]]
[1] "orange" "green"  "purple" "blue"

[[42]]
[1] "orange" "blue"   "red"    "green"

[[43]]
[1] "orange" "blue"   "purple" "green"

[[44]]
[1] "orange" "red"    "blue"   "green" 

[[45]]
[1] "orange" "red"    "green"  "blue"

[[46]]
[1] "orange" "red"    "purple" "blue"

[[47]]
[1] "orange" "red"    "purple" "green"

[[48]]
[1] "orange" "yellow" "blue"   "green"

[[49]]
[1] "orange" "yellow" "green"  "blue"

[[50]]
[1] "orange" "yellow" "red"    "blue"

[[51]]
[1] "orange" "yellow" "red"    "green"

[[52]]
[1] "orange" "yellow" "purple" "blue"

[[53]]
[1] "orange" "yellow" "purple" "green"

[[54]]
[1] "orange" "purple" "blue"   "green"

[[55]]
[1] "orange" "purple" "green"  "blue"

[[56]]
[1] "orange" "purple" "red"    "blue"

[[57]]
[1] "orange" "purple" "red"    "green"

基准

microbenchmark(
    grid = Filter(Negate(anyDuplicated), asplit(unname(expand.grid(nodes_lst)), 1)),
    recur = f(),
    unit = "relative"
)

表演

Unit: relative
  expr      min       lq     mean   median       uq       max neval
  grid 2.294061 2.164969 2.127688 2.167528 2.259993 0.8629289   100
 recur 1.000000 1.000000 1.000000 1.000000 1.000000 1.0000000   100
最新问题
© www.soinside.com 2019 - 2024. All rights reserved.