Hesaplama Uygulamaları

Edgar H. Sibley
Panel Editörü

Çok sayıda çizge algoritmasının kolay ve güvenli biçimde programlanmasına olanak tanıyan soyut bir çizge modülü, ileri ve geri komşuluk listelerinin simetrik biçimde saklanmasıyla gerçekleştirilmiştir; böylece genel yönlü ve yönsüz çizgelerde kenar odaklı dolaşmalar desteklenir.

Kenar Odaklı Çizge Algoritmaları için Çok Yönlü Bir Veri Yapısı

Jürgen Ebert

Çizgelerin, bilgisayar programlarında gerçekliğin ilgili bölümlerini modellemek için yararlı bir araç olduğu yaygın biçimde kabul edilmektedir. Çizgeler; yol haritaları, elektrik ağları, kimyasal yapı formülleri, bilgisayar programlarının veri ve kontrol akışı, ayrık oyunların durum uzayları, sosyolojik diyagramlar, zaman çizelgeleri vb. için oldukça doğal modellerdir. Ayrıca birçok alandaki pek çok ayrık problem (örneğin biçimsel dil kuramı, otomat kuramı, derleyici geliştirme, işletim sistemleri kuramı, yöneylem araştırması) eşdeğer çizge problemlerine dönüştürülebilir ve ardından çizge algoritmaları kullanılarak çözülebilir.

Temsil biçimi, çizge algoritmalarının verimliliğini büyük ölçüde etkiler. Çoğu zaman doğrusal karmaşıklık yalnızca komşuluk bilgilerinin uygun biçimde saklanmasıyla sağlanabilir (bkz. örneğin [6]). Prosedürel dillerde çizgelerin içsel olarak temsil edilmesinin çeşitli yolları vardır; bunlar arasında komşuluk matrisleri, sıralı veya bağlı komşuluk listeleri ve kenar listeleri bulunur (bkz. [2]). Öte yandan, çizge üzerinde işlemleri ve çizge tarafından tetiklenen kontrol ifadelerini (örneğin for-döngüleri) içeren daha soyut çizge temsilleri, iyi ve açık algoritma tasarımını büyük ölçüde kolaylaştırır.

Bu makalede, çizge algoritmalarının kenar odaklı programlama paradigmasına özellikle uygun olan soyut bir çizge işleme modülünü açıklıyoruz ve bu modülün Algol benzeri dillerde nasıl verimli biçimde gerçekleştirilebileceğini gösteriyoruz. Bu çizge gerçekleştirmesi komşuluk listesi türündedir ve yönlü ile yönsüz çizgeler için uygundur (birden fazla kenara izin verilir). Yönsüz çizgeler, her kenara rastgele bir yön atanarak yönlü çizgeler şeklinde temsil edilir (ve karşılık gelen simetrik çizgenin saklanması yoluyla değil). Bu temsil birçok uygulamada başarıyla kullanılmıştır; örneğin, fonksiyonel dillerin gerçekleştirilmesine yönelik EMS projesinde çizgeleri temsil etmek için bir araç olarak kullanılmıştır [3].

Çizgeler

Çizge türlerinin çok geniş bir çeşitliliği vardır. Uygulama alanına bağlı olarak çizgeler yönlü veya yönsüz, ağırlıklı veya ağırlıksız ve sıralı veya sırasız olabilir. Çoklu kenarlara ve öz-ilmeklere ya izin verilir ya da yasaklanır. Burada, bu varyantların tümüne uygun bir çizge temsili sunuyoruz ([1] ve [5] çizge kuramına giriş kitaplarıdır; [2] ve [4] ise çizge algoritmalarını tanıtır).

Oldukça genel bir çizge tanımı kullanıldığında, bir (sonlu) yönlü çizge (G = (V, E, α, ω)), sonlu ve boş olmayan bir (V) düğüm kümesinden, sonlu bir (E) kenar kümesinden ((V ∩ E = ∅)) ve iki fonksiyondan oluşur:

• (α : E → V) başlangıç düğümünü belirtir
• (ω : E → V) her kenarın bitiş düğümünü belirtir

Eğer (v = α(e)) ve (w = ω(e)) düğümlerine sahip bir (e) kenarı varsa, o zaman (w), (v)'nin ardılıdır ve (v), (w)'nin öncülüdür. (v = α(e)) olan kenarlar ("e, v'den çıkar") (v)'nin ileri yıldızını (forward star) oluşturur. Benzer biçimde, (v = ω(e)) olan kenarlar ("e, v'ye girer") (v)'nin geri yıldızını (backward star) oluşturur.

Öte yandan, bir (sonlu) yönsüz çizge (G = (V, E, Ψ)) yalnızca bir fonksiyon içerir

[Ψ : E → {W ⊆ V \mid |W| ≤ 2}]

ve her kenara en fazla iki düğüm atar. Bir öz-ilmek, (|Ψ(e)| = 1) olan bir (e) kenarıdır. Eğer (v ∈ Ψ(e)) ise, (v) ve (e)'nin ilişkili (incident) olduğu söylenir. Bir (v) düğümünün yıldızı (star), (v) ile ilişkili olan tüm kenarlardan oluşur. (v)'nin derecesi (γ(v)), (v) ile ilişkili kenarların sayısıdır; burada öz-ilmekler iki kez sayılır.

Bir yönlü çizge (G = (V, E, α, ω)) için, altında yatan yönsüz çizge (H = (V, E, Ψ)) şu şekilde verilir

[Ψ(e) = {α(e), ω(e)}]

Böylece, yönsüz çizgeler için tanımlanan tüm kavramlar ve algoritmalar, yönlü çizgeler için de yalnızca onların altında yatan yönsüz çizgelerine başvurularak kullanılabilir. Dolayısıyla bir (e) kenarı ve bir (v) düğümü, (v = α(e)) veya (v = ω(e)) ise ilişkilidir ve (α(e) = ω(e)) ise (e) bir öz-ilmektir.

Aşağıda verilen gerçekleştirme ile, altında yatan yönsüz çizgenin temsili çizgenin kendi temsiliyle aynıdır. Böylece yönsüz çizgeler için tasarlanmış algoritmalar (örneğin kapsayan ağaçları bulma veya (iki-)bağlantılılığı sınama algoritmaları) yönlü çizgeler üzerinde ek bir uyarlama gerektirmeden çalıştırılabilir.

Kenar Odaklı Çizge Algoritmaları

Burada açıklanan çizge modülü, çizgeleri ele almanın kenar odaklı bir yaklaşımını güçlü biçimde destekler. Bu paradigma programlamayı daha güvenli hale getirir ve aynı zamanda çoklu kenarlara sahip çizgelerin işlenmesi için uygundur.

Çizge algoritmalarının kenar odaklı programlanması için aşağıdaki kurallar geçerlidir:

• Düğümlerin komşulukları, verilen bir düğümle ilişkili kenarlara başvurularak dolaşılır.
• Kenarlar iki duruma sahip nesneler olarak kabul edilir. Dışa doğru işaret ediyor olabilirler (pozitif işaret) veya içe doğru işaret ediyor olabilirler (negatif işaret).

Örnek sözde kod:

for all edges e out of v do
    let w be the other vertex of e;
    process w
od.

Şekil 1. Bir Köprü Tespit Algoritmasının Kenar Odaklı Sözde Kod Sürümü

procedure DFS (v : vertex);
LOWPT[v] := NUMBER[v] := NUM := NUM + 1;

for all e incident with v do
    let w be the other vertex of e;

    if NUMBER[w] = 0 then
        PARENT[w] := e;
        DFS(w);

        if LOWPT[w] > NUMBER[v] then
            e is bridge
        fi;

        LOWPT[v] := min(LOWPT[v], LOWPT[w])

    else
        if NUMBER[v] < NUMBER[w]
        and e is not a tree edge then
            LOWPT[v] := min(LOWPT[v], NUMBER[w])
        fi
    fi
od;

NUM := 0;

for all v in V do
    PARENT[v] := NUMBER[v] := 0
od;

for all v in V do
    if NUMBER[v] = 0 then
        DFS(v)
    fi
od.

Kenarların işareti, “diğer” düğümden söz etmeyi mümkün kılar.

Kenarlar üzerinde döngüler kullanmak ve kenarlara bir durum atamak, for-döngülerinin while-döngüsü ile bazı standart fonksiyon çağrılarının birleşimine doğrudan çevrilmesini sağlar; çünkü işaretli kenarlar, bir while-döngüsüne yeniden girip bir sonraki kenarı işlemek için yeterli bilgiyi içerir. Bu durum (örneğin ardıl düğümler üzerindeki) düğüm döngüleri için mümkün değildir.

Ayrıca, komşulukları tüm ilişkili kenarlara açıkça bakarak dolaşmak, çoklu kenarlar mevcutsa ardılların birden fazla kez listelendiğini açıkça gösterir. (Düğüm odaklı bir for-döngüsü çoğu zaman yalnızca çoklu kenar içermeyen çizgeler için geçerlidir.)

Buna ek olarak, kenarlar üzerindeki işaretler yeterli bilgiyi saklamaya olanak tanır; böylece bazı arama algoritmalarında olduğu gibi kenarlar daha sonra kullanılmak üzere ara bir veri yapısında saklandığında ertelenmiş işlem yapılabilir. Bir kenar geri alındığında, işareti onun kökeninin anlaşılmasına yardımcı olur.

Kenarlara yön (işaret) atamak ayrıca yönlü çizgelerde yönsüz aramalar sırasında gelen ve giden kenarları ayırt etmeye yardımcı olur. Ayrıca yönlü çizgelerin (yönsüz) çevrimlerinde ve/veya kesitlerinde kenarların yönünü tanımlamaya da yardımcı olur.

Çizge İşlemleri

Şimdi, Algol benzeri dillerde kenar odaklı algoritmaların gerçekleştirilmesi için bir modülün (soyut veri yapısı anlamında) tanımını veriyoruz.

Yukarıda verilen dışa doğru yıldız üzerindeki for-döngüsü gibi bir sözde ifadeyi programlamak için first-out ve next-out dolaşım fonksiyonlarını ve yardımcı bir omega fonksiyonunu kullanırız.

Şekil 2. Dolaşım Prosedürleri

edge procedure first-out (v : vertex)
    returns first edge going out of v.

edge procedure next-out (e : edge)
    returns edge following e in forward star of alpha(e).

edge procedure first-in (v : vertex)
    returns first edge going into v.

edge procedure next-in (e : edge)
    returns edge following e in backward star of omega(e).

edge procedure first (v : vertex)
    returns first edge incident with v.

edge procedure next (e : edge)
    returns edge following e in star of this(e).

vertex procedure first-vertex()
    returns first vertex of the graph.

vertex procedure next-vertex(v : vertex)
    returns vertex following v in the graph.

edge procedure first-edge()
    returns first edge of the graph.

edge procedure next-edge(e : edge)
    returns edge following e in the graph.

Bu fonksiyonlar tüm kümeler üzerinde keyfi fakat sabit bir sıralama olduğunu varsayar. İşaretli kenarları işlemek için bazı yardımcı aktarım fonksiyonları gereklidir.

Şekil 3. “İşaretli” Kenarların İşlenmesi için Yardımcı Aktarım Prosedürleri

vertex procedure alpha (e : edge)
    returns start vertex of e.

vertex procedure omega (e : edge)
    returns end vertex of e.

vertex procedure this (e : edge)
    returns start vertex of e if e is positive,
    and end vertex otherwise.

vertex procedure that (e : edge)
    returns end vertex of e if e is positive,
    and start vertex otherwise.

edge procedure normal (e : edge)
    returns edge e with positive direction.

edge procedure reverse (e : edge)
    returns edge e with reversed direction.

Şekil 4. Köprü Tespiti için Somut Program

procedure DFS (v : vertex);
LOWPT[v] := NUMBER[v] := NUM := NUM + 1;

e := first(v);
while e <> 0 do

    w := that(e);

    if NUMBER[w] = 0 then
        PARENT[w] := normal(e);
        DFS(w);

        if LOWPT[w] >= NUMBER[w] then
            output(e, "is bridge")
        fi;

        LOWPT[v] := min(LOWPT[v], LOWPT[w])

    else
        if NUMBER[v] < NUMBER[w]
        and normal(e) <> PARENT[v] then
            LOWPT[v] := min(LOWPT[v], NUMBER[w])
        fi
    fi;

    e := next(e)
od;

NUM := 0;

v := first-vertex();
while v <> 0 do
    PARENT[v] := NUMBER[v] := 0;
    v := next-vertex(v)
od;

v := first-vertex();
while v <> 0 do
    if NUMBER[v] = 0 then
        DFS(v)
    fi;
    v := next-vertex(v)
od.

Çizge Temsili

Komşuluk listeleri genellikle her düğümün ardıllarını bağlı listeler aracılığıyla saklamak için kullanılır. Altında yatan yönsüz çizge üzerinde algoritmaların çalıştırılmasını sağlamak amacıyla öncülleri de saklıyoruz. Bazı pratik teknikler kullanarak, çizge modülünün tüm işlemlerini verimli biçimde gerçekleştiren bir depolama şeması elde ederiz.

(|V| = n) ve (|E| = m) olan bir yönlü çizge (G = (V, E, α, ω)) olsun. (V) kümesindeki düğümleri 1’den (n)’e, (E) kümesindeki kenarları ise 1’den (m)’e numaralandırırız.

Düğümler ve kenarlar hakkında tüm somut bilgiler (örneğin adlar, ağırlıklar, uzunluklar, işaretlemeler) sırasıyla uzunluğu (n) veya (m) olan dizilerde ayrı olarak saklanabilir. Komşuluk listesi temsillerinin komşuluk matrislerine göre bir avantajı, yönsüz çizgeler için bile düğüm ve kenar değerlerinin yalnızca bir kez saklanması gerekliliğidir.

Bu numaraları ilgili nesneler için tanımlayıcı olarak kullanırız, ancak düğüm i ile kenar i’nin karıştırılmamasını sağlarız. Aşağıdaki türler kullanılır; burada tam sayının işareti kenarlar için yön göstergesi olarak kullanılır ve sıfır boş değer anlamına gelir:

vertex = 0 .. n
edge   = -m .. m

Şekil 6. Dolaşım Prosedürlerinin Gerçekleştirilmesi

edge procedure first-out (v : vertex);
    e := FIRST[v];
    while e < 0 do
        e := NEXT[e]
    od;
    return e.

edge procedure next-out (e : edge);
    e := NEXT[abs(e)];
    while e < 0 do
        e := NEXT[e]
    od;
    return e.

edge procedure first-in (v : vertex);
    e := FIRST[v];
    while e > 0 do
        e := NEXT[e]
    od;
    return e.

edge procedure next-in (e : edge);
    e := NEXT[-abs(e)];
    while e > 0 do
        e := NEXT[e]
    od;
    return e.

edge procedure first (v : vertex);
    return FIRST[v].

edge procedure next (e : edge);
    return NEXT[e].

vertex procedure first-vertex();
    return 1.

vertex procedure next-vertex (v : vertex);
    return if v = n then 0 else v + 1 fi.

edge procedure first-edge();
    return 1.

edge procedure next-edge (e : edge);
    return if e = m then 0 else e + 1 fi.

ŞEKİL 5. Örnek Bir Çizge ve Dizi Temsili

NODE: array[edge] of vertex

Her kenar e için α(e)’yi NODE[-e] içinde ve ω(e)’yi NODE[e] içinde saklayabiliriz. Bu sayede tüm kenar listesi odaklı algoritmalar yalnızca NODE dizisine erişerek yapımız üzerinde kullanılabilir.

Tersine, her düğüm v için komşuluk listeleri dizi indeksleri bağlantı olarak kullanılarak dolaşılabilir hale getirilir:

FIRST: array[vertex] of edge
NEXT: array[edge] of edge

Bu diziler, FIRST[v] ile başlayan, NEXT girişlerini izleyen ve sıfır girdisi ile sonlanan indeks zinciri kullanılarak v düğümü ile ilişkili tüm kenarları v’ye bağlar. v’den çıkan kenarlar için indeksler pozitif, v’ye giren kenarlar için negatiftir. Böylece FIRST/NEXT dizilerindeki sıfır olmayan girdiler, ilgili düğüm açısından yönü görülen işaretli kenarların kendisidir.

Şekil 5, örnek bir çizgeyi ve onun dizi temsilini göstererek bir örnek sunar.

Şekil 6, Şekil 2’deki dolaşım prosedürlerinin yapımız kullanılarak nasıl gerçekleştirilebileceğini gösterir ve Şekil 7 ise Şekil 3’teki yardımcı fonksiyonların gerçekleştirilmesini verir. (Pratik uygulamalarda genel olarak kullanılabilen tüm prosedürlerin argümanlarını denetlemesi gerektiğine dikkat edin. Sunumu basitleştirmek için bu denetimler atlanmıştır.)

Dolaşım fonksiyonlarının bu gerçekleştirmeleri, bir düğüm v’nin (ileri/geri) yıldızları üzerindeki for-döngülerinin karmaşıklığını (γ(v)) ile orantılı hale getirir. Benzer biçimde, V ve E üzerindeki for-döngülerinin karmaşıklığı sırasıyla n ve m ile orantılıdır. Yardımcı fonksiyonların tüm gerçekleştirmeleri görünüşe göre sabit zaman kullanır.

first/next fonksiyon çifti öz-ilmekleri iki kez sayar. Eğer bu istenmiyorsa, gerekirse first ve next fonksiyonları negatif kenar değerlerini e göz ardı edecek şekilde değiştirilmelidir.

Çizge modülü elbette gerek duyulduğunda ek işlemlerle genişletilebilir; örneğin dereceleri belirleme prosedürleri, kenar varlığını sınama prosedürleri vb. is-edge(v, w) sınamalarının karmaşıklığının en az (min(γ(v), γ(w))) ile orantılı olduğuna dikkat edin.

YENİDEN OLUŞTURMA VE SIKIŞTIRMA

NODE dizisi tek başına (çizgenin bir kenar listesi temsili olarak) zaten tüm ilişki bilgilerini içerir. Dolayısıyla örneğin harici depolama için bu dizi yeterlidir.

Yardımcı Prosedürler

vertex procedure alpha(e : edge);
    return NODE[-abs(e)].

vertex procedure omega(e : edge);
    return NODE[abs(e)].

vertex procedure this(e : edge);
    return NODE[-e].

vertex procedure that(e : edge);
    return NODE[e].

edge procedure normal(e : edge);
    return abs(e).

edge procedure reverse(e : edge);
    return -e.

ŞEKİL 7. Girdi Parametrelerinin Geçerli Olduğu Varsayılarak Şekil 3’teki Yardımcı Prosedürlerin Gerçekleştirilmesi

Şekil 8, önceki bölümde açıklanan çizge temsilinin NODE dizisinden doğrusal zamanda nasıl yeniden kurulabileceğini gösterir.

Bu algoritma, kenar listesini ters sırada dolaşır. Her (pozitif) e kenarını α(e) düğümünün komşuluk listesinin başına ekler ve -e’yi ω(e) listesinin içine ekler.

for v := 1 to n do
    FIRST[v] := 0
od;

for e := m downto 1 do
    NEXT[e] := FIRST[NODE[-e]];
    FIRST[NODE[-e]] := e;

    NEXT[-e] := FIRST[NODE[e]];
    FIRST[NODE[e]] := -e
od.

ŞEKİL 8. NODE Dizisinden Graf Gösteriminin Doğrusal Zamanda Yeniden Kurulması

Bu algoritma sıralamayı korur: Eğer NODE dizisi tüm komşuluk listeleriyle uyumluysa, komşuluk listeleri daha önce oldukları biçimde yeniden kurulurlar. Öte yandan, NODE dizisi sıralanırsa (örneğin bir ağırlığa göre), yeniden kurma işleminden sonra tüm komşuluk listeleri de sıralanmış olur.

Bu yordam, graf girdisini yalnızca bir kenar listesinin okunmasına indirgemek için de kullanılabilir. Graf çıktısı, NODE dizisi dolaşılırken kenar listesinin yazdırılmasıyla gerçekleştirilebilir. Ancak NODE dizisinin sırası komşuluk listelerinin sıralarıyla uyumlu değilse, graf dış bir ortama yazılırken bazı topolojik sıralama işlemleri yapılmalıdır. Aksi halde yıldızlar üzerindeki özgün sıra yeniden kurulamaz.

(Bu uyumsuzluk, örneğin graf bir sonraki bölümde sunulan yordamlar kullanılarak dinamik olarak oluşturulduysa ortaya çıkabilir.)

Şekil 9, graf yapısını doğrusal zamanda bir kenar listesine sıkıştırmak için kullanılan bir algoritma verir. Burada kuyruklama için (m’e kadar) normalize edilmiş kenarlar ve işaretleme için (2m’e kadar) işaretli kenarlar tutmak üzere doğrusal miktarda ek çalışma alanına ihtiyaç vardır.

Bu algoritma bir e kenarını yalnızca α(e) ve ω(e) komşuluk listelerindeki tüm öncülleri yazdırılmışsa yazdırır. Bu özelliğe karar verebilmek için e ve -e üzerinde bir işaretleme kullanılır. Bir kuyruk, yazdırılabilir tüm kenarların izlenmesine yardımcı olur.

Eğer komşuluk listesi sıralamasıyla uyumlu bir NODE dizi sıralaması yoksa, bu algoritma başarısız olur (tüm kenarları yazdırmayarak).

Sıkıştırma Algoritması

procedure test-and-mark(e : edge):
    if e <> 0 and not is-marked(e) then
        mark(e);
        if is-marked(-e) then
            enqueue(abs(e))
        fi;
        if NODE[-e] = NODE[e] then
            test-and-mark(-e)
        fi
    fi;

init-queue();
init-marking();

for v := 1 to n do
    test-and-mark(FIRST[v])
od;

while not is-empty-queue() do
    e := extract-front-of-queue();
    output(NODE[-e], "^", NODE[e]);
    test-and-mark(NEXT[e]);
    test-and-mark(NEXT[-e])
od.

ŞEKİL 9. Graf Yapısını Bir Kenar Listesine Sıkıştırmak İçin Doğrusal Zamanlı Bir Algoritma

DİNAMİK GRAFLAR

Birçok uygulama, yürütme sırasında boyutu ve yapısı değişen graflar kullanır. Bu durum, düğüm ve kenarları oluşturmak ve silmek için yordamların gerekli olduğu anlamına gelir.

Bu makalede sunulan gösterim, düğüm ve/veya kenar sayısı (ılımlı biçimde) değişen graflar için kolayca genişletilebilir; yeter ki her ikisi için de bir maksimum sayı (NMAX/MMAX) verilebilsin. Şekil 10, dinamik grafları yönetmek için gerekli yordamları verir.

Bu dizilerdeki sıfır girişlerini (şu ana kadar kullanılmamış olanları) başlangıç işaretçisi olarak kullanarak, kullanılmayan girişleri bir yığın disiplini izleyerek birbirine bağlayabiliriz.

Kullanılan girişlerle kullanılmayanları ayırt etmek için, kullanılmayan girişleri zincirlemek amacıyla FIRST ve NEXT içindeki bağlantı değerlerine büyük bir LARGE değeri (tercihen MMAX) ekleriz.

Bu durumda graf, aşağıdaki yordam kullanılarak boş bir graf olarak başlatılmalıdır. (Bu durumda düğüm ve kenar kümeleri üzerinde dolaşan yordamların uyarlanması gerekir.)

Kenarların düğümlere eklenme sırasını izlemek için ek bir dizi kullanmak da mümkündür:

LAST: array[vertex] of edge

Bu dizi, her düğüm için son kenar girişini tutar. Bu durum ileri ve geri yıldızlar ile (yönsüz) yıldızlar için de geçerlidir.

Bu durumda komşuluk kümeleri üzerinde değişen tüm döngüler bu kümeleri kenarların eklenme sırasına göre dolaşır. Bu da sıralı graflara yol açar; burada her düğüme bitişik kenarlar doğrusal biçimde sıralanmıştır.

Şekil 11, oluşturma/silme yordamlarının nasıl gerçekleştirildiğini gösterir; iki yardımcı yordam ise Şekil 12’de verilmiştir.

Oluşturma yordamları sabit zaman kullanır. delete-vertex işleminin karmaşıklığı γ(v) ile orantılıdır. delete-edge(e) yordamı ise γ(α(e)) + γ(ω(e)) ile orantılı zaman kullanır. Kenarlar üzerinde çift zincirler kullanılarak sabit zamanlı yapılabilir, ancak bu genellikle zahmete değmez.

Dinamik Graf İşlemleri

• create-vertex() → yeni bir düğüm döndürür
• delete-vertex(v : vertex) → v düğümünü siler
• create-edge(v, w : vertex) → yeni bir kenar döndürür
• delete-edge(e : edge) → e kenarını siler

Başlatma Yordamı

procedure init();
    for v := 0 to NMAX do
        FIRST[v] := v + 1 + LARGE
    od;

    for e := 0 to MMAX do
        NEXT[-e] := 0;
        NEXT[e] := e + 1 + LARGE
    od;

    n := 0;
    m := 0.

Dinamik grafları gerçekleştirmek için FIRST/NEXT dizilerindeki tüm kullanılmayan (negatif olmayan) girişleri birbirine bağlarız.

ŞEKİL 10. Dinamik Grafların Yönetimi İçin Oluşturma ve Silme Yordamları

Oluşturma ve Silme Yordamlarının Gerçeklenmesi

vertex procedure create-vertex();
    v := FIRST[0] - LARGE;
    FIRST[0] := FIRST[v];
    FIRST[v] := LAST[v] := 0;
    n := n + 1;
    return v.

procedure delete-vertex(v : vertex);
    while FIRST[v] <> 0 do
        delete-edge(FIRST[v])
    od;
    FIRST[v] := FIRST[0];
    FIRST[0] := v + LARGE;
    n := n - 1.

edge procedure create-edge(v, w : vertex);
    e := NEXT[0] - LARGE;
    NEXT[0] := NEXT[e];
    NEXT[e] := 0;
    m := m + 1;
    create-entry(v, e);
    create-entry(w, -e);
    return e.

procedure delete-edge(e : edge);
    e := abs(e);
    delete-entry(NODE[-e], e);
    delete-entry(NODE[e], -e);
    NODE[-e] := NODE[e] := NEXT[-e] := 0;
    NEXT[e] := NEXT[0];
    NEXT[0] := e + LARGE;
    m := m - 1.

ŞEKİL 11. Girdi Parametrelerinin Geçerli Olduğu Varsayılarak ve Taşma Koşulları Denetlenmeden Oluşturma ve Silme Yordamlarının Gerçeklenmesi

Yardımcı Yordamlar

procedure create-entry(v : vertex, e : edge);
    if FIRST[v] = 0 then
        FIRST[v] := e
    else
        NEXT[LAST[v]] := e
    fi;
    LAST[v] := e;
    NODE[-e] := v.

procedure delete-entry(v : vertex, e : edge);
    if FIRST[v] = e then
        FIRST[v] := NEXT[e];
        if LAST[v] = e then
            LAST[v] := 0
        fi
    else
        i := FIRST[v];
        while NEXT[i] <> e do
            i := NEXT[i]
        od;
        NEXT[i] := NEXT[e];
        if LAST[v] = e then
            LAST[v] := i
        fi
    fi.

SONUÇ

Kenar yönlendirme paradigmasını izleyerek, genel graflar için yazılım modülümüz ve bunun von Neumann makineleri üzerindeki gerçekleştirilmesi, çok sayıda graf algoritmasının kolay ve güvenli biçimde programlanmasına olanak tanır; çünkü ileri ve geri yıldızların dolaşılması ile kenarların numaralandırılması özellikle kolaydır.

Yönlü bir graf ile onun altında yatan yönsüz graf arasında bir ayrım yapılmadığından, modülümüz yayımlanmış algoritmaların somut programlama koduna oldukça doğrudan aktarılmasına olanak verir.

Bu modül çeşitli uygulamalarda başarıyla kullanılmıştır. C dilinde yazılmış bir sürümü, fonksiyonel dillerin graflar aracılığıyla gerçekleştirilmesi için kullanılan EMS sisteminin temel yapı taşlarından biridir.

KAYNAKLAR

1. Berge, C. Graphs and Hypergraphs. North-Holland, Amsterdam, 1973.
   Graf kuramı üzerine bir ders kitabı.

2. Ebert, J. Effiziente Graphenalgorithmen. Aula, Wiesbaden, Batı Almanya, 1981.
   Graf algoritmaları ve bunların Algol-benzeri dillerde soyut veri ve iyileştirmeler kullanılarak gerçekleştirilmesi üzerine bir ders kitabı.

3. Ebert, J. Implementing a functional language on a von Neumann computer. Tech. Rep. 3/85, EWH Koblenz, Fachbereich Informatik, Mar. 1985.

4. Even, S. Graph Algorithms. Pitman, Marshfield, Mass., 1979.

5. Harary, F. Graph Theory. Addison-Wesley, Reading, Mass., 1969.

6. Tarjan, R. E. Depth-first search and linear graph algorithms. SIAM Journal on Computing, 1(2), 1972, 146–160.

CR Kategorileri ve Konu Tanımlayıcıları:
E.1 [Veri]: Veri Yapıları — diziler, graflar, listeler
E.2 [Veri]: Veri Depolama Gösterimleri — bitişik gösterimler, bağlı gösterimler
F.2.2 [Algoritma Analizi ve Problem Karmaşıklığı]: Sayısal Olmayan Algoritmalar ve Problemler — ayrık yapılar üzerinde hesaplamalar
G.2.2 [Ayrık Matematik]: Graf Kuramı — graf algoritmaları

Genel Terimler: Algoritmalar
Ek Anahtar Kelimeler ve İfadeler: Kenar yönelimli algoritmalar, graf dolaşımı

Yazarın Güncel Adresi: Jürgen Ebert, EWH Koblenz, Informatik, Rheinau 3–4, 5400 Koblenz, Batı Almanya.

Alınma: 6/86; kabul: 11/86

Communications of the ACM, Haziran 1987, Cilt 30, Sayı 6