CODEWITHSUNDEEP
rigraph
r.user.05apr
r.user.05apr

Reputation: 5456

Efficiently extract duplicate/multiple paths with igraph

How can one extract duplicate paths from igraph and is there a more efficient way than the double loop in the example below? By duplicate/multiple paths I mean that the result should contain both B1 -> B2a -> B3 and B1 -> B2b -> B3. But my code does not yield that. 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.

Upvotes: 0

Views: 179

Answers (1)

ThomasIsCoding
ThomasIsCoding

Reputation: 102469

You can try the code below

do.call(
  c,
  lapply(
    starts,
    all_simple_paths,
    graph = g,
    to = finals
  )
)

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

Upvotes: 2

Related Questions