# How the Topological Sort Algorithm Calculates Node Dependency Paths in Ceres

> Discover how Ceres uses topological sort to calculate node dependency paths. Learn about dependency matrices, cycle detection, and O(1) lookups for efficient computation.

- Repository: [AkiKurisu/ceres](https://github.com/akikurisu/ceres)
- Tags: internals
- Published: 2026-02-24

---

**Ceres calculates node dependency paths by building a dependency matrix through depth-first traversal, detecting cycles, and caching the results for O(1) runtime lookups.**

The **topological sort algorithm** in Ceres determines the execution order of graph nodes by analyzing their declared dependencies. Implemented in the `CeresGraph` class, this system pre-computes dependency paths to ensure nodes execute only after their upstream requirements are satisfied.

## Building the Dependency Matrix

The core logic resides in [`Runtime/Core/Models/Graph/CeresGraph.cs`](https://github.com/akikurisu/ceres/blob/main/Runtime/Core/Models/Graph/CeresGraph.cs) within the static `TopologicalSort` method (lines 466‑518). This method constructs an **adjacency matrix** where each entry contains the sorted indices of nodes that must execute before the target node.

### Allocation and Initialization

The algorithm begins by allocating an array of integer arrays:

```csharp
int[][] paths = new int[nodes.Count][];

```

Each index in `paths` corresponds to a node in the graph and will eventually store the complete upstream dependency chain for that node.

### Depth-First Traversal and Cycle Detection

For every node in the graph, the algorithm invokes `VisitDependency`, a recursive helper that performs **depth-first search** (DFS) through the dependency graph. The method tracks visitation state using a pooled `Dictionary<string, bool>` named `visited`, where the key is the node's GUID and the value indicates whether the node is currently "in-search."

If the algorithm encounters a node already marked as "in-search," it throws an `ArgumentException`, preventing **circular dependencies** from crashing the execution engine.

### Filtering Forward Execution Nodes

During traversal, `VisitDependency` reads each node's dependency GUIDs via `current.NodeData.GetDependencies()`. For each dependency, it locates the corresponding node using `graph.FindNode(dependency)`. The algorithm specifically ignores **forward-execution nodes** (where `dependencyNode.NodeData.executionPath == ExecutionPath.Forward`) because these do not affect upstream ordering constraints.

### Recursive Collection and Storage

The recursion continues until reaching leaf nodes (nodes with no dependencies). As the call stack unwinds, the algorithm collects node indices into a temporary list named `sorted`. Each index is added **only if** it is not already present and is not the destination node itself (preventing self-dependency entries).

Once `VisitDependency` completes for a destination node, the `sorted` list (now containing the full upstream execution order) is copied to `paths[i]`. The temporary containers are cleared before processing the next node.

## Querying Pre-Computed Dependency Paths

After `TopologicalSort` returns the `int[][]` matrix, Ceres caches it via `SetDependencyPath`. Runtime code queries these paths using `GetNodeDependencyPath(string guid)`, which performs an O(1) lookup to return the pre-computed `int[]` of dependent node indices.

This caching strategy ensures that the expensive topological sort runs only when the graph structure changes, while execution-time lookups remain instantaneous.

## Practical Implementation Example

The following example demonstrates how to retrieve and resolve dependency paths for a specific node:

```csharp
// Assume `graph` is a loaded CeresGraph instance
int[][] allPaths = graph.GetDependencyPaths();          // ← triggers TopologicalSort if not cached

// Get the execution order for a specific node by GUID
string targetGuid = "a1b2c3d4";                         // <-- replace with a real GUID
int[] dependencyIndices = graph.GetNodeDependencyPath(targetGuid);

// Resolve the actual CeresNode objects from the indices
CeresNode[] nodes = graph.nodes.ToArray();
CeresNode[] dependencies = dependencyIndices
    .Select(idx => nodes[idx])
    .ToArray();

// `dependencies` now contains the nodes that must run before the target node
foreach (var dep in dependencies)
{
    Debug.Log($"Dependency: {dep.GetType().Name} ({dep.Guid})");
}

```

The call to `GetDependencyPaths()` invokes `TopologicalSort` only on the first execution or when the graph is modified, populating the internal `_nodeDependencyPath` cache for subsequent O(1) lookups.

## Summary

- **Dependency Matrix Construction**: Ceres builds an `int[][]` matrix where each entry contains the sorted indices of upstream dependencies for every node in the graph.
- **Depth-First Traversal**: The `TopologicalSort` method in [`CeresGraph.cs`](https://github.com/akikurisu/ceres/blob/main/CeresGraph.cs) (lines 466‑518) uses recursive DFS via `VisitDependency` to walk the dependency graph.
- **Cycle Detection**: A pooled `Dictionary<string, bool>` tracks "in-search" states, throwing `ArgumentException` immediately upon detecting circular dependencies.
- **Execution Path Filtering**: Forward-execution nodes are explicitly excluded from dependency chains because they do not constrain upstream ordering.
- **Caching Strategy**: Results are cached via `SetDependencyPath`, enabling O(1) lookups at runtime through `GetNodeDependencyPath`.

## Frequently Asked Questions

### How does Ceres detect circular dependencies in the topological sort?

Ceres detects cycles using a **depth-first search** with a visitation tracking dictionary. During the recursive `VisitDependency` traversal, each node's GUID is marked as "in-search" (true) when entered and cleared (false) when exited. If the algorithm encounters a GUID already marked true, it immediately throws an `ArgumentException`, preventing infinite loops caused by circular dependencies.

### What is the time complexity of the topological sort algorithm in Ceres?

The algorithm runs in **O(V + E)** time where V is the number of nodes and E is the number of dependency edges. This standard complexity for topological sorting via DFS applies to the `TopologicalSort` method. However, because Ceres caches the resulting dependency matrix, runtime queries via `GetNodeDependencyPath` operate in **O(1)** after the initial computation.

### Why does Ceres ignore forward-execution nodes when calculating dependencies?

Forward-execution nodes (where `executionPath == ExecutionPath.Forward`) are ignored because they represent **downstream** execution flow rather than upstream constraints. In the `VisitDependency` method, these nodes are explicitly skipped when traversing dependencies. This ensures that the topological sort only considers nodes that must execute *before* the current node, not those that execute *after* it, maintaining correct ordering for backward-chaining dependency resolution.

### Where is the dependency path data stored after the topological sort completes?

After `TopologicalSort` finishes execution, the resulting `int[][]` matrix is stored in the graph's internal cache via `SetDependencyPath`. This data structure, referenced as `_nodeDependencyPath` internally, maps each node's index to an array of dependency indices. Runtime systems then access this cached matrix through `GetNodeDependencyPath(string guid)`, which performs a lookup to return the pre-computed dependency indices without recalculating the sort.