JavaScript – Sort depending on dependency tree

  • A+
Category:Languages

I must show a set of images that depend on each other. For example

 Image A depends on no one  Image B depends on A  Image C depends on A and B  Image D depends on F  Image E depends on D and C  Image F depends on no one 

I have a javascript object like this:

const imageDependencies = {     A: [],     B: ['A'],     C: ['A', 'B'],     D: [F],     E: ['D', 'C'],     F: [] } 

I need to get all my image names ordered by their dependencies. The result of this example could be any of these:

//   so first yo get the value of A. Once you have it you can get the value of B. Once you have the value of A and B you can get C, and so on  result_1 = [A, B, C, F, D, E]   // this could be another correct result result_2 = [A, F, D, B, C, E] 

I've tried using the Array.sort() function like this:

let names = Object.keys(imageDependencies); names.sort((a,b) => {     if(imageDependencies [a].includes(b)) return 1     else return -1 }) 

But is not working properly.

How can this be done?

 


You coult take a Set for added keys and check if the actual dependency has all elements added to the set. Then add this key, otherwise go on. Proceed until no more items are in the array.

var dependencies = { A: [], B: ['A'], C: ['A', 'B'], D: ['F'], E: ['D', 'C'], F: [], G: ['H'], H: ['G'] },     keys = Object.keys(dependencies),     used = new Set,     result = [],     i, item, length;      do {     length = keys.length;     i = 0;     while (i < keys.length) {         if (dependencies[keys[i]].every(Set.prototype.has, used)) {             item = keys.splice(i, 1)[0];             result.push(item);             used.add(item);             continue;         }         i++;     } } while (keys.length && keys.length !== length)  console.log('circle', ...keys); result.push(...keys);  console.log(result);
.as-console-wrapper { max-height: 100% !important; top: 0; }

For getting the items first who have no dependency, you could filter the keys and take the values directly.

var dependencies = { A: [], B: ['A'], C: ['A', 'B'], D: ['F'], E: ['D', 'C'], F: [], G: ['H'], H: ['G'] },     keys = Object.keys(dependencies),     used = new Set,     result = [],     items, length;      do {     length = keys.length;     items = [];     keys = keys.filter(k => {         if (!dependencies[k].every(Set.prototype.has, used)) return true;         items.push(k);     });     result.push(...items);     items.forEach(Set.prototype.add, used); } while (keys.length && keys.length !== length)  console.log('circle', ...keys); result.push(...keys);  console.log(result);
.as-console-wrapper { max-height: 100% !important; top: 0; }

Comment

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen: