代码之家 › 专栏 › 技术社区 › gss

如何找到“直接”连接的组件?

igraph graph-theory r

gss · 技术社区 · 3 年前

我不知道图论,所以我担心问题的标题不是属性公式化的,所以我将展示一个代码:

library(magrittr)
library(igraph)

df <- data.frame(from = c(1, 1, 2, 2, 6),
                 to = c(2, 4, 3, 5, 3))

graph_from_data_frame(df) %>% 
  components() %>% 
  membership() %>% 
  stack()
#>   values ind
#> 1      1   1
#> 2      1   2
#> 3      1   6
#> 4      1   4
#> 5      1   3
#> 6      1   5


# find only "direct" paths

data.frame(values = c(1, 1, 2, 1, 1, 1, 2),
           ind = c(1, 2, 6, 4, 3, 5, 3))
#>   values ind
#> 1      1   1
#> 2      1   2
#> 3      2   6
#> 4      1   4
#> 5      1   3
#> 6      1   5
#> 7      2   3

拥有 data.frame 如上所述,我知道如何找到所有连接的组件,无论它们是如何连接的。但我也希望能够找到上面代码块末尾显示的东西,即“6”不属于组“1”,而是与“3”相连,这就是为什么我重复了“3”——它属于“1”和“2”组。

中有这个函数吗 igraph 或其他包装 R ?但我更喜欢 igraph .这个过程在图论中有名字吗?因此,我将能够找到更多关于这方面的信息。

编辑

谢谢大家的帮助。我发现对于我的用例,我可以使用 igraph::subcomponent() (我以前在的底部没有找到这个函数 igraph::component() 帮助页面),因为一次我只需要为一个选定的顶点找到组件,我知道我是需要找到所有连接的组件,还是只需要找到“简单路径”组件,幸运的是,在第二种情况下,它总是在路径的“末端”(开始?)

df <- data.frame(react_id = c("r1", "r1", "r2", "r2", "r6"),
                 depends_on = c("r2", "r4", "r3", "r5", "r3"))

gdf <- igraph::graph_from_data_frame(df)

# get all connected components for specific react_id

igraph::subcomponent(gdf, "r3", "all") |>
  names()
#> [1] "r3" "r2" "r6" "r1" "r5" "r4"

# get "simple paths" components

igraph::subcomponent(gdf, "r1", "out") |>
  names()
#> [1] "r1" "r2" "r4" "r3" "r5"

1 回复 | 直到 3 年前

Rui Barradas 3 年前

像这样的东西?

suppressPackageStartupMessages(
  library(igraph)
)

df <- data.frame(from = c(1, 1, 2, 2, 6),
                 to = c(2, 4, 3, 5, 3))

g <- df |> graph_from_data_frame()
i <- g |> degree(mode = "out") > 0

lapply(V(g)[i], \(x) all_simple_paths(g, from = x, mode = "out"))
#> $`1`
#> $`1`[[1]]
#> + 2/6 vertices, named, from c3ceef6:
#> [1] 1 2
#> 
#> $`1`[[2]]
#> + 3/6 vertices, named, from c3ceef6:
#> [1] 1 2 3
#> 
#> $`1`[[3]]
#> + 3/6 vertices, named, from c3ceef6:
#> [1] 1 2 5
#> 
#> $`1`[[4]]
#> + 2/6 vertices, named, from c3ceef6:
#> [1] 1 4
#> 
#> 
#> $`2`
#> $`2`[[1]]
#> + 2/6 vertices, named, from c3ceef6:
#> [1] 2 3
#> 
#> $`2`[[2]]
#> + 2/6 vertices, named, from c3ceef6:
#> [1] 2 5
#> 
#> 
#> $`6`
#> $`6`[[1]]
#> + 2/6 vertices, named, from c3ceef6:
#> [1] 6 3

^{创建于2022-09-04由

reprex package

(v2.0.1)}

ThomasIsCoding 3 年前

我想这就是你想要的东西

lapply(
  V(g)[degree(g, mode = "in") == 0],
  function(x) V(g)[!is.infinite(distances(g, x, mode = "out"))]
)

它给出

$`1`
+ 5/6 vertices, named, from d7ae5cb:
[1] 1 2 4 3 5

$`6`
+ 2/6 vertices, named, from d7ae5cb:
[1] 6 3

如果你想将结果保存在data.frame中,你可以尝试

transform(
  stack(
    lapply(
      V(g)[degree(g, mode = "in") == 0],
      function(x) names(V(g)[!is.infinite(distances(g, x, mode = "out"))])
    )
  ),
  ind = as.integer(factor(ind))
)

它给出

  values ind
1      1   1
2      2   1
3      4   1
4      3   1
5      5   1
6      6   2
7      3   2