Определить петли внутри карты зависимостей

Question

Я работаю над драгоценным камнем под названием ActiveTouch. Он предназначен для создания сложных сетей с неактивным доступом или кэш-памяти. В настоящее время я пытаюсь определить способ идентификации циклов в сети.

Упрощенная версия карты зависимостей - это хеш, где ключ представляет модель, а значение представляет собой модели, которые были затронуты.

Например

{ 
    A => [B, C], 
    B => [D, F], 
    D => [A] 
} 

В этом примере мы можем видеть, что есть петля зависимость между А и D, A-> B-> D-> А или D-> A-> B-> D

Чтобы определить цикл, мне нужно увидеть все возможные пути. Как я могу увидеть все возможные пути, как это:

[ 
    [A, B, D, A], 
    [A, B, F], 
    [A, C], 
    ... 
    [D, A, B, D] 
] 

Ответ на Ruby, было бы здорово, но на любом языке будет достаточно.

Answer 1

В основном ваш вопрос сводится к поиску петли на графике.

У вас уже есть ваш график здесь, как adjacency list representation. Циклы обнаружения - это standard procedure и могут быть выполнены с помощью алгоритма DFS. Вы начинаете с некоторой вершины и запускаете DFS, пока не увидите две вершины дважды.

Если вы отключили график, вы делаете это на всех компонентах.