Определить исходные вершины и найти все пути к целевой вершине

Question

Учитывая следующий ориентированный граф:

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)

Я хотел бы получить все пути из двух исходных вершин, "x"и «k», которые ведут к целевой вершине «c», без указания исходных вершин в начале путей.

Ожидаемый результат:

путь 1: k -> z -> a -> b -> c

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

На данный момент я выяснил, как получить все вершины к вершине "c", используя подкомпонент:

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

не то, что я ищу.

Answer 1

Этот вопрос тесно связан с Все пути в ориентированном графе дерева от корня до листьев в igraph R .Основные методы те же, но здесь пути определяются из нескольких исходных вершин.

Вычисление degree вершин для входящих ребер (mode == "in").Чтобы определить исходные вершины, проверьте, равна ли степень нулю.Используйте полученный логический вектор для индексации вершин (V(g)[...]).

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

Цикл по вершинам источника, чтобы найти все простые пути от каждого источника к "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 не предоставил никакого правила для различия между двумя альтернативнымипути для каждой исходной вершины.