Döngüsel grafiği ağacı azaltın (bağımlılık grafiği -> ağaç)

Question

Bazı kodları bağımlılıkları için analiz ediyorum.

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

B A bağlıdır ve C C C ve D B bağlıdır F ve C ve E

bağlıdır E B ve F bağlıdır : orada bazı örülmüş bağımlılıkları, böylece gibi diyelim

B ve C ile ilgili bir problemimiz var, birbirlerine bağlılar. Süper düğümde birleştirilmelidirler. C ve E ve F ile ilgili bir sorunumuz var, bir döngüye sahipler. Süper düğümde birleştirilmelidirler.

Böyle azaltılması için izin veren iyi bir kütüphane veya algoritma (Java tercih ama önerilerine açık) kaynak var mı

A 
    | 
    V 
super 
node 
    | 
    | 
    D 

ile sona ereceğini?

Bir döngüdeki tüm düğümler tek bir düğümde birleştirilir. Yeni düğümdeki herhangi bir düğüme işaret eden herhangi bir düğüm, yeni düğüme işaret etmelidir. Yeni düğümdeki herhangi bir düğüm tarafından işaret edilen herhangi bir düğüm, yeni düğümün bu düğüme işaret etmesine neden olur.

Teşekkürler!

Answer 1

Grafiğin strongly connected components değerini birleştirmeyi istediğinizi düşünüyorum. Evet?

Algoritmayı hatırlamıyorum, bakmaya çalışacağım.

Düzenleme: Öğrendiğimiz Tarjan'ın. Öğretmek için yeterince iyi hatırlamıyorum ama here is the Wikipedia page.

Temel fikri vermeyi deneyeceğim. Her düğüme bir indeks verin. Sonra her düğüme bir lowlink # verin. Lowlink, bizim tarafımızdan kökteki düğümün indisidir: bize ulaşacak bir yol bulabilecek ilk düğüm. Eğer bizim lowlink == indeksimiz ise, o zaman güçlü bir şekilde bağlı bir bileşenin köküdür. Aksi takdirde, bizim lowlink bizim ile aynı bileşendedir. Bunu tüm grafik üzerinde yaparak, hangi düğümlerin güçlü bir şekilde bağlı bileşenlerin parçası olduğunu belirleyebiliriz.