How to find a "direct" connected components?-CodePudding

I don't know graph theory, so I'm afraid question's title is not property formulated, so I will show a code:

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

Having a data.frame as above, I know how i can find all connected components, no matter "how" they are connected. But I would like also to be able to find something which is shown at the end of the code block above, i.e. that "6" do not belong to the group "1", but is connected with "3", that's why I have repeated "3" - it belongs to group "1" and "2".

Is there a function for this in igraph or other package in R? But I would prefer igraph. And does this procedure have a name in graph theory? So then I will be able to find some more information about this.

EDIT

Thank you all for help. I have found that for my use case I can use igraph::subcomponent() (I didn't find this function before at the bottom of igraph::component() help page), because at one time I need to find components only for one chosen vertex and I know if I need to find all components connected or just "simple paths" components and, luckily, in this second case it is always vertex "at the end" (beginning?) of path

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"

CodePudding user response：

Something like this?

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

^{Created on 2022-09-04 by the reprex package (v2.0.1)}

CodePudding user response：

I guess this is thing you are after

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

which gives

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

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

If you want the result saved in a data.frame, you can try

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))
)

which gives

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