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-09-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)                           # max per row
layers <- max(layers) - layers                          # shift down

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

如果

dist

矩阵不适合内存，则必须进行

dfs()

搜索，计算层数。

Answer 2

这是一种更基本的方法。 在此解决方案中，我们通过

depth-first search

搜索图并递归计算每个顶点的层。

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

## Depth-first search.
## Mark node as visited.
## Calculate layers indexed by vertex.
## Layer of v is
##   - equal to zero if there are no descendants and
##   - otherwise the largest layer among the descendants plus 1.
layers <- rep(0L, vcount(tree2))
visit <- function(g, v){
  if (length(visited)>0L && !visited[v]) {
    visited[v] <<- 1L

    max_layer_descendents <- -1L 
    outgoing <- V(g)[.outnei(v)]
    for (w in outgoing) {
      stopifnot(v != w)
      visit(g, w)
      max_layer_descendents <- max(max_layer_descendents, layers[w])
    }

    layers[v] <<- max_layer_descendents + 1L
  }
}

## mark vertices as non-visited and calculate layers
visited <- rep(0L, vcount(tree2))
for (v in V(tree2)) visit(tree2, v)
layers
# [1] 2 1 1 0 0 0 0 0 0 0 3 2 1 1 1 0 0 0 0 0

plot(tree2, layout=layout_with_sugiyama(tree2, layers=max(layers)-layers))

Answer 3

另一种解决方案，但代价是反转所有边：

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

## Calculate x,y coordinates by Sugiyama,
## flip y coordinate, and plot.
lyt     <- layout_with_sugiyama(reverse_edges(tree2))$layout
lyt[,2] <- (1L + max(lyt[,2])) - lyt[,2]
lyt[,2]
plot(tree2, layout=lyt)

这给出了

[1] 3 2 2 1 1 1 1 1 1 1 4 3 2 2 2 1 1 1 1 1

Answer 4

在提供的示例中，计算根和根级别如下：

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

roots <- V(tree2)[which(degree(tree2, mode="in") == 0)]   # no incoming edges
dist      <- distances(tree2, roots)                      # all distances from roots
dist[which(is.infinite(dist))] <- NA                      # remove infinite
rootlevel  <- apply(dist, 1, max, na.rm = TRUE)           # max per row
rootlevel  <- max(rootlevel) - rootlevel + 1              # offset
plot(tree2, layout=layout_as_tree(tree2, root=roots, rootlevel=rootlevel))

如果

dist

矩阵不适合内存，则必须进行

dfs()

搜索，计算层数。