Determine source vertices and find all paths to a target vertex

Question

Given the following directed graph:

g <- make_graph(c("k","z", "x","z", "z","d", "z","a", "a","b",
                  "b","c", "d","e", "e","c", "c","f", "f","g"), directed = TRUE)

plot(g)

I would like to get all the paths from the two source vertices, "x" and "k", which lead to the target vertex "c", without specifying the source vertices at the beginning of the paths.

Expected result:

path 1: k -> z -> a -> b -> c

path 2: x -> z -> d -> e -> c

At the moment I have figured out how to get all the vertices to the "c" vertex by using subcomponent:

subcomponent(g, "c", mode = "in")

Which is not what I'm looking for.

I've tried this: all_simple_paths(g, from = "c", to = V(g), mode = "in") — Dario Federici, Jul 08 '19 at 06:52
Yes but how can I automatically detect x and k as ends of the paths ? — Dario Federici, Jul 08 '19 at 06:59
Are you looking for the paths to "c" from the 'roots' of the graph? Something like this might be relevant: https://stackoverflow.com/q/47519204/1222578 — Marius, Jul 08 '19 at 07:00
[All paths in directed tree graph from root to leaves in igraph R](https://stackoverflow.com/questions/31406328/all-paths-in-directed-tree-graph-from-root-to-leaves-in-igraph-r). Thus, to detect x and k: `from = V(g)[degree(g, v = V(g), mode = "in") == 0]`. Then `lapply(from, function(v) all_simple_paths(g, from = v, to = "c"))`. What are the rules to distinguish between `k z d e c` vs `k z a b c`, and `x z d e c` vs `x z a b c`? — Henrik, Jul 08 '19 at 08:21
Henrik you've solved it thanks. Please post it as the answer if you want — Dario Federici, Jul 08 '19 at 21:49

Henrik · Accepted Answer · 2019-07-09T11:21:15.520

This question is highly related to All paths in directed tree graph from root to leaves in igraph R . The basic methods are the same, but here paths are determined from several source vertices.

Calculate degree of vertices for incoming edges (mode == "in"). To identify source vertices, check if degree equals zero. Use the resulting logical vector to index vertices (V(g)[...]).

from <- V(g)[degree(g, v = V(g), mode = "in") == 0]
from
# + 2/10 vertices, named, from 6cff414:
# [1] k x

Loop over source vertices to find all simple paths from each source to "c":

lapply(from, function(v) all_simple_paths(g, from = v, to = "c")) 

# $k
# $k[[1]]
# + 5/10 vertices, named, from 6cff414:
# [1] k z d e c
# 
# $k[[2]]
# + 5/10 vertices, named, from 6cff414:
# [1] k z a b c
# 
# 
# $x
# $x[[1]]
# + 5/10 vertices, named, from 6cff414:
# [1] x z d e c
# 
# $x[[2]]
# + 5/10 vertices, named, from 6cff414:
# [1] x z a b c

OP has not provided any rule to distinguish between the two alternative paths for each source vertex.

Determine source vertices and find all paths to a target vertex

1 Answers1