For example, say we have an object like
const primaryDependencies = {
'service1': ['service2'],
'service2': ['service3', 'service4'],
'service3': ['service7'],
'service4': ['service5'],
'service5': [],
'service6': ['service7'],
'service7': []
}
I would like to find all dependencies of a given service. By all dependencies, I mean primary dependencies + primary dependencies of each primary dependency of the original service. (Note - we can ignore circular dependencies for now)
Example 1, for service 1
primaryDependencies = ['service2']
allDependencies = [ 'service2', 'service3', 'service4', 'service7', 'service5' ]
Example 2, for service 4
primaryDependencies = ['service5']
allDependencies = ['service5']
What I've done so far (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()
Looking for an efficient and optimized solution, preferably without any recursion.
Thanks for reading! have a nice day...
You could take a smaller approach and take the Set for collecting and checking.
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; }This can be handled with Breadth-First Search, which is a tree traversal algorithm. Notice that this does not have any recursion.
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;
}