Efficiently extract duplicate paths with igraph

November 24, 2021

How can one extract duplicate paths from igraph and is there a more efficient way than the double loop in the example below?
The data:

library(dplyr)
library(igraph)

d <- tribble(~input, ~output,
             "A1", "A2",
             "A2", "A3a",
             "A2", "A3b",
             "B1", "B2a",
             "B1", "B2b",
             "B2a", "B3",
             "B2b", "B3")

My analysis:

g <- graph_from_data_frame(d, directed = TRUE)
(finals <- V(g)[degree(g, mode = "out") == 0])
(starts <- V(g)[degree(g, mode = "in") == 0])
res_collect <- vector("list", length(starts) * length(finals))
tmp <- 1
for (i_s in seq_along(starts)) {
  for (i_f in seq_along(finals)) {
    res <- tryCatch(
      {
        all_simple_paths(g, from = starts[[i_s]], to = finals[[i_f]])[[1]]
      },
      error = function(cond) {
        message("failed at starts-nr=", i_s, ", finals-nr=", i_f); return(as.integer(NA))
      }
    )
    res_collect[[tmp]] <- res
    tmp <- tmp + 1
  }
}

The problem:

res_collect[!is.na(res_collect)]
# [[1]]
# + 3/8 vertices, named, from 60df173:
#   [1] A1  A2  A3a
# 
# [[2]]
# + 3/8 vertices, named, from 60df173:
#   [1] A1  A2  A3b
# 
# [[3]]
# + 3/8 vertices, named, from 60df173:
#   [1] B1  B2a B3

1 path is missing: B1 -> B2b -> B3.

>Solution :

You can try the code below

unlist(
  lapply(
    decompose(g),
    function(x) {
      finals <- V(x)[degree(x, mode = "out") == 0]
      starts <- V(x)[degree(x, mode = "in") == 0]
      all_simple_paths(x, starts, finals)
    }
  ),
  recursive = FALSE
)

which gives

[[1]]
+ 3/4 vertices, named, from fb6335c:
[1] A1  A2  A3a

[[2]]
+ 3/4 vertices, named, from fb6335c:
[1] A1  A2  A3b

[[3]]
+ 3/4 vertices, named, from fb6335c:
[1] B1  B2a B3

[[4]]
+ 3/4 vertices, named, from fb6335c:
[1] B1  B2b B3