Yönlendirilmiş Asiklik Grafikler için Diff

Question

İki Yönlü Asiklik Grafikler (DAG'ler) diff olabilir bir algoritma arıyorum. Yani, ikinci DAG'ı üretmek için ilk DAG üzerinde bir dizi silme ve ekleme üreten bir algoritma istiyorum.

Yüzde yüz emin değilim, ancak DAG'lere en sık görülen bir alt dizinin uygulanabileceğini düşünüyorum. Ortaya çıkan düzenleme dizisinin uzunluğu hakkında (daha kısa olduğu sürece) ve algoritmanın çalışma süresi hakkında daha fazla endişeleniyorum.

Tek bir sorun, tek bir kök düğümü haricinde, köşelerimden hiçbirinin etiketlenmemesidir. Kök düğüm ayrıca sıfır kenarlı tek düğümdür. Grafiğin kenarları etiketlenir ve grafikteki 'veriler', kökten yapraklar olan yollarla temsil edilir. Bu bir trie'a benzer, ancak bir ağaç yerine yönlendirilmiş bir grafikle. Aslında benim grafiklerim directed acyclic word graph veri yapısına oldukça benziyor.

İşte bir örnek.

DAG1

DAG 2 almak için

DAG2, sadece etiketin 'b' ile başka tepe için kökten bir köşe noktası eklemek. Bu köşeden DAG 1'deki son 'ac' vertex'in bir kenarı ve etiketi 'd' olan yeni bir köşe çizgisinin bir kenarı vardır. Bu son noktadan itibaren DAG 1'deki 'ac' vertex'inin bir başka kenarı vardır. DAG formundaki diff'e bir link yayınlayacağım, ancak ikiden fazla link yayınlayamıyorum.

Teşekkürler ve umarım bu yeterlidir.

Answer 1

Bu biraz geç olabilir, ancak sadece eğlence için: Her iki DAG'leriniz de matrisler olarak ifade edilebilir, burada "from" vertex'i gösteren satır dizini ve "to" vertex'i gösteren sütun dizini ve kenar kimliği ile etiketlenmiş karşılık gelen hücre. Benzersiz ve rastgele kimlikler vertex.

Sonraki bölüm biraz zor, çünkü yalnızca kenarlarınız DAG1'den DAG2'ye eşlenen anlamlı bir etikete sahip. DAG1 ve DAG2'den etiketli kenarların kesiştiği bir kenar kümesi (E *) olduğunu varsayalım, bir dizi sıra kaydırması (yukarı veya aşağı hareket et) veya sütun kaydırması (sola veya sağa hareket ettir) yapmanız gerekir. DAG1'deki E * 'deki kenarlar ve DAG2 birbiriyle eşleşir. Matrix'te temsil edilen bir DAG için, tüm satırın veya tüm sütunun kaydırma pozisyonunun hala gösterim eşdeğerini oluşturduğunu unutmayın.

kalan işlem iki matrisler karşılaştırma, eşleştirilmiş matrislerine göre köşe adlandırmak ve çıkarılabilir yeni kenarlar ve yeni tepe noktası gerekli (ve kenarları ve köşeleri belirlemek olacaktır.