| 2037 | * @returns {Record<string, number>} Map of nodeId to its depth |
| 2038 | */ |
| 2039 | export const calculateNodesDepth = (graph: INodeDirectedGraph, startingNodeIds: string[]): Record<string, number> => { |
| 2040 | const depths: Record<string, number> = {} |
| 2041 | const visited = new Set<string>() |
| 2042 | |
| 2043 | // Initialize all nodes with depth -1 (unvisited) |
| 2044 | for (const nodeId in graph) { |
| 2045 | depths[nodeId] = -1 |
| 2046 | } |
| 2047 | |
| 2048 | // BFS queue with [nodeId, depth] |
| 2049 | const queue: [string, number][] = startingNodeIds.map((id) => [id, 0]) |
| 2050 | |
| 2051 | // Set starting nodes depth to 0 |
| 2052 | startingNodeIds.forEach((id) => { |
| 2053 | depths[id] = 0 |
| 2054 | }) |
| 2055 | |
| 2056 | while (queue.length > 0) { |
| 2057 | const [currentNode, currentDepth] = queue.shift()! |
| 2058 | |
| 2059 | if (visited.has(currentNode)) continue |
| 2060 | visited.add(currentNode) |
| 2061 | |
| 2062 | // Process all neighbors |
| 2063 | for (const neighbor of graph[currentNode]) { |
| 2064 | if (!visited.has(neighbor)) { |
| 2065 | // Update depth if unvisited or found shorter path |
| 2066 | if (depths[neighbor] === -1 || depths[neighbor] > currentDepth + 1) { |
| 2067 | depths[neighbor] = currentDepth + 1 |
| 2068 | } |
| 2069 | queue.push([neighbor, currentDepth + 1]) |
| 2070 | } |
| 2071 | } |
| 2072 | } |
| 2073 | |
| 2074 | return depths |
| 2075 | } |
| 2076 | |
| 2077 | /** |
| 2078 | * Helper function to get all nodes in a path starting from a node |