我有一个项目列表，我需要编译一个给定项目中的所有依赖项列表和依赖项树。列表是无序的，每个项目包含一个id和dep，其中deep是对另一个项目的引用，该项目是给定项目的子项目。
每个id可以有多个深度，我需要能够检测到循环依赖在树的任何地方。
我建立了一个包含大多数用例的示例列表:
输入:
const input = [
{ id: '1' },
{ id: '2' },
{ id: '3' },
{ id: '4', dep: '1' },
{ id: '5', dep: '2' },
{ id: '6', dep: '3' },
{ id: '7', dep: '4' },
{ id: '8', dep: '5' },
{ id: '8', dep: '1' },
{ id: '8', dep: '4' },
{ id: '9', dep: '8' },
{ id: '10', dep: '8' },
{ id: '11', dep: '10' },
{ id: '12', dep: '11' },
{ id: '14', dep: '13' }, // Circular reference
{ id: '13', dep: '17' }, // Circular reference
{ id: '15', dep: '13' }, // Circular reference
{ id: '16', dep: '13' }, // Circular reference
{ id: '17', dep: '16' }, // Circular reference
{ id: '18', dep: '13' }, // Circular reference
{ id: '19', dep: '20' }, // Circular reference
{ id: '20', dep: '14' }, // Circular reference
{ id: '21', dep: '22' },
{ id: '17', dep: '21' },
{ id: '16', dep: '14' }
];
期望的结果不需要完全是这个，而是类似的东西。预期结果:
const output = {
'1': null,
'2': null,
'3': null,
'4': { allDeps: [ '1' ], tree: { '1': null }},
'5': { allDeps: [ '2' ], tree: { '2': null }},
'6': { allDeps: [ '3' ], tree: { '3': null }},
'7': {
allDeps: [ '4', '1' ],
tree: { '4': { '1': null }}
},
'8': {
allDeps: [ '5', '2', '1', '4' ],
tree: {
'5': { '2': null },
'4': { '1': null },
'1': null
}
},
'9': {
allDeps: [ '8', '5', '2', '1', '4' ],
tree: { '8': { '5': { '2': null }, '4': { '1': null }, '1': null }}
},
'10': {
allDeps: [ '8', '5', '2', '1', '4' ],
tree: { '8': { '5': { '2': null }, '4': { '1': null }, '1': null }}
},
'11': {
allDeps: [ '10', '8', '5', '2', '1', '4' ],
tree: { '10': { '8': { '5': { '2': null }, '4': { '1': null }, '1': null }}}
},
'12': {
allDeps: [ '11', '10', '8', '5', '2', '1', '4' ],
tree: { '11': { '10': { '8': { '5': { '2': null }, '4': { '1': null }, '1': null }}}}
},
'13': {
allDeps: [ '17', '16', '13', '22', '21', '14' ],
hasCircular: true,
circularIds: [[ '13', '16' ], [ '13', '14' ]],
tree: {
'17': {
'16': {
'13': 'circular',
'14': { '13': 'circular' }
},
'21': { '22': null }
}
}
},
'14': {
allDeps: [ '13', '17', '16', '22', '21', '13', '14' ],
hasCircular: true,
circularIds: [[ '13', '16' ], [ '14', '16' ]],
tree: {
'13': {
'17': {
'16': {
'13': 'circular',
'14': 'circular'
},
'21': { '22': null }
}
}
}
},
'15': {
allDeps: [ '13', '17', '16', '22', '21', '13', '14' ],
hasCircular: true,
circularIds: [[ '13', '16' ], [ '13', '14' ]],
tree: {
'13': {
'17': {
'16': {
'13': 'circular',
'14': { '13': 'circular' }
},
'21': { '22': null }
}
}
}
},
'16': {
allDeps: [ '13', '17', '16', '14', '22', '21' ],
hasCircular: true,
circularIds: [[ '17', '16' ], [ '17', '16' ]],
tree: {
'13': {
'17': {
'16': 'circular',
'21': { '22': null }
}
},
'14': {
'13': {
'17': {
'16': 'circular',
'21': { '22': null }
},
'21': { '22': null }
}
}
}
},
'17': {
allDeps: [ '16', '13', '17', '21', '22', '14' ],
hasCircular: true,
circularIds: [[ '13', '17' ], [ '13', '17' ]],
tree: {
'16': {
'13': { '17': 'circular' },
'14': {
'13': { '17': 'circular' }
}
},
'21': { '22': null }
}
},
'18': {
allDeps: [ '13', '17', '16', '21', '22', '14' ],
hasCircular: true,
circularIds: [[ '13', '16' ], [ '14', '13' ]],
tree: {
'13': {
'17': {
'16': {
'13': 'circular',
'14': { '13': 'circular' }
},
'21': { '22': null }
}
}
}
},
'19': {
allDeps: [ '20', '14', '13', '17', '16', '22', '21' ],
hasCircular: true,
circularIds: [[ '13', '16' ], [ '14', '16' ]],
tree: {
'20': {
'14': {
'13': {
'17': {
'16': {
'13': 'circular',
'14': 'circular'
},
'21': { '22': null }
}
}
}
}
}
},
'20': {
allDeps: [ '14', '13', '17', '16', '21', '22' ],
hasCircular: true,
circularIds: [[ '13', '16' ], [ '16', '14' ]],
tree: {
'14': {
'13': {
'17': {
'16': {
'13': 'circular',
'14': 'circular'
},
'21': { '22': null }
}
}
}
}
},
'21': {
allDeps: [ '22' ],
tree: { '22': null }
},
'22': null
};
我已经手工构建了预期的结果，所以这里可能有问题，但我认为它完成了表达想法的目标。此外，结构不是最终的，我需要所有依赖项的完整平面列表，循环依赖项的存在及其发生的位置的标识，以及具有父/子结构的树。如果这是一个对象数组或者一个不相关的对象
真实的数据对于每个id都有多行，就像你在id=8中看到的那样，而完整的数据集有数十万行。
到目前为止，我构建的代码可以开始构建allDeps属性，但它不检测循环依赖，而且我没有找到构建树部分的方法。
我发现了一堆树搜索算法的引用，但它们都与parent_id而不是child_id一起工作，就像我的情况。
我花了几天时间尝试使用DFS创建代码，但我没有成功，所以我寻求帮助。
下面的代码是我所能做的，它甚至有一些优化。请不要用我的代码约束自己:
function getMap(fullList) {
const portifolioMap = {};
const itemsWithDependencies = new Set(); // This exists so i can build the null values first as an optimization
const portfolioCache = {}; // This is a cache of all the items that have the same id so i dont need to loop a bunch of times later
const emptyRow = { allDeps: new Set() };
// get all unique ids
const uniqueIds = fullList.reduce((acc, item) => {
acc.add(item.id);
if(item.dep) {
acc.add(item.dep);
itemsWithDependencies.add(item.id);
}
if(!portfolioCache[item.id]) {
portfolioCache[item.id] = [];
}
if(item.dep && !portfolioCache[item.dep]) {
portfolioCache[item.dep] = [];
}
portfolioCache[item.id].push(item);
return acc;
}, new Set());
function visitNode(firstNodeId, node) {
if(!node) return;
if(!portifolioMap[firstNodeId]) {
portifolioMap[firstNodeId] = Object.assign({}, emptyRow);
}
if(node.dep) {
portifolioMap[firstNodeId].allDeps.add(node.dep);
}
const allItemsFromThisDep = portfolioCache[node.dep] || [];
allItemsFromThisDep.forEach(thisNode => visitNode(firstNodeId, thisNode));
return;
}
function buildTree(id) {
const allItemsFromThisCnpj = portfolioCache[id];
if(!allItemsFromThisCnpj.length) return null;
if(!portifolioMap[id]) {
portifolioMap[id] = Object.assign({}, emptyRow);
}
allItemsFromThisCnpj.forEach((item) => visitNode(id, item));
return portifolioMap[id];
}
// lopp all the unique ids
uniqueIds.forEach((id) => {
if(!itemsWithDependencies.has(id)) {
portifolioMap[id] = null;
return;
}
portifolioMap[id] = buildTree(id);
});
return portifolioMap;
}
edge
你的输入是根据图的边来定义的。我们将为标识符定义一个类型tident，并为边定义一个类型tedge。你的问题没有贴上TypeScript的标签，但从类型的角度思考会对我们有所帮助。在post -
type tident = number
type tnullable<T> = T | null
type tedge = { id: tident, dep: tnullable<tident> }
现在我们输入input为Array<tedge>-
const input: Array<tedge> = [
{ id: 1, dep: null },
{ id: 2, dep: null },
{ id: 3, dep: null },
{ id: 4, dep: 1 },
{ id: 5, dep: 2 },
…
]
图
下面我们用addEdge-
graphtype tgraph = Map<tident, Set<tident>>
const graph = (): tgraph => {
return new Map()
}
const addEdge = (t: tgraph, { id, dep }: tedge): tgraph => {
let r = new Map(t)
if (!r.has(id)) r.set(id, new Set)
if (dep == null) return r
if (!r.has(dep)) r.set(dep, new Set)
r.set(id, new Set(r.get(id)!).add(dep))
return r
}
你的图g可以通过写-
const g: tgraph = input.reduce(addEdge, graph())
Map {
1 => Set {},
2 => Set {},
3 => Set {},
4 => Set {1},
5 => Set {2},
6 => Set {3},
7 => Set {4},
8 => Set {5, 1, 4},
9 => Set {8},
10 => Set {8},
11 => Set {10},
12 => Set {11},
14 => Set {13},
13 => Set {17},
17 => Set {16, 21},
15 => Set {13},
16 => Set {13, 14},
18 => Set {13},
19 => Set {20},
20 => Set {14},
21 => Set {22},
22 => Set {}
}
deps
现在很容易编写图形所需的较小函数，例如deps-
const deps = (t: tgraph, id: tident): Array<tident> => {
const seen: Set<tident> = new Set
function *loop(id: tident): Generator<tident> {
if (seen.has(id)) return
seen.add(id)
yield id
for (const dep of t.get(id) ?? new Set)
yield *loop(dep)
}
const res = new Set(loop(id))
res.delete(id)
return Array.from(res)
}
让我们预览一些deps查询-
console.log(deps(g, 1))
console.log(deps(g, 14))
console.log(deps(g, 18))
注意，与输出不同，标识符永远不会作为自身的依赖项列出-
[]
[13, 17, 16, 21, 22]
[13, 17, 16, 14, 21, 22]
节点/strong>现在让我们为我们的图形编写node函数-
type tnode = { id: tident, deps: ttree | "circular" }
type ttree = Array<tnode>
const node = (t: tgraph, id: tident): tnode => {
function loop(id: tident, seen: Set<tident>): tnode {
if (seen.has(id)) return { id, deps: "circular" }
return {
id,
deps: Array
.from(t.get(id) ?? new Set as Set<tident>)
.map(dep => loop(dep, new Set(seen).add(id)))
}
}
return loop(id, new Set)
}
让我们查询几个节点-
console.log(node(g, 1))
console.log(node(g, 16))
{
"id": 1,
"deps": []
}
{
"id": 16,
"deps": [
{
"id": 13,
"deps": [
{
"id": 17,
"deps": [
{
"id": 16,
"deps": "circular"
},
{
"id": 21,
"deps": [
{
"id": 22,
"deps": []
}
]
}
]
}
]
},
{
"id": 14,
"deps": [
{
"id": 13,
"deps": [
{
"id": 17,
"deps": [
{
"id": 16,
"deps": "circular"
},
{
"id": 21,
"deps": [
{
"id": 22,
"deps": []
}
]
}
]
}
]
}
]
}
]
}
达到目标
既然我们已经把复杂的任务分开了，我们可以把小的部分组合成一个更复杂的解决方案——
type tinfo = { id: tident, allDeps: Array<tident>, tree: tnode }
const info: Array<tinfo> = Array.from(
g.keys(),
id => ({
id,
allDeps: deps(g, id),
tree: node(g, id)
})
)
console.log("info", info)
准备好滚动-
[{
"id": 1,
"allDeps": [],
"tree": {
"id": 1,
"deps": []
}
}, {
"id": 2,
"allDeps": [],
"tree": {
"id": 2,
"deps": []
}
}, {
"id": 3,
"allDeps": [],
"tree": {
"id": 3,
"deps": []
}
}, {
"id": 4,
"allDeps": [
1
],
"tree": {
"id": 4,
"deps": [
{
"id": 1,
"deps": []
}
]
}
}, {
"id": 5,
"allDeps": [
2
],
"tree": {
"id": 5,
"deps": [
{
"id": 2,
"deps": []
}
]
}
}, {
"id": 6,
"allDeps": [
3
],
"tree": {
"id": 6,
"deps": [
{
"id": 3,
"deps": []
}
]
}
}, {
"id": 7,
"allDeps": [
4,
1
],
"tree": {
"id": 7,
"deps": [
{
"id": 4,
"deps": [
{
"id": 1,
"deps": []
}
]
}
]
}
}, {
"id": 8,
"allDeps": [
5,
2,
1,
4
],
"tree": {
"id": 8,
"deps": [
{
"id": 5,
"deps": [
{
"id": 2,
"deps": []
}
]
},
{
"id": 1,
"deps": []
},
{
"id": 4,
"deps": [
{
"id": 1,
"deps": []
}
]
}
]
}
}, {
"id": 9,
"allDeps": [
8,
5,
2,
1,
4
],
"tree": {
"id": 9,
"deps": [
{
"id": 8,
"deps": [
{
"id": 5,
"deps": [
{
"id": 2,
"deps": []
}
]
},
{
"id": 1,
"deps": []
},
{
"id": 4,
"deps": [
{
"id": 1,
"deps": []
}
]
}
]
}
]
}
}, {
"id": 10,
"allDeps": [
8,
5,
2,
1,
4
],
"tree": {
"id": 10,
"deps": [
{
"id": 8,
"deps": [
{
"id": 5,
"deps": [
{
"id": 2,
"deps": []
}
]
},
{
"id": 1,
"deps": []
},
{
"id": 4,
"deps": [
{
"id": 1,
"deps": []
}
]
}
]
}
]
}
}, {
"id": 11,
"allDeps": [
10,
8,
5,
2,
1,
4
],
"tree": {
"id": 11,
"deps": [
{
"id": 10,
"deps": [
{
"id": 8,
"deps": [
{
"id": 5,
"deps": [
{
"id": 2,
"deps": []
}
]
},
{
"id": 1,
"deps": []
},
{
"id": 4,
"deps": [
{
"id": 1,
"deps": []
}
]
}
]
}
]
}
]
}
}, {
"id": 12,
"allDeps": [
11,
10,
8,
5,
2,
1,
4
],
"tree": {
"id": 12,
"deps": [
{
"id": 11,
"deps": [
{
"id": 10,
"deps": [
{
"id": 8,
"deps": [
{
"id": 5,
"deps": [
{
"id": 2,
"deps": []
}
]
},
{
"id": 1,
"deps": []
},
{
"id": 4,
"deps": [
{
"id": 1,
"deps": []
}
]
}
]
}
]
}
]
}
]
}
}, {
"id": 14,
"allDeps": [
13,
17,
16,
21,
22
],
"tree": {
"id": 14,
"deps": [
{
"id": 13,
"deps": [
{
"id": 17,
"deps": [
{
"id": 16,
"deps": [
{
"id": 13,
"deps": "circular"
},
{
"id": 14,
"deps": "circular"
}
]
},
{
"id": 21,
"deps": [
{
"id": 22,
"deps": []
}
]
}
]
}
]
}
]
}
}, {
"id": 13,
"allDeps": [
17,
16,
14,
21,
22
],
"tree": {
"id": 13,
"deps": [
{
"id": 17,
"deps": [
{
"id": 16,
"deps": [
{
"id": 13,
"deps": "circular"
},
{
"id": 14,
"deps": [
{
"id": 13,
"deps": "circular"
}
]
}
]
},
{
"id": 21,
"deps": [
{
"id": 22,
"deps": []
}
]
}
]
}
]
}
}, {
"id": 17,
"allDeps": [
16,
13,
14,
21,
22
],
"tree": {
"id": 17,
"deps": [
{
"id": 16,
"deps": [
{
"id": 13,
"deps": [
{
"id": 17,
"deps": "circular"
}
]
},
{
"id": 14,
"deps": [
{
"id": 13,
"deps": [
{
"id": 17,
"deps": "circular"
}
]
}
]
}
]
},
{
"id": 21,
"deps": [
{
"id": 22,
"deps": []
}
]
}
]
}
}, {
"id": 15,
"allDeps": [
13,
17,
16,
14,
21,
22
],
"tree": {
"id": 15,
"deps": [
{
"id": 13,
"deps": [
{
"id": 17,
"deps": [
{
"id": 16,
"deps": [
{
"id": 13,
"deps": "circular"
},
{
"id": 14,
"deps": [
{
"id": 13,
"deps": "circular"
}
]
}
]
},
{
"id": 21,
"deps": [
{
"id": 22,
"deps": []
}
]
}
]
}
]
}
]
}
}, {
"id": 16,
"allDeps": [
13,
17,
21,
22,
14
],
"tree": {
"id": 16,
"deps": [
{
"id": 13,
"deps": [
{
"id": 17,
"deps": [
{
"id": 16,
"deps": "circular"
},
{
"id": 21,
"deps": [
{
"id": 22,
"deps": []
}
]
}
]
}
]
},
{
"id": 14,
"deps": [
{
"id": 13,
"deps": [
{
"id": 17,
"deps": [
{
"id": 16,
"deps": "circular"
},
{
"id": 21,
"deps": [
{
"id": 22,
"deps": []
}
]
}
]
}
]
}
]
}
]
}
}, {
"id": 18,
"allDeps": [
13,
17,
16,
14,
21,
22
],
"tree": {
"id": 18,
"deps": [
{
"id": 13,
"deps": [
{
"id": 17,
"deps": [
{
"id": 16,
"deps": [
{
"id": 13,
"deps": "circular"
},
{
"id": 14,
"deps": [
{
"id": 13,
"deps": "circular"
}
]
}
]
},
{
"id": 21,
"deps": [
{
"id": 22,
"deps": []
}
]
}
]
}
]
}
]
}
}, {
"id": 19,
"allDeps": [
20,
14,
13,
17,
16,
21,
22
],
"tree": {
"id": 19,
"deps": [
{
"id": 20,
"deps": [
{
"id": 14,
"deps": [
{
"id": 13,
"deps": [
{
"id": 17,
"deps": [
{
"id": 16,
"deps": [
{
"id": 13,
"deps": "circular"
},
{
"id": 14,
"deps": "circular"
}
]
},
{
"id": 21,
"deps": [
{
"id": 22,
"deps": []
}
]
}
]
}
]
}
]
}
]
}
]
}
}, {
"id": 20,
"allDeps": [
14,
13,
17,
16,
21,
22
],
"tree": {
"id": 20,
"deps": [
{
"id": 14,
"deps": [
{
"id": 13,
"deps": [
{
"id": 17,
"deps": [
{
"id": 16,
"deps": [
{
"id": 13,
"deps": "circular"
},
{
"id": 14,
"deps": "circular"
}
]
},
{
"id": 21,
"deps": [
{
"id": 22,
"deps": []
}
]
}
]
}
]
}
]
}
]
}
}, {
"id": 21,
"allDeps": [
22
],
"tree": {
"id": 21,
"deps": [
{
"id": 22,
"deps": []
}
]
}
}, {
"id": 22,
"allDeps": [],
"tree": {
"id": 22,
"deps": []
}
}]
评论
递归是函数式的遗产，因此将它与函数式风格结合使用会产生最好的结果。这意味着要避免突变、变量重赋和其他副作用。它还强调隔离行为和组合小程序来构建大程序。希望您能够看到这种风格在解决这个问题时的优势。
我没有保留你建议的输出，因为它有几个问题-
- 一个节点永远不应该被列为自身的依赖项
- 对象应该具有已知的属性。这意味着您应该始终支持
{ name: "foo", value: "bar" }而不是{ foo: "bar" }。 - 额外的属性，如
hasCircular和circularDeps是多余的，派生状态。如果你想包含它们，这是留给读者的练习。编写hasCircular(t: tgraph): bool和circularDeps(t: tgraph): Array<tedge>，最后更新info以使用较小的函数-
没有打印稿
这是香草graph.js模块，由typescript编译-
export const graph = () => {
return new Map();
};
export const addEdge = (t, { id, dep }) => {
let r = new Map(t);
if (!r.has(id))
r.set(id, new Set);
if (dep == null)
return r;
if (!r.has(dep))
r.set(dep, new Set);
r.set(id, new Set(r.get(id)).add(dep));
return r;
};
export const deps = (t, id) => {
const seen = new Set;
function* loop(id) {
if (seen.has(id))
return;
seen.add(id);
yield id;
for (const dep of t.get(id) ?? new Set)
yield* loop(dep);
}
const res = new Set(loop(id));
res.delete(id);
return Array.from(res);
};
export const node = (t, id) => {
function loop(id, seen) {
if (seen.has(id))
return { id, deps: "circular" };
return {
id,
deps: Array
.from(t.get(id) ?? new Set)
.map(dep => loop(dep, new Set(seen).add(id)))
};
}
return loop(id, new Set);
};
在typescript playground中在自己的浏览器中验证结果。