JavaScript - сортировка в зависимости от дерева зависимостей

Question

Я должен показать набор изображений, которые зависят друг от друга.Например,

 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

У меня есть такой объект javascript:

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

Мне нужно получить все имена изображений, упорядоченные поих зависимости.Результатом этого примера может быть любой из них:

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

Я пытался использовать функцию Array.sort(), например, такую:

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

, но не работает должным образом.

Как это можно сделать?

Answer 1

Вот еще один взлом, используя 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 2

здесь вы хотите получить топологическую сортировку

(https://en.wikipedia.org/wiki/Topological_sorting).

. Я использовал этот пример

https://gist.github.com/shinout/1232505#file-tsort-js-L9

написано Шин Судзуки

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 3

Вот мой пример:

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

Answer 4

Вы можете взять Set для добавленных ключей и проверить, есть ли в фактической зависимости все элементы, добавленные в набор. Затем добавьте этот ключ, иначе продолжайте. Продолжайте, пока в массиве больше не будет элементов.

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

Чтобы получить элементы первыми, у которых нет зависимости, вы можете отфильтровать ключи и получить значения напрямую.

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