英文:
Build dependency tree object from flat array in javascript with child_id references
问题
I have translated the code for you:
function getMap(fullList) {
const portfolioMap = {};
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 don't 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 (!portfolioMap[firstNodeId]) {
portfolioMap[firstNodeId] = Object.assign({}, emptyRow);
}
if (node.dep) {
portfolioMap[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 (!portfolioMap[id]) {
portfolioMap[id] = Object.assign({}, emptyRow);
}
allItemsFromThisCnpj.forEach(item => visitNode(id, item));
return portfolioMap[id];
}
// Loop all the unique ids
uniqueIds.forEach(id => {
if (!itemsWithDependencies.has(id)) {
portfolioMap[id] = null;
return;
}
portfolioMap[id] = buildTree(id);
});
return portfolioMap;
}
Please note that the translation includes the code comments as well.
英文:
I have a list of items, and I need to compile a list of all dependencies in a given item and the tree of dependencies. The list is not ordered, and each item contains an id and dep where dep is the reference to another item that's a child of the given item.
Each id can have multiple deps and I need to be able to detect circular dependencies anywhere in the tree.
I built an example list that would contain most of use cases:
Input:
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' }
];
The expected result doesn't need to be exatcly this one, but something similar.
Expected Result:
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
};
I've built the expected result by hand, so something can be wrong there, but I think it accomplishes the goal of expressing the idea. Also, the structure is not final, I do need the full flat list of all dependencies, the identification of the existence of circular dependency and where that happens, and a tree with parent/child structure. If that's an array of objects or an object is not relevant.
The real data have multiple rows for each id as you can see with id=8, and the full dataset has hundreds of thousands of rows.
The code I built so far can start building the allDeps property, but it doesn't detect circular dependencies, and I didn't find a way to build the tree part.
I found a bunch of references of tree-search algos, but they all work with parent_id instead of child_id, like the case I have.
I spent a few days trying to create the code using DFS, but I was not successful, so I'm asking for help.
The code below is the further I could go, and it even has some optimizations. Please don't restrain yourselves by my code:
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;
}
答案1
得分: 0
edge
你的输入是根据图的 边 来定义的。我们将为你的标识符定义一个类型 tident，以及边的类型 tedge。虽然你的问题没有标记为 TypeScript，但考虑类型将有助于我们进行下一步的操作。在帖子的最后提供了纯粹的 JavaScript 版本 -
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 },
…
]
graph
接下来，我们将使用 addEdge 函数构建一个 graph -
type 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, 1},
8 => Set {5, 2, 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]
node
现在让我们为我们的图编写 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": []
}
]
}
]
}
]
}
]
}
]
}
reaching the goal
现在，我们已经将复杂的任务分解，可以将较小的部分组合成更复杂的解决方案 -
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": []
}
}, {
<details>
<summary>英文:</summary>
**edge**
Your input is defined in terms of a graph's *edges*. We will define a type for your identifiers, `tident`, and a type for the edges, `tedge`. Your question isn't tagged with TypeScript but thinking in types will assist us along the way. A vanilla JavaScript version is available at the end of the post -
```ts
type tident = number
type tnullable<T> = T | null
type tedge = { id: tident, dep: tnullable<tident> }
Now we type your input as 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 },
…
]
graph
Next we functions to construct a graph using addEdge -
type 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
}
Your graph g can be constructed by writing -
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
Now it's easy to write the smaller functions our graph needs, such as 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)
}
Let's preview some deps queries -
console.log(deps(g, 1))
console.log(deps(g, 14))
console.log(deps(g, 18))
Notice unlike your output, an identifier will never be listed as a dependency of itself -
[]
[13, 17, 16, 21, 22]
[13, 17, 16, 14, 21, 22]
node
Now let's write the node function for our graph -
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)
}
Let's query a couple nodes -
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": []
}
]
}
]
}
]
}
]
}
]
}
reaching the goal
Now that we've divided the complex task, we can combine the smaller parts into a more sophisticated solution -
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)
Get ready to scroll -
[{
"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": []
}
}]
remarks
Recursion is a functional heritage and so using it with functional style yields the best results. That means avoiding things like mutation, variable reassignments, and other side effects. It also emphasizes isolating behaviors and composing small programs to build large ones. Hopefully you were able to see the strengths of this style applied to this problem.
I didn't keep your proposed output because it has several problems -
- A node should never be listed as a dependency of itself
- Objects should have known properties. That means you should always favor
{ name: "foo", value: "bar" }over{ foo: "bar" }. - Additional properties like
hasCircularandcircularDepsare redundant, derived state. If you want to include them, this is left as an exercise for the reader. WritehasCircular(t: tgraph): boolandcircularDeps(t: tgraph): Array<tedge>, and finally updateinfoto use the smaller functions -
without typescript
Here's the vanilla graph.js module, as compiled by 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);
};
demo
Verify the result in your own browser at typescript playground.
通过集体智慧和协作来改善编程学习和解决问题的方式。致力于成为全球开发者共同参与的知识库，让每个人都能够通过互相帮助和分享经验来进步。
评论