Given an object of services and their primary dependencies, find all dependecies of every service (i-CodePudding

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...

CodePudding user response：

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, 'service2'));

// breadth-first search
function bfs(input, key) {
  const output = {
    primaryDependencies: input[key],
    allDependencies: []
  };

  input[key].forEach(entry => output.allDependencies.push(entry));

  const root = input[key];
  if (!root) {
    return output;
  }

  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;
}

CodePudding user response：

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; }