МАТЛАБ: Как найти узлы, которые находятся в любом цикле в ориентированном графе?

Question

Допустим, матрица смежности ориентированного графа A задается как

0     1     0     0
1     0     0     0
0     1     0     0
0     0     0     1

Тогда узлы в любом цикле

1 (1->2->1)
2 (2->1->2)
4 (4->4)

Есть ли эффективный способ получить список узлов в любом цикле?

Я знаю суммирование A, A ^ 2, A ^ 3, A ^ 4 ... и поиск ненулевых диагональных произведений, но я работаю над многомерной матрицей, и это занимает слишком много времени.

Спасибо.

Answer 1

Вы можете использовать dfsearch с опцией edgetodiscovered, чтобы найти начальный и конечный узлы всех циклов. Затем используйте цикл, чтобы найти shortest path от конечного узла до начального узла:

G = digraph(A);
e = dfsearch(G, 1, 'edgetodiscovered', 'Restart', true);
n = size(e,1);
result = cell(1,n);
for k = 1:n
    result{k} = shortestpath(G, e(k,2), e(k,1), 'Method', 'unweighted');
end

Чтобы избежать цикла, вы можете создать фиктивный узел и добавить ребра из этого узла во все конечные узлы циклов. Затем используйте shortestpathtree, чтобы найти кратчайшие пути от фиктивного узла до начальных узлов циклов. Обратите внимание, что каждый путь в результате начинается с фиктивного узла, который должен быть удален из пути.

G = digraph(A);
e = dfsearch(G, 1, 'edgetodiscovered', 'Restart', true);
n = size(e,1);
dummy = numnodes(G) + 1;
G = addedge(G, repmat(dummy, n, 1) , e(:,2));
result = shortestpathtree(G, dummy , e(:,1), 'OutputForm', 'cell', 'Method', 'unweighted');