在树图中获取 parents 向量的最快方法

Question

给定一个像这样的树图：

library(igraph)
g <- sample_pa(1000, power=1, directed=FALSE)
nodes <- V(g)[-1] # exclude root node since it has no parent.

最快获取每个节点的 parent 的方法是什么？

我目前使用的是：

parents <- unlist(adjacent_vertices(g, nodes, mode = c("out")))

但这实际上是我的代码瓶颈之一，因为我需要对数千个图（每个约 50 个顶点）执行此操作。

Answer 1

首先，让我们在较小的图表上尝试一下，以便我们了解发生了什么：

library(igraph)
set.seed(144)
g <- sample_pa(20, power=1, directed=FALSE)
plot(g)

在你的图表中，每个节点都有一个父节点，所以我希望一个长度为 n-1 的向量用于具有 n 个节点的图表（在本例中为 19，在你提供的示例中为 999 ).你可以从边缘列表中高效地获取，选择第一列：

get.edgelist(g)[,1]
# [1] 1 1 2 3 3 2 4 1 6 1 9 6 2 6 2 1 1 8 7

从视觉上我们可以确认节点2的父节点是节点1，节点3的父节点是节点1，节点4的父节点是节点2，节点5的父节点是节点3，以此类推。

这将比对大图使用 adjacent_vertices 的方法更有效。例如，在您的大小为 1,000 的图形上，速度大约快 1,700 倍：

set.seed(144)
g <- sample_pa(1000, power=1, directed=FALSE)
nodes <- V(g)[-1] # exclude root node since it has no parent.
library(microbenchmark)
microbenchmark(get.edgelist(g)[,1], unlist(adjacent_vertices(g, nodes, mode = c("out"))))
# Unit: microseconds
#                                                  expr        min         lq        mean     median         uq        max neval
#                                  get.edgelist(g)[, 1]     84.558    110.891    262.4235    125.497    169.947   9673.282   100
#  unlist(adjacent_vertices(g, nodes, mode = c("out"))) 303523.390 350459.141 455860.3464 444960.802 528314.593 754882.895   100

此外，您的示例 returns 本示例中长度为 1,965 的向量甚至认为该图有 999 条边。这是因为大多数边由您的代码返回两次，每个端点一次。

如果您真的希望所有 1,965 个值都完全按照您在问题中提供的代码中返回，您仍然可以使用 get.edgelist:

显着加快操作速度（750 倍）

match.op.output <- function(g) {
  el <- get.edgelist(g)
  el <- rbind(el, el[,2:1])
  el <- el[order(el[,1], el[,2]),]
  el[el[,1] != 1,2]
}
all.equal(match.op.output(g), unlist(adjacent_vertices(g, nodes, mode = c("out"))))
# [1] TRUE
microbenchmark(match.op.output(g), unlist(adjacent_vertices(g, nodes, mode = c("out"))))
# Unit: microseconds
#                                                  expr        min          lq       mean    median          uq        max neval
#                                    match.op.output(g)    541.416    585.5115    692.889    652.18    744.0785   1437.427   100
#  unlist(adjacent_vertices(g, nodes, mode = c("out"))) 382952.446 429673.4950 507641.095 486633.23 554715.5570 749883.994   100

在树图中获取 parents 向量的最快方法

Fastest way to get vector of parents in a tree graph

r

igraph