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