JavaScript - Sort depending on dependency tree
Here's my go at it :
const imageDependencies = {
A: [],
B: ["A"],
C: ["A", "B"],
D: ["F"],
E: ["D", "C"],
F: []
};
let keys = Object.keys(imageDependencies), // ["A","B","C","D","E","F"]
output = [];
while (keys.length) {
for (let i in keys) {
let key = keys[i], // "A"
dependencies = imageDependencies[key]; // []
if (dependencies.every(dependency => output.includes(dependency))) { // If all dependencies are already in the output array
output.push(key); // Pushing "A" to the output
keys.splice(i, 1); // Removing "A" from the keys
}
}
}
console.log("output = ", output);
what you want here is a topological sort
(https://en.wikipedia.org/wiki/Topological_sorting).
I used this example
https://gist.github.com/shinout/1232505#file-tsort-js-L9
written by Shin Suzuki
https://gist.github.com/shinout
const imageDependencies = {
A: [],
B: ['A'],
C: ['A', 'B'],
D: ['F'],
E: ['D', 'C'],
F: []
}
function tsort(edges) {
let nodes = {}, sorted = [], visited = {};
let Node = function (id) {
this.id = id;
this.afters = [];
}
edges.forEach( (v)=> {
let from = v[0], to = v[1];
if (!nodes[from]) nodes[from] = new Node(from);
if (!nodes[to]) nodes[to] = new Node(to);
nodes[from].afters.push(to);
});
Object.keys(nodes).forEach(function visit(idstr, ancestors) {
let node = nodes[idstr],id = node.id;
if (visited[idstr]) return;
if (!Array.isArray(ancestors)) ancestors = [];
ancestors.push(id);
visited[idstr] = true;
node.afters.forEach(function (afterID) {
if (ancestors.indexOf(afterID) >= 0)
throw new Error('closed chain : ' + afterID + ' is in ' + id);
visit(afterID.toString(), ancestors.map(function (v) { return v }));
});
sorted.unshift(id);
});
return sorted;
}
const createEdges = (dep) => {
let result = []
Object.keys(dep).forEach(key => {
dep[key].forEach(n => {
result.push([n, key])
})
})
return result
}
const list = createEdges(imageDependencies)
console.log(tsort(list))
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; }
Here's another crack using Array.prototype.reduce()
const imageDependencies = {
A: [],
B: ['A'],
C: ['A', 'B'],
D: ['F'],
E: ['D', 'C'],
F: []
}
const imageDependenciesBad = {
A: ["X"],
B: ['A'],
C: ['A', 'B'],
D: ['F'],
E: ['D', 'C'],
F: []
}
const sort = (names, obj, start, depth = 0) => {
const processed = names.reduce((a,b,i) => {
if (obj[b].every(Array.prototype.includes, a)) a.push(b)
return a
}, start)
const nextNames = names.filter(n => !processed.includes(n)),
goAgain = nextNames.length && depth <= names.length
return goAgain ? sort(nextNames, obj, processed, depth + 1) : processed
}
console.log(sort(Object.keys(imageDependencies), imageDependencies, []).join(","))
console.log(sort(Object.keys(imageDependenciesBad), imageDependenciesBad, []).join(","))