递归地使用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)

1. 得到一个向量，该向量包含节点名称与其顺序之间的对应关系。

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

1. 定义要对搜索

进行strat的节点。

start_node = 1 # The first node is FG1

1. 生成所需的变量：

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)

1. 将顺序替换为名称

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()，但它也对生成的list执行bind_rows()。

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