使用 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

我用tidyverse、igraph和tidygraph来解决这个问题：

转换 net 的类型，以便它可以被 TidyGraph 包操作

gr <- as_tbl_graph(net)

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

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

定义要进行搜索的节点

start_node = 1 # The first node is FG1

生成你想要的变量：

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)

用名称替换订单

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 2

我们可以使用 igraph::ego() 而不是 neigborhood() 来获取节点向量可以从感兴趣的节点到达。结合 igraph::induced_subgraph() 和 igraph::distances() 我们可以获得您的所有信息正在找。请参阅下文如何 assemble 这一切。 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

Answer 3

这是一个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

使用 igraph 对象递归循环邻居

Recursively looping through neighbors with an igraph object

r

igraph