Yönlendirilmiş döngüsel grafik için veri yapısı ve algoritmalar (F #)

Question

derlemesi başvurulan bir uygulamayı analiz etmeye çalışıyorum yönelimli-asiklik bir grafik olmalıdır, ancak değil. Ayrıca, bir alt alt montajın farklı sürümlerini referans alan alt montajlar ile ilgili bir sorun var (think Escher...)

Yapmak istediklerim, her bir montaj-alt montaj çiftini analiz etmek ve herhangi bir şeyin yanlış olduğu bir resim oluşturmaktır.

Bunun için iyi bir veri yapısı olacağına dair bir rehberliğe ihtiyacım var. Değişmez bir yapıya sahip olabileceğime emin değilim, ama içsel olarak değiştirilip sonra değiştirilemez hale geldiğine inanmıyorum.

Sorunun diğer kısmı, veri yapısını doldurmak için kullanmam gereken algoritmaları ve daha sonra da problemleri "analiz etmek" için kullanacağım algoritmalardır.

Answer 1

Ne yapmak istediğiniz "Topolojik sıralama" olarak adlandırılır.

http://en.wikipedia.org/wiki/Topological_sort

Answer 2

sadece NDepend kullanabilirsiniz, sizin meclisleri analiz eder ve bağımlılık döngüleri algılar: Vikipedi iyi bir genel bakış vardır.

Bunu gerçekten yapmak istiyorsanız, bağımlılık grafiklerini modellemek için QuickGraph kullanırım, topolojik sıralama gibi grafik algoritmalarını da içerir.

Answer 3

İçinde içsel olarak değiştirilip sonra değiştirilemez hale getirilmiş olması umrumda değil.

Tümüyle değiştirilemeyen veri yapılarını daha kolay kullanmayı da bulabilirsiniz. Özellikle, bir grafiği, kaynak düğümlerden hedef düğüm kümelerine kadar Map olarak kolayca temsil edebilirsiniz. Topolojik sıralama için, bir hedef düğümün kaynak düğümlerine verimli bir şekilde erişmek istiyorsanız, grafiğinizi başka yöne doğru ilerletmek için başka bir Map ile artırmak isteyebilirsiniz.

Sadece F # Bu uygulamaya ve topolojik sıralama durum biraz aslında benim soru ima daha karmaşıktır, :-) ...