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

这里你想要的是拓扑排序

（https://en.wikipedia.org/wiki/Topological_sorting）。

我用了这个例子

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

作者：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 2

您可以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; }

Answer 3

这是使用 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 4

这是我的尝试：

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 5

toposort是一个很好的

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