Topological Sort ve Cycle Detection: Bağımlılık Sırası ve Kahn Algoritması

Sürüm notu: Bu yazıdaki kodlar .NET 10 ve C# 14 ile derlenip xUnit v3 4.0.2 testleriyle doğrulanmıştır; DI (Dependency Injection) örneği Microsoft.Extensions.DependencyInjection 10 (ASP.NET Core 10 shared framework) ile çalıştırılmıştır.

Önce Tahmin Et

Yeni bir test ortamına Bookstore'un seed data'sını yüklüyoruz. Tablolar arasında foreign key'ler var: OrderItems hem Orders'a hem Books'a, Orders Customers'a, Books Authors'a, Payments Orders'a bağlı. Her tablonun neye bağlı olduğunu bir dictionary'de yazdık:

Dictionary<string, string[]> tables = new()
{
    ["OrderItems"] = ["Orders", "Books"],
    ["Orders"] = ["Customers"],
    ["Books"] = ["Authors"],
    ["Payments"] = ["Orders"],
    ["Customers"] = [],
    ["Authors"] = [],
};
Console.WriteLine($"seed (Kahn): {string.Join(", ", TopologicalSort.Kahn(tables).Order)}");
Console.WriteLine($"seed (DFS):  {string.Join(", ", TopologicalSort.Dfs(tables).Order)}");

Bu yazıda yazacağımız iki algoritma da insert sırasını hesaplıyor. İkisi aynı sırayı mı üretir? Üretmiyorsa hangisi doğru? Ve testte hangi sırayı Assert.Equal ile sabitlemelisin?

DAG ve Topological Sort

Bağımlılıklar directed bir graph oluşturur: "A, B'ye bağlı" ilişkisini B'den A'ya bir edge olarak düşünürüz (önce B, sonra A). Topological sort, bu graph'ın vertex'lerini her edge'in başlangıcı bitişinden önce gelecek şekilde sıralamaktır. Böyle bir sıra ancak graph'ta cycle yoksa vardır; cycle'sız directed graph'a DAG (Directed Acyclic Graph) denir. Orders Customers'a, Customers da Orders'a bağlı olsaydı hiçbir sıra iki şartı birden sağlayamazdı.

Gerçek hayatta bu problem her yerde: solution'daki project'lerin build sırası, seed data'nın foreign key sırası, migration script'lerinin sırası, bir pipeline'daki job'ların sırası, bir spreadsheet'te formüllerin hesaplanma sırası. Hepsi aynı soru: "kimse kendi bağımlılığından önce gelmesin".

Kahn Algoritması: In-Degree ve Queue

Kahn'ın 1962'de yayımladığı algoritmanın fikri sezgisel: hiçbir şeye bağlı olmayanlarla başla. Her vertex için kaç bağımlılığı kaldığını (in-degree) say. Sayısı sıfır olanları bir queue'ya koy. Queue'dan birini al, sıraya ekle ve ona bağlı olanların sayacını bir azalt; sayacı sıfıra inen yeni vertex'ler queue'ya girer:

public sealed record TopologicalResult<T>(IReadOnlyList<T> Order, IReadOnlyList<T>? Cycle)
{
    public bool HasCycle => Cycle is not null;
}

// dependsOn[x] = x'ten önce gelmesi gerekenler. Edge yönü: bağımlılık -> bağımlı.
public static TopologicalResult<T> Kahn<T>(IReadOnlyDictionary<T, T[]> dependsOn) where T : notnull
{
    Dictionary<T, int> inDegree = [];
    Dictionary<T, List<T>> dependents = [];
    foreach ((T item, T[] deps) in dependsOn)
    {
        inDegree.TryAdd(item, 0);
        foreach (T dep in deps)
        {
            inDegree.TryAdd(dep, 0);
            inDegree[item]++;
            if (!dependents.TryGetValue(dep, out List<T>? list))
            {
                dependents[dep] = list = [];
            }

            list.Add(item);
        }
    }

    Queue<T> ready = new(inDegree.Where(kv => kv.Value == 0).Select(kv => kv.Key));
    List<T> order = [];
    while (ready.Count > 0)
    {
        T current = ready.Dequeue();
        order.Add(current);
        foreach (T next in dependents.GetValueOrDefault(current) ?? [])
        {
            if (--inDegree[next] == 0)
            {
                ready.Enqueue(next);
            }
        }
    }

    // Kalanların hâlâ karşılanmamış bağımlılığı var: bir cycle'ın üstünde ya da arkasındalar
    return order.Count == inDegree.Count
        ? new(order, null)
        : new(order, [.. inDegree.Where(kv => kv.Value > 0).Select(kv => kv.Key)]);
}

Her vertex queue'ya bir kez girer, her edge bir kez azaltılır: O(V + E). Cycle tespiti bedava gelir: cycle'daki vertex'lerin sayacı hiçbir zaman sıfıra inmez, çünkü her biri bir diğerini bekler. Döngü bittiğinde sıraya girmemiş vertex kalmışsa graph DAG değildir.

Solution'daki project'lerin build sırası:

Dictionary<string, string[]> projects = new()
{
    ["Bookstore.Api"] = ["Bookstore.Application", "Bookstore.Infrastructure"],
    ["Bookstore.Infrastructure"] = ["Bookstore.Application", "Bookstore.Domain"],
    ["Bookstore.Application"] = ["Bookstore.Domain"],
    ["Bookstore.Domain"] = [],
    ["Bookstore.Tests"] = ["Bookstore.Api"],
};
Console.WriteLine($"build (Kahn): {string.Join(" -> ", TopologicalSort.Kahn(projects).Order)}");

build (Kahn): Bookstore.Domain -> Bookstore.Application -> Bookstore.Infrastructure -> Bookstore.Api -> Bookstore.Tests

Kahn'ın güzel bir yan ürünü var: aynı anda queue'da duran vertex'ler birbirinden bağımsızdır ve paralel işlenebilir. Build araçlarının bağımsız project'leri aynı anda derlemesi, CI (Continuous Integration) pipeline'larının bağımsız job'ları paralel koşması kavramsal olarak bu "hazır olanlar kümesi"dir.

Gerçek Bir Örnek: EF Core SaveChanges

EF (Entity Framework) Core, SaveChanges'ta yeni bir Author ile ona bağlı Book'u aynı anda eklediğinde, INSERT komutlarını foreign key'lerin gerektirdiği sıraya koymak zorunda. Bunu kendi kaynak kodunda tam olarak bu algoritmayla yapıyor: dotnet/efcore deposundaki Multigraph sınıfının TopologicalSortCore method'unda "breadth-first topological sort (Kahn's algorithm)" yorumu var ve relational provider'daki CommandBatchPreparer, modification komutlarını bu graph'ın BatchingTopologicalSort'u ile batch'lere ayırıyor. Yani EF Core serisinde "SaveChanges hangi sırayla INSERT atar" sorusunun cevabı, bu yazıdaki 30 satırlık method'un endüstriyel versiyonu.

Seed script'ini elle yazarken de aynı sırayı kullanırsın. Açılıştaki sorunun ilk yarısının cevabı:

seed (Kahn): Customers, Authors, Orders, Books, Payments, OrderItems
seed (DFS):  Customers, Orders, Authors, Books, OrderItems, Payments

İki algoritma farklı sıra üretiyor ve ikisi de doğru. Customers ile Authors arasında bir bağımlılık yok; hangisinin önce geleceği yalnız algoritmanın ve input sırasının bir sonucu. Bir DAG'in genellikle birden çok geçerli topological sırası vardır.

DFS ile Topological Sort: White, Gray, Black

İkinci yol serinin 15. yazısındaki DFS'e (Depth-First Search) dayanır. Her vertex üç renkten birindedir: white (henüz görülmedi), gray (şu an recursion yolunun üstünde, işi bitmedi), black (kendisi ve bütün bağımlılıkları bitti). Bir vertex'in bütün bağımlılıklarını gezip bitirdiğimiz an (post-order) onu sıraya ekleriz; böylece her vertex bağımlılıklarından sonra gelir:

private enum Color { White, Gray, Black }

// Üç renkli DFS; back edge görünce cycle'ın tam yolunu döndürür
public static TopologicalResult<T> Dfs<T>(IReadOnlyDictionary<T, T[]> dependsOn) where T : notnull
{
    Dictionary<T, Color> color = [];
    List<T> order = [];
    List<T> path = [];

    foreach (T start in dependsOn.Keys)
    {
        if (color.GetValueOrDefault(start) == Color.White && Visit(start) is { } cycle)
        {
            return new(order, cycle);
        }
    }

    return new(order, null);

    List<T>? Visit(T node)
    {
        color[node] = Color.Gray;
        path.Add(node);
        foreach (T dep in dependsOn.GetValueOrDefault(node) ?? [])
        {
            switch (color.GetValueOrDefault(dep))
            {
                case Color.Gray:
                    // dep hâlâ yolun üstünde: yoldaki dep'ten bugüne kadar olan kısım cycle'dır
                    List<T> cycle = [.. path[path.IndexOf(dep)..], dep];
                    return cycle;
                case Color.White when Visit(dep) is { } found:
                    return found;
            }
        }

        path.RemoveAt(path.Count - 1);
        color[node] = Color.Black;
        order.Add(node); // post-order: bağımlılıklar zaten listede
        return null;
    }
}

Gray rengin varlık sebebi cycle tespiti. Gezinirken gray bir vertex'e rastlarsak, o vertex hâlâ bizim recursion yolumuzun üstünde demektir: kendi kendimize geri dönmüşüzdür (back edge). Black bir vertex'e rastlamak ise sorun değildir; o dal daha önce başka bir yoldan bitirilmiştir. İki renkle (görüldü/görülmedi) bu ayrımı yapamazsın ve her "ikinci kez görmeyi" yanlışlıkla cycle sanırsın. Color enum'ının ilk üyesinin White olması da bilinçli: GetValueOrDefault görülmemiş vertex için default(Color), yani White döner.

Cycle'ı Bulmak ve Raporlamak

"Graph'ta cycle var" demek kullanıcıya pek yardım etmez; hangi cycle olduğunu söylemek gerekir. Bookstore'da üç service birbirine bağlanmış olsun:

Dictionary<string, string[]> services = new()
{
    ["OrderService"] = ["PaymentService"],
    ["PaymentService"] = ["InvoiceService"],
    ["InvoiceService"] = ["OrderService"],
    ["CatalogService"] = [],
};
TopologicalResult<string> kahn = TopologicalSort.Kahn(services);
TopologicalResult<string> dfs = TopologicalSort.Dfs(services);
Console.WriteLine($"Kahn: order=[{string.Join(", ", kahn.Order)}], blocked=[{string.Join(", ", kahn.Cycle!)}]");
Console.WriteLine($"DFS cycle: {string.Join(" -> ", dfs.Cycle!)}");

Kahn: order=[CatalogService], blocked=[OrderService, PaymentService, InvoiceService]
DFS cycle: OrderService -> PaymentService -> InvoiceService -> OrderService

İki algoritmanın cycle karşısındaki davranışı farklı. Kahn, sıraya giremeyen vertex'leri verir; bu küme cycle'daki vertex'leri ve cycle'ı bekleyenleri (cycle'daki bir vertex'e bağımlı olanları) birlikte içerir ve hangisinin hangisi olduğunu söylemez. DFS ise back edge'i gördüğü an yolun ilgili kısmını kesip cycle'ın kendisini, sırasıyla verir. Hata mesajı yazacaksan DFS'in çıktısı çok daha kullanışlı.

Bu çıktı tanıdık geliyorsa sebebi var. ASP.NET Core'un DI container'ı aynı problemi çözer: bir service'i oluşturmak için constructor bağımlılıklarını, onlarınkini, onlarınkini oluşturur. Aynı üç service'i gerçek container'a kaydedip doğrulattım:

namespace Bookstore.Services;

public sealed class OrderService(PaymentService payments);
public sealed class PaymentService(InvoiceService invoices);
public sealed class InvoiceService(OrderService orders);

ServiceCollection collection = new();
collection.AddScoped<OrderService>();
collection.AddScoped<PaymentService>();
collection.AddScoped<InvoiceService>();
try
{
    using ServiceProvider provider = collection.BuildServiceProvider(new ServiceProviderOptions { ValidateOnBuild = true });
}
catch (AggregateException ex)
{
    Console.WriteLine(ex.InnerExceptions[0].Message);
}

Error while validating the service descriptor 'ServiceType: Bookstore.Services.OrderService Lifetime: Scoped ImplementationType: Bookstore.Services.OrderService': A circular dependency was detected for the service of type 'Bookstore.Services.OrderService'.
Bookstore.Services.OrderService -> Bookstore.Services.PaymentService -> Bookstore.Services.InvoiceService -> Bookstore.Services.OrderService

Container'ın raporu bizim DFS'imizin çıktısıyla aynı biçimde: yol, başladığı yere dönene kadar. Container'ın lifetime ve captive dependency kurallarını C# İleri serisinin "C# Dependency Injection Temelleri" yazısında anlattık; burada tanıdığımız şey, altta yatan algoritma. Çözüm de graph'tan okunur: cycle'daki edge'lerden birini kır. Örneğin InvoiceService siparişin kendisine değil, yalnız ihtiyaç duyduğu veriye (bir OrderSummary record'u) bağlı olabilir ya da iki service arasına bir event girebilir.

Test: Tek Bir Sıraya Assert Etme

Açılıştaki sorunun ikinci yarısı. Assert.Equal(["Customers", "Authors", "Orders", ...], result.Order) yazarsan test bugün geçer; yarın biri dictionary'ye tabloları farklı sırayla eklediğinde ya da algoritmayı Kahn'dan DFS'e çevirdiğinde, sonuç hâlâ doğru olduğu halde kırılır. Test sıranın kendisini değil, sıranın kuralını doğrulamalı:

public static bool IsValidOrder<T>(IReadOnlyList<T> order, IReadOnlyDictionary<T, T[]> dependsOn) where T : notnull
{
    Dictionary<T, int> position = [];
    for (int i = 0; i < order.Count; i++) position[order[i]] = i;
    return dependsOn.All(kv => kv.Value.All(dep =>
        position.TryGetValue(dep, out int d) && position.TryGetValue(kv.Key, out int k) && d < k));
}

[Fact]
public void Kahn_Dag_ReturnsValidOrder()
{
    TopologicalResult<string> result = TopologicalSort.Kahn(Tables);
    Assert.False(result.HasCycle);
    Assert.Equal(6, result.Order.Count);
    // Birden çok sıra geçerli: belirli bir listeyi değil, kuralı kontrol et
    Assert.True(TopologicalSort.IsValidOrder(result.Order, Tables));
}

[Fact]
public void Dfs_Cycle_ReturnsCyclePath()
{
    Dictionary<string, string[]> services = new()
    {
        ["OrderService"] = ["PaymentService"],
        ["PaymentService"] = ["InvoiceService"],
        ["InvoiceService"] = ["OrderService"],
    };

    TopologicalResult<string> result = TopologicalSort.Dfs(services);
    Assert.Equal(["OrderService", "PaymentService", "InvoiceService", "OrderService"], result.Cycle);
}

Test run summary: Passed!
  total: 5
  failed: 0
  succeeded: 5
  skipped: 0
  duration: 318ms

Cycle yolunda belirli bir sıraya assert etmek burada kabul edilebilir, çünkü cycle'ın tek bir girişi var ve DFS dictionary'nin ilk key'inden başlıyor. Ama bu da bir varsayım: Dictionary silme yapılmadıkça pratikte ekleme sırasını korur, dokümanı ise bunu garanti etmez. Böyle bir varsayım testin içinde yorum olarak durmalı. IsValidOrder'ın kendisini de yanlış bir sırayla test etmeyi unutma: hiç false dönmeyen bir doğrulayıcı her testi geçirir.

Üretimde Dikkat

Deterministik sıra gerekiyorsa bunu açıkça iste. Migration ya da seed script'i üretiyorsan, aynı input'tan her seferinde aynı çıktıyı almak (diff'lenebilir, review edilebilir dosya) önemlidir. Kahn'da queue yerine isme göre sıralı bir priority queue kullanmak "hazır olanlar arasında alfabetik ilk"i seçer ve sırayı deterministik yapar; EF Core'un Multigraph'ındaki ikincil comparer de aynı amaca hizmet ediyor. Bedeli O(V log V).

Self-referencing foreign key'ler. Categories.ParentId gibi bir tablo kendine bağlıdır; tablo düzeyindeki graph'ta bu bir self-loop, yani cycle'dır. Gerçek çözüm satır düzeyindedir: önce ParentId'si null olan kök kategoriler, sonra onların çocukları (serinin 11. yazısındaki tree). Tablo düzeyinde algoritmaya "self-loop'u yok say" kuralı eklemek gerekir.

Gerçek cycle'larda iş kuralı karar verir. Orders ile Customers birbirine zorunlu foreign key ile bağlıysa hiçbir insert sırası işe yaramaz; ya bir foreign key nullable yapılır (önce null ile ekle, sonra güncelle) ya da constraint işlem sonunda kontrol edilecek şekilde ertelenir (PostgreSQL'de DEFERRABLE INITIALLY DEFERRED). Algoritmanın görevi cycle'ı bulmak ve net raporlamak; kırmak bir tasarım kararı.

Büyük graph'larda recursion. DFS tabanlı versiyon recursive; binlerce adımlık bir bağımlılık zinciri (örneğin bir build sisteminin dosya düzeyindeki graph'ı) stack'i tüketebilir. Kahn iterative'dir ve bu riski taşımaz; cycle raporu gerekiyorsa önce Kahn ile engellenen vertex'leri bul, sonra DFS'i yalnız o küçük küme üzerinde çalıştır.

Sık Düşülen Tuzaklar

Birden fazla geçerli sıra olduğunu unutup testlerde tek sıraya assert etmek. Yukarıda gördük; kuralı test et, listeyi değil.

Edge yönünü karıştırmak. "A, B'ye bağlı" ilişkisinde edge'i A'dan B'ye çizersen algoritma tam ters sırayı üretir ve OrderItems'ı Orders'tan önce eklemeye çalışırsın. Dictionary'nin anlamını (dependsOn[x] = x'ten önce gelmesi gerekenler) tek bir yerde yorumla belgelemek ve IsValidOrder testini yazmak bu hatayı yakalar.

Dictionary'de key olarak geçmeyen vertex'ler. Authors'ı hiç key olarak yazmayıp yalnız Books'un bağımlılığı olarak verirsen, bazı implementasyonlar onu sonuçtan düşürür. Bizim Kahn'ımız bağımlılıkları da inDegree'ye eklediği için bu durumu karşılıyor; kendi implementasyonunda bunu bir testle sabitle.

İki renkli DFS ile cycle aramak. "Daha önce görüldü" bilgisi, "şu an yolun üstünde" bilgisiyle aynı değil. Diamond şeklindeki bir graph'ta (Api hem Application'a hem Infrastructure'a, ikisi de Domain'e bağlı) iki renkli bir DFS Domain'i ikinci kez gördüğünde yanlışlıkla cycle raporlar.

Küçük Bir Deneme

★☆☆ Kahn'ı sonucu katmanlara ayıracak şekilde değiştir: her turda queue'daki bütün vertex'leri tek bir "paralel çalışabilir" grup olarak döndür. Project graph'ı için kaç katman çıkıyor?

★★☆ Queue yerine PriorityQueue<T, T> kullanıp hazır olanlar arasında alfabetik ilkini seçen deterministik bir Kahn yaz. Input dictionary'nin sırasını karıştırarak 100 kez çalıştır ve her seferinde aynı çıktıyı aldığını test et.

★★★ Kendi küçük DI container'ını yaz: Register<TService, TImplementation>() ve Resolve<T>(). Constructor parametrelerini reflection ile oku, bağımlılık graph'ını kur, kayıt sırasında cycle varsa DFS ile yolu raporla ve resolve sırasında topological sıraya göre instance oluştur.

Bağımlılık graph'larında edge'ler sadece "önce bu" diyordu. Bir sonraki yazıda edge'ler bir bedel taşıyor: şehirler arası kargo maliyeti. İstanbul'dan Antalya'ya en ucuz rota için BFS (Breadth-First Search) artık yetmiyor; Dijkstra'yı PriorityQueue ile yazacak, lazy deletion'ı uygulayacak ve A*'a kısa bir bakış atacağız.