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;
}
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 -
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 -
{ name: "foo", value: "bar" } over { foo: "bar" }.hasCircular and circularDeps are redundant, derived state. If you want to include them, this is left as an exercise for the reader. Write hasCircular(t: tgraph): bool and circularDeps(t: tgraph): Array<tedge>, and finally update info to 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.