r - igraph:终端(非根)节点位于同一级别的树形图？

Question

我想在 R 中使用 igraph 绘制一个树形图，使所有终端节点都处于同一级别，这与默认情况下所有根节点都处于同一级别不同。

layout_as_tree 有一种基于根节点的方法可以做到这一点。需要指定它们 (root) 以及它们的级别 (rootlevel)。所以我可以使用这个选项，尽管它似乎涉及一个非常复杂的工作流程:a)将树分成子树b)查找每个子树的根节点c)查找每个子树的最大路径4)指定根第一级相对给别人...

是否有更简单的方法从终端节点开始执行此操作？假设我不知道哪些节点是根节点(1 和 11)，但只知道哪些节点是终端节点(4:11 和 16:20)。

这是一个示例，但我希望终端节点 4、16 和 17 位于最低级别:

library(igraph)
tree2 <- make_tree(10, 3) + make_tree(10, 2)

plot(tree2, layout=layout_as_tree(tree2, root=c(1,11),
                                  rootlevel=c(2, 1)))

^{创建于 2022 年 9 月 23 日 reprex v2.0.2}

Answer 1

当从下往上计算层数时，解变为:

require(igraph)

tree2  <- make_tree(10, 3) + make_tree(10, 2) + edge(1,5)
tree3  <- set_edge_attr(tree2, name="weight", value=-1) # longest path = shortest negative.
dist   <- (-distances(tree3, v=(V(tree3)), mode="out")) # matrix of VxV distances of shortest paths.
layers <- apply(dist, 1, max)                           # maximum distance from bottom to top (max per row).
layers <- max(layers) - layers                          # minimal distance from top    to bottom.

plot(tree3, layout=layout_with_sugiyama(tree3, layers=layers))

如果dist矩阵不适合内存，则必须执行dfs()搜索，计算层。