How to get all possible paths between leaf nodes in a graph?

user_13438149 0
Viewed 157

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.

igraph graph-theory r
2 Answers

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
user_23720640

Maybe we follow the steps below:

  1. Filter all leaves based on their degree
  2. Enumerate all combinations of leaves using combn
  3. Produce a list of all_simple-paths for every paired leaves

You can try this

unlist(
  combn(
    V(G)[degree(G) == 1],
    2,
    function(x) all_simple_paths(G, x[1], x[2]),
    simplify = FALSE
  ),
  recursive = FALSE
)

which gives

[[1]]
+ 3/9 vertices, from 27e9df3:
[1] 1 2 3

[[2]]
+ 4/9 vertices, from 27e9df3:
[1] 1 2 5 6

[[3]]
+ 7/9 vertices, from 27e9df3:
[1] 1 2 5 4 7 8 9

[[4]]
+ 6/9 vertices, from 27e9df3:
[1] 1 2 5 4 8 9

[[5]]
+ 4/9 vertices, from 27e9df3:
[1] 3 2 5 6

[[6]]
+ 7/9 vertices, from 27e9df3:
[1] 3 2 5 4 7 8 9

[[7]]
+ 6/9 vertices, from 27e9df3:
[1] 3 2 5 4 8 9

[[8]]
+ 6/9 vertices, from 27e9df3:
[1] 6 5 4 7 8 9

[[9]]
+ 5/9 vertices, from 27e9df3:
[1] 6 5 4 8 9
user_121587570
Related