Я предполагаю, что вас интересуют только пути, которые не проходят через какой-либо узел дважды, за исключением того, что начало равно концу. Немного поработав, вы можете сделать это в igraph, используя all_simple_paths. Ключевым моментом, на который следует обратить внимание, является то, что любой замкнутый цикл без повторяющихся узлов - это простой путь от вершины v до одного из соседей v, за которым следует одиночная ссылка от соседа обратно до v. Я покажу, как получить все простые замкнутые такие циклы начинаются и заканчиваются одним узлом. Вы можете просто перебрать все узлы, если хотите, чтобы все примеры были на графике.
Для начала нам нужны примеры данных.
library(igraph)
set.seed(1234)
g = erdos.renyi.game(8,0.35)
plot(g)
Я получу закрытые циклы, начинающиеся и заканчивающиеся на узле 8, потому что этот узел показывает интересные проблемы.
V = 8
SP = all_simple_paths(g, from=V, to=neighbors(g, v=V))
Мы не хотим включать пути, которые просто идут к соседу и обратно (например, 8-2-8), поэтому мы исключаем пути только одной ссылкой.
SP2 = SP[sapply(SP, function(p) length(p)> 2)]
В зависимости от того, что вы хотите, мы можем сделать здесь, но я подозреваю, что вы не хотите, чтобы путь и один и тот же путь были наоборот, например Я думаю, что вы не хотите, как 8-2-5-8 и 8-5-2-8. Мы можем избавиться от этих дубликатов, настаивая на том, что первый сосед (второй узел в пути) имеет меньший индекс, чем последний.
SP3 = SP2[sapply(SP2, function(p) p[2] < p[length(p)])]
Но мы также прекратили возврат к первому узлу, поэтому мы добавляем первый узел в конец каждого пути.
SP4 = lapply(SP3, function(p) c(unclass(p), V))
SP4
[[1]]
[1] 8 2 5 8
[[2]]
[1] 8 2 5 4 8
[[3]]
[1] 8 2 5 7 3 4 8
[[4]]
[1] 8 4 3 7 5 8
[[5]]
[1] 8 4 5 8