Topological Sort and Cycle Detection: Dependency Order and Kahn's Algorithm

Version note: The code in this post was built with .NET 10 and C# 14 and verified with xUnit v3 4.0.2 tests; the DI (Dependency Injection) example was run with Microsoft.Extensions.DependencyInjection 10 (from the ASP.NET Core 10 shared framework).

Guess First

We are loading the Bookstore seed data into a new test environment. There are foreign keys between the tables: OrderItems depends on both Orders and Books, Orders on Customers, Books on Authors, Payments on Orders. We wrote down what each table depends on in a dictionary:

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)}");

Both algorithms we will write in this post compute an insert order. Do they produce the same order? If not, which one is right? And which order should you pin with Assert.Equal in a test?

DAGs and Topological Sort

Dependencies form a directed graph: we think of "A depends on B" as an edge from B to A (B first, then A). Topological sort orders the vertices of this graph so that the start of every edge comes before its end. Such an order exists only if the graph has no cycle; a directed graph without cycles is called a DAG (Directed Acyclic Graph). If Orders depended on Customers and Customers on Orders, no order could satisfy both conditions.

In real life this problem is everywhere: the build order of projects in a solution, the foreign key order of seed data, the order of migration scripts, the order of jobs in a pipeline, the evaluation order of formulas in a spreadsheet. They are all the same question: "nobody may come before their own dependency".

Kahn's Algorithm: In-Degree and a Queue

The idea of the algorithm Kahn published in 1962 is intuitive: start with what depends on nothing. For every vertex count how many dependencies remain (its in-degree). Put the ones with a count of zero into a queue. Take one from the queue, add it to the order and decrement the counter of everything that depends on it; new vertices whose counter drops to zero enter the queue:

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

// dependsOn[x] = what x needs first. Edge direction: dependency -> dependent.
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);
            }
        }
    }

    // Anything left still has unmet dependencies: it sits on or behind a cycle.
    return order.Count == inDegree.Count
        ? new(order, null)
        : new(order, [.. inDegree.Where(kv => kv.Value > 0).Select(kv => kv.Key)]);
}

Every vertex enters the queue once and every edge is decremented once: O(V + E). Cycle detection comes for free: the counters of vertices on a cycle never reach zero, because each one waits for another. If vertices remain outside the order when the loop ends, the graph is not a DAG.

The build order of the projects in the solution:

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 has a nice by-product: vertices sitting in the queue at the same time are independent of each other and can be processed in parallel. Build tools compiling independent projects at the same time, or CI (Continuous Integration) pipelines running independent jobs in parallel, are conceptually this "set of ready items".

A Real Example: EF Core SaveChanges

When EF (Entity Framework) Core adds a new Author and a Book that depends on it in the same SaveChanges, it has to put the INSERT commands in the order the foreign keys require. It does so in its own source code with exactly this algorithm: the TopologicalSortCore method of the Multigraph class in the dotnet/efcore repository carries the comment "breadth-first topological sort (Kahn's algorithm)", and CommandBatchPreparer in the relational provider splits modification commands into batches with this graph's BatchingTopologicalSort. So the answer to "in what order does SaveChanges send INSERTs" from the EF Core series is the industrial version of the 30-line method in this post.

You use the same order when writing a seed script by hand. The answer to the first half of the opening question:

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

The two algorithms produce different orders and both are correct. There is no dependency between Customers and Authors; which comes first is just a consequence of the algorithm and the input order. A DAG usually has more than one valid topological order.

Topological Sort with DFS: White, Gray, Black

The second approach is based on the DFS (Depth-First Search) from the 15th post of the series. Every vertex has one of three colors: white (not seen yet), gray (currently on the recursion path, not finished), black (it and all its dependencies are done). The moment we finish visiting all dependencies of a vertex (post-order), we add it to the order; that way every vertex comes after its dependencies:

private enum Color { White, Gray, Black }

// DFS with three colors; on a back edge it returns the exact cycle path.
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 is still on the path: the part of the path from dep to here is the cycle
                    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: dependencies are already in the list
        return null;
    }
}

Gray exists for cycle detection. If we run into a gray vertex while traversing, that vertex is still on our recursion path: we have come back to ourselves (a back edge). Running into a black vertex is fine; that branch was already finished via another path. With two colors (seen/unseen) you cannot make this distinction and you mistake every "seeing it a second time" for a cycle. White being the first member of the Color enum is deliberate too: GetValueOrDefault returns default(Color), which is White, for an unseen vertex.

Finding and Reporting the Cycle

Saying "the graph has a cycle" does not help the user much; you need to say which cycle. Suppose three Bookstore services depend on each other:

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

The two algorithms behave differently in the face of a cycle. Kahn gives the vertices that could not enter the order; that set contains both the vertices on the cycle and those waiting on it (that depend on a vertex of the cycle), without telling which is which. DFS cuts out the relevant part of the path the moment it sees the back edge and gives the cycle itself, in order. If you are writing an error message, the DFS output is far more useful.

If this output looks familiar, there is a reason. The ASP.NET Core DI container solves the same problem: to create a service it creates its constructor dependencies, and theirs, and theirs. I registered the same three services in the real container and had it validate them:

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

The container's report has the same shape as our DFS output: the path, until it returns to where it started. We covered the container's lifetime and captive dependency rules in the "Dependency Injection Basics in C#" post of the C# Advanced series; what we recognize here is the underlying algorithm. The fix is read from the graph too: break one of the edges on the cycle. For example InvoiceService could depend not on the order service itself but only on the data it needs (an OrderSummary record), or an event could sit between the two services.

Testing: Do Not Assert a Single Order

The second half of the opening question. If you write Assert.Equal(["Customers", "Authors", "Orders", ...], result.Order), the test passes today; tomorrow, when someone adds the tables to the dictionary in a different order or switches the algorithm from Kahn to DFS, it breaks even though the result is still correct. The test should verify the rule of the order, not the order itself:

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);
    // Several orders are valid: check the rule, not one specific list.
    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

Asserting a specific order for the cycle path is acceptable here, because the cycle has a single entry and DFS starts from the dictionary's first key. But that is an assumption too: Dictionary keeps insertion order in practice as long as nothing is removed, but its documentation does not guarantee it. An assumption like that belongs in the test as a comment. And do not forget to test IsValidOrder itself with a wrong order: a validator that never returns false makes every test pass.

Production Notes

If you need a deterministic order, ask for it explicitly. If you generate a migration or seed script, getting the same output from the same input every time (a diffable, reviewable file) matters. Using a priority queue sorted by name instead of a queue in Kahn picks "the alphabetically first of the ready ones" and makes the order deterministic; the secondary comparer in EF Core's Multigraph serves the same purpose. The price is O(V log V).

Self-referencing foreign keys. A table like Categories.ParentId depends on itself; in the table-level graph that is a self-loop, i.e. a cycle. The real solution is at the row level: first the root categories with a null ParentId, then their children (the tree from the 11th post of the series). At the table level the algorithm needs an "ignore self-loops" rule.

With real cycles a business rule decides. If Orders and Customers reference each other with mandatory foreign keys, no insert order works; either one foreign key becomes nullable (insert with null first, then update) or the constraint is deferred to be checked at the end of the transaction (DEFERRABLE INITIALLY DEFERRED in PostgreSQL). The algorithm's job is to find the cycle and report it clearly; breaking it is a design decision.

Recursion on large graphs. The DFS-based version is recursive; a dependency chain thousands of steps long (say a build system's file-level graph) can exhaust the stack. Kahn is iterative and does not carry that risk; if you need a cycle report, first find the blocked vertices with Kahn, then run DFS only on that small set.

Common Pitfalls

Forgetting that there are several valid orders and asserting a single one in tests. We saw it above; test the rule, not the list.

Mixing up the edge direction. If you draw the edge for "A depends on B" from A to B, the algorithm produces the exact reverse order and you try to insert OrderItems before Orders. Documenting the meaning of the dictionary (dependsOn[x] = what must come before x) in a comment in one place and writing the IsValidOrder test catches this.

Vertices that never appear as a dictionary key. If you never write Authors as a key and only give it as a dependency of Books, some implementations drop it from the result. Our Kahn also adds dependencies to inDegree, so it handles this case; pin it down with a test in your own implementation.

Searching for cycles with a two-color DFS. "Seen before" is not the same as "currently on the path". In a diamond-shaped graph (Api depends on both Application and Infrastructure, both of which depend on Domain), a two-color DFS reports a cycle by mistake when it sees Domain the second time.

A Small Experiment

★☆☆ Change Kahn to split the result into layers: in each round return all vertices in the queue as a single "can run in parallel" group. How many layers does the project graph have?

★★☆ Write a deterministic Kahn that uses a PriorityQueue<T, T> instead of a queue and picks the alphabetically first of the ready vertices. Run it 100 times with the input dictionary shuffled and test that you get the same output every time.

★★★ Write your own small DI container: Register<TService, TImplementation>() and Resolve<T>(). Read constructor parameters with reflection, build the dependency graph, report the path with DFS if there is a cycle at registration time, and create instances in topological order on resolve.

In dependency graphs the edges only said "this first". In the next post the edges carry a price: the shipping cost between cities. BFS (Breadth-First Search) is no longer enough for the cheapest route from Istanbul to Antalya; we will write Dijkstra with PriorityQueue, apply lazy deletion and take a brief look at A*.