使用 igraph 对象递归循环邻居

Question

感谢任何指向以下所需输出的指针。我知道我需要进行某种形式的递归，但确定如何准确地做到这一点。

我有以下代码

>> start of code
# BOM data
library("dplyr")
library(igraph)

text1 <- ("
          matnr,comp
          FG1,SA1
          FG1,SA2
          SA1,SA3
          SA1,SA4
          SA1,SA5
          SA5,SA6
          FG2,SA1
          FG2,SA8
          SA8,SA9
          SA9,SA10
          SA9,SA11")

df1 <- read.table(textConnection(text1),  header = TRUE, stringsAsFactors=FALSE, strip.white = TRUE, sep=",")
head(df1)
net <- graph_from_data_frame(df1)
net
neighbors_FG1 <- neighbors(net, v=c("FG1"), mode=c("out"))
neighbors_FG1

neighbors_FG2 <- neighbors(net, v=c("FG2"), mode=c("out"))
neighbors_FG2            

neighbors_SA1 <- neighbors(net, v=c("SA1"), mode=c("out"))
neighbors_SA1

>> end of code

我希望能够生成如下所示的数据框。我认为这需要某种递归，我想获得这方面的帮助。如果您甚至可以帮助我如何获得下面的输出，那就太好了。

FG,level,material,Comp  
FG1,1,FG1,SA1  
FG1,1,FG1,SA2  
FG1,2,SA1,SA3  
FG1,2,SA1,SA4  
FG1,2,SA1,SA5  
FG1,3,SA5,SA6  
FG2,1,FG2,SA1  
FG2,1,FG2,SA8  
FG2,2,SA8,SA9  

Answer 1

这是一个

igraph

选项

lst <- lapply(
  names(V(net))[degree(net, mode = "in") == 0],
  function(x) {
    d <- Filter(
      is.finite,
      setNames(
        c(distances(net, x, mode = "out") + 1),
        names(V(net))
      )
    )
    cbind(
      FG = x,
      merge(
        setNames(get.data.frame(
          induced_subgraph(
            net,
            names(d)
          )
        ), c("matnr", "comp")),
        setNames(
          rev(stack(d)),
          c("matnr", "lvl")
        )
      )
    )
  }
)

res <- `row.names<-`(
  subset(
    do.call(rbind, lst),
    ave(seq_along(matnr), matnr, comp, lvl, FUN = seq_along) == 1
  ), NULL
)

这给出了

> res
    FG matnr comp lvl
1  FG1   FG1  SA1   1
2  FG1   FG1  SA2   1
3  FG1   SA1  SA3   2
4  FG1   SA1  SA4   2
5  FG1   SA1  SA5   2
6  FG1   SA5  SA6   3
7  FG2   FG2  SA1   1
8  FG2   FG2  SA8   1
9  FG2   SA8  SA9   2
10 FG2   SA9 SA10   3
11 FG2   SA9 SA11   3

Answer 2

我用

tidyverse

、

igraph

和

tidygraph

来解决这个问题：

1. 转换

   net

   的类型，以便可以通过 TidyGraph 包操作

gr <- as_tbl_graph(net)

2. 获取一个包含节点名称及其顺序之间对应关系的向量。

name_vector <- gr %>%
  activate(nodes) %>% 
  as_tibble() %>%
  as_vector()

3. 定义用于策略搜索的节点

start_node = 1 # The first node is FG1

4. 生成你想要的变量：

temp <- gr %>%
  activate(nodes) %>%
  mutate(
    # Get the nodes from which each node is visited in a breath first search
    material = bfs_parent(root = start_node), 
    # Get the succession in which the nodes are visited in a depth first search
    level = bfs_dist(root = start_node)) %>%
  as_tibble() %>%
  drop_na() %>%
  rename(Comp = name)

5. 用名字替换订单

temp <- temp %>%
  mutate(FG = name_vector[start_node],
         material = name_vector[material])

这就是结果：

> temp %>% arrange(level)
# A tibble: 6 x 4
  Comp  material level FG   
  <chr> <chr>    <int> <chr>
1 SA1   FG1          1 FG1  
2 SA2   FG1          1 FG1  
3 SA5   SA1          2 FG1  
4 SA3   SA1          2 FG1  
5 SA4   SA1          2 FG1  
6 SA6   SA5          3 FG1    

根据上面的代码，我们找到了所有

start_node = 1

的情况。
您可以使用循环重新定义

start_node

并将这些结果组合在一起。

Answer 3

我们可以使用

neigborhood()

来代替

igraph::ego()

来获取节点向量 可以从感兴趣的节点到达。结合

igraph::induced_subgraph()

和

igraph::distances()

我们可以获得您的所有信息 正在找。请参阅下面如何组装它们。

purrr

有

map_dfr()

，其工作方式类似于

lapply()

，但它也会在结果

bind_rows()

上执行

list

。

library(purrr)
#> 
#> Attaching package: 'purrr'
#> The following objects are masked from 'package:igraph':
#> 
#>     compose, simplify

我们现在创建一个由我们想要描述其邻域的所有节点组成的向量。

FGs <- c("FG1", "FG2")  

我们将该向量输入

map_dfr()

，对

~{...}

中的每个值执行

FGs

中定义的函数。

res <- map_dfr(FGs, ~{
  
  # Inside the function we first extract the subgraph that is reachable by
  # outgoing edges from our node of interest.
  
  sub_g <- induced_subgraph(net, 
                            ego(net, 
                                order = diameter(net), 
                                nodes=.x, 
                                mode=c("out"))[[1]])
  
  # We then calculate the distances from our node of interest to
  # all other nodes, transform the distances to a data.frame/tibble and
  # join it with the edgelist of the subgraph.
  
  distances(sub_g, .x) %>% 
    t() %>% 
    as_tibble(rownames = "Comp") %>% 
    inner_join(as_data_frame(sub_g), by = c("Comp" = "to")) %>% # Join with edgelist
    mutate(FG = .x) %>% 
    dplyr::select(FG, level = 2, material = from, Comp)
}) %>% 
  arrange(FG, level)

结果：

res
#> # A tibble: 15 x 4
#>    FG    level material Comp 
#>    <chr> <dbl> <chr>    <chr>
#>  1 FG1       1 FG1      SA1  
#>  2 FG1       1 FG1      SA2  
#>  3 FG1       2 SA1      SA5  
#>  4 FG1       2 SA1      SA3  
#>  5 FG1       2 SA1      SA4  
#>  6 FG1       3 SA5      SA6  
#>  7 FG2       1 FG2      SA1  
#>  8 FG2       1 FG2      SA8  
#>  9 FG2       2 SA1      SA5  
#> 10 FG2       2 SA8      SA9  
#> 11 FG2       2 SA1      SA3  
#> 12 FG2       2 SA1      SA4  
#> 13 FG2       3 SA5      SA6  
#> 14 FG2       3 SA9      SA10 
#> 15 FG2       3 SA9      SA11

Answer 4

执行 ThomasIsCoding 答案后的补充（2021 年 5 月 28 日 8:25）

（正如您问@ThomasIsCoding，即使答案的核心是您的:)在我阅读您的答案之前，我已经在特定时间内寻找答案）

gNew<- igraph::graph_from_data_frame(res %>% select(matnr,comp,lvl,FG), directed = TRUE)

在我的真实案例中，我有一个巨大的图表，所以在我真实的 POC 中，也许在我的应用程序中，我将 vapply

names(V(net))[degree(net, mode = "in") == 0]

的第一个参数替换为

c("FG1","FG2")

，所以在我的案例中

gNew

将是一个子图。

igraph 图表

plot(gNew, layout = layout_as_tree(gNew))

交互式可视网络图

edges<-setNames( as.data.frame (
  igraph::as_edgelist(gNew, names = TRUE) ),
  c("to","from")
)

nodes<-bind_rows( 
  edges %>% transmute(id=from,label=id),
  edges %>% transmute(id=to,label=id)  ) %>% unique(.) 

(visNetwork::visNetwork(
  nodes, 
  edges, 
  heigh="1000px", 
  width = "1000px")
  %>% visNetwork::visEdges(arrows = "from") 
  %>% visNetwork::visHierarchicalLayout(
    direction = "DU", 
    sortMethod="directed",
    shakeTowards ="leaves")
)