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?

Answer 1

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"]

Answer 2

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

Answer 3

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

Answer 4

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

Answer 5

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