Section 4.6Source: server/src/analytics/ordering/DependencyOrderingAnalyzer.ts

Dependency Ordering (Toposort)

Determining a valid topological initialization order for a symbol's dependency subgraph using Kahn's algorithm and graph inversion.

Source: server/src/analytics/ordering/DependencyOrderingAnalyzer.ts

The Two-Phase Ordering Pipeline

DependencyOrderingAnalyzer answers: "In what order must the symbols that X depends on be initialized so that every dependency is ready before its dependents?"

Phase 1: Subgraph Collection via Iterative DFS

Runs an iterative DFS from sourceNodeId following only symbol-to-symbol dependency edges (calls, extends, implements, instantiates) to gather all relevant nodes.

Phase 2: Kahn's Algorithm & Graph Inversion

In CodeGraph, an edge A -> B means A depends on B. For dependency-first ordering,B must come before A. In this inverted graph, an in-degree of 0 represents a node whose dependencies have all been processed:

server/src/analytics/ordering/DependencyOrderingAnalyzer.ts

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
// Indegree represents: "How many unprocessed dependencies does this node have?"
for (const nodeId of relevantNodeIds) {
    for (const edgeId of this.graph.outgoingEdges.get(nodeId) || []) {
        const edge = this.graph.edges.get(edgeId);
        if (edge && dependencyRelationshipKinds.has(edge.relationshipKind) && relevantNodeIds.has(edge.targetId)) {
            indegree.set(nodeId, indegree.get(nodeId)! + 1);
        }
    }
}

// Kahn's queue initialized with nodes having 0 dependencies
const queue = Array.from(relevantNodeIds).filter(id => indegree.get(id) === 0);
while (queue.length > 0) {
    const nodeId = queue.shift()!;
    orderedNodeIds.push(nodeId);

    // Decrement indegree for all nodes that depend on this node
    for (const edgeId of this.graph.incomingEdges.get(nodeId) || []) {
        const edge = this.graph.edges.get(edgeId);
        if (edge && relevantNodeIds.has(edge.sourceId)) {
            const newDeg = indegree.get(edge.sourceId)! - 1;
            indegree.set(edge.sourceId, newDeg);
            if (newDeg === 0) queue.push(edge.sourceId);
        }
    }
}

Unorderable Subgraphs (Cycles)

If the subgraph contains a circular dependency, isOrderable evaluates to false because the cyclic nodes never reach in-degree 0.

4.5 Circular Dependency Analysis

4.7 Connectivity & Degree Analysis