JavaScript - Sort depending on dependency tree

Question

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?

Nauseating

You could implement that programmatically exactly as you do it manually. – Graffito

Answer 1

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

Mieshamiett

it will never finish in case of a cycle { A: ['B'], B: ['A'] ,C:[]} – Permutation

@NaorTedgi, thanks for pointing out. now it add these items at the end. please see edit. – Mieshamiett

Are we supposed to support invalid inputs and dependency loops? Because {A: ['B'], B: ['A']} is a dependency loop – Crocker

@JeremyThille not really, if not specified. but it does not hurt if it does not break with loops. – Mieshamiett

Answer 2

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

Permutation

When there are cycles, there is no definite order, so that would make the order ambiguous. I don't think it should be treated, except by throwing an error maybe. – Prohibition

@JeremyThille This answer should be upvoted for the first line alone : it makes it much easier to find and understand corresponding algorithms on the internet. – Gannon

Answer 3

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(","))

Beryllium

Answer 4

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

Crocker

I upvoted. :) It could be improved with a control for throwing an error instead of looping indefinitely? And maybe an additional outputSet: Set<string> in order to handle the case where imageDependencies is big. – Graffito

it looks like, you had a similar idea :-) – Mieshamiett

it will never finish in case of a cycle { A: ['B'], B: ['A'] ,C:[]} – Permutation

Obviously it requires valid dependencies. { A: ['B'], B: ['A'] } is not valid, it's a dependency loop. – Crocker

Answer 5

toposort is a pretty good library for this https://github.com/marcelklehr/toposort

const toposort = require("toposort")
const imageDependencies = {
    A: [],
    B: ['A'],
    C: ['A', 'B'],
    D: ['F'],
    E: ['D', 'C'],
    F: []
}

// split dependencies into pairs for toposort
let deps = []
Object.keys(imageDependencies).forEach(k => {
    imageDependencies[k].forEach(d => {
        deps.push([d,k])
    })
})

toposort.array(Object.keys(imageDependencies), deps)
// -> ["A", "B", "C", "F", "D", "E"]

Eelworm