Por ejemplo, digamos que tenemos un objeto como
const primaryDependencies = { 'service1': ['service2'], 'service2': ['service3', 'service4'], 'service3': ['service7'], 'service4': ['service5'], 'service5': [], 'service6': ['service7'], 'service7': [] }Me gustaría encontrar todas las dependencias de un servicio dado. Por todas las dependencias, me refiero a dependencias primarias + dependencias primarias de cada dependencia primaria del servicio original. (Nota: podemos ignorar las dependencias circulares por ahora)
Ejemplo 1, para el servicio 1
primaryDependencies = ['service2'] allDependencies = [ 'service2', 'service3', 'service4', 'service7', 'service5' ]Ejemplo 2, para el servicio 4
primaryDependencies = ['service5'] allDependencies = ['service5']Lo que he hecho hasta ahora (REPL - https://replit.com/@pcajanand/CreepyFumblingInformation#index.js )
const primaryDependencies = { 'service1': ['service2'], 'service2': ['service3', 'service4'], 'service3': ['service7'], 'service4': ['service5'], 'service5': [], 'service6': ['service7'], 'service7': [] } const getDependentServices = (service) => { return primaryDependencies[service] } const main = () => { console.log('service1', findAllDependents('service1', [])) console.log('service2', findAllDependents('service2', [])) console.log('service3', findAllDependents('service3', [])) console.log('service4', findAllDependents('service4', [])) console.log('service5', findAllDependents('service5', [])) console.log('service6', findAllDependents('service6', [])) console.log('service7', findAllDependents('service7', [])) } const findAllDependents = (service, visited) => { let allDeps = [] const directDeps = getDependentServices(service) allDeps = allDeps.concat(directDeps) visited.push(service) if (allDeps.length > 0) { allDeps.forEach(dep => { if (visited.indexOf(dep) === -1) { allDeps = allDeps.concat(findAllDependents(dep, visited), allDeps) } else { throw new Error('Possible circular dependency') } visited.push(dep) }) } let set = new Set(allDeps) set.delete(service) return [...set] } main()Buscando una solución eficiente y optimizada, preferiblemente sin ninguna recursividad.
¡Gracias por leer! que tengas un lindo día...
Podría adoptar un enfoque más pequeño y tomar el Set para recopilar y verificar.
const getDependencies = (dependencies, key, s = new Set) => { if (s.has(key)) throw new Error('Circular dependency'); s.add(key); dependencies[key].forEach(k => { if (s.has(k)) return; getDependencies(dependencies, k, s); }); return [...s]; }, primaryDependencies = { service1: ['service2'], service2: ['service3', 'service4'], service3: ['service7'], service4: ['service5'], service5: [], service6: ['service7'], service7: [] }; Object.keys(primaryDependencies).forEach(k => console.log(...getDependencies(primaryDependencies, k))); .as-console-wrapper { max-height: 100% !important; top: 0; }Esto se puede manejar con Breadth-First Search, que es un algoritmo transversal de árbol. Tenga en cuenta que esto no tiene ninguna recursividad.
const primaryDependencies = { 'service1': ['service2'], 'service2': ['service3', 'service4'], 'service3': ['service7'], 'service4': ['service5'], 'service5': [], 'service6': ['service7'], 'service7': [] }; console.log(bfs(primaryDependencies, 'service1')); // breadth-first search function bfs(input, key) { const output = { primaryDependencies: [], allDependencies: [] }; const root = input[key]; if (!root) { return output; } output.primaryDependencies = root; output.allDependencies = [...root]; const queue = []; queue.push(...root); while (queue.length) { const size = queue.length; for (let i = 0; i < size; i++) { const curr = queue.shift(); const children = input[curr]; for (let j = 0; j < children.length; j++) { output.allDependencies.push(children[j]); queue.push(children[j]); } } } // Using Set in order to remove possible duplicates output.allDependencies = new Set(output.allDependencies); output.allDependencies = [...output.allDependencies]; return output; }