Yönlendirilmiş bir grafiği 'serileştirmek' için basit bir algoritma arıyorum. Özellikle, yürütme sırasındaki bağımlılıklara sahip bir dizi dosyam var ve derleme zamanında doğru sırayı bulmak istiyorum. Bunu yapmanın oldukça yaygın bir şey olduğunu biliyorum - derleyiciler bunu her zaman yapıyorlar - ama google-fu'm bugün zayıf. Bunun için 'git' algoritması nedir?Grafik serileştirme
Topological Sort: Grafik Teoride
, topolojik bir sıralama veya yönlendirilmiş asiklik grafik (DAG) topolojik sipariş her düğüm gelir ki burada onun düğüm doğrusal sıralamadır 'un tüm düğümlerinden önce giden kenarları vardır. Her DAG bir veya daha fazla topolojik çeşitliliğe sahiptir.
Sözde kodu: dosyalarınız için
L ← Empty list where we put the sorted elements
Q ← Set of all nodes with no incoming edges
while Q is non-empty do
remove a node n from Q
insert n into L
for each node m with an edge e from n to m do
remove edge e from the graph
if m has no other incoming edges then
insert m into Q
if graph has edges then
output error message (graph has a cycle)
else
output message (proposed topologically sorted order: L)
Buna ihtiyaç duyan araçların ağacın derinliklerine ilk bakışta yürümesini beklerim ve bir yaprağa çarptığında, sadece işleyin (örn. Derleyin) ve grafikten çıkarın (veya işlendiği gibi işaretleyin ve işleyin) tüm yapraklar yaprakları ile işlenen düğümler).
Bir DAG olduğu sürece, bu basit yığın tabanlı yürüyüş önemsiz olmalıdır.
Evet, işte böyle yapıyorsunuz. Derinlik-ilk arama (DFS) denir. Ve bir DAG'nız olduğundan emin değilseniz, arka kenarları kontrol etmelisiniz, aksi takdirde bir döngü sizi sonsuz bir döngüye gönderecektir. Bir foreach kullanımı yerine – sleske
Oldukça naif özyinelemeli algoritması (sözde kod) ile geldim:
Map<Object, List<Object>> source; // map of each object to its dependency list
List<Object> dest; // destination list
function resolve(a):
if (dest.contains(a)) return;
foreach (b in source[a]):
resolve(b);
dest.add(a);
foreach (a in source):
resolve(a);
bu en büyük sorunlarından birisi halkalı bağımlılıkları tespit etme özelliği yoktur - o (sonsuz özyinelemeye geçebiliriz yani yığın taşması; - p). Görebildiğim tek yol, özyinelemeli algoritmayı manuel bir yığınla interaktif olana çevirmek ve tekrarlanan elemanlar için yığını el ile kontrol etmektir.
Herkes daha iyi bir şey var mı? (Vikipedi)
bir süre kullanın, verileri a'dan geçen iki işaretçiyi koruyun, bir öncekinden iki adım ve bir adımda bu tek adım. Önde gelen işaretçi, acutal kararları ele alır ve eğer izleyen işaretçiyi geride bırakırsa, bir döngü vardır. – Tenderdude
grafik döngüleri içeriyorsa, nasıl orada izin bulunmamakta edebilir yürütme emirleri? Bana göre, eğer grafik döngüleri içeriyorsa, o zaman çözümünüz yok ve bu , yukarıdaki algoritma tarafından doğru şekilde rapor ediliyor.
Evet, bir grafik döngüleri içeriyorsa topolojik sıralama mümkün değildir. Bu gerçek dünyaya tekabül eder: Eğer A'dan önce A, B ve * B önce yapmanı istersem, beni tatmin edecek bir yol yoktur ;-). – sleske
Eh ... wikipedia doğrudan kopyalandı? – Benjol
evet, lütfen kaynaklardan alıntı yapın –
Teşekkürler. Bağımlılık ağacının bu yöntem kullanılarak sıralanabileceği gerçeğini eşleştirmeme yardımcı oldu. :-) –