1

我有一个可以被认为是树的非循环图。这是一个简化的示例：

library(tidygraph)
create_tree(20,2, directed = TRUE, mode="in") %>% plot

是

现实生活中的例子可能稍微复杂一些，因为我可能有多个从叶子到根的路径（所有这些路径都是非循环的）。

我想通过删除中间节点来简化图形，如下所示：

K=0

在最极端的情况下（我们称之为“k = 0”简化）我会枚举所有叶子，确保它们通过深度优先搜索连接到根，然后删除所有中间连接，有效地将每个叶子连接到根。

K=-1

下一级简化（比如“k=-1”）我想从至少有一个叶子孩子的节点开始，然后重复相同的过程。简化后，所有中间节点都会被移除：

data.frame(from=c(5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20),
           to = c(1,1,1,1,1, 5, 5, 6, 6, 7, 7, 8, 8, 9, 9,10)) %>% 
  as_tbl_graph() %>% plot

想

K=-2

下一步的简化对这个图没有意义，因为不会修改边，也不会删除节点。

如何在 R 中使用igraph/对其进行编码？tidygraph

4

1 回答 1

0

解决方案最重要的部分是能够枚举从叶子到根的节点，有效地测量“到最近叶子的距离”

使用与上面相同的示例，让我们添加节点名称（create_tree()由于某些奇怪的原因，不生成节点）：

library(tidygraph)

graph <- create_tree(20,2, directed = TRUE, mode="in") %>% 
  activate(nodes) %>% mutate(name=1:n())

我们需要一个辅助函数来测量“到叶子的距离”：

make_levels <- function(grdf){
  i <- 0
  repeate <- TRUE
  # create helper column
  grdf <- grdf %>% 
    mutate(leaf = node_is_leaf(),
           level=ifelse(leaf, i, NA))

  while(repeate){
  i <- i + 1
  index <- grdf %>% activate(edges) %>%
    mutate(from_leaf=.N()$leaf[from]) %>% 
    as_tibble() %>% filter(from_leaf) %>% pull(to)

  grdf <- grdf %>% activate(nodes) %>% 
    mutate(leaf = 1:n() %in% index,
           level=ifelse(leaf & is.na(level), i, level))

  repeate <- grdf %>% activate(nodes) %>% 
    as_tibble() %>% pull(level) %>% is.na() %>% any()
  }
  # remove helper column
  grdf %>% activate(nodes) %>% select(-leaf)    
}

在此之后，解决方案（k=-1以上）应该很容易：

graph %>% make_levels() %>% activate(edges) %>% 
  reroute(from = from, to = 1, subset=(to %in% which(.N()$level==2))) %>% 
  activate(nodes) %>% filter(level!=2) %>% plot()

产生：

完毕

于 2017-11-05T21:55:50.977 回答