Graph-Native Data Structures in C#, Part 6: DAGs and Dependency Graphs

Directed Acyclic Graphs (DAGs) show up all over software: build systems, task schedulers, data pipelines, CI orchestrators, workflow engines. They all rely on the same rule. Edges point in one direction, and no cycle is allowed. Break that rule and a build deadlocks, a pipeline stalls, or a workflow engine runs forever.

This is Part 6 of the Graph-Native Data Structures in C# series. Part 1 is where we set up the schema conventions: VID prefixing ('entity_type:' + name), tag definitions, and the C# session patterns we use everywhere. Everything below builds on that.

We are using NebulaGraph 3.8.0 (Community Edition, Apache 2.0) with the nebula-net C# client. Several path finding bugs that matter for cycle detection were fixed in 3.8.0, so do not go back to 3.6 or 3.7 for a DAG workload. There is more on that below.

Where DAGs Show Up

The usual example is a build system. deploy depends on test, test depends on build, and build depends on install-deps. The same shape appears in a lot of other places:

• Build systems (Make, Bazel, MSBuild): targets with prerequisite targets.
• Task schedulers (Hangfire, Azure Durable Functions): activities that must finish before the next fan out.
• Data pipelines (dbt, Apache Airflow): transformation nodes whose inputs are upstream outputs.
• Workflow engines: approval steps, compensation steps, parallel branches that join again.

They all need the same three things. Get the execution order right, catch illegal cycles when someone writes them, and answer the question "what is blocked right now" without a full scan.

Modeling Dependencies as Directed Edges

The schema is small on purpose.

CREATE TAG IF NOT EXISTS task(name STRING, state STRING);
CREATE EDGE IF NOT EXISTS depends_on();

VIDs follow the Part 1 convention, 'task:' + name, so 'task:deploy', 'task:test', 'task:build' and 'task:install-deps'.

Edge direction is task to prerequisite. The edge (task:deploy)-[:depends_on]->(task:test) reads as deploy depends on test. I picked that direction for a reason. Traversing forward from a task gives you its prerequisites, which is what must finish first. Traversing backward gives you its dependents, which is what is blocked by it.

The important property is acyclicity. nGQL has no CREATE CONSTRAINT ACYCLIC or anything like it, so the database will not enforce this for you. Keeping the invariant is your job, and the right place to do it is when you insert an edge.

Topological Ordering: Kahn's Algorithm in C#

nGQL has no TOPO SORT statement. You fetch the edges and sort them in memory. Run a variable hop traversal to collect every reachable (src, dst) pair, rebuild the adjacency structure in C#, then run Kahn's algorithm.

Kahn's is O(V + E), and you get cycle detection for free. If the output list has fewer nodes than the input set, some nodes were stuck in a cycle and never reached in degree zero.

public async Task<List<string>> TopologicalOrderAsync(string rootTaskVid)
{
    var session = await _pool.GetSessionAsync();
    try
    {
        // Fetch all transitive dependency edges from the root.
        // YIELD DISTINCT is mandatory. Diamond topologies produce duplicates without it.
        var nGql = $@"GO 1 TO 20 STEPS FROM '{rootTaskVid}'
                       OVER depends_on
                       YIELD DISTINCT src(edge) AS src, dst(edge) AS dst";
 
        var result = await session.ExecuteAsync(nGql);
        var edges = result.ToList<(string Src, string Dst)>();
 
        // Collect all vertices involved.
        var allNodes = new HashSet<string>(edges.SelectMany(e => new[] { e.Src, e.Dst }));
        allNodes.Add(rootTaskVid); // root may have no prerequisites
 
        // Build adjacency (src depends_on dst means src has an outgoing edge to dst).
        var inDegree = allNodes.ToDictionary(n => n, _ => 0);
        var adjacency = allNodes.ToDictionary(n => n, _ => new List<string>());
 
        foreach (var (src, dst) in edges)
        {
            adjacency[src].Add(dst);
            inDegree[dst]++;
        }
 
        // Kahn's algorithm. Process nodes with in-degree 0 first.
        var queue = new Queue<string>(inDegree.Where(kv => kv.Value == 0).Select(kv => kv.Key));
        var order = new List<string>();
 
        while (queue.Count > 0)
        {
            var node = queue.Dequeue();
            order.Add(node);
            foreach (var neighbour in adjacency[node])
            {
                if (--inDegree[neighbour] == 0)
                    queue.Enqueue(neighbour);
            }
        }
 
        if (order.Count < allNodes.Count)
            throw new InvalidOperationException(
                $"Cycle detected: only {order.Count}/{allNodes.Count} nodes ordered.");
 
        // Reverse so prerequisites come before their dependents.
        order.Reverse();
        return order;
    }
    finally
    {
        session.Release();
    }
}

The GO 1 TO 20 STEPS upper bound is a NebulaGraph idiom. If your graph can legitimately go deeper than 20 hops, check the depth first or switch to FIND ALL PATH. The traversal stops at 20 without telling you, and that is a real problem in production.

Cycle Detection from C#

Before you insert an edge from A to B, meaning task A depends on B, check whether a path already exists from B back to A. If it does, the new edge closes a cycle.

public async Task<bool> WouldCreateCycleAsync(
    string taskVid, string newPrerequisiteVid)
{
    var session = await _pool.GetSessionAsync();
    try
    {
        // If a path exists from the new prerequisite back to the task,
        // adding the edge task->newPrerequisite creates a cycle.
        var nGql = $@"FIND SHORTEST PATH FROM '{newPrerequisiteVid}'
                       TO '{taskVid}'
                       OVER depends_on
                       YIELD path AS p";
 
        var result = await session.ExecuteAsync(nGql);
        var paths = result.ToList<object>(); // non-empty means a path exists
        return paths.Count > 0;
    }
    finally
    {
        session.Release();
    }
}
 
public async Task AddDependencyAsync(string taskVid, string prerequisiteVid)
{
    if (await WouldCreateCycleAsync(taskVid, prerequisiteVid))
        throw new InvalidOperationException(
            $"Adding dependency {taskVid} -> {prerequisiteVid} would create a cycle.");
 
    var session = await _pool.GetSessionAsync();
    try
    {
        await session.ExecuteAsync(
            $"INSERT EDGE depends_on() VALUES '{taskVid}'->'{prerequisiteVid}':();");
    }
    finally
    {
        session.Release();
    }
}

That costs one extra round trip per insert. If you are bulk loading a whole pipeline at startup, keep an in memory copy of the adjacency, run the cycle check locally with DFS, and write to NebulaGraph in batches once the batch is clean.

A note on 3.8.0. Before 3.8.0, FIND NOLOOP PATH did not exclude self loops, so self cycle checks written that way were quietly wrong. MATCH SHORTEST PATH had self loop problems too. Use FIND SHORTEST PATH and make sure you are on 3.8.0 or later. That release also fixed several crashes and wrong result bugs in SHORTEST PATH, ALL PATH and NOLOOP PATH (#5679, #5699, #5720, #5787, #5789).

Incremental Work Queries

Once the graph is built and acyclic, three query patterns cover most of what you need day to day.

What Does a Task Depend On?

GO FROM 'task:deploy' OVER depends_on YIELD dst(edge)         // direct
GO 1 TO 20 STEPS FROM 'task:deploy' OVER depends_on
    YIELD DISTINCT dst(edge)                                   // all transitive

WhatDependsOnAsync(taskVid) wraps the transitive query. Use YIELD DISTINCT. A diamond shape, where two tasks share a prerequisite, produces duplicates without it, and on a graph with wide fan in that duplication grows fast.

What Is Blocked By a Task?

Turn the traversal around:

GO FROM 'task:build' OVER depends_on REVERSELY YIELD dst(edge)

WhatIsBlockedByAsync(taskVid) uses the REVERSELY modifier. It returns every task that cannot move until the given task finishes, directly or through a chain. This is the query you run when a task fails and you need to show the user how much is affected.

Which Tasks Are Ready to Run?

The ready set is every task whose prerequisites are all in state 'completed'. A simple implementation fetches all tasks in state 'pending', and for each one checks whether GO 1 STEPS FROM taskVid OVER depends_on YIELD dst(edge) returns any vertex that is not completed. Tasks with nothing outstanding go into the ready queue.

On a large graph that gets expensive. Keep a counter of outstanding prerequisites per task instead, and decrement it atomically as tasks complete, so you do not re-query the predecessor set on every state change.

Pitfalls and Operational Gotchas

Hidden long range cycles. Manual edits through Studio or an ad hoc nGQL session skip your application level check. Run a periodic offline job that does a full Kahn's pass over the graph and alerts when it finds a cycle.

Diamond dependencies without DISTINCT. In a graph with A->C, A->B and B->C, node C sits on two paths from A. A variable hop GO N STEPS without YIELD DISTINCT returns it twice, and on wide diamonds that gets out of hand. Always use YIELD DISTINCT on variable hop traversals.

Large fan in and fan out. A task that 50 others depend on produces a very wide GO result. Paginate with LIMIT and OFFSET, or query in batches.

The 20 hop limit. GO 1 TO 20 STEPS stops at 20 and says nothing. If your dependency graph can be deeper, for example a long sequential chain of small tasks, check the maximum depth first or use FIND ALL PATH, which does not carry the same convention.

The database does not enforce acyclicity. There is no INSERT IF ACYCLIC. Every write path that skips the pre insert check can introduce a cycle. Make AddDependencyAsync the only way to write an edge, and make it impossible to bypass in the repository layer.

Session leaks. Release the session in a finally block every time. Pool exhaustion under load fails quietly, and it will confuse you at 2am.

The FIND PATH WITH PROP one hop bug. Before 3.8.0, a single hop FIND PATH WITH PROP returned wrong results (#5759). If you add property data to the cycle check path, be on 3.8.0 or later.

Where This Leads

The model here is deliberately small. One task tag with a name and a state, and one depends_on edge type. Real pipelines add edge properties such as estimated duration or retry policy, more edge types such as triggers and notifies, and task group vertices. The schema grows fine, and none of the cycle detection or topological sort logic has to change.

Part 7 takes the series into bipartite graphs, where two different kinds of vertex connect only across the divide, and shows how that shape powers collaborative filtering and recommendations.