使用 igraph、网络或其他 R 包计算有向无环图的所有生成树

Question

我想计算图形的完整生成树集。我正在使用的图形很小(通常少于 10 个节点)。

我看到了使用igraph计算最小生成树的功能：

library(igraph)
g <- sample_gnp(100, 3/100)
g_mst <- mst(g)

我看到之前的 StackOverflow 帖子描述了如何使用广度优先搜索计算生成树。下面的代码改编自公认的答案：

r <- graph.bfs(g, root=1, neimode='all', order = TRUE, father = TRUE)
h <- graph(rbind(r$order, r$father[r$order, na_ok = TRUE])[,-1], directed = FALSE)

但是，我不知道如何调整它来计算多个生成树。如何调整此代码以计算所有生成树？我认为其中的一部分是遍历每个节点以用作每棵树的"根"，但我认为这不会让我一路走到那里(因为仍然可能有多个生成树与给定的根节点相关联)。

编辑

最终目标是计算图形的失真，其定义如下(链接，请参阅第 5 页)：

考虑图 G 上的任何

生成树 T，并计算在G中共享链路的任何两个节点之间 T 上的平均距离t = E[HT]。失真测量T如何扭曲G中的链接，即 它测量如果我们仅限于使用T，从G中链路的一端到另一端需要多少额外的跃点。 失真被定义为[13]是所有可能的Ts上的最小平均值。直观失真衡量的是图表的树状程度。

[13] R. G. H. 塔格穆纳伦基特和S. Jamin，"网络拓扑生成器：基于度的与 结构"，载于SIGMCOMM，2002年。

Answer 1

我认为您不会在 R 包上找到执行此操作的函数。

图上有 n^{n-2} 生成树(根据凯莱公式)。即使在具有 10 个节点的图形上，也可能存在 1,000,000,000 个不同的生成树，这是一个很大的数字。

此外，对给定图的所有生成树进行计数或枚举的问题是 #P 完全的，这与NP-完全问题一样困难。

如果你真的愿意这样做，我建议放弃 R 并开始使用 C 或 C++，它可以比任何 R 代码更快地计算你的问题。
请查看本文，了解计算连接图的所有生成树的算法(我认为是这种情况)。