Свести циклический граф к дереву (граф зависимостей -> дерево)

Question

Я анализирую некоторый код на предмет его зависимостей.Допустим, есть некоторые взаимосвязанные зависимости, например:

                 F
      A         /|
      |        / |
      |       /  |
      V      <   V
      B<--->C--->E
       \   /     |
        > <      |
         D<------+

B зависит от A, а CC зависит от B, а FE зависит от C, а FD зависит от B и C, а E

Weесть проблемы с B и C, они зависят друг от друга.Они должны быть объединены в супер-узел.У нас проблемы с C и E и F, у них есть цикл.Они должны быть объединены в супер-узел.

В итоге вы получите

  A
  |
  V
super
 node
  |
  |
  D

Есть ли хороший источник библиотеки или алгоритма (Java предпочтен, но открыт для предложений), который позволяеттакое сокращение?

Любые узлы в цикле объединяются в один узел.Любой узел, который указал на любой узел в новом узле, должен указывать на новый узел.Любой узел, на который указывает любой узел в новом узле, должен заставить новый узел указывать на этот узел.

Спасибо!

Answer 1

Я полагаю, вы просите объединить сильно связанные компоненты графика. Да?

Я не помню алгоритм, постараюсь найти его.

Редактировать: Мы узнали Тарьяна. Я не помню этого достаточно хорошо, чтобы преподавать, но вот страница Википедии .

Я постараюсь дать основную идею. Дайте каждому узлу индекс #. Затем дайте каждому узлу низкочастотную связь #. Нижняя ссылка - это индекс узла в корне от нас: первый рассматриваемый узел, который может найти путь к нам. Если наша lowlink == наш индекс, то мы являемся корнем сильно связанного компонента. В противном случае мы находимся в том же компоненте, что и наша нижняя ссылка. Делая это по всему графу, мы можем определить, какие узлы являются частями каких сильно связанных компонентов.