Graph Traversal Primitive

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
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
export class GraphTraversal {
    traverse(startNodeId: string, options: TraversalOptions): TraversalResult {
        const visited = new Set<string>([startNodeId]);
        const queue: TraversalQueueItem[] = [{ nodeId: startNodeId, depth: 0 }];
        const nodes: string[] = [];
        const depthByNode = new Map<string, number>();

        let queueIndex = 0;
        while (queueIndex < queue.length) {
            const current = queue[queueIndex++];

            // Depth cutoff guard
            if (options.maxDepth !== undefined && current.depth >= options.maxDepth) continue;

            const edgeIds = options.direction === "outgoing"
                ? this.graph.outgoingEdges.get(current.nodeId)
                : this.graph.incomingEdges.get(current.nodeId);

            for (const edgeId of edgeIds || []) {
                const edge = this.graph.edges.get(edgeId);
                if (!edge) continue;

                // Relationship filter
                if (options.relationshipKinds && !options.relationshipKinds.includes(edge.relationshipKind)) {
                    continue;
                }

                const nextNodeId = options.direction === "outgoing" ? edge.targetId : edge.sourceId;

                if (!visited.has(nextNodeId)) {
                    visited.add(nextNodeId);
                    nodes.push(nextNodeId);
                    depthByNode.set(nextNodeId, current.depth + 1);
                    queue.push({ nodeId: nextNodeId, depth: current.depth + 1 });
                }
            }
        }

        return { startNodeId, nodes, depthByNode };
    }
}