I want to obtain a list of "connected groups" in a graph. Here is an example:

library(igraph)
G <- graph(c(1,2,2,3,2,5,4,5,5,6,4,7,4,8,7,8,8,9), directed=F)
plot(G)

I would like to get all possible paths between two leaf nodes:

[1] 1 2 3
[2] 1 2 5 6
[3] 1 2 5 4 8 9
[4] 1 2 5 4 7 8 9
[5] 3 2 5 6
[6] 3 2 5 4 8 9
[7] 3 2 5 4 7 8 9
[8] 6 5 4 7 8 9
[9] 6 5 4 8 9

I am using R. Thank you for your help.

CodePudding user response：

I'm not quite sure what the exact logic here is, but you seem to want to get the paths from each of the leaf nodes to all the other leaf nodes. We can write a helper function to do that.

get_leaf_paths <- function(G) {
  leafs <- V(G)[degree(G)==1]
  do.call("c", lapply(1:(length(leafs)-1), function(i) {
    all_simple_paths(G,leafs[[i]], leafs[[-(1:i)]])
  }))  
}

Basically we find the leaf node by looking for those that are connected to only one other node, then we call all_simple_paths for each of those nodes to get connections to all the other leaf nodes. We only look for connections to others further down the list to avoid repeats. Finally we combine the results of all the shortest path calls into one object that will collect all the paths. The output would look like this

get_leaf_paths(G)
# [[1]]
#   3/9 vertices, from 6d0bb8d:
# [1] 1 2 3
# [[2]]
#   7/9 vertices, from 6d0bb8d:
# [1] 1 2 5 4 7 8 9
# [[3]]
#   6/9 vertices, from 6d0bb8d:
# [1] 1 2 5 4 8 9
# [[4]]
#   4/9 vertices, from 6d0bb8d:
# [1] 1 2 5 6
# [[5]]
  7/9 vertices, from 6d0bb8d:
# [1] 3 2 5 4 7 8 9
# [[6]]
#   6/9 vertices, from 6d0bb8d:
# [1] 3 2 5 4 8 9
# [[7]]
#   4/9 vertices, from 6d0bb8d:
# [1] 3 2 5 6
# [[8]]
#   6/9 vertices, from 6d0bb8d:
# [1] 6 5 4 7 8 9
# [[9]]
#   5/9 vertices, from 6d0bb8d:
# [1] 6 5 4 8 9