Подходящий алгоритм, чтобы найти все циклы транзитивного замыкания в графе?

Question

Я хочу найти все циклы транзитивного замыкания в моем графике, имеющие следующие условия:

1. если все узлы, присутствующие в идентифицированном цикле, являются подмножеством другого идентифицированного цикла, то мы рассмотрим только суперсет.
2. найти все различные петли.

ПРИМЕЧАНИЕ: читать «петлю» как -> петлю транзитивного замыкания (то есть узлы в наборе транзитивного замыкания)

Answer 1

Используйте Алгоритм Флойда-Варшалла только для транзитивной части, затем проверьте наличие любых возвратных циклов, поскольку переходные циклы в конце будут представлены как возвратные циклы.