时间戳

首页 > 解决方案 > 使用 igraph、network 或其他 R 包计算有向无环图的所有生成树

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

问题描述

我想计算图表的完整生成树集。我正在使用的图表很小（通常少于 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，并计算 T 上任何两个共享 G 中的链接的节点之间的平均距离t = E [ H T ]。失真衡量T如何扭曲G中的链接，即如果我们限制使用T ，它衡量从G中的链接的一侧到另一侧需要多少额外的跳数。失真被定义为 [13] 是所有可能的T s中最小的这种平均值。直观上，失真衡量了一个图的树状程度。

[13] RGH Tagmunarunkit 和 S. Jamin，“网络拓扑生成器：基于度数与结构性”，SIGMCOMM，2002 年。

标签： rdistanceigraphgraph-theory

解决方案

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

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

此外，计算或枚举给定图的所有生成树的问题是#P-Complete，它与 NP-Complete 问题一样难。

如果您真的愿意这样做，我建议您放弃 R 并开始使用 C 或 C++，它可以比任何 R 代码更快地计算您的问题。
看看这篇论文，对计算连通图的所有生成树的算法进行调查（我认为这是你的情况）。

推荐阅读