Как получить список краев сильно связанных компонентов в графе?

Question

У меня есть взвешенный направленный мультиграф с несколькими циклами. С помощью функции clusters в пакете igraph я могу получить узлы, принадлежащие сильно связанным компонентам. Но мне нужен путь/порядок узлов, которые образуют цикл.

EDIT после @ josilber Ответные

У меня очень плотный график, с 30 узлами и около 2000 ребер. Так что graph.get.subisomorphisms.vf2 занимает слишком много времени, чтобы работать в моем случае.

Я не знаком с алгоритмом графа, но я думаю, что, возможно, сделать DFS в исходном или обратном графике, и использовать order или order.out может работать, но не уверен.

Или любые другие идеи для ускорения этого запуска приветствуются!

Пример

library(igraph) 
set.seed(123) 
graph <-graph(c(1,2,1,2,2,3,3,4,4,5,5,6,6,7,7,8,8,9,8,10,9,10,9,10,10,11,10,5,11,12,12,13,13,14,14,15,14,20,15,16, 16,17,17,18,18,19,19,20,20,21,21,1,22,23,22,23,23,22),directed=T) 
E(graph)$weight= runif(ecount(graph),0,10) 

> clusters(graph, "strong") 
$membership 
[1] 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 1 1 

$csize 
[1] 2 21 

$no 
[1] 2 

Как получить список края цикла с наибольшим весом здесь? Благодаря!

Answer 1

Предполагая, что все узлы в каждом сильно соединенном компоненте образуют цикл и что вас интересует только этот большой цикл (например, в вашем примере вас интересует только цикл с узлами 1:21 и цикл с узлами 22:23), вы можете извлечь порядок узлов, который формирует цикл, захватить веса по краям и вычислить общий вес цикла.

# Compute the node order of the cycle for each component by performing an 
# isomorphism with a same-sized directed ring graph 
clusts <- clusters(graph, "strong") 
(cycles <- lapply(1:clusts$no, function(x) { 
    sg <- induced.subgraph(graph, clusts$membership == x) 
    n <- sum(clusts$membership == x) 
    col <- rep(c(1, 0), c(1, n-1)) # Used to grab isomorphism starting at 1 
    sg.idx <- graph.get.subisomorphisms.vf2(sg, graph.ring(n, directed=TRUE), col, col)[[1]] 
    which(clusts$membership == x)[sg.idx] 
})) 
# [[1]] 
# [1] 22 23 
# 
# [[2]] 
# [1] 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 

Теперь вы можете получить сумму весов ребер для каждого цикла:

sapply(cycles, function(x) sum(graph[from=x, to=c(tail(x, -1), x[1])])) 
# [1] 8.833018 129.959437 

Следует отметить, что это в целом NP-трудной, так как нахождение гамильтонова цикла в целом график NP- жесткий. Поэтому вызов graph.get.subisomorphisms.vf2 может быть довольно медленным для больших графиков.