Reduce cyclic graph to tree (dependency graph-->tree)

I'm analyzing some code for its dependencies. Let's say there are some interwoven dependencies, like so:

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

B depends on A and C C зависит от B и F E зависит от C и F D зависит от B, C и E

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

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

  A
  |
  V
super
 node
  |
  |
  D

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

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

Спасибо!

6
задан corsiKa 31 March 2011 в 23:52
поделиться